A *アルゴリズム：閉じたリストに含まれる要素が多すぎる/大きすぎます

JavaScriptでA *アルゴリズムを実装しています。しかし、私は問題に遭遇しました。私のclosedListは大きすぎるようです。ここでは、出力のスクリーンショットです：A *アルゴリズム：閉じたリストに含まれる要素が多すぎる/大きすぎます

A* Implementation in 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++; 
     } 
    } 

} 
}

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

出典

2013-03-25 dislick

全体のHTML + JSコードでjsfiddleをセットアップできますか？ – Uby

なぜあなたのclosedListが大きくなりすぎていると思いますか？そして、いいえ、マンハッタンの距離は素晴らしいヒューリスティックであるようです。 – Bergi

あなたが示したパスでは、閉リストにはグリッド内のほぼすべての四角形が表示されるはずですから、間違いはないと思います。もちろん、固定グリッドで作業しているときにA *を実装する方が良い方法があります。 – Dave