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，那么这两个位置之间就没有路径。 我认为就是这样。我希望这有帮助。
请注意，搜索并不需要被“定向”向目标;我所建议的搜索所有可能的路径，只是“碰巧”被杀死尝试检查已经搜寻过的位置路径中寻找最直接的路线（这意味着一些其他的路径已经到了那里第一，因此更短）。