Sign in to follow this  
Psychopathetica

A* Pathfinding And Sprite Path Following

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:

[code]
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
[/code]

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 this post


Link to post
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 this post


Link to post
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:

[code]
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
[/code]

Share this post


Link to post
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 [b]+ TILE_WIDTH / 2[/b]
AStar_Position.Y = (Astar_Path(Current_Path - 1).Y * TILE_HEIGHT) + Map(0).Position.Y [b]+ TILE_HEIGHT / 2[/b]

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 :P

Share this post


Link to post
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 this post


Link to post
Share on other sites
[quote name='Psychopathetica' timestamp='1307633322' post='4821343']
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
[/quote]

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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this