Jump to content
  • Advertisement
Sign in to follow this  
Dandz

Help With A* Pathfinding

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

EDIT: I realized that method really wouldn't work with anything of a decent size, so i've moved to an actual A* algorithm. I'm not allowing diagonal movement (at least of the entities controlled by this function) and all terrain is equally difficult to move over, so G is zero and thus i only have F (F=G)

Here is the pathfinding routine

[source = "vb"]
Public Function Pathfind(ByVal destination As Point, ByVal start As Point) As Integer
Dim x1, y1, x2, y2 As Integer
Dim Openlist As List(Of map) = New List(Of map)
Dim closedlist As List(Of map) = New List(Of map)
Dim currentnode As map
x1 = destination.X / 50
x2 = start.X / 50
y1 = destination.X / 50
y2 = start.X / 50
Openlist.Add(grid(x1, y1))


While Not closedlist.Contains(grid(x2, y2))
Openlist.Sort(AddressOf sortfscore)
currentnode = Openlist(0)
closedlist.Add(Openlist(0))
Openlist.Remove(Openlist(0))
If currentnode.x / 50 + 1 < xbound And currentnode.y / 50 < ybound And currentnode.x / 50 + 1 > -1 And currentnode.y / 50 > -1 Then
If (Not closedlist.Contains(grid(currentnode.x / 50 + 1, currentnode.y / 50))) And grid(currentnode.x / 50 + 1, currentnode.y / 50).check_collision(player, wall) = 0 Then
If Not Openlist.Contains(grid(currentnode.x / 50 + 1, currentnode.y / 50)) Then
Openlist.Add(grid(currentnode.x / 50 + 1, currentnode.y / 50))
grid(currentnode.x / 50 + 1, currentnode.y / 50).parent = currentnode
grid(currentnode.x / 50 + 1, currentnode.y / 50).Fscore = getfscore(grid(currentnode.x / 50 + 1, currentnode.y / 50), destination)
Else
grid(currentnode.x / 50 + 1, currentnode.y / 50).parent = currentnode
grid(currentnode.x / 50 + 1, currentnode.y / 50).Fscore = getfscore(grid(currentnode.x / 50 + 1, currentnode.y / 50), destination)
End If
End If
End If
If currentnode.x / 50 - 1 < xbound And currentnode.y / 50 < ybound And currentnode.x / 50 - 1 > -1 And currentnode.y / 50 > -1 Then
If (Not closedlist.Contains(grid(currentnode.x / 50 - 1, currentnode.y / 50))) And grid(currentnode.x / 50 - 1, currentnode.y / 50).check_collision(player, wall) = 0 Then
If Not Openlist.Contains(grid(currentnode.x / 50 - 1, currentnode.y / 50)) Then
Openlist.Add(grid(currentnode.x / 50 - 1, currentnode.y / 50))
grid(currentnode.x / 50 - 1, currentnode.y / 50).parent = currentnode
grid(currentnode.x / 50 - 1, currentnode.y / 50).Fscore = getfscore(grid(currentnode.x / 50 - 1, currentnode.y / 50), destination)
Else
grid(currentnode.x / 50 - 1, currentnode.y / 50).parent = currentnode
grid(currentnode.x / 50 - 1, currentnode.y / 50).Fscore = getfscore(grid(currentnode.x / 50 - 1, currentnode.y / 50), destination)
End If
End If
End If
If currentnode.x / 50 < xbound And currentnode.y / 50 + 1 < ybound And currentnode.x / 50 > -1 And currentnode.y / 50 + 1 > -1 Then
If (Not closedlist.Contains(grid(currentnode.x / 50, currentnode.y / 50 + 1))) And grid(currentnode.x / 50, currentnode.y / 50 + 1).check_collision(player, wall) = 0 Then
If Not Openlist.Contains(grid(currentnode.x / 50, currentnode.y / 50 + 1)) Then
Openlist.Add(grid(currentnode.x / 50, currentnode.y / 50 + 1))
grid(currentnode.x / 50, currentnode.y / 50 + 1).parent = currentnode
grid(currentnode.x / 50, currentnode.y / 50 + 1).Fscore = getfscore(grid(currentnode.x / 50, currentnode.y / 50 + 1), destination)
Else
grid(currentnode.x / 50, currentnode.y / 50 + 1).parent = currentnode
grid(currentnode.x / 50, currentnode.y / 50 + 1).Fscore = getfscore(grid(currentnode.x / 50, currentnode.y / 50 + 1), destination)
End If
End If
End If
If currentnode.x / 50 < xbound And currentnode.y / 50 - 1 < ybound And currentnode.x / 50 > -1 And currentnode.y / 50 - 1 > -1 Then
If (Not closedlist.Contains(grid(currentnode.x / 50, currentnode.y / 50 - 1))) And grid(currentnode.x / 50, currentnode.y / 50 - 1).check_collision(player, wall) = 0 Then
If Not Openlist.Contains(grid(currentnode.x / 50, currentnode.y / 50 - 1)) Then
Openlist.Add(grid(currentnode.x / 50, currentnode.y / 50 - 1))
grid(currentnode.x / 50, currentnode.y / 50 - 1).parent = currentnode
grid(currentnode.x / 50, currentnode.y / 50 - 1).Fscore = getfscore(grid(currentnode.x / 50, currentnode.y / 50 - 1), destination)
Else
grid(currentnode.x / 50, currentnode.y / 50 - 1).parent = currentnode
grid(currentnode.x / 50, currentnode.y / 50 - 1).Fscore = getfscore(grid(currentnode.x / 50, currentnode.y / 50 - 1), destination)
End If
End If
End If
End While


End Function



This is the "map" class which defines the nodes being used in the lists:
[source = "vb"]
Public Class map
Public x As Integer
Public y As Integer
Public Fscore As Integer
Public topleft As Point
Public parent As map
Public bottomright As Point
Public Sub New(ByVal x1, ByVal y1, ByVal counter1)
x = x1
y = y1
Fscore = counter1
topleft = New Point(x, y)
bottomright = topleft
End Sub
Public Function check_collision(ByVal entities As Entity, ByVal walll() As barrier) As Integer
For z = 0 To 4
If walll(z).bottomright.Y < topleft.Y Then
check_collision = 0
'Form1.TextBox2.Text = "true"
ElseIf bottomright.Y < walll(z).topleft.Y Then
check_collision = 0
'Form1.TextBox4.Text = "true"
ElseIf walll(z).bottomright.X < topleft.X Then
check_collision = 0
'Form1.TextBox3.Text = "true"
ElseIf bottomright.X < walll(z).topleft.X Then
check_collision = 0
'Form1.TextBox5.Text = "True"
Else
check_collision = 1
z = 5
End If
Next
End Function
End Class



And finally this is what returns the fscore of each node:
[source = "vb"]
Public Function getfscore(ByVal node As map, ByVal destination As Point) As Integer
Dim x1, y1, x2, y2, sumx, sumy As Integer
x1 = destination.X / 50
y1 = destination.Y / 50
x2 = node.x / 50
y2 = node.x / 50
sumx = x1 - x2
If sumx < 0 Then
sumx = -sumx
End If
sumy = y1 - y2
If sumy < 0 Then
sumy = -sumy
End If
getfscore = sumy + sumx
End Function



The problem is i get an out of range exception when trying to set currentnode to the first indexed member of openlist. I'm not sure at how many iterations this happens, but the very fact that the list isn't being populated leads me to believe there is a serious flaw, else the algorithm wouldn't have gotten itself to a point where no nodes would be added. Thanks for the help!

[Edited by - Dandz on July 12, 2010 4:29:19 PM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
i've moved to an actual A* algorithm. [...] all terrain is equally difficult to move over, so G is zero and thus i only have F (F=G)

If you don't have any movement costs, then you don't actually have A*, you'd have a generic greedy best-first search. Not F=G: You have F=H. H for Heuristic - thus it shouldn't be called the 'fscore'. Anyway, you need to track the movement costs, and they should be in the same units as the heuristic. I expect in this case it means each movement costs precisely 1. If you don't do this you won't get optimal paths.

Besides that:

If there is no possible path at all, eventually you'll run out of nodes on the open list. So your algorithm needs to deal with that. The "While Not closedlist.Contains(grid(x2, y2))" bit seems wrong - normally you iterate until the open list is empty, and if you find your solution, bail out at that point. You don't need to put your solution onto the closed list.

Once you've fixed that, if you're finding that it says there is no path when you believe there should be a path, add some logging and double-check that it is doing what you expect. If you use a small grid and output every node that gets added to the open and closed lists then you will probably spot the error quite quickly.

I also suggest cleaning up your code to make bugs easier to spot. Shift the map bounds-checking out into another function - it's not a core part of A* and shouldn't be there among the rest of the algorithm. Similarly, you shouldn't have those masses of divisions by 50 in there. Calculate those values just once and use the calculated value in the equations.

Share this post


Link to post
Share on other sites
Thanks Kyolotan. This here is a really gross bit of code, but i didn't know how else to do it. It assembles the list of nodes in order of the parent structure created. The probably is, after a few calls to pathfind it throws an outofmemory exception

path.Add(grid(x1, y1))
currentnode = grid(x1, y1)
While currentnode.parent IsNot Nothing
path.Add(currentnode.parent)
currentnode = currentnode.parent
End While

Share this post


Link to post
Share on other sites
You probably have a loop in the calculated route, which will make that algorithm run forever, until path gets too big and it crashes.

If you have a loop, this is usually because you didn't correctly discard the cheaper already-visited and already-queued nodes when finding the path in the first place. Alternatively, if you're not discarding such already-visited and already-queued nodes, it's not usually a problem if your path costs are greater than zero, as these paths will never be optimal. (But it means you can't do the usual trick of pretending 1 map location equals 1 node.)

If your path costs are zero or negative, which isn't allowed in A*. After all, if it costs nothing to move from one node to the next, then going from A->B->C is no cheaper than going A->B->A->B->A->B->A->B->A->B->A->B->A->B->A->B->C, and so on. You could end up generating a path like that, and when you trace the parents, B leads to A and A leads back to B.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!