April 2008 - Posts

• Bresenham's Line Algorithm - VB XNA style

  1: Imports Microsoft.Xna.Framework 2: Imports System.Math 3:   4: Public Class Utils 5: ''' <summary> 6: ''' This function uses Bresenham's Line Algorithm to find the 7: ''' most direct path between two points on a 2D grid and stores 8: ''' all the points in a list. 9: ''' </summary> 10: ''' <param name="StartPosition">Starting X,Y coordinates</param> 11: ''' <param name="EndPosition">Starting X,Y coordinates</param> 12: ''' <returns>List(Of Vector2)</returns> 13: ''' <remarks></remarks> 14: Public Function DeterminePath(ByVal StartPosition As Vector2, _ 15:   ByVal EndPosition As Vector2) As List(Of Vector2) 16: Dim myPoint As Vector2 = StartPosition ' current point 17: Dim myPath As New List(Of Vector2) ' collection of path points 18:   19: ' Get the difference between 2 points 20: Dim deltaX As Integer = EndPosition.X - StartPosition.X 21: Dim deltaY As Integer = EndPosition.Y - StartPosition.Y 22: Dim leftover As Integer 23:   24: ' Figure out direction based on the +/- value of the deltas 25: Dim dirX As Integer = IIf(deltaX < 0, -1, 1) 26: Dim dirY As Integer = IIf(deltaY < 0, -1, 1) 27:   28: ' Get absolute, we'll decide whether to add/subtract later 29: deltaX = Abs(deltaX) 30: deltaY = Abs(deltaY) 31:   32: ' Uncomment this to add the first point to the path (list) 33: ' myPath.Add(myPoint) 34:   35: ' iterate through whichever axis is longest 36: If deltaX > deltaY Then 37: leftover = (deltaY * 2) - deltaX 38: While myPoint.X <> EndPosition.X 39: If leftover >= 0 Then 40: myPoint.Y = myPoint.Y + dirY 41: leftover = leftover - deltaX 42: End If 43: myPoint.X = myPoint.X + dirX 44: leftover = leftover + deltaY 45: myPath.Add(myPoint) 46: End While 47: Else 48: leftover = (deltaX * 2) - deltaY 49: While myPoint.Y <> EndPosition.Y 50: If leftover >= 0 Then 51: myPoint.X = myPoint.X + dirX 52: leftover = leftover - deltaY 53: End If 54: myPoint.Y = myPoint.Y + dirY 55: leftover = leftover + deltaX 56: myPath.Add(myPoint) 57: End While 58: End If 59:   60: Return myPath 61: End Function 62: End Class While I was working on my EnemyAI demo for code camp, I needed a way to plot the most efficient line between two points. Bresenham's Line Drawing Algorithm is pretty much the industry standard for lines, but I couldn't find a VB implementation I liked, so I wrote my own. I went ahead and used the Vector2 data type from XNA, but if you aren't doing XNA you could easily create a custom data type that contains a pair of integer values. The way you use this is pretty simple.  Given two sets of coordinates (begin and end position), this will return a collection of Vector2s.   How it works This algorithm compares the delta between the starting and ending X coordinate, and the starting and ending Y coordinate. In order to have the straightest possible line (that isn't purely horizontal or purely vertical) we have a rule that you can't have adjacent pixels on the shortest axis. This provides a much smoother transition along the longer axis. Posted Apr 15 2008, 07:22 PM by admin with no comments Filed under: xna, vb.net, bresenham