# Help With A* Pathfinding

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

## 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 on other sites
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 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 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633669
• Total Posts
3013259
×