Clever Geek Handbook

My A * pathfinding implementation does not create shortest path

I am making a flash game that requires proper pathfinding. I used the pseudocode in this tutorial and the diagonal heuristic. I haven't followed their code closely. The language is ActionScript 3 and I also use the flashpunk libraries.

My current problem is that the program is creating a path that is clearly not the shortest path. Here is a screenshot showing the problem:

enter image description here

Gray boxes do not intersect, green boxes mark nodes that have been "visited", and blue boxes show the path generated by the algorithm.

It looks like the cost of a diagonal trip is equal to the cost of an off-diagonal trip, despite my attempt to make the diagonal cost higher (1.414).

This is a general implementation of the algorithm.

function solveMaze() {

    // intitialize starting node
    startingNode.g = 0;
    startingNode.h = diagonalHeuristic(startingNode, destinationNode);
    startingNode.f = startingNode.g + startingNode.h;

    // Loop until destination node has been reached.
    while (currentNode != destinationNode) {

        if (openNodes.length == 0) {
            return null;
        }

        // set lowest cost node in openNode list to current node
        currentNode = lowestCostInArray(openNodes);

        //remove current node from openList
        openNodes.splice(openNodes.indexOf(currentNode), 1);

        //find 8 nodes adjacent to current node
        connectedNodes = findConnectedNodes(currentNode);

        //for each adjacent node,
        for each (var n:Node in connectedNodes) {
            // if node is not in open list AND its not in closed list AND its traversable
            if ((openNodes.indexOf(n) == -1) && (closedNodes.indexOf(n) == -1) && n.traversable) {

                // Calculate g and h values for the adjacent node and add the adjacent node to the open list
                // also set the current node as the parent of the adjacent node

                if ((n.mapX != currentNode.mapX) && (n.mapY != currentNode.mapY)) {
                    cost = 1.414; 
                } else {
                    cost = 1;
                }
                if(n.g> currentNode.g + cost){
                n.g = currentNode.g + cost;
                n.f=calculateCostOfNode(n);
                n.parentNode =currentNode;
                openNodes.push(n);
               }
            }
        }
        // turn current node into grass to indicate its been traversed
        currentNode.setType("walked_path");

        //var temp2:TextEntity = new TextEntity(n.h.toFixed(1).toString(), 32 * currentNode.mapX, 32 * currentNode.mapY);
        //add(temp2);

        // add current node to closed list
        closedNodes.push(currentNode);
    }

    // create a path from the destination node back to the starting node by following each parent node
    var tempNode:Node = destinationNode.parentNode;

    tempNode.setType("path2"); // blue blocks
    while(tempNode != startingNode){
        tempNode = tempNode.parentNode;
        tempNode.setType("path2");

    }
}

These were the helper functions:

function findConnectedNodes(inputNode:Node):Array {
    var outputArray:Array=[];

    // obtain all nodes that are either 1 unit away or 1.4 units away.
    for each (var n:Node in listOfNodes){
        if ((diagonalHeuristic(inputNode, n) == 1)||(diagonalHeuristic(inputNode, n) == 1.4) {
            outputArray.push(n);
        }
    }
    return outputArray;
}

public static function diagonalHeuristic(node:Node, destinationNode:Node, cost:Number = 1.0, diagonalCost:Number = 1.4):Number {
    var dx:Number = Math.abs(node.mapX - destinationNode.mapX);
    var dy:Number = Math.abs(node.mapY - destinationNode.mapY);

    if (dx > dy) {
        return diagonalCost * dy + (dx - dy);
    }else {
        return diagonalCost * dx + (dy - dx);
    }       
}

function lowestCostInArray(inputArray:Array):Node {
    var tempNode:Node = inputArray[0];
    for each (var n:Node in inputArray) {
        if (n.f < tempNode.f) {
            tempNode = n;
        }
    }
    return tempNode;
}

I can provide the source code of the project if it helps.

+3


source to share


1 answer


I see several possible errors.



  • You are potentially rewriting the values ​​here:

            n.g = currentNode.g + cost;
        n.f=calculateCostOfNode(n);
        n.parentNode =currentNode;
        openNodes.push(n);

    It should be:

         if n.g > currentNode.g + cost:
        n.g = currentNode.g + cost;
        n.f=calculateCostOfNode(n);
        n.parentNode =currentNode;
        if n not already in openNodes:
            openNodes.push(n);

    C n.g

    , triggered to a very large value, or you can do a check like if n not in the open set or n.g > currentNode.g + cost

    .

    You have to delete the check if ((openNodes.indexOf(n) == -1)

    from where you have it and place it where I said. If the new value is g

    better, you should update it even if it is on the open list. You only update node once. If it is that you check the diagonals first, you are completely ignoring the side steps.

    This is probably a problem: by ignoring neighbors that are on the open list, you will only update their value once. It's okay to update their value as long as they are not on a closed list.

  • I don't know for sure if this is a valid problem, but I think you are playing with fire a bit using 1.414

    a heuristic function. The heuristic function must be valid, which means that it should never overestimate the value. If you run into some floating point issues, you can overestimate. I would play it safe and use it 1.4

    for heuristics and 1.414

    for the actual cost between diagonally adjacent nodes.

+1


source






More articles:


All Articles