Thuật toán A *: danh sách đóng chứa quá nhiều phần tử/quá lớn

Question

Tôi hiện đang triển khai thuật toán A * trong JavaScript. Tuy nhiên, tôi đã gặp phải vấn đề: Danh sách đóng của tôi dường như quá lớn. Đây là một ảnh chụp màn hình của đầu ra:

gì có thể gây ra vấn đề này? Tính toán heuristic của tôi có sai không?

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

Hoặc đã làm tôi hiểu/thực hiện một cái gì đó sai trong phương pháp này ?:

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

} 
} 

Nếu bạn muốn xem chi tiết các bộ phận của mã, chỉ cần cho tôi biết. Tôi đánh giá cao sự giúp đỡ nào, cảm ơn bạn.

Answer 1

Bạn cần phải break ties towards the endpoint.

(Nếu không phá vỡ mối quan hệ đối với thiết bị đầu cuối)

(Với mối quan hệ vi phạm đối với thiết bị đầu cuối)

(Ví dụ với một chướng ngại vật)