My A* pathfinding implementation does not produce the shortest path

Question

I am building a flash game that requires correct pathfinding. I used the pseudo code in this tutorial and a diagonal heuristic. I did not closely follow their code. The language is ActionScript 3 and I am also using flashpunk libraries.

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

The grey blocks are non traversable, the green blocks mark nodes that have been "visited" and the blue blocks show the path generated by the algorithm.

It looks as if the diagonal travel cost is equal to the non-diagonal travel cost, despite my attempt to make the diagonal cost higher (1.414).

This is the overall algorithm implementation.

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 used:

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 project source code if it would help.

Answer 1

I see a few potential things wrong.

1. You are potentially overwriting 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);
   

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

   You should remove the check if ((openNodes.indexOf(n) == -1) from where you have it now and put it where I said. If the new g cost is better, you should update it, even if it's in the open list. You only update each node once. If it so happens that you check diagonals first, you will completely ignore side steps.

   This is likely the problem: by ignoring neighbors that are in the open list, you will only update their cost once. It is OK to update their cost as long as they are not in the closed list.

2. I don't know for sure if this is a valid concern, but I think you're playing with fire a little by using 1.414 in the heuristic function. The heuristic function has to be admissible, which means it should never overestimate the cost. If you run into some floating point issues, you might overestimate. I'd play it safe and use 1.4 for the heuristic and 1.414 for the actual cost between diagonally adjacent nodes.