A* Algorithme : la liste fermée contient trop d'éléments / trop grande

Question

Je suis en train d'implémenter l'algorithme A* en JavaScript. Cependant, j'ai rencontré un problème : ma liste fermée semble beaucoup trop grande. Voici une capture d'écran de la sortie :

Quelle pourrait être la cause de ce problème ? Mon calcul heuristique est-il erroné ?

Node.prototype.getHeuristic = function(pos0, pos1)
{
    // Manhatten Distance
    var horizontalDistance = Math.abs(pos1.x - pos0.x);
    var verticalDistance = Math.abs(pos1.y - pos0.y);
    return horizontalDistance + verticalDistance;
}

Ou ai-je mal compris/implémenté quelque chose dans cette méthode ?

PathFinder.prototype.findPath = function() 
{
var start = new Date().getTime();
var openList = [];
var closedList = [];

var startNode = this.startNode;
var grid = this.grid;
var endNode = this.finishNode;

openList.push(startNode);

while (openList.length > 0)
{
    var lowInd = 0;
    for(var i = 0; i < openList.length; i++) {
        if (openList[i].f < openList[lowInd].f) 
        {
            lowInd = i; 
        }
    }
    var currentNode = openList[lowInd];

    if (currentNode.x == endNode.x && currentNode.y == endNode.y)
    {
        var curr = currentNode;
        var ret = [];
        while (curr.parent)
        {
            ret.push(curr);
            curr.type = NODES.PATH;
            curr = curr.parent;
        }   

        this.finishNode.type = NODES.FINISH;
        this.printGrid();   
        console.log("Total Operations: " + this.operations);

        var end = new Date().getTime();
        var time = end - start;
        console.log('Execution time: ' + time + "ms");

        return true;
    }

    openList.splice(lowInd, 1);
    closedList.push(currentNode);
    if (currentNode.type != NODES.START) 
    {
        currentNode.type = NODES.CLOSED;
    }

    var neighbors = currentNode.getNeighbors(this.grid);

 for (var indexNeighbors = 0; indexNeighbors < neighbors.length; indexNeighbors++)
    {
        var neighbor = neighbors[indexNeighbors];

        if (this.findNodeInArray(closedList, neighbor) || neighbor.isWall())
        {
            continue;
        }

        var gValue = currentNode.g + 1;
        var isGvalueLowest = false;

        if (!this.findNodeInArray(openList, neighbor))
        {
            isGvalueLowest = true;
            neighbor.h = neighbor.getHeuristic(neighbor, endNode);
            openList.push(neighbor);
        } 
        else if (gValue < neighbor.g) 
        {
            isGvalueLowest = true;
        }

        if (isGvalueLowest) 
        {
            neighbor.parent = currentNode;
            neighbor.g = gValue;
            neighbor.f = neighbor.g + neighbor.h;   
            neighbor.type = NODES.MARKED;

            console.log(neighbor);
            this.operations++;
        }
    }

}
}

Si vous voulez voir d'autres parties du code, dites-le moi. J'apprécie toute aide, merci.

Answer 1

Vous devez rompre les liens vers le point final .

(Sans rompre les liens vers le point final)

(Avec des liens de rupture vers le point final)

(Exemple avec un obstacle)