GM:S 1.4 Messy A* Pathfinding

Discussion in 'Programming' started by Spazz, Mar 29, 2017.

Tags:
  1. Spazz

    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: Mar 29, 2017
  2. Lycanphoenix

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

    Spazz Guest

    Hm. The code is actually simple, i failed somewhere but i can't figure out where or how
     
  4. Lycanphoenix

    Lycanphoenix Guest

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

    Xer0botXer0 Member

    Joined:
    Jun 29, 2016
    Posts:
    668
    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.
     
    Spazz and Lycanphoenix like this.
  6. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,861
    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.
     
  7. Lycanphoenix

    Lycanphoenix Guest

    The image isn't animated, from the looks of it. Just a regular screenshot.
     
  8. Spazz

    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):
    [​IMG]
    With Diagonals(A nightmare):
    [​IMG]
    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: Mar 29, 2017
  9. Spazz

    Spazz Guest

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

    ph101 Member

    Joined:
    Jun 20, 2016
    Posts:
    415
    Spazz, surely we would need to see the code to try and find the problem?
     
  11. FrostyCat

    FrostyCat Member

    Joined:
    Jun 26, 2016
    Posts:
    4,313
    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.
     
  12. Spazz

    Spazz Guest

    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
    Are there any better alternatives to Manhattan? Paths like those would look ugly in-game.
     
  13. FrostyCat

    FrostyCat Member

    Joined:
    Jun 26, 2016
    Posts:
    4,313
    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?
     
  14. Spazz

    Spazz Guest

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

    Spazz Guest

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

    FrostyCat Member

    Joined:
    Jun 26, 2016
    Posts:
    4,313
    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.
     
  17. Spazz

    Spazz Guest

    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: Mar 30, 2017

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice