Jump to content
  • Advertisement
Sign in to follow this  
Dandz

Trouble with A* Pathfinding

This topic is 2954 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

So A* is always supposed to give the shortest route, which makes it pretty clear i've done something wrong here. The paths always get to the destination and go around barriers, but they often take an arc shape instead of a straight line. For instance if they could merely move the right, they will always move diagonally up and right first and then diagonally down and right. I added penalties for direction changes to no change. I tried changing the holistic from manhattan to a straight line but that didn't help either. Could someone look as this and tell me what they think might be the problem?

[source = vb.net]
Public Function Pathfind(ByVal destination As Point, ByVal start As Point) As Integer
Dim x1, y1, x2, y2, x3, y3 As Integer
Dim Openlist As List(Of map) = New List(Of map)
Dim closedlist As List(Of map) = New List(Of map)
Dim path As List(Of map) = New List(Of map)
Dim currentnode As map
Dim completed As Boolean
Dim failed As New map(50, 50, 50)
Dim fail As List(Of map) = New List(Of map)
Dim dirpenalty As Boolean = False
Dim currentdir As Integer
Dim olddir As Integer
x1 = destination.X \ nodespacing
x2 = start.X \ nodespacing
y1 = destination.Y \ nodespacing
y2 = start.Y \ nodespacing
Openlist.Add(grid(x2, y2))
x3 = x2
y3 = y2
fail.Add(failed)
While Not Openlist.Contains(grid(x1, y1)) And Not Openlist.Count = 0 'Runs until destination is reached
Openlist.Sort(AddressOf sortfscore) 'Sorts the list according to fscore
currentnode = Openlist.First()
closedlist.Add(currentnode) 'adds best fscore to the closed list, removes from the openlist
Openlist.Remove(currentnode)
x2 = currentnode.x \ nodespacing
y2 = currentnode.y \ nodespacing
If x2 + 1 < xbound And y2 < ybound And x2 + 1 > -1 And y2 > -1 Then 'Ignores new node if its outside grid bounds
If (Not closedlist.Contains(grid(x2 + 1, y2))) And grid(x2 + 1, y2).check_collision(player, screen.barrierlist) = 0 Then 'Ignores node if its a wall or if its in closedlist
currentdir = 3
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2 + 1, y2)) Then
Openlist.Add(grid(x2 + 1, y2))
grid(x2 + 1, y2).parent = currentnode
grid(x2 + 1, y2).Fscore = getfscore(grid(x2 + 1, y2), destination, False, dirpenalty)
Else
grid(x2 + 1, y2).parent = currentnode
grid(x2 + 1, y2).Fscore = getfscore(grid(x2 + 1, y2), destination, False, dirpenalty)
End If
End If
End If
If x2 - 1 < xbound And y2 < ybound And x2 - 1 > -1 And y2 > -1 Then
If (Not closedlist.Contains(grid(x2 - 1, y2))) And grid(x2 - 1, y2).check_collision(player, screen.barrierlist) = 0 Then
currentdir = 2
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2 - 1, y2)) Then
Openlist.Add(grid(x2 - 1, y2))
grid(x2 - 1, y2).parent = currentnode
grid(x2 - 1, y2).Fscore = getfscore(grid(x2 - 1, y2), destination, False, dirpenalty)
Else
grid(x2 - 1, y2).parent = currentnode
grid(x2 - 1, y2).Fscore = getfscore(grid(x2 - 1, y2), destination, False, dirpenalty)
End If
End If
End If
If x2 < xbound And y2 + 1 < ybound And x2 > -1 And y2 + 1 > -1 Then
If (Not closedlist.Contains(grid(x2, y2 + 1))) And grid(x2, y2 + 1).check_collision(player, screen.barrierlist) = 0 Then
currentdir = 0
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2, y2 + 1)) Then
Openlist.Add(grid(x2, y2 + 1))
grid(x2, y2 + 1).parent = currentnode
grid(x2, y2 + 1).Fscore = getfscore(grid(x2, y2 + 1), destination, False, dirpenalty)
Else
grid(x2, y2 + 1).parent = currentnode
grid(x2, y2 + 1).Fscore = getfscore(grid(x2, y2 + 1), destination, False, dirpenalty)
End If
End If
End If
If x2 < xbound And y2 - 1 < ybound And x2 > -1 And y2 - 1 > -1 Then
If (Not closedlist.Contains(grid(x2, y2 - 1))) And grid(x2, y2 - 1).check_collision(player, screen.barrierlist) = 0 Then
currentdir = 1
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2, y2 - 1)) Then
Openlist.Add(grid(x2, y2 - 1))
grid(x2, y2 - 1).parent = currentnode
grid(x2, y2 - 1).Fscore = getfscore(grid(x2, y2 - 1), destination, False, dirpenalty)
Else
grid(x2, y2 - 1).parent = currentnode
grid(x2, y2 - 1).Fscore = getfscore(grid(x2, y2 - 1), destination, False, dirpenalty)
End If
End If
End If
If x2 + 1 < xbound And y2 + 1 < ybound And x2 + 1 > -1 And y2 + 1 > -1 Then 'Ignores new node if its outside grid bounds
If (Not closedlist.Contains(grid(x2 + 1, y2 + 1))) And grid(x2 + 1, y2 + 1).check_collision(player, screen.barrierlist) = 0 Then 'Ignores node if its a wall or if its in closedlist
currentdir = 4
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2 + 1, y2 + 1)) Then
Openlist.Add(grid(x2 + 1, y2 + 1))
grid(x2 + 1, y2 + 1).parent = currentnode
grid(x2 + 1, y2 + 1).Fscore = getfscore(grid(x2 + 1, y2 + 1), destination, True, dirpenalty)
Else
grid(x2 + 1, y2 + 1).parent = currentnode
grid(x2 + 1, y2 + 1).Fscore = getfscore(grid(x2 + 1, y2 + 1), destination, True, dirpenalty)
End If
End If
End If
If x2 - 1 < xbound And y2 + 1 < ybound And x2 - 1 > -1 And y2 + 1 > -1 Then 'Ignores new node if its outside grid bounds
If (Not closedlist.Contains(grid(x2 - 1, y2 + 1))) And grid(x2 - 1, y2 + 1).check_collision(player, screen.barrierlist) = 0 Then 'Ignores node if its a wall or if its in closedlist
currentdir = 5
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2 - 1, y2 + 1)) Then
Openlist.Add(grid(x2 - 1, y2 + 1))
grid(x2 - 1, y2 + 1).parent = currentnode
grid(x2 - 1, y2 + 1).Fscore = getfscore(grid(x2 - 1, y2 + 1), destination, True, dirpenalty)
Else
grid(x2 - 1, y2 + 1).parent = currentnode
grid(x2 - 1, y2 + 1).Fscore = getfscore(grid(x2 - 1, y2 + 1), destination, True, dirpenalty)
End If
End If
End If
If x2 + 1 < xbound And y2 - 1 < ybound And x2 + 1 > -1 And y2 - 1 > -1 Then 'Ignores new node if its outside grid bounds
If (Not closedlist.Contains(grid(x2 + 1, y2 - 1))) And grid(x2 + 1, y2 - 1).check_collision(player, screen.barrierlist) = 0 Then 'Ignores node if its a wall or if its in closedlist
currentdir = 6
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2 + 1, y2 - 1)) Then
Openlist.Add(grid(x2 + 1, y2 - 1))
grid(x2 + 1, y2 - 1).parent = currentnode
grid(x2 + 1, y2 - 1).Fscore = getfscore(grid(x2 + 1, y2 - 1), destination, True, dirpenalty)
Else
grid(x2 + 1, y2 - 1).parent = currentnode
grid(x2 + 1, y2 - 1).Fscore = getfscore(grid(x2 + 1, y2 - 1), destination, True, dirpenalty)
End If
End If
End If
If x2 - 1 < xbound And y2 - 1 < ybound And x2 - 1 > -1 And y2 - 1 > -1 Then 'Ignores new node if its outside grid bounds
If (Not closedlist.Contains(grid(x2 - 1, y2 - 1))) And grid(x2 - 1, y2 - 1).check_collision(player, screen.barrierlist) = 0 Then 'Ignores node if its a wall or if its in closedlist
currentdir = 7
If currentnode IsNot grid(x3, y3) Then
If currentnode.x < currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 3
ElseIf currentnode.x > currentnode.parent.x And currentnode.y = currentnode.parent.y Then
olddir = 2
ElseIf currentnode.y < currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 1
ElseIf currentnode.y > currentnode.parent.y And currentnode.x = currentnode.parent.x Then
olddir = 0
ElseIf currentnode.x > currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 5
ElseIf currentnode.x < currentnode.parent.x And currentnode.y > currentnode.parent.y Then
olddir = 4
ElseIf currentnode.x > currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 7
ElseIf currentnode.x < currentnode.parent.x And currentnode.y < currentnode.parent.y Then
olddir = 6
End If
If currentdir = olddir Then
dirpenalty = False
Else
dirpenalty = True
End If
Else
dirpenalty = False
End If
If Not Openlist.Contains(grid(x2 - 1, y2 - 1)) Then
Openlist.Add(grid(x2 - 1, y2 - 1))
grid(x2 - 1, y2 - 1).parent = currentnode
grid(x2 - 1, y2 - 1).Fscore = getfscore(grid(x2 - 1, y2 - 1), destination, True, dirpenalty)
Else
grid(x2 - 1, y2 - 1).parent = currentnode
grid(x2 - 1, y2 - 1).Fscore = getfscore(grid(x2 - 1, y2 - 1), destination, True, dirpenalty)
End If
End If
End If
End While

If Openlist.Contains(grid(x1, y1)) And closedlist.Count <> 0 Then
completed = True
Else
completed = False
End If
Openlist.Clear()
closedlist.Clear()
path.Add(grid(x1, y1))
If completed = True Then
currentnode = grid(x1, y1)
While currentnode IsNot grid(x3, y3)
path.Add(currentnode.parent)
currentnode = currentnode.parent
End While

Else
Pathfind = 5
End If
Dim currentindex As Integer = 0
Dim length As Integer
Dim z As Integer
pathdir.Clear()
length = path.Count - 1
For z = length To 1 Step -1
If path(z).x < path(z - 1).x And path(z).y = path(z - 1).y Then
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 3
ElseIf path(z).x > path(z - 1).x And path(z).y = path(z - 1).y Then
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 2
ElseIf path(z).y < path(z - 1).y And path(z).x = path(z - 1).x Then
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 1
ElseIf path(z).y > path(z - 1).y And path(z).x = path(z - 1).x Then
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 0
ElseIf path(z).x > path(z - 1).x And path(z).y > path(z - 1).y Then
'leftup
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 5
ElseIf path(z).x < path(z - 1).x And path(z).y > path(z - 1).y Then
'rightup
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 4
ElseIf path(z).x > path(z - 1).x And path(z).y < path(z - 1).y Then
'leftdown
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 7
ElseIf path(z).x < path(z - 1).x And path(z).y < path(z - 1).y Then
'rightdown
grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction = 6
End If

pathdir.Add(grid(path(z).x \ nodespacing, path(z).y \ nodespacing).direction)

Next
If Pathfind <> 5 Then
Pathfind = pathdir.First
End If
End Function
Public Function getfscore(ByVal node As map, ByVal destination As Point, ByVal diag As Boolean, ByVal dirpenalty As Boolean) As Single
Dim x1, y1, x2, y2, sumx, sumy, tiebreaker, resist, heuristic As Single
x1 = destination.X \ nodespacing
y1 = destination.Y \ nodespacing
x2 = node.x \ nodespacing
y2 = node.x \ nodespacing
If diag = True Then
resist = 14
Else
resist = 10
End If
If dirpenalty = True Then
resist = resist + 1000
End If
sumx = x1 - x2
If sumx < 0 Then
sumx = -sumx
End If
sumy = y1 - y2
If sumy < 0 Then
sumy = -sumy
End If
heuristic = CType((sumx ^ 2 + sumy ^ 2) ^ (0.5), Single)
tiebreaker = CType((node.x * destination.Y - destination.X * node.y), Single) * CType(0.001, Single)
If tiebreaker < 0 Then
tiebreaker = -tiebreaker
End If
getfscore = resist + heuristic + tiebreaker
End Function

Private Shared Function sortfscore(ByVal x As map, ByVal y As map) As Integer
Return x.Fscore.CompareTo(y.Fscore)
End Function




[Edited by - Dandz on August 21, 2010 9:43:50 PM]

Share this post


Link to post
Share on other sites
Advertisement
I don't really have time to look through all that code (seems like a lot for a straightforward A* execution) but I will point out that A* is only guaranteed to produce an optimal path if it uses an admissible heuristic, which, if diagonal movement is allowed, neither straight line distance nor Manhattan distance are.

Share this post


Link to post
Share on other sites
I figured it out, sorry this is my first game. I misread what G represented. I thought it was the difficulty value of this particular move rather than the sum of it and all its parents. Got it working now :D

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!