Have A* Path. How do I Properly Follow it?

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

Recommended Posts

I feel that my method of following the A* path is totally wrong. I basically been checking the angle of the next tile for the monster to follow which seems to work, but I run into situations where if the next tile it must approach is at an angle and theres a wall there, the monster will drag along the wall till it reaches it. The A* Path I have literally starts at the Monsters Tile coordinate and goes all the way to the Players Tile coordinate, which is why I must check the next tile the monster must go in the array. But somethings iffy. What is the proper way for a sprite to go from one tile to another to follow the A* Star path you have? Here's what I currently have. If anyone has any ideas let me know. I can convert C++ and C# code to VB since I know everyone on this site mainly uses that.

 Public Sub Follow_AStar_Path(Map As Map_Type, Predator As Sprite_Type, Prey As Sprite_Type, ByVal Speed As Single) Dim AStar_Position As Vector Dim Distance As Single Dim Angle As Single Dim Velocity As Vector Dim Vec As Vector If Predator.Path_Found = True And Predator.Path_Hunt = False Then If IsArrayInitialized(VarPtrArray(Predator.AStar_Path)) = True Then If Predator.Current_Path > 0 Then AStar_Position.X = (Predator.AStar_Path(Predator.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE / 2) AStar_Position.Y = (Predator.AStar_Path(Predator.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE / 2) Angle = Radian_To_Degree(Get_Radian(Predator.Center_of_Sprite_Position.X, Predator.Center_of_Sprite_Position.Y, AStar_Position.X, AStar_Position.Y)) Vec.X = AStar_Position.X - Predator.Center_of_Sprite_Position.X Vec.Y = AStar_Position.Y - Predator.Center_of_Sprite_Position.Y Velocity.X = Cos(Angle * PI / 180) * Speed Velocity.Y = Sin(Angle * PI / 180) * Speed Predator.Position.X = Predator.Position.X + Velocity.X Predator.Position.Y = Predator.Position.Y + Velocity.Y End If If (Predator.Center_of_Tile_Coordinates.X = Prey.Center_of_Tile_Coordinates.X And Predator.Center_of_Tile_Coordinates.Y = Prey.Center_of_Tile_Coordinates.Y) Then Exit Sub End If Distance = Sqr(Vec.X * Vec.X + Vec.Y * Vec.Y) If Int(Distance) <= 0 Then Predator.Current_Path = Predator.Current_Path - 1 If Predator.Current_Path <= 0 Then Predator.Current_Path = 0 End If End If Else Clear_AStar Map End If End Sub 

Share on other sites
It sounds like you already have collision with the environment, so the next half is checking to see if your monster will collide with the wall on the way to the next point and, if so, altering the monsters' path. If you're using sphere-line segment collision, the next step is capsule- (swept sphere) line-segment collision.

Of interest to smooth path movement is <a href="http://www.mvps.org/directx/articles/catmull/">Catmull-Rom splines</a>.

Share on other sites
So apparently it doesn't handle .html anymore and I'm not seeing an "edit" button. So, re-link: Catmull-Rom splines. That link is primarily because it adaquatly explains and has the math.

Share on other sites
Thanks for the reply, but to be honest, I wasn't having my sprites curve from one node to another. More like move straight into one node into another. I guess I can check if theres collision, but there's really no documentation anywhere online that I could find for what I'm trying to do even though there should, so I'm practically having to guess and make it up as I go along just to get a sprite to move from one node to another. It should be basic knowledge game programming 101. o.O

Share on other sites
It sounds to me like you need more nodes. If an edge from one node to another goes through a wall, that's not really a valid edge, is it?

Share on other sites
Nah none of my nodes are going through walls. My only issue was having the sprite go from node to node. But I think I solved it cause it goes through my maze pretty smoothly with this funky algorithm I done with a couple If statements:

 Public Sub Follow_AStar_Path(Map As Map_Type, Predator As Sprite_Type, Prey As Sprite_Type, ByVal Speed As Single) Dim AStar_Position As Vector Dim Distance As Single Dim Angle As Single Dim Velocity As Vector Dim Vec As Vector With Predator If .Path_Found = True And .Path_Hunt = False Then If IsArrayInitialized(VarPtrArray(.AStar_Path)) = True Then If (Int(.Center_of_Sprite_Position.X) < Int((.AStar_Path(.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE \ 2))) And (Int(.Center_of_Sprite_Position.Y) = Int((.AStar_Path(.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE \ 2))) Or _ (Int(.Center_of_Sprite_Position.X) = Int((.AStar_Path(.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE \ 2))) And (Int(.Center_of_Sprite_Position.Y) < Int((.AStar_Path(.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE \ 2))) Then AStar_Position.X = (.AStar_Path(.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE / 2) AStar_Position.Y = (.AStar_Path(.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE / 2) ElseIf (Int(.Center_of_Sprite_Position.X) > Int((.AStar_Path(.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE \ 2))) And (Int(.Center_of_Sprite_Position.Y) = Int((.AStar_Path(.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE \ 2))) Or _ (Int(.Center_of_Sprite_Position.X) = Int((.AStar_Path(.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE \ 2))) And (Int(.Center_of_Sprite_Position.Y) > Int((.AStar_Path(.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE \ 2))) Then AStar_Position.X = (.AStar_Path(.Current_Path - 1).X * TILE_SIZE) + (TILE_SIZE / 2) AStar_Position.Y = (.AStar_Path(.Current_Path - 1).Y * TILE_SIZE) + (TILE_SIZE / 2) Else AStar_Position.X = (.AStar_Path(.Current_Path).X * TILE_SIZE) + (TILE_SIZE / 2) AStar_Position.Y = (.AStar_Path(.Current_Path).Y * TILE_SIZE) + (TILE_SIZE / 2) End If Angle = Radian_To_Degree(Get_Radian(.Center_of_Sprite_Position.X, .Center_of_Sprite_Position.Y, AStar_Position.X, AStar_Position.Y)) Vec.X = AStar_Position.X - .Center_of_Sprite_Position.X Vec.Y = AStar_Position.Y - .Center_of_Sprite_Position.Y Velocity.X = Cos(Angle * PI / 180) * Speed Velocity.Y = Sin(Angle * PI / 180) * Speed .Position.X = .Position.X + Velocity.X .Position.Y = .Position.Y + Velocity.Y Distance = Sqr(Vec.X * Vec.X + Vec.Y * Vec.Y) frmMain.Caption = Distance If Round(Distance, 0.05) <= 0 Then .Current_Path = .Current_Path - 1 If .Current_Path <= 0 Then .Current_Path = 0 End If If (.Center_of_Tile_Coordinates.X = Prey.Center_of_Tile_Coordinates.X And .Center_of_Tile_Coordinates.Y = Prey.Center_of_Tile_Coordinates.Y) Then Exit Sub End If End If Else Clear_AStar Map End If End With End Sub 

[EDIT]

Nevermind. At different speeds it gets iffy. Back to the drawing board

Share on other sites
I don't think you are understanding the terminology. A node is an specific position. And edge is a connector between nodes. Even if your nodes are out in the open, an edge between two nodes could be passing through a wall. You need to position your nodes so that the edges between them don't conflict with obstacles. That way, when a sprite is following an edge, it doesn't bump up against a wall.

Share on other sites
How would I test if the edge passed through a wall? I could use ray casting but it might be slow if there's 100s of enemys. Also i don' t think my edges pass through the wall anyways cause I just figured something out. Basically I been using the top left of the sprites and tiles rather than the dead center of em. So now I redid everything to be based off the center. The reason why I changed it was cause if the sprite or player were to go left or up, one pixel within the next tile would change the tile coordinates of that sprtie. For right and down to change, it would need to completely pass the tile, cause like I said the top left of the sprite needs to pass the next tile in order for it to change coordinates. Now I'm working with the center of the sprites and all my nodes now are in the center of where the monster needs to go and it flows smoothly, so now I no longer need to work with .Current_Path - 1, but just .Current_Path. Also with this new Follow_AStar_Path sub I created, rather than use angles, I'm gonna make if statements for up, down, left, right, upleft, upright, downleft, downright cause those are the only angles I want the sprite to be moving anyways.

 Public Sub Follow_AStar_Path(Map As Map_Type, Predator As Sprite_Type, Prey As Sprite_Type, ByVal Speed As Single) Dim AStar_Position As Vector Dim Distance As Single Dim Angle As Single Dim Velocity As Vector Dim Vec As Vector Dim Current_Path As Long With Predator If .Path_Found = True And .Path_Hunt = False Then If IsArrayInitialized(VarPtrArray(.AStar_Path)) = True Then If .Current_Path > 0 Then Angle = Radian_To_Degree(Get_Radian(.Center_of_Sprite_Position.X, .Center_of_Sprite_Position.Y, .AStar_Path(.Current_Path).X, .AStar_Path(.Current_Path).Y)) Vec.X = .AStar_Path(.Current_Path).X - .Center_of_Sprite_Position.X Vec.Y = .AStar_Path(.Current_Path).Y - .Center_of_Sprite_Position.Y Velocity.X = Cos(Angle * PI / 180) * Speed Velocity.Y = Sin(Angle * PI / 180) * Speed .Position.X = .Position.X + Velocity.X .Position.Y = .Position.Y + Velocity.Y Distance = Sqr(Vec.X * Vec.X + Vec.Y * Vec.Y) If Int(Distance) <= 0 Then .Current_Path = .Current_Path - 1 If .Current_Path <= 0 Then .Current_Path = 0 End If End If If (.Center_Coordinates.X = Prey.Center_Coordinates.X And .Center_Coordinates.Y = Prey.Center_Coordinates.Y) Then Exit Sub End If End If Else Clear_AStar Map End If End With End Sub 

However I ran into another problem. I only have AStar fire whenever the sprite moves to a new tile coordinate or the player moves to a new coordinate, and when they do, it clears the astar list and resets everything so a new path can be made. When the player does nothing its fine. But when the player moves to a new coordinate as the monsters moving, it causes the monster to get jittery, cause the astar list was cleared as the monster was trying to move to that next tile, and instead is trying to move to the same tile its already on, rather than the next tile. Here's the AStar function I currently have:

 Public Sub AStar_Find_Path(Map As Map_Type, Predator As Sprite_Type, Prey As Sprite_Type) Dim Parent As Vector Dim Current As Vector Dim tempCost As Long Dim Walkable As Boolean Dim Temp As Vector, Temp2 As Vector Dim Current_Node As Long If Predator.Compute_AStar_Enabled = True Or Prey.Compute_AStar_Enabled = True Then If Prey.Coordinates.X < 0 Or Prey.Coordinates.Y < 0 Or Prey.Coordinates.X > (Map.Width - 1) Or Prey.Coordinates.Y > (Map.Height - 1) Then Exit Function If Predator.Coordinates.X < 0 Or Predator.Coordinates.Y < 0 Or Predator.Coordinates.X > (Map.Width - 1) Or Predator.Coordinates.Y > (Map.Height - 1) Then Exit Function If Prey.Center_Coordinates.X < 0 Or Prey.Center_Coordinates.Y < 0 Or Prey.Center_Coordinates.X > (Map.Width - 1) Or Prey.Center_Coordinates.Y > (Map.Height - 1) Then Exit Function If Predator.Center_Coordinates.X < 0 Or Predator.Center_Coordinates.Y < 0 Or Predator.Center_Coordinates.X > (Map.Width - 1) Or Predator.Center_Coordinates.Y > (Map.Height - 1) Then Exit Function 'Make sure the starting point and ending point are not the same If (Predator.Center_Coordinates.X = Prey.Center_Coordinates.X) And (Predator.Center_Coordinates.Y = Prey.Center_Coordinates.Y) Then Exit Function If Map.Collision_Map.Response(Predator.Coordinates.X, Predator.Coordinates.Y) = COLLISION_WALL Then Exit Function If Map.Collision_Map.Response(Prey.Coordinates.X, Prey.Coordinates.Y) = COLLISION_WALL Then Exit Function 'Set the flags Predator.Path_Found = False Predator.Path_Hunt = True 'Put the starting point on the open list Predator.Nodes(Predator.Center_Coordinates.X, Predator.Center_Coordinates.Y).OCList = Opened Add Predator, 0, Predator.Center_Coordinates.X, Predator.Center_Coordinates.Y 'Find the children Do While Predator.Path_Hunt If Predator.Size_Of_Heap <> 0 Then 'Get the parent node Parent.X = Predator.Heap(1).X Parent.Y = Predator.Heap(1).Y 'Remove the root Predator.Nodes(Parent.X, Parent.Y).OCList = Closed Remove_Root Predator 'Find the available children to add to the open list For Current.Y = (Parent.Y - 1) To (Parent.Y + 1) For Current.X = (Parent.X - 1) To (Parent.X + 1) 'Make sure we are not out of bounds If Current.X >= 0 And Current.X <= Map.Width - 1 And Current.Y >= 0 And Current.Y <= Map.Height - 1 Then 'Make sure it's not on the closed list If Predator.Nodes(Current.X, Current.Y).OCList <> Closed Then 'Make sure no wall If Map.Collision_Map.Response(Current.X, Current.Y) = COLLISION_NONE Then 'Don't cut across corners Walkable = True If Current.X = Parent.X - 1 Then If Current.Y = Parent.Y - 1 Then If Map.Collision_Map.Response(Parent.X - 1, Parent.Y) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X, Parent.Y - 1) = COLLISION_WALL Then Walkable = False ElseIf Current.Y = Parent.Y + 1 Then If Map.Collision_Map.Response(Parent.X, Parent.Y + 1) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X - 1, Parent.Y) = COLLISION_WALL Then Walkable = False End If ElseIf Current.X = Parent.X + 1 Then If Current.Y = Parent.Y - 1 Then If Map.Collision_Map.Response(Parent.X, Parent.Y - 1) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X + 1, Parent.Y) = COLLISION_WALL Then Walkable = False ElseIf Current.Y = Parent.Y + 1 Then If Map.Collision_Map.Response(Parent.X + 1, Parent.Y) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X, Parent.Y + 1) = COLLISION_WALL Then Walkable = False End If End If 'If we can move this way If Walkable = True Then If Predator.Nodes(Current.X, Current.Y).OCList <> Opened Then 'Calculate the G If Math.Abs(Current.X - Parent.X) = 1 And Math.Abs(Current.Y - Parent.Y) = 1 Then Predator.Nodes(Current.X, Current.Y).G = Predator.Nodes(Parent.X, Parent.Y).G + 14 Else Predator.Nodes(Current.X, Current.Y).G = Predator.Nodes(Parent.X, Parent.Y).G + 10 End If 'Calculate the H Predator.Nodes(Current.X, Current.Y).H = 10 * (Math.Abs(Current.X - Prey.Center_Coordinates.X) + Math.Abs(Current.Y - Prey.Center_Coordinates.Y)) Predator.Nodes(Current.X, Current.Y).F = (Predator.Nodes(Current.X, Current.Y).G + Predator.Nodes(Current.X, Current.Y).H) 'Add the parent value Predator.Nodes(Current.X, Current.Y).X = Parent.X Predator.Nodes(Current.X, Current.Y).Y = Parent.Y 'Add the item to the heap Add Predator, Predator.Nodes(Current.X, Current.Y).F, Current.X, Current.Y 'Add the item to the open list Predator.Nodes(Current.X, Current.Y).OCList = Opened Else 'We will check for better value Dim AddedG As Long If Math.Abs(Current.X - Parent.X) = COLLISION_WALL And Math.Abs(Current.Y - Parent.Y) = COLLISION_WALL Then AddedG = 14 Else AddedG = 10 End If tempCost = Predator.Nodes(Parent.X, Parent.Y).G + AddedG If tempCost < Predator.Nodes(Current.X, Current.Y).G Then Predator.Nodes(Current.X, Current.Y).G = tempCost Predator.Nodes(Current.X, Current.Y).X = Parent.X Predator.Nodes(Current.X, Current.Y).Y = Parent.Y If Predator.Nodes(Current.X, Current.Y).OCList = Opened Then Dim NewCost As Long: NewCost = Predator.Nodes(Current.X, Current.Y).H + Predator.Nodes(Current.X, Current.Y).G Add Predator, NewCost, Current.X, Current.Y End If End If End If End If End If End If End If Next Current.X Next Current.Y Else Predator.Path_Found = False Predator.Path_Hunt = False 'MsgBox "Path Not Found", vbExclamation 'Instead of a message box, you could have the run back where it originated instead or not move at all. Exit Function End If 'If we find a path If Predator.Nodes(Prey.Center_Coordinates.X, Prey.Center_Coordinates.Y).OCList = Opened Then Predator.Path_Found = True Predator.Path_Hunt = False 'MsgBox "path found" End If Loop If Predator.Path_Found Then Temp.X = Prey.Center_Coordinates.X Temp.Y = Prey.Center_Coordinates.Y Do While True ReDim Preserve Predator.AStar_Path(Current_Node) As Vector Temp2.X = Predator.Nodes(Temp.X, Temp.Y).X Temp2.Y = Predator.Nodes(Temp.X, Temp.Y).Y Predator.AStar_Path(Current_Node).X = (Temp.X * TILE_SIZE) + (TILE_SIZE / 2) Predator.AStar_Path(Current_Node).Y = (Temp.Y * TILE_SIZE) + (TILE_SIZE / 2) Predator.Current_Path = Current_Node Current_Node = Current_Node + 1 Predator.Length_Of_AStar_Path = Current_Node If Temp.X = Predator.Center_Coordinates.X And Temp.Y = Predator.Center_Coordinates.Y Then Exit Do Temp.X = Temp2.X Temp.Y = Temp2.Y Loop If Prey.Compute_AStar_Enabled = True Then Predator.Current_Path = Predator.Current_Path - 1 End If End If End If End Sub 

I'm thinking my solution to that problem is this located at the end of the sub:

If Prey.Compute_AStar_Enabled = True Then
Predator.Current_Path = Predator.Current_Path - 1
End If

Although better, it still does it once in awhile. I feel I shouldn't be doing that. Any bright ideas?

Share on other sites
You don't "test" to see if your edges go through walls, you design the edges that way before hand. I really am wondering how it was that you constructed your map.You can't just have connectivity between any two pairs of nodes on the map. It doesn't work that way.

Perhaps a screenshot of what you are trying to accomplish?

Share on other sites
Well the edges don't go through the walls anyways. See for yourself. It consistantly goes to each dot when moving. Right now I have it stationary for snapshot purposes.. Even if there were open spaces enough for the monster (red) to go diagonal ,the edge still won't go through any walls.

Up above where I had the AStar_Find_Path sub source code, has this:

 'Don't cut across corners Walkable = True If Current.X = Parent.X - 1 Then If Current.Y = Parent.Y - 1 Then If Map.Collision_Map.Response(Parent.X - 1, Parent.Y) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X, Parent.Y - 1) = COLLISION_WALL Then Walkable = False ElseIf Current.Y = Parent.Y + 1 Then If Map.Collision_Map.Response(Parent.X, Parent.Y + 1) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X - 1, Parent.Y) = COLLISION_WALL Then Walkable = False End If ElseIf Current.X = Parent.X + 1 Then If Current.Y = Parent.Y - 1 Then If Map.Collision_Map.Response(Parent.X, Parent.Y - 1) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X + 1, Parent.Y) = COLLISION_WALL Then Walkable = False ElseIf Current.Y = Parent.Y + 1 Then If Map.Collision_Map.Response(Parent.X + 1, Parent.Y) = COLLISION_WALL Or Map.Collision_Map.Response(Parent.X, Parent.Y + 1) = COLLISION_WALL Then Walkable = False End If End If 

I believe this was the edge thing you were talking about so it was already done. Right now my only issue is when the player is moving as the sprites moving, it resets the list when it reaches a new coordinate as the sprite is trying to head to the next tile, forcing the sprite to bounce back to the tile its already at one in awhile.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633704
• Total Posts
3013460
×