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.
