A* 算法:封闭列表包含太多元素/太大 [英] A* Algorithm: closed list contains too many elements / too large

问题描述

我目前正在 JavaScript 中实现 A* 算法.但是，我遇到了一个问题:我的 closedList 似乎太大了.这是输出的屏幕截图:

I'm currently implementing the A* algorithm in JavaScript. However, I've ran into a problem: My closedList seems way too large. Here is a screenshot of the output:

是什么导致了这个问题?我的启发式计算是错误的吗?

What could cause this problem? Is my heuristic calculation wrong?

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

或者我在这个方法中理解/实现了错误吗?:

Or did I understand/implement something wrong in this method?:

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

}
}

如果您想查看代码的更多部分，请告诉我.感谢您的帮助，谢谢.

If you want to see more parts of the code, just tell me. I appreciate any help, thank you.

推荐答案

您需要打破与端点的联系.

(不打破与端点的联系)

(打破与端点的联系)

(有障碍物的例子)

这篇关于A* 算法:封闭列表包含太多元素/太大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！