Implementing Bresenhams Line Algorithm

[Shaggy]

So I'm sure most of the people here know what Bresenhams Line Algorithm is, but if not then check this out
http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

I'm trying to figure out how to implement it in visual basic .net to check line of sight for field of view as well as creature AI and a few other things. I've got some old vb6 code that I found, but I don't really understand it. I get what the algorithm does, but not how to implement it in a 2d grid for the roguelike.


Here's the code I got
[it's converted to vb.net from vb6, but the parts I was unsure of I just commented out.]

Code: [Select]

   Private Sub FoVLine(ByVal InitialX As Long, ByVal InitialY As Long, ByVal FinalX As Long, ByVal FinalY As Long)
        ' Bresenham's line algorithm for Microsoft Visual Basic 6.0
        ' Implementation by Robert Lee,  July, 2002 Public Domain
        ' Converted to VB .Net 2010 by Max Roe, Nobember, 2010 Public Domain

        Dim Steep As Boolean
        Dim DeltaX, DeltaY, Delta, StepX, StepY, Coord As Long

        Steep = False
        DeltaX = Math.Abs((FinalX - InitialX))

        If (FinalX - InitialX) > 0 Then
            StepX = 1
        Else
            StepX = -1
        End If

        Console.Title = Console.Title & "A"

        DeltaY = Math.Abs((FinalY - InitialY))

        If Math.Abs((FinalY - InitialY)) > 0 Then
            StepY = 1
        Else
            StepY = -1
        End If

        Console.Title = Console.Title & "B"

        If DeltaY > DeltaX Then
            Steep = True
            Swap(InitialX, InitialY)
            Swap(DeltaX, DeltaY)
            Swap(StepX, StepY)
        End If

        Console.Title = Console.Title & "C"

        Delta = Math.Abs((DeltaY * 2) - DeltaX)

        For Coord = 0 To DeltaX - 1

            Console.Title = Console.Title & Coord & "[" & DeltaX & "]"

            If Steep = True Then
                'VB 6 CODE
                'Me.PSet(InitialY, InitialX)

                If MapFloor(InitialY, InitialX).SeeThrough = False Then Exit For 'Hits an obstruction, stop drawing line
                FoV(InitialY, InitialX) = True

            Else
                'VB 6 CODE
                'Me.PSet(InitialX, InitialY)

                If MapFloor(InitialX, InitialY).SeeThrough = False Then Exit For 'Hits an obstruction, stop drawing line
                FoV(InitialX, InitialY) = True

            End If

            While Delta >= 0
                InitialY = InitialY + StepY
                Delta = Math.Abs(Delta - (DeltaX * 2))
            End While

            InitialX = InitialX + StepX
            Delta = Math.Abs(Delta + (DeltaY * 2))

        Next

        'VB 6 CODE
        'Coord(Me.PSet(FinalX, FinalY))

    End Sub

Anyone have any ideas?

[corremn]

Not sure what you are asking. Are you asking for someone to explain this code, or the bit that is commented out.  Anyway I dont understand vb code anyway:) But if you ask a more specific question someone might be able to help you out.

The Me.PSet(InitialY, InitialX) and Me.PSet(InitialX, InitialY) code is generally where you would test to see if the coordinate is blocked, or add the Coord to a trajectory list, or update the coord on the screen, etc.

How you would use this is for each new InitialY and InitialX that is calculated at the end of the loop is either;
   1/ Check if path is blocked - Check if coord(InitialX ,InitialY ) is transparent and set the funtion to return false if not, other wise return true at the end, or
   2/ Get a COORD list from x1,y1:x2,y2 - Add coord(InitialX ,InitialY ) to a list and then process the list of coords after you return from the algorithm and traverse through the list to see if each coord is transparent.  (this also is good for getting a coord list for trajectories)

Let me know if you want me to explain this more.

Generally people use Bresenhams for LOS not for FOV.  Although it can be used for field of view, a sub-optimal way is to run the LOS on every square that the player can possibly see, I guess.

Also as a side note, remember that Bresenhams Line Algorithm does not produce the same path when going from x1,y1 to x2,y2 compared to x2,y2 to x1,y1. I.e sometimes you cant see a monster but it can see you.

Good luck, I remember getting when I got Bresenhams to work it was very rewarding.

[Shaggy]

I changed the code in the first post, and did what I thought I needed to do so that it would work. But it's getting stuck in an infinite loop within the algorithm somewhere, and I'm not sure why exactly.

Let me explain some of the code

MapFloor(InitialY, InitialX).SeeThrough
is a boolean property that is false if that tile obstructs view

FoV(InitialY, InitialX)
is an array of booleans that are true if that area of the map is visible to the player, false if it's not

And then the swap(int,int) function does exactly what you think it does

[scaught]

Code: [Select]

            While Delta >= 0
                InitialY = InitialY + StepY
                Delta = Math.Abs(Delta - (DeltaX * 2))
            End While
Delta will always be >= 0 after Math.Abs(), no?

[corremn]

But it's getting stuck in an infinite loop within the algorithm somewhere, and I'm not sure why exactly.

Yeah most likely the while loop.
You should be able to determine where an infinite loop occurred when debugging.  With Vb.net you will use Visual Studio so learn up on the debugger and you life will become easier.

[Shaggy]

Delta will always be >= 0 after Math.Abs(), no?

See, and that's where my lack of understanding concerning the algorithm itself comes into play. I didn't write the original code, I just converted it so that it would run in vb.net versus vb6.

[MrMorley]

There shouldn't really be any need for a while loop :S Hang on (boots up Visual Studio 2010)

Code: [Select]

Module Module1

    Sub Swap(ByRef X As Long, ByRef Y As Long)
        Dim t As Long = X
        X = Y
        Y = t
    End Sub

    ' If the plot function returns true, the bresenham's line algorithm continues.
    ' if the plot function returns false, the algorithm stops
    Delegate Function PlotFunction(ByVal x As Long, ByVal y As Long) As Boolean

    Sub Bresenham(ByVal x1 As Long, ByVal y1 As Long, ByVal x2 As Long, ByVal y2 As Long, ByVal plot As PlotFunction)
        Dim steep As Boolean = (Math.Abs(y2 - y1) > Math.Abs(x2 - x1))
        If (steep) Then
            Swap(x1, y1)
            Swap(x2, y2)
        End If

        If (x1 > x2) Then
            Swap(x1, x2)
            Swap(y1, y2)
        End If

        Dim deltaX As Long = x2 - x1
        Dim deltaY As Long = y2 - y1
        Dim err As Long = deltaX / 2
        Dim ystep As Long
        Dim y As Long = y1

        If (y1 < y2) Then
            ystep = 1
        Else
            ystep = -1
        End If

        For x As Long = x1 To x2
            Dim result As Boolean
            If (steep) Then result = plot(y, x) Else result = plot(x, y)
            If (Not result) Then Exit Sub
            err = err - deltaY
            If (err < 0) Then
                y = y + ystep
                err = err + deltaX
            End If
        Next

    End Sub

    Function plot(ByVal x As Long, ByVal y As Long) As Boolean
        Console.WriteLine(x.ToString() + " " + y.ToString())
        Return True 'This just prints each co-ord
    End Function

    Sub Main()
        ' example
        Bresenham(1, 1, 10, 15, New PlotFunction(AddressOf plot))
        Console.ReadLine()
    End Sub

End Module

Here is a generic Bresenham function which uses a delegate as the plot function. The idea is you create your FOV-checking code in it's own function, and pass that function to the algorithm. Feel free to dissect the code how you see fit. I may have made some mistakes, I don't pretend to like or regularly use VB xD

(Aside: Dear lord the delegate code in VB is ugly compared to C#'s...I mean, it's still prettier than C++'s boost::function code but jebus...)