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
The way you use this is pretty simple. Given two sets of coordinates (begin and end position), this will return a collection of Vector2s.
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.