Legacy GM Messy A* Pathfinding

S

Spazz

Guest
Hi :)
I'm trying to implement A* pathfinding to my game(I can't use the built-in pathfinding system because i want to have full control of the routing system)
But i'm getting messy results when trying to get a path around a wall:
AAMess.png
The red circles are the Open nodes, with their heuristic values above them
The blue circles are the closed nodes with their order above them
The black circle is the target and the big green circle is the player
As you can see, it struggles a lot before finally going around the wall... I don't know what's wrong :/
I'm using Manhattan for heuristic. I will send the scripts if it's needed.
It's 8-directional, diagonals, horizontal and vertical
 
Last edited by a moderator:
L

Lycanphoenix

Guest
I'm afraid I don't know much about how this actually works, but my guess is that you might have over-built it. You should try something simpler. You could also try adding more Open Nodes, I'm noticing some gaps.
 
S

Spazz

Guest
I'm afraid I don't know much about how this actually works, but my guess is that you might have over-built it. You should try something simpler.
Hm. The code is actually simple, i failed somewhere but i can't figure out where or how
 
L

Lycanphoenix

Guest
Not the code. I meant make the path itself something easier to follow.
 

NightFrost

Member
That looks a bit odd, because A star should be able to figure that shorter path goes over the wall instead of beneath it. Now, I've always used the inbuilt system instead of coding my own, so I'm going by memory on what I've read about the algo... We don't see there how you solve the F value of a node (heuristic + movement cost) and how you handle it. Did you use a priority queue for your list? That's important so the lowest F value node always gets picked for processing.
 
L

Lycanphoenix

Guest
Is this image animated ? If it is then this work pc is crap and I cant see it.
If not please upload an animated one so we can see what's wrong and how this works.
The image isn't animated, from the looks of it. Just a regular screenshot.
 
S

Spazz

Guest
The heuristic gets calculated from the X Distance and the Y Distance from the tile to the destination.
So if the tile X and Y are 0 and the destination X is 64 and Y is 32 it will return 3(because it's using a 32x32 grid). Movement cost is 10 for any tiles.
Without Diagonals(It's a lot better, still not perfect):

With Diagonals(A nightmare):

I tried adding a cost of 10 to the vertical and horizontal tiles and 14 to the diagonals, and it gives almost the same result as not using diagonals.
The path is already pretty easy to follow.
EDIT:
Here's a screenshot of the non-diagonal setup messing up:
nodiagms.png
I guess this has to do with the heuristic calculation? I'm not sure...
 
Last edited by a moderator:
S

Spazz

Guest
It actually makes sense why it struggles so much when you look closely, but i can't find a fix for it.
 
P

ph101

Guest
Spazz, surely we would need to see the code to try and find the problem?
 

FrostyCat

Redemption Seeker
If you knew the heuristic is Manhattan, this should not come as a surprise to you.

A* weighs boundary nodes by the known distance to them plus the heuristic distance to the target. It's easy to deduce that at the early stages of evaluating your input, the nodes near the top have the lowest Manhattan distance to the target. They are being evaluated first as prescribed by the algorithm.

As long as it finds a valid path, it's fine. It's naive to expect every input to be fast.
 
S

Spazz

Guest
Spazz, surely we would need to see the code to try and find the problem?
The code is messy because it's something for Unity, but i'm using GameMaker to make a prototype first. So it's lazy and uncommented:
Global Left Mouse Pressed(Player Object):
Code:
nsteps = 0
pathset = true
destx = mouse_x
desty = mouse_y
gridx = round(x / global.gridsize)  * global.gridsize
gridy = round(y / global.gridsize)  * global.gridsize
gdestx = round(destx / global.gridsize)  * global.gridsize
gdesty = round(desty / global.gridsize)  * global.gridsize
if collision_circle(gdestx,gdesty,global.pradius,OWall,true,false)
{
    pathset = false
    exit
}
cx = gridx
cy = gridy

openx = ds_list_create()
openy = ds_list_create()
openf = ds_list_create()
openpx = ds_list_create()
openpy = ds_list_create()
closedx = ds_list_create()
closedy = ds_list_create()
donerouting = false
while (donerouting == false)
{
    if nsteps >= maxsteps
    {
        show_message("Reached max steps!")
        donerouting = true
        break;
    }
    nsteps += 1
    ds_list_add(closedx,cx)
    ds_list_add(closedy,cy)
    if cx == gdestx and cy == gdesty
    {
        donerouting = true
        show_debug_message("Success")
        break;
    }
    //Adjacents
    putx = cx-global.gridsize
    puty = cy
    AddOpen(putx,puty,vercost)
    putx = cx+global.gridsize
    puty = cy
    AddOpen(putx,puty,vercost)
    putx = cx
    puty = cy+global.gridsize
    AddOpen(putx,puty,vercost)
    putx = cx
    puty = cy-global.gridsize
    AddOpen(putx,puty,vercost)


    //Diagonals
    if allowdiag == true
    {
    putx = cx+global.gridsize
    puty = cy+global.gridsize
    AddOpen(putx,puty,diagcost)
putx = cx+global.gridsize
puty = cy-global.gridsize
AddOpen(putx,puty,diagcost)
putx = cx-global.gridsize
puty = cy-global.gridsize
AddOpen(putx,puty,diagcost)
putx = cx-global.gridsize
puty = cy+global.gridsize
AddOpen(putx,puty,diagcost)
}
lowestf = 0
lowfset = false
lowestid = 0
for(i=0;i<ds_list_size(openx);i+=1)
{
    thisf = ds_list_find_value(openf,i)
    thispx = ds_list_find_value(openx,i)
    thispy = ds_list_find_value(openy,i)
    if lowfset == false
    {
       
        if allowdiag == false
        {
            if (thispx == cx-global.gridsize and thispy == cy) or (thispx == cx+global.gridsize and thispy == cy) or (thispx == cx and thispy == cy+global.gridsize) or (thispx == cx and thispy == cy-global.gridsize)
            {
                lowfset = true
                lowestf = thisf
                lowestid = i
            }
        }
        else
        {
            if (thispx == cx or thispx == cx-global.gridsize or thispx == cx+global.gridsize) and (thispy == cy or thispy == cy-global.gridsize or thispy == cy+global.gridsize)
            {
                lowfset = true
                lowestf = thisf
                lowestid = i
            }
        }
    }
    else
    {
        if thisf <= lowestf
        {
        if allowdiag == false
        {
            if (thispx == cx-global.gridsize and thispy == cy) or (thispx == cx+global.gridsize and thispy == cy) or (thispx == cx and thispy == cy+global.gridsize) or (thispx == cx and thispy == cy-global.gridsize)
            {
                lowfset = true
                lowestf = thisf
                lowestid = i
            }
        }
        else
        {
            if (thispx == cx or thispx == cx-global.gridsize or thispx == cx+global.gridsize) and (thispy == cy or thispy == cy-global.gridsize or thispy == cy+global.gridsize)
            {
                lowfset = true
                lowestf = thisf
                lowestid = i
            }
        }
        }
    }
}
if lowfset == false or ds_list_size(openx) == 0
{
    show_message("Routing failed")
    ds_list_clear(openx)
    ds_list_clear(openy)
    ds_list_clear(openf)
    ds_list_clear(closedx)
    ds_list_clear(closedy)
    ds_list_clear(openpx)
    ds_list_clear(openpy)
    pathset = false
    break;
}
else
{
    if lowfset == true
    {
        cx = ds_list_find_value(openx,lowestid)
        cy = ds_list_find_value(openy,lowestid)
        ds_list_delete(openx,lowestid)
        ds_list_delete(openy,lowestid)
        ds_list_delete(openf,lowestid)
    }
}
}
AddOpen(Script):
Code:
/// AddOpen(x,y,f)
cando = true
if collision_circle(argument0,argument1,global.pradius,OWall,true,false)
{
    cando = false
}
for(i=0;i<ds_list_size(closedx);i+=1)
{
    if ds_list_find_value(closedx,i) == argument0 and ds_list_find_value(closedy,i) == argument1
    cando = false
}
for(i=0;i<ds_list_size(openx);i+=1)
{
    if ds_list_find_value(openx,i) == argument0 and ds_list_find_value(openy,i) == argument1
    {
        cando = false
        ds_list_replace(openf,i,CalculateF(argument0,argument1,gdestx,gdesty)+argument2)
    }
}
if cando == true
{
    ds_list_add(openx,argument0)
    ds_list_add(openy,argument1)
    ds_list_add(openf,CalculateF(argument0,argument1,gdestx,gdesty)+argument2)
    ds_list_add(openpx,cx)
    ds_list_add(openpy,cy)
}
CalculateF(Script):
Code:
/// CalculateF(x,y,tox,toy)
hcost = 0
cux = argument0
cuy = argument1
toy = argument3
tox = argument2
/*
if calctype == 0
{
while(cuy != toy)
{
    if toy > cuy
    cuy += global.gridsize
    if toy < cuy
    cuy -= global.gridsize
    hcost += 1
}
while(cux != tox)
{
    if tox > cux
    cux += global.gridsize
    if tox < cux
    cux -= global.gridsize
    hcost += 1
}
}
else
{
while(cux != tox or cuy != toy)
{
    if tox > cux
    cux += global.gridsize
    if tox < cux
    cux -= global.gridsize
    if toy > cuy
    cuy += global.gridsize
    if toy < cuy
    cuy -= global.gridsize
    hcost += 1
}
}
*/
if calctype == 0
{
xDistance = abs(argument0-tox)
yDistance = abs(argument1-toy)
if xDistance > yDistance
     hcost = 14*yDistance + 10*(xDistance-yDistance)
else
     hcost = 14*xDistance + 10*(yDistance-xDistance)
}
else
{
    hcost = 10*(abs(argument0-tox) + abs(argument1-toy))
}
return hcost
If you knew the heuristic is Manhattan, this should not come as a surprise to you.

A* weighs boundary nodes by the known distance to them plus the heuristic distance to the target. It's easy to deduce that at the early stages of evaluating your input, the nodes near the top have the lowest Manhattan distance to the target. They are being evaluated first as prescribed by the algorithm.

As long as it finds a valid path, it's fine. It's naive to expect every input to be fast.
Are there any better alternatives to Manhattan? Paths like those would look ugly in-game.
 

FrostyCat

Redemption Seeker
Are there any better alternatives to Manhattan? Paths like those would look ugly in-game.
Manhattan is fine for your purposes, the problem with your drawing is that it shows the order in which nodes are explored (wrong) as opposed to the actual weight of each individual node (right). What does the path look like if you take the best known next node from each node in sequence?
 
S

Spazz

Guest
Manhattan is fine for your purposes, the problem with your drawing is that it shows the order in which nodes are explored (wrong) as opposed to the actual weight of each individual node (right). What does the path look like if you take the best known next node from each node in sequence?
nodedraw.png
There. It's displaying the node weights instead of order in the closed ones. I'm using a much smaller font because i'm using a different heuristic now:
Code:
xDistance = abs(NodeX-TargetX)
yDistance = abs(NodeY-TargetY)
if xDistance > yDistance
     hcost = 14*yDistance + 10*(xDistance-yDistance)
else
     hcost = 14*xDistance + 10*(yDistance-xDistance)
So, this is how it's supposed to work?
EDIT:
Here's an example with bold font in case you can't see the previous one:
nodraw2.png
 
S

Spazz

Guest
I feel like, somehow, i have to make a path out of the closed ones to delete the zig zagging?
 

FrostyCat

Redemption Seeker
The weights look completely off. I suggest that you start over, this time coding around the actual A* pseudocode as a starting guide.

Also, if you plan on allowing diagonal movement, try using uniform norm instead of Manhattan or that odd-looking heuristic you tried later. You need a heuristic that never over-estimates the true distance to the target in order to get the optimal path.
 
S

Spazz

Guest
The weights look completely off. I suggest that you start over, this time coding around the actual A* pseudocode as a starting guide.

Also, if you plan on allowing diagonal movement, try using uniform norm instead of Manhattan or that odd-looking heuristic you tried later. You need a heuristic that never over-estimates the true distance to the target in order to get the optimal path.
Yeah, it's the first time i try this. Thanks for the links, i'll try to make it right.
There's a little question i have(Line 33 of the Wikipedia pseudocode):
Code:
            tentative_gScore := gScore[current] + dist_between(current, neighbor)
In dist_between, should i use a normal uniform norm distance or a heuristic?
 
Last edited by a moderator:
Top