# A* Pathfinding And Sprite Path Following

This topic is 2450 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi there. I have successfully pulled off A* Pathfinding in my game but im having a very hard time making the monster follow the path I have. In this code is the A* Algorithm:

 Option Explicit Public Type Node Parent As Long H As Single G As Single Score As Single X As Long Y As Long Used As Boolean End Type Public Type Path_Piece X As Long Y As Long Parent As Long End Type Public Number_Of_Nodes As Long Public Open_List() As Node Public Closed_List() As Node Public Complete As Boolean Public Complete2 As Boolean Public Path As Long 'To look through the path Public Parent As Long 'To temporaryly store parent Public Current_Square_Open As Long 'To keep track of the current square on the open list Public Current_Square_Closed As Long 'To keep track of the current square on the closed list Public Is_Clear(7) As Boolean Public Astar_Path() As Path_Piece Public Starting_Path As Path_Piece 'The start of the path Public Ending_Path As Path_Piece 'The End of the path Public Length_Of_Astar_Path As Long Public Compute_AStar_Enabled As Boolean Public Sub Add_To_Open_List(Prey As Sprite_Type, Predator As Sprite_Type, ByVal X As Long, ByVal Y As Long, Map As Map_Type, ByVal G As Long, ByVal Parent As Long) Dim I As Long For I = 0 To Number_Of_Nodes If X <= 0 Then X = 0 If Y <= 0 Then Y = 0 If X >= UBound(Map.Collision_Map.Response, 1) Then X = UBound(Map.Collision_Map.Response, 1) If Y >= UBound(Map.Collision_Map.Response, 2) Then Y = UBound(Map.Collision_Map.Response, 2) If (Closed_List(I).X = X And Closed_List(I).Y = Y And Closed_List(I).Used) Or _ Map.Collision_Map.Response(X, Y) = COLLISION_WALL Then Exit Sub If Open_List(I).X = X And Open_List(I).Y = Y And Open_List(I).Used = True Then Dim TempG As Long TempG = Closed_List(Parent).G + G If TempG < Open_List(I).G Then Open_List(I).Parent = Parent Open_List(I).G = TempG End If Open_List(I).Score = Open_List(I).G + Open_List(I).H Exit Sub End If If Open_List(I).Used = False Then Open_List(I).G = Closed_List(Parent).G + G Open_List(I).X = X Open_List(I).Y = Y Open_List(I).H = (Abs(Prey.Coordinates.X - X) + Abs(Prey.Coordinates.Y - Y)) * 10 Open_List(I).Score = Open_List(I).G + Open_List(I).H Open_List(I).Parent = Parent End If Next I Open_List(FNO).Used = True End Sub Public Function Add_To_Closed_List(N As Node) Dim I As Long, Temp As Long For I = 0 To Number_Of_Nodes If Closed_List(I).Used = False Then Closed_List(I).Parent = N.Parent Closed_List(I).X = N.X Closed_List(I).Y = N.Y Closed_List(I).G = N.G Closed_List(I).H = N.H Closed_List(I).Score = N.Score End If Next I Temp = FNC Current_Square_Closed = Temp Closed_List(Temp).Used = True N.Used = False N.Score = 100000 End Function 'FNO = gets a Free Node from the Open list Public Function FNO() As Long Dim I As Long For I = 0 To Number_Of_Nodes If Open_List(I).Used = False Then FNO = I Exit Function End If Next I End Function 'FNC = gets a Free Node from the Closed list Public Function FNC() As Long Dim I As Long For I = 0 To Number_Of_Nodes If Closed_List(I).Used = False Then FNC = I Exit Function End If Next I End Function Public Function Reset_Lists() Dim I As Long Complete = False Current_Square_Open = 0 Current_Square_Closed = 0 Path = 0 For I = 0 To 7 Is_Clear(I) = True Next I Number_Of_Nodes = (Map.Width - 1) * (Map.Height - 1) ReDim Open_List(Number_Of_Nodes) As Node ReDim Closed_List(Number_Of_Nodes) As Node ReDim Astar_Path(Number_Of_Nodes) As Path_Piece End Function Private Sub Mini_Check_Clear(Offset_X As Long, Offset_Y As Long, X As Long, Y As Long, Clear_Number As Long, Map As Map_Type) If Is_Clear(Clear_Number) = False Then Exit Sub If X + Offset_X <= 0 Then X = 0 If Y + Offset_Y <= 0 Then Y = 0 If X + Offset_X >= UBound(Map.Collision_Map.Response, 1) Then X = UBound(Map.Collision_Map.Response, 1) If Y + Offset_Y >= UBound(Map.Collision_Map.Response, 2) Then Y = UBound(Map.Collision_Map.Response, 2) If Map.Collision_Map.Response(X, Y) = COLLISION_WALL Then Is_Clear(Clear_Number) = False Else Is_Clear(Clear_Number) = True End If End Sub Public Sub A_Star_Chase_Algorithm(Prey As Sprite_Type, Predator As Sprite_Type, Map As Map_Type) Dim I As Long 'Only activate if we pulled aggro to help speed things up If Predator.Aggroed = True Then 'Only fire this for every new coordinate change so we dont waste cpu computations to also speed things up If Compute_AStar_Enabled = True Then 'Number_Of_Nodes = (Map.Width - 1) * (Map.Height - 1) 'ReDim Open_List(Number_Of_Nodes) As Node 'ReDim Closed_List(Number_Of_Nodes) As Node 'ReDim Astar_Path(Number_Of_Nodes) As Path_Piece Reset_Lists 'Starting X and Y will be at the predator Add_To_Open_List Prey, Predator, Predator.Coordinates.X, Predator.Coordinates.Y, Map, 0, 0 Do DoEvents Dim Running_Total As Long Running_Total = 0 For I = 0 To Number_Of_Nodes If Open_List(I).Used = True Then If Open_List(I).Score < Open_List(Current_Square_Open).Score Then Current_Square_Open = I Else Running_Total = Running_Total + 1 End If Next I If (Running_Total > Number_Of_Nodes - 1 And Current_Square_Open <> 0) Or (FNC = 0 And Current_Square_Open <> 0) Then 'Cant make path Reset_Lists Exit Sub End If 'Switch it Add_To_Closed_List Open_List(Current_Square_Open) For I = 0 To 7 Is_Clear(I) = True Next I 'Check around me to see if it is clear Mini_Check_Clear -1, -1, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 0, Map Mini_Check_Clear 0, -1, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 1, Map Mini_Check_Clear 1, -1, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 2, Map Mini_Check_Clear 1, 0, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 3, Map Mini_Check_Clear 1, 1, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 4, Map Mini_Check_Clear 0, 1, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 5, Map Mini_Check_Clear -1, 1, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 6, Map Mini_Check_Clear -1, 0, Closed_List(Current_Square_Closed).X, Closed_List(Current_Square_Closed).Y, 7, Map 'Add the nodes around all of the closed nodes If Is_Clear(0) And Is_Clear(1) And Is_Clear(7) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X - 1, Closed_List(Current_Square_Closed).Y - 1, Map, 14, Current_Square_Closed 'Top Left If Is_Clear(1) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X + 0, Closed_List(Current_Square_Closed).Y - 1, Map, 10, Current_Square_Closed 'Top If Is_Clear(2) And Is_Clear(1) And Is_Clear(3) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X + 1, Closed_List(Current_Square_Closed).Y - 1, Map, 14, Current_Square_Closed 'Top Right If Is_Clear(3) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X + 1, Closed_List(Current_Square_Closed).Y + 0, Map, 10, Current_Square_Closed 'Right If Is_Clear(4) And Is_Clear(5) And Is_Clear(3) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X + 1, Closed_List(Current_Square_Closed).Y + 1, Map, 14, Current_Square_Closed 'Bottom Right If Is_Clear(5) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X + 0, Closed_List(Current_Square_Closed).Y + 1, Map, 10, Current_Square_Closed 'Bottom If Is_Clear(6) And Is_Clear(5) And Is_Clear(7) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X - 1, Closed_List(Current_Square_Closed).Y + 1, Map, 14, Current_Square_Closed 'Bottom Left If Is_Clear(7) Then Add_To_Open_List Prey, Predator, Closed_List(Current_Square_Closed).X - 1, Closed_List(Current_Square_Closed).Y + 0, Map, 10, Current_Square_Closed 'Left For I = 0 To Number_Of_Nodes If Closed_List(I).X = Prey.Coordinates.X And Closed_List(I).Y = Prey.Coordinates.Y And Closed_List(I).Used Then Complete = True Next I Loop Until Complete = True Astar_Path(0).X = Closed_List(Current_Square_Closed).X Astar_Path(0).Y = Closed_List(Current_Square_Closed).Y Astar_Path(0).Parent = Closed_List(Current_Square_Closed).Parent Parent = Closed_List(Current_Square_Closed).Parent Complete = False Do 'DoEvents Path = Path + 1 Astar_Path(Path).X = Closed_List(Parent).X Astar_Path(Path).Y = Closed_List(Parent).Y Parent = Closed_List(Parent).Parent Astar_Path(Path).Parent = Parent If Astar_Path(Path).X = Predator.Coordinates.X And Astar_Path(Path).Y = Predator.Coordinates.Y Then Complete = True Loop Until Complete = True Length_Of_Astar_Path = Path End If End If End Sub 

And Astar_Path() is where the coordinates are stored. Also in my game I highlighted the tiles to visually see the path. The picture I uploaded is an example. I have tried my hardest to get the monster to follow that path but everything i have done has failed. If anyone has any insight or code examples to help me do this I would apprieciate it. I dont mind c++ examples either. Thanks in advance.

##### Share on other sites
Have you hand-traced your movement code? No one here will answer likely your question unless you have. And if you have, you should have found your error by doing so.

##### Share on other sites
Basically Im trying to get my monster to move from one coordinate to another in the Astar_Path(), and when it finishes reaching that coordinate, will go on to the next coordinate off the Astar_Path(). Ill try again but if it fails ill come back and post what I tried and well see how it needs fixed.

##### Share on other sites
I almost pulled it off but ran into a slight issue. Basically the Current_Path starts at the maximum length of the AStar path. And for every tile the monster goes, itll subtract the path by one working its way down until it reaches its prey. But my problem is that it sometimes gets caught when my player hides behind a wall for some reason. Perhaps theres a better approach than this:

 Private Sub Follow_A_Star_Path(Prey As Sprite_Type, Predator As Sprite_Type, ByVal Speed As Single, ByVal Distance_To_Stop As Single) Dim AStar_Position As Vector Dim Distance As Single Dim Vec As Vector If IsArrayInitialised(VarPtrArray(Astar_Path)) = True Then If Prey.Distance >= Distance_To_Stop Then If Current_Path > 0 Then If Cursor_Visible = True Then AStar_Position.X = (Astar_Path(Current_Path - 1).X * TILE_WIDTH) + Map(0).Position.X AStar_Position.Y = (Astar_Path(Current_Path - 1).Y * TILE_HEIGHT) + Map(0).Position.Y Predator.Angle = Radian_To_Degree(Get_Radian(Predator.Position.X, Predator.Position.Y, AStar_Position.X, AStar_Position.Y)) Vec.X = Astar_Path(Current_Path - 1).X - Predator.Position.X Vec.Y = Astar_Path(Current_Path - 1).Y - Predator.Position.Y Predator.Velocity.X = Cos(Predator.Angle * PI / 180) * Speed Predator.Velocity.Y = Sin(Predator.Angle * PI / 180) * Speed Predator.Position.X = Predator.Position.X + Predator.Velocity.X Predator.Position.Y = Predator.Position.Y + Predator.Velocity.Y Else AStar_Position.X = (Astar_Path(Current_Path - 1).X * TILE_WIDTH) + Initial_Map_Position.X AStar_Position.Y = (Astar_Path(Current_Path - 1).Y * TILE_HEIGHT) + Initial_Map_Position.Y Predator.Angle = Radian_To_Degree(Get_Radian(Predator.Initial_Position.X, Predator.Initial_Position.Y, AStar_Position.X, AStar_Position.Y)) Vec.X = AStar_Position.X - Predator.Initial_Position.X Vec.Y = AStar_Position.Y - Predator.Initial_Position.Y Predator.Velocity.X = Cos(Predator.Angle * PI / 180) * Speed Predator.Velocity.Y = Sin(Predator.Angle * PI / 180) * Speed Predator.Initial_Position.X = Predator.Initial_Position.X + Predator.Velocity.X Predator.Initial_Position.Y = Predator.Initial_Position.Y + Predator.Velocity.Y End If Distance = Sqr(Vec.X * Vec.X + Vec.Y * Vec.Y) If Int(Distance) <= 15 Then Current_Path = Current_Path - 1 If Current_Path <= 0 Then Current_Path = 0 End If End If End If End If End Sub 

##### Share on other sites
Um I think I might have improved it a notch by adding a couple things in these lines of code

AStar_Position.X = (Astar_Path(Current_Path - 1).X * TILE_WIDTH) + Map(0).Position.X + TILE_WIDTH / 2
AStar_Position.Y = (Astar_Path(Current_Path - 1).Y * TILE_HEIGHT) + Map(0).Position.Y + TILE_HEIGHT / 2

Basically it was going from the top left point of every astar_path tile coordinate when it needed to be traveling from the center of the tiles. I think I might have solved it but if there are improvements let me know.
Problem solved

##### Share on other sites
And that's why we step-trace our code.

##### Share on other sites
Nice WoW art assets

##### Share on other sites
Yea Im making wow in 2D. Only Im calling it Bosskillers. Its also gonna be a multiplayer game to where you strategically go through dungeons and take down difficult trash pulls and raid bosses. Drawing bosses is gonna be a royal pain but at least it plays exactly like wow, even holding down the mouse button to move the map around feels like it.. As for Link, hes my test dummy. =P

##### Share on other sites

Yea Im making wow in 2D. Only Im calling it Bosskillers. Its also gonna be a multiplayer game to where you strategically go through dungeons and take down difficult trash pulls and raid bosses. Drawing bosses is gonna be a royal pain but at least it plays exactly like wow, even holding down the mouse button to move the map around feels like it.. As for Link, hes my test dummy. =P

You are planning on replacing the stolen art before a release though, right? Otherwise you will be slapped with a nice lawsuit if blizzard gets wind of it.

##### Share on other sites
Its a fan made game but its mainly for me and my friends

• 10
• 14
• 11
• 10
• 11