Algorytm * zamknięta lista zawiera zbyt wiele elementów/zbyt dużych

Question

Aktualnie implementuję algorytm A * w JavaScript. Jednakże natrafiłem na problem: Moja closedList wydaje się zbyt duża. Oto zrzut ekranu wyjścia:

Co może być przyczyną tego problemu? Czy moje obliczenia heurystyczne są błędne?

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

Albo nie rozumiem/zaimplementować coś złego w tej metodzie ?:

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

} 
} 

Jeśli chcesz zobaczyć więcej części kodu, po prostu powiedz. Doceniam każdą pomoc, dziękuję.

Answer 1

Musisz break ties towards the endpoint.

(bez zerwania związki kierunku końcowego)

(łamiącym więzów w kierunku końcowego)

(przykład z przeszkodą)