A星實現，沒有找到最短路徑問題

Question

我有代碼，應該找到從A點到B點的最短路徑。爲此，我使用A-star變體。我正在使用2d數組來表示一個2D網格，但我的路徑沒有采用對角線快捷方式，只有左，右，上，下。到目前爲止，一切都很好，除了它並不總能找到最短的路徑。我想知道發生了什麼問題，爲什麼會出現問題，以及我如何解決問題。先謝謝你。

這裏是爲了說明究竟是發生了一個畫面：

，這裏是我的代碼（尋路類第一，那麼它的輔助類）：

BTW：數學矢量只不過是一個幾何點類，並且playerTileLocation和enemyTileLocation都只是對應於網格上的開始和結束節點的點。此外，我使用類AStarNode作爲地圖上所有拼貼的節點，而不是常規對象。

package { 
import src.Characters.Character; 
import src.InGame.Map; 
import src.Maths.MathVector; 

public final class BaseAI { 
// REPRESENTS UP, DOWN, RIGHT, AND LEFT OF ANY ONE NODE 
    private static const bordersOfNode:Array = new Array(
     new MathVector(-1, 0), new MathVector(1, 0), new MathVector(0, -1), new MathVector(0, 1)); 


    private var _player:Character; 
    private var map:Map; 

    private var playerTileLocation:MathVector; 



    private var openList:Array; 
    private var closedList:Array; 
// 2D ARRAY OF MAP TILES (I DON'T USE HERE, BUT I PLAN TO IN FUTURE) 
    private var mapArray:Array; 
    private var originNode:AStarNode; 
    private var complete:Boolean; 


    public function BaseAI(_player:Character,map:Map):void { 
     this._player = _player; 
     this.map = map; 

     openList = new Array(); 
     closedList = new Array(); 
     mapArray = map.tiles; 
    } 
    public function get player():Character { 
     return this._player; 
    } 

    public function calculatePlayerTileLocation():void { 
     playerTileLocation = map.worldToTilePoint(player.groundPosition); 
    } 
//WILL EVENTUAL RETURN A DIRECTION FOR THE ENEMY TO TAKE THAT ITERATION (EVERY 1-2 SECONDS) 
    public function getDirection(enemy:Character):String { 
     var enemyTileLocation:MathVector = map.worldToTilePoint(enemy.groundPosition); 


     originNode = new AStarNode(enemyTileLocation, playerTileLocation); 
     originNode.setAsOrigin(); 

     openList = [originNode]; 
     closedList = []; 

     complete = false; 
     var currentNode:AStarNode; 
     var examiningNode:AStarNode; 

     while (!complete) { 

      openList.sortOn("F", Array.NUMERIC); 
      currentNode = openList[0]; 
      closedList.push(currentNode); 
      openList.splice(0, 1); 

      for (var i in bordersOfNode) { 
       examiningNode = new AStarNode(new MathVector(currentNode.X + bordersOfNode[i].x, currentNode.Y + bordersOfNode[i].y),playerTileLocation); 

       if (map.isOpenTile(map.getTile(examiningNode.X, examiningNode.Y)) && !examiningNode.isThisInArray(closedList)) { 
        if (!examiningNode.isThisInArray(openList)) { 
         openList.push(examiningNode); 
         examiningNode.parentNode = currentNode; 
        }else { 

        } 
        if (examiningNode.X == playerTileLocation.x && examiningNode.Y == playerTileLocation.y) { 
         complete = true; 
         var done:Boolean = false; 
         var thisNode:AStarNode; 
         thisNode = examiningNode; 
         while (!done) { 
          if (thisNode.checkIfOrigin()) { 
           done = true; 
          }else { 
           thisNode = thisNode.parentNode; 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

}

package { 
import src.Maths.MathVector; 

internal final class AStarNode { 
    private var _X:int; 
    private var _Y:int; 

    private var _G:int; 
    private var _H:int; 
    private var _F:int; 
    private var _parentNode:AStarNode; 

    private var _isOrigin:Boolean; 

    public static const VERTICAL:uint = 10; 

    public function AStarNode(thisNodeLocation:MathVector, targetNodeLocation:MathVector) { 
     X = thisNodeLocation.x; 
     Y = thisNodeLocation.y; 
     H = Math.abs(X - targetNodeLocation.x) + Math.abs(Y - targetNodeLocation.y); 
     G = 0; 
     F = H + G; 
    } 

    public function set X(newX:int):void { 
     this._X = newX; 
    } 
    public function get X():int { 
     return this._X; 
    } 

    public function set Y(newY:int):void { 
     this._Y = newY; 
    } 
    public function get Y():int { 
     return this._Y; 
    } 

    public function set G(newG:int):void { 
     this._G = newG; 
    } 
    public function get G():int { 
     return this._G; 
    } 

    public function set H(newH:int):void { 
     this._H = newH; 
    } 
    public function get H():int { 
     return this._H; 
    } 

    public function set F(newF:int):void { 
     this._F = newF; 
    } 
    public function get F():int { 
     return this._F; 
    } 

    public function set parentNode(newParentNode:AStarNode):void { 
     this._parentNode = newParentNode; 
    } 
    public function get parentNode():AStarNode { 
     return this._parentNode; 
    } 

    public function setAsOrigin():void { 
     _isOrigin = true; 
    } 
    public function checkIfOrigin():Boolean { 
     return _isOrigin; 
    } 

    public function isThisInArray(arrayToCheck:Array):Boolean { 
     for (var i in arrayToCheck) { 
      if (arrayToCheck[i].X == this.X && arrayToCheck[i].Y == this.Y) { 
       return true 
      } 
     } 
     return false 
    } 
} 
enter code here 

}

Answer 1

快速掃一眼代碼中引發了錯誤的啓發式的想法。您的G值在節點中始終爲0，至少我沒有看到它可以改變的地方。然而，在你的任務的A星算法中（找到障礙物的最短路徑），它應該表示已經達到單元的步數。這將允許算法用較短的路徑替換較長的路徑。

Answer 2

有一次，我編碼了一顆A星「算法」我用了一個二維數組作爲網格（就像你一樣）。在搜索開始時，每個網格位置的「搜索」屬性設置爲false。每個網格位置也會有一個連接方向陣列;玩家可以選擇進入的選項 - 有些可能是開放的，有些可能會被阻擋並且無法訪問。
我會開始搜索，通過檢查它有多少方向選項的起始網格位置。對於每個選項，我會將「路徑」數組推入_paths數組。每個「路徑」數組最後都會包含一系列「移動」（0代表上移，1代表右移，2代表下移，3代表左移）。因此，對於每條最初的路線，我都會推動相應的開局。我還會將網格位置的「搜索」屬性設置爲true。
然後，我會遍歷每個路徑，通過該序列的移動來到達最近添加的位置。我會檢查該位置是否是目標位置。如果不是，我會將該位置標記爲搜索，然後檢查哪些方向可用，忽略已搜索的位置。如果不可用，路徑將被關閉並從路徑陣列'拼接'。
否則，當前路徑Array的ByteArray'深度拷貝'是針對每個可用的移動選項進行的，超出了第一個移動選項。在一個方向上的移動被添加到當前路徑和新路徑中，在它們各自的方向上。
如果路徑數量達到0，那麼這兩個位置之間就沒有路徑。 我認爲就是這樣。我希望這有幫助。
請注意，搜索並不需要被「定向」向目標;我所建議的搜索所有可能的路徑，只是「碰巧」被殺死嘗試檢查已經搜尋過的位置路徑中尋找最直接的路線（這意味着一些其他的路徑已經到了那裏第一，因此更短）。