## A* Implementation in FB: Part 2

### Written by Torahteen

Well, I feel bad about making such a hard to understand and totally "unprofessional" looking tutorial last time. So, I'll try to be a bit better this time. Here goes for my second tutorial ever written.

So last time I left you off with some pseudo-code. Today, I'm gonna show you how to implement this into FB code. First things first. There are a few things that every A* program needs. These are your constants, your UDTs (User Defined Types), your open and closed lists, and your subs and functions. So to start, I'm gonna go ahead and throw some code at you.

>     DefInt A-Z
>     '$Dynamic
>     Declare Sub ClearScreen()
>     Declare Sub DrawScreen()

>     Declare Sub FindPath()
>     Declare Sub AddToOpen(x As Integer, y As Integer)
>     Declare Sub AddToClosed(x As Integer, y As Integer)
>     Declare Sub AddToPath(x As Integer, y As Integer)
>     Declare Function IsOnOpen(x As Integer, y As Integer)
>     Declare Function IsOnClosed(x As Integer, y As Integer)

>     const Ground = 0
>     const Water = 1
>     const Hill = 2
>     const Cliff = 3
>     const Wall = 4
>     const Start = 5
>     const Finish = 6

>     const False = 0
>     const True = Not False

>     const GroundCost = 10
>     const HillCost = 25
>     const WaterCost = 50
>     const CliffCost = 100

>     Type SquareType
>         fScore As Integer
>         gScore As Integer
>         hScore As Integer
>         mType As Integer
>         pX As Integer
>         pY As Integer
>     End Type

>     Type PointType
>         x As Integer
>         y As Integer
>     End Type

Ok, first of all notice that I use dynamic arrays in my program. What we have done here is declared the subs and functions that we are using in the program (you should think ahead so you can remember what subs and/or functions you need to implement), declared the constants (we'll get to these in a bit), and set up two UDTs.

Take a look at the constants. The first seven constants are used to make and read from a user-made map. Each square on the map has an mType, which says what kind of tile it is (ground, water, walls, etc.). The next two constants are my two boolean values (true and false). The last four are the most important. These are the G scores for each of the different passable squares (if you haven't allready, you should read my other tutorial, "Implementing A* in FB: Part One"). These values determine what path is the best. The higher the score, the less likely A* will choose that square for the path.

The two UDTs are SquareType and PointType. PointType is used for defining points on the map. SquareType is the type used for each tile on the map. SquareType has six variables. The f, g, and hScore variables are just that, the f, g, and h Scores for that square. The mType is one of the seven constants we defined ealier (Ground, Water, Cliff, etc.). pX and pY are the x and y values of this squares parent.

Ok, so now we open the "board.brd" file to get the height and width of the map. We'll then dimension all the global variables that we need to:

>     Open "board.brd" For Input As #1
>     Input #1, sWidth, sHeight

>     Dim Shared Map(sWidth, sHeight) As SquareType
>     Dim Shared OpenList() As PointType
>     Dim Shared ClosedList() As PointType
>     Dim Shared Path() As PointType
>     Dim Shared mStart As PointType
>     Dim Shared mFinish As PointType
>     Dim Shared comp As PointType

>     For y = 1 To sHeight
>         For x = 1 To sWidth
>             Input #1, Map(x,y).mType
>             If Map(x,y).mType = Finish Then
>                 mFinish.x = x
>                 mFinish.y = y
>             ElseIf Map(x,y).mType = Start Then
>                 mStart.x = x
>                 mStart.y = y
>             End If
>         Next x
>     Next y
>     Close #1

BTW, here is the example "board.brd" file from the last tutorial.

>     10,8
>     4,4,4,4,4,4,4,4,4,4
>     4,0,0,0,0,0,0,0,0,4
>     4,0,0,0,4,0,0,0,0,4
>     4,5,0,0,4,0,0,0,0,4
>     4,0,0,0,4,0,0,6,0,4
>     4,0,0,0,4,0,0,0,0,4
>     4,0,0,0,0,0,0,0,0,4
>     4,4,4,4,4,4,4,4,4,4

Notice I put a wall around the map. You should do this or it will screw A* up (well, my program anyway).

This get's the width and height from the "board.brd" file, dimensions a multi-dimensional array of SquareType variables, and dimensions all our other variables (they are all self-explanatory, except for comp, which is used later). The nested FOR loops at the end there input one square at a time into the Map array, each time checking to see if it inputed the start or finish square.

Now that we have our variables and our map, let's implement the Subs and Functions, starting with the helper subs.

>     Sub AddToOpen(x As Integer, y As Integer)
>     	Redim Preserve OpenList(uBound(OpenList) + 1)
>     	OpenList(uBound(OpenList)).x = x
>     	OpenList(uBound(OpenList)).y = y
>     End Sub

>     Sub AddToClosed(x As Integer, y As Integer)
>     	Redim Preserve ClosedList(uBound(ClosedList) + 1)
>     	ClosedList(uBound(ClosedList)).x = x
>     	ClosedList(uBound(ClosedList)).y = y
>     End Sub

>     Sub AddToPath(x As Integer, y As Integer)
>     	Redim Preserve Path(uBound(Path) + 1)
>     	Path(uBound(Path)).x = x
>     	Path(uBound(Path)).y = y
>     End Sub

>     Function IsOnOpen(x As Integer, y As Integer)
>         For i = 1 to uBound(OpenList)
>             If OpenList(i).x = x And OpenList(i).y = y Then
>             'It's on the open list
>             IsOnOpen = True
>             Exit For
>             End If
>         Next i
>     End Function

>     Function IsOnClosed(x As Integer, y As Integer)
>         For i = 1 to uBound(ClosedList)
>             If ClosedList(i).x = x And ClosedList(i).y = y Then
>             'It's on the closed list
>             IsOnClosed = True
>             Exit For
>             End If
>         Next i
>     End Function

These are all fairly self-explanatory. The AddToXXXX subs simply REDIM the appropriate array, and then add the new value to them. The two IsOnXXXX functions loop through the appropriate array and checks if the square at x,y is on the list. If it is, it returns True. If not, it returns False.

Now for the center of the whole program, the FindPath subroutine.

>     Sub FindPath()
>         'A* pathfinding Algorithm
>         Dim c As PointType              'Current Square
>         Dim onFinish As Integer

>         c.x = mStart.x                  'Set the current square to
>         c.y = mStart.y                  'the start square coord.

>         Do While onFinish = False       'Do this while we have not found the Finish square
>             Print ".";
>             AddToClosed c.x, c.y        'Add the current square to the Closed list
>             For y = -1 to 1
>                 For x = -1 to 1
>                     If Not Map((c.x + x),(c.y+y)).mType = Wall Then             'If it is not a Wall square
>                         If (IsOnClosed((c.x + x),(c.y + y))) = False Then       'If it is not on the Closed List
>                             If (IsOnOpen((c.x + x),(c.y + y))) = False Then     'It is not on the Open list, add it

>                                 'Calculate F, G, and H scores
>                                 'G First
>                                 If Map((c.x + x),(c.y + y)).mType = Ground Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + GroundCost
>                                 ElseIF Map((c.x + x),(c.y + y)).mType = Hill Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + HillCost
>                                 ElseIf Map((c.x + x),(c.y + y)).mType = Water Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + WaterCost
>                                 ElseIF Map((c.x + x),(c.y + y)).mType = Cliff Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + CliffCost
>                                 End If

>                                 'Now H score using Manhattan distance
>                                 hx = 10 * (ABS(((c.x + x)-(mFinish.x))))
>                                 hy = 10 * (ABS(((c.y + y)-(mFinish.y))))

>                                 Map((c.x + x),(c.y + y)).hScore = hx + hy

>                                 'Finally, the F score

>                                 Map((c.x + x),(c.y + y)).fScore = Map((c.x + x),(c.y + y)).gScore + Map((c.x + x),(c.y + y)).hScore

>                                 'Make the current square the parent of this square
>                                 Map((c.x + x),(c.y + y)).pX = c.x
>                                 Map((c.x + x),(c.y + y)).pY = c.y

>                                 'Then add this square to the Open List

>                                 AddToOpen (c.x + x), (c.y + y)

>                                 'If it's the finish square, we've found the path!
>                                 If (c.x + x) = mFinish.x And (c.y + y) = mFinish.y Then
>                                     onFinish = True
>                                 End If

>                             Else        'Then it is on the Open List. Check to see if this is the better route

>                                 If Map((c.x + x),(c.y + y)).mType = Ground Then
>                                     tempG = Map((c.x),(c.y)).gScore + GroundCost
>                                 ElseIF Map((c.x + x),(c.y + y)).mType = Hill Then
>                                     tempG = Map((c.x),(c.y)).gScore + HillCost
>                                 ElseIf Map((c.x + x),(c.y + y)).mType = Water Then
>                                     tempG = Map((c.x),(c.y)).gScore + WaterCost
>                                 ElseIf Map((c.x + x),(c.y + y)).mType = Cliff Then
>                                     tempG = Map((c.x),(c.y)).gScore + CliffCost
>                                 End If

>                                 If tempG < Map((c.x + x),(c.y + y)).gScore Then     'This is the better route
>                                     'Make the current square the parent of this square
>                                     Map((c.x + x),(c.y + y)).pX = c.x
>                                     Map((c.x + x),(c.y + y)).pY = c.y

>                                     'Recalculate G and F scores
>                                     'G
>                                     Map((c.x + x),(c.y + y)).gScore = tempG
>                                     'F
>                                     Map((c.x + x),(c.y + y)).fScore = Map((c.x + x),(c.y + y)).gScore + Map((c.x + x),(c.y + y)).hScore

>                                 End If

>                             End If
>                         End If
>                     End If
>                 Next x
>             Next y

>             'Go through the Open List to find the lowest F score
>             curScore = 20000    'Set to a random number to start.
>             For i = 1 to uBound(OpenList)
>             If IsOnClosed((OpenList(i).x),(OpenList(i).y)) = False Then
>                 If Map((OpenList(i).x),(OpenList(i).y)).fScore <= curScore Then
>                     c.x = OpenList(i).x
>                     c.y = OpenList(i).y
>                     curScore = Map((OpenList(i).x),(OpenList(i).y)).fScore
>                 End If
>             End If
>            Next i

>        Loop

>     'We've found the target square.
>     Dim onStart As Integer
>     c.x = mFinish.x
>     c.y = mFinish.y
>     i = 1
>     Do While onStart = False
>         AddToPath c.x,c.y

>         If c.x = mStart.x And c.y = mStart.y Then
>             onStart = True
>         End If

>         x = c.x
>         y = c.y

>         c.x = Map(x,y).pX               'Make the Current Square the parent square
>         c.y = Map(x,y).pY

>         i = i + 1                       'Increment i
>     Loop

>     End Sub

This code goes through the squares, adding them to the open or closed list, until it reaches the finishing square. At this point, it goes from the finishing square and, using the pX and pY of that square, adds each square's parent square to the path.

Ok, so we only have a two things left to do. Those are to implement the two remaining subs, DrawScreen and ClearScreen, and to make the code to show the path. The two subs are easy.

>     Sub ClearScreen()
>         Line (0,0)-(639,479), 0, BF
>     End Sub

>     Sub DrawScreen()
>         For y = 1 to uBound(Map, 2)
>             For x = 1 to uBound(Map,1)
>                 Square = Map(x,y).mType
>                 Select Case Square
>                 Case Ground: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 2, BF
>                 Case Hill: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 21, BF
>                 Case Water: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 33, BF
>                 Case Wall: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 8, BF
>                 Case Cliff: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 7, BF
>                 Case Start: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 15, BF
>                 Case Finish: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 4, BF
>                 End Select
>             Next x
>         Next y
>         Dim ox, oy As Integer
>             ox = mFinish.x
>             oy = mFinish.y

>             For i = 1 To uBound(Path)
>                 x = Path(i).x
>                 y = Path(i).y
>                 Line (ox * 10 + 5,oy * 10 + 5)-(x * 10 + 5,y * 10 + 5), 14
>                 ox = x
>                 oy = y
>             Next i
>             Circle (comp.x, comp.y), 3, 14
>         Locate 20,1
>             For i = 1 To uBound(Path)
>             Print Path(i).x;
>             Print ",";
>             Print Path(i).y;
>         Next i
>     End Sub

The DrawScreen sub goes through the map, and depending on the mType, draws a colored square at that location. It then goes through the path, drawing a yellow line from square to square. Then it draws a circle at the comp's x and y position (which will be updated in the main part of the program). Finally, it prints out each coordinate for the path (I put that there before I used a yellow line). The ClearScreen sub just draws a black box over the screen (Faster than CLS).

Now, last but not least, we write out our main program which calls the FindPath sub, and shows the user our path.

>     CLS
>     Screen 18

>     Print "Finding Path"

>     FindPath

>     Print "Path Found"
>     sleep

>     ClearScreen
>     DrawScreen

>     For i = 1 to uBound(Path)
>         comp.x = (Path(i).x * 10 + 5)
>         comp.y = (Path(i).y * 10 + 5)

>         ClearScreen
>         DrawScreen
>         Sleep
>     Next i

>     Sleep
>     End

That was the easiest part. Now, put it all together to get our final code!

>     DefInt A-Z
>     '$Dynamic
>     Declare Sub ClearScreen()
>     Declare Sub DrawScreen()

>     Declare Sub FindPath()
>     Declare Sub AddToOpen(x As Integer, y As Integer)
>     Declare Sub AddToClosed(x As Integer, y As Integer)
>     Declare Sub AddToPath(x As Integer, y As Integer)
>     Declare Function IsOnOpen(x As Integer, y As Integer)
>     Declare Function IsOnClosed(x As Integer, y As Integer)

>     const Ground = 0
>     const Hill = 2
>     const Water = 1
>     const Cliff = 3
>     const Wall = 4
>     const Start = 5
>     const Finish = 6

>     const False = 0
>     const True = Not False

>     const GroundCost = 10
>     const HillCost = 25
>     const WaterCost = 50
>     const CliffCost = 100

>     Type SquareType
>         fScore As Integer
>         gScore As Integer
>         hScore As Integer
>         mType As Integer
>         pX As Integer
>         pY As Integer
>     End Type

>     Type PointType
>         x As Integer
>         y As Integer
>     End Type

>     Open "board.brd" For Input As #1
>     Input #1, sWidth, sHeight

>     Dim Shared Map(sWidth, sHeight) As SquareType
>     Dim Shared OpenList() As PointType
>     Dim Shared ClosedList() As PointType
>     Dim Shared Path() As PointType
>     Dim Shared mStart As PointType
>     Dim Shared mFinish As PointType
>     Dim Shared comp As PointType

>     For y = 1 To sHeight
>         For x = 1 To sWidth
>             Input #1, Map(x,y).mType
>             If Map(x,y).mType = Finish Then
>                 mFinish.x = x
>                 mFinish.y = y
>             ElseIf Map(x,y).mType = Start Then
>                 mStart.x = x
>                 mStart.y = y
>             End If
>         Next x
>     Next y
>     Close #1

>     CLS
>     Screen 18

>     Print "Finding Path"

>     FindPath

>     Print "Path Found"
>     sleep

>     ClearScreen
>     DrawScreen

>     For i = 1 to uBound(Path)
>         comp.x = (Path(i).x * 10 + 5)
>         comp.y = (Path(i).y * 10 + 5)

>         ClearScreen
>         DrawScreen
>         Sleep
>     Next i

>     Sleep
>     End

>     Sub FindPath()
>         'A* pathfinding Algorithm
>         Dim c As PointType              'Current Square
>         Dim onFinish As Integer

>         c.x = mStart.x                  'Set the current square to
>         c.y = mStart.y                  'the start square coord.

>         Do While onFinish = False       'Do this while we have not found the Finish square
>             Print ".";
>             AddToClosed c.x, c.y        'Add the current square to the Closed list
>             For y = -1 to 1
>                 For x = -1 to 1
>                     If Not Map((c.x + x),(c.y+y)).mType = Wall Then             'If it is not a Wall square
>                         If (IsOnClosed((c.x + x),(c.y + y))) = False Then       'If it is not on the Closed List
>                             If (IsOnOpen((c.x + x),(c.y + y))) = False Then     'It is not on the Open list, add it

>                                 'Calculate F, G, and H scores
>                                 'G First
>                                 If Map((c.x + x),(c.y + y)).mType = Ground Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + GroundCost
>                                 ElseIF Map((c.x + x),(c.y + y)).mType = Hill Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + HillCost
>                                 ElseIf Map((c.x + x),(c.y + y)).mType = Water Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + WaterCost
>                                 ElseIF Map((c.x + x),(c.y + y)).mType = Cliff Then
>                                     Map((c.x + x),(c.y + y)).gScore = Map((c.x),(c.y)).gScore + CliffCost
>                                 End If

>                                 'Now H score using Manhattan distance
>                                 hx = 10 * (ABS(((c.x + x)-(mFinish.x))))
>                                 hy = 10 * (ABS(((c.y + y)-(mFinish.y))))

>                                 Map((c.x + x),(c.y + y)).hScore = hx + hy

>                                 'Finally, the F score

>                                 Map((c.x + x),(c.y + y)).fScore = Map((c.x + x),(c.y + y)).gScore + Map((c.x + x),(c.y + y)).hScore

>                                 'Make the current square the parent of this square
>                                 Map((c.x + x),(c.y + y)).pX = c.x
>                                 Map((c.x + x),(c.y + y)).pY = c.y

>                                 'Then add this square to the Open List

>                                 AddToOpen (c.x + x), (c.y + y)

>                                 'If it's the finish square, we've found the path!
>                                 If (c.x + x) = mFinish.x And (c.y + y) = mFinish.y Then
>                                     onFinish = True
>                                 End If

>                             Else        'Then it is on the Open List. Check to see if this is the better route

>                                 If Map((c.x + x),(c.y + y)).mType = Ground Then
>                                     tempG = Map((c.x),(c.y)).gScore + GroundCost
>                                 ElseIF Map((c.x + x),(c.y + y)).mType = Hill Then
>                                     tempG = Map((c.x),(c.y)).gScore + HillCost
>                                 ElseIf Map((c.x + x),(c.y + y)).mType = Water Then
>                                     tempG = Map((c.x),(c.y)).gScore + WaterCost
>                                 ElseIf Map((c.x + x),(c.y + y)).mType = Cliff Then
>                                     tempG = Map((c.x),(c.y)).gScore + CliffCost
>                                 End If

>                                 If tempG < Map((c.x + x),(c.y + y)).gScore Then     'This is the better route
>                                     'Make the current square the parent of this square
>                                     Map((c.x + x),(c.y + y)).pX = c.x
>                                     Map((c.x + x),(c.y + y)).pY = c.y

>                                     'Recalculate G and F scores
>                                     'G
>                                     Map((c.x + x),(c.y + y)).gScore = tempG
>                                     'F
>                                     Map((c.x + x),(c.y + y)).fScore = Map((c.x + x),(c.y + y)).gScore + Map((c.x + x),(c.y + y)).hScore

>                                 End If

>                             End If
>                         End If
>                     End If
>                 Next x
>             Next y

>             'Go through the Open List to find the lowest F score
>             curScore = 20000    'Set to a random number to start.
>             For i = 1 to uBound(OpenList)
>             If IsOnClosed((OpenList(i).x),(OpenList(i).y)) = False Then
>                 If Map((OpenList(i).x),(OpenList(i).y)).fScore <= curScore Then
>                     c.x = OpenList(i).x
>                     c.y = OpenList(i).y
>                     curScore = Map((OpenList(i).x),(OpenList(i).y)).fScore
>                 End If
>             End If
>            Next i

>        Loop

>     'We've found the target square.
>     Dim onStart As Integer
>     c.x = mFinish.x
>     c.y = mFinish.y
>     i = 1
>     Do While onStart = False
>         AddToPath c.x,c.y

>         If c.x = mStart.x And c.y = mStart.y Then
>             onStart = True
>         End If

>         x = c.x
>         y = c.y

>         c.x = Map(x,y).pX               'Make the Current Square the parent square
>         c.y = Map(x,y).pY

>         i = i + 1                       'Increment i
>     Loop

>     End Sub

>     Sub AddToOpen(x As Integer, y As Integer)
>         Dim TempOpen(uBound(OpenList)) As PointType

>         For i = 1 to uBound(OpenList)
>             TempOpen(i).x = OpenList(i).x
>             TempOpen(i).y = OpenList(i).y
>         Next i
>         size = uBound(OpenList)
>         Redim OpenList(size+1) As PointType

>         For i = 1 to uBound(TempOpen)
>             OpenList(i).x = TempOpen(i).x
>             OpenList(i).y = TempOpen(i).y
>         Next i

>         OpenList(uBound(OpenList)).x = x
>         OpenList(uBound(OpenList)).y = y
>     End Sub

>     Sub AddToClosed(x As Integer, y As Integer)
>         Dim TempClosed(uBound(ClosedList)) As PointType

>         For i = 1 to uBound(ClosedList)
>             TempClosed(i).x = ClosedList(i).x
>             TempClosed(i).y = ClosedList(i).y
>         Next i
>         size = uBound(ClosedList)
>         Redim ClosedList(size+1) As PointType

>         For i = 1 to uBound(TempClosed)
>             ClosedList(i).x = TempClosed(i).x
>             ClosedList(i).y = TempClosed(i).y
>         Next i

>         ClosedList(uBound(ClosedList)).x = x
>         ClosedList(uBound(ClosedList)).y = y
>     End Sub

>     Sub AddToPath(x As Integer, y As Integer)
>         Dim TempPath(uBound(Path)) As PointType

>         For i = 1 to uBound(Path)
>             TempPath(i).x = Path(i).x
>             TempPath(i).y = Path(i).y
>         Next i
>         size = uBound(Path)
>         Redim Path(size+1) As PointType

>         For i = 1 to uBound(TempPath)
>             Path(i).x = TempPath(i).x
>             Path(i).y = TempPath(i).y
>         Next i

>         Path(uBound(Path)).x = x
>         Path(uBound(Path)).y = y
>     End Sub

>     Function IsOnOpen(x As Integer, y As Integer)
>         For i = 1 to uBound(OpenList)
>             If OpenList(i).x = x And OpenList(i).y = y Then
>             'It's on the open list
>             IsOnOpen = True
>             Exit For
>             End If
>         Next i
>     End Function

>     Function IsOnClosed(x As Integer, y As Integer)
>         For i = 1 to uBound(ClosedList)
>             If ClosedList(i).x = x And ClosedList(i).y = y Then
>             'It's on the closed list
>             IsOnClosed = True
>             Exit For
>             End If
>         Next i
>     End Function

>     Sub ClearScreen()
>         Line (0,0)-(639,479), 0, BF
>     End Sub

>     Sub DrawScreen()
>         For y = 1 to uBound(Map, 2)
>             For x = 1 to uBound(Map,1)
>                 Square = Map(x,y).mType
>                 Select Case Square
>                 Case Ground: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 2, BF
>                 Case Hill: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 21, BF
>                 Case Water: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 33, BF
>                 Case Wall: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 8, BF
>                 Case Cliff: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 7, BF
>                 Case Start: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 15, BF
>                 Case Finish: Line(x * 10, y * 10)-(x * 10 + 10, y * 10 + 10), 4, BF
>                 End Select
>             Next x
>         Next y
>         Dim ox, oy As Integer
>             ox = mFinish.x
>             oy = mFinish.y

>             For i = 1 To uBound(Path)
>                 x = Path(i).x
>                 y = Path(i).y
>                 Line (ox * 10 + 5,oy * 10 + 5)-(x * 10 + 5,y * 10 + 5), 14
>                 ox = x
>                 oy = y
>             Next i
>             Circle (comp.x, comp.y), 3, 14
>         Locate 20,1
>             For i = 1 To uBound(Path)
>             Print Path(i).x;
>             Print ",";
>             Print Path(i).y;
>         Next i
>     End Sub

And there you have it! It really isn't too difficult. Here are a few more tips:

### Preventing the "Go Through Walls" problem

You may notice that in a game, this would generate paths that cut through the corner of the wall. To prevent this, you need to keep A* from checking diagonal squares that are next to a wall. I haven't tried this but have been told it isn't too hard. Go ahead and give it a shot.

### Turn it into a function

One of the greatest things about any algorithm is the ablility to make it into a function. Make the FindPath sub in this code into a function that asks for:

1. An array such as the Map array in this example.
2. A starting square.
3. A Finishing square.

All it would take is a little bit of messing around with the code. Try it out!

### There is more than the Manhattan Method

There is more than one method of calculating the H score. Here are a couple:

- Euclidean Distance

  The Euclidean Distance is the exact distance in a straight line to the finishing square. It is really only feasible if your units can move at any angle rather than in grid directions (north, southwest, etc.). The formula is:
  H = D * SQR((TargetX - SquareX)^2 + (TargetY - SquareY)^2)
  Where D is the is the minimum cost to move from one square to another (The lowest G cost).

- Diagonal Distance

  The Diagonal Distance is perhaps a slightly better formula for diagonally moving units (such as in the example). It simply accounts for the ability to move diagonally across squares.
  H = D * max(ABS(TargetX - SquareX) + ABS(TargetY - SquareY))

### So in Conclusion

Thanks for taking the time to read this tutorial. I hope I did better this time. This program can be downloaded on my site in the "Programming" section. If there are any questions or comments, you can PM Torahteen on the QBN message boards, or you can post a message on my site's forum. Until next time!

Torahteen