5

私は現在JavaScriptでA*アルゴリズムを実装しています。ただし、問題が発生しました。closedListが大きすぎるようです。出力のスクリーンショットは次のとおりです。

A*JSでの実装

この問題の原因は何ですか?私のヒューリスティック計算は間違っていますか?

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;
}

または、この方法で何か間違ったことを理解/実装しましたか?:

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++;
        }
    }

}
}

コードのより多くの部分を見たい場合は、教えてください。助けてくれてありがとう、ありがとう。

4

1 に答える 1

8

エンドポイントとの関係を断ち切る必要があります。

エンドポイントへの結びつきを壊すことなく
(エンドポイントとの関係を断ち切ることなく)

エンドポイントへの結びつきを断ち切る
(エンドポイントへの結びつきを断ち切る)

障害物のある例
(障害物のある例)

于 2013-03-25T20:21:44.750 に答える