My A* pathfinding implementation not giving expected results

Question

My AS3 A* pathfinding implementation sometimes doesn't returns the most efficient route, rather like this:

[E][X][ ][ ][ ]
[.][X][.][.][ ]
[ ][.][ ][i][S]

(where . is the node walked, and X is walls. S = start, E = end, i = my imaginary marker)

The problem: i should have a total score of (distance to end) 30 + (distance from start) 10 = 40, while the tile above i should have a total score of (distance to end) 40 + (distance from start) 14 = 54. Why is 54 being picked instead of 40, I don't know - I use this to find the node with lowest total score on the open list:

        var lowestTScore:int = 10000;
        var pointerTo:PathNode;
        for each (var Cur:PathNode in openList) {
            //loops through each node in openlist and finds the one with lowest total score.
            if (Cur.distS + Cur.distE < lowestTScore) {
                lowestTScore = Cur.distS + Cur.distE;
                pointerTo = Cur;
            }
        }

(which I can't see any problems with.)

I thought, maybe it's a error with me calculating distance to the end. So I checked my code for that:

theNode.distE = (Math.abs(theNode.xpos - endPts[0]) + Math.abs(theNode.ypos - endPts[1])) * 10;

(which, again I can't see any problems with.)

I'm really stumped on this.

Main.as: http://pastebin.com/ZKQJwY4S PathSearcher:as: http://pastebin.com/KnmWGbQw

(I understand that it is better to post directly the problem code, but I don't know where is the problem code :( Sorry)

Thanks for any help!

apscience · Accepted Answer · 2011-08-11 08:20:15Z

1

Found the problem! I didn't add

    theNode.distS = theNode.parentNode.distS + cost;

when changing parents of theNode. I only changed parentNode, but not the distS score.

answered Aug 11, 2011 at 8:20

apscience

7,28311 gold badges58 silver badges91 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

My A* pathfinding implementation not giving expected results

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related