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


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>.

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.

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

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?

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

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.

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?

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?

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.