Temple of The Roguelike Forums
Development => Programming => Topic started by: Shaggy on November 15, 2010, 10:34:50 PM
-
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.]
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?
-
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.
-
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
-
While Delta >= 0
InitialY = InitialY + StepY
Delta = Math.Abs(Delta - (DeltaX * 2))
End While
Delta will always be >= 0 after Math.Abs(), no?
-
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.
-
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.
-
There shouldn't really be any need for a while loop :S Hang on (boots up Visual Studio 2010)
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...)