0

我的代码应该找到从 A 点到 B 点的最短路径。为此，我使用了 A 星变体。我使用 2d 数组来表示 2d 网格，但我的路径不采用对角线捷径，只有左、右、上和下。到目前为止，一切正常，只是它并不总是找到可能的最短路径。我想知道出了什么问题，为什么会出错，以及如何解决它。先感谢您。

这是一张图片来说明到底发生了什么：

A-Star 出错的例子

这是我的代码（首先是路径查找类，然后是它的帮助类）：

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

}

4

2 回答 2

1

快速浏览您的代码会引发错误启发式的想法。您的 G 值在一个节点中始终为 0，至少我看不出它在哪里可以改变。但是，在您的任务的 A-star 算法中（找到有障碍物的最短路径），它应该代表已经到达单元格的步数。这将允许算法用较短的路径替换长路径。

于 2013-09-23T02:37:32.247 回答
0

有一次我编写了一个 A 星“算法”，我使用了一个二维数组作为网格（正如你所拥有的）。在搜索开始时，每个网格位置的“搜索”属性都设置为 false。每个网格位置也将有一个连接方向数组；玩家可以选择进入的选项 - 有些可能是开放的，有些可能会被阻止且无法访问。
我将通过检查起始网格位置以了解它有多少方向选项来开始搜索。对于每个选项，我都会将“路径”数组推入 _paths 数组。每个“路径”数组最终将包含一系列“移动”（0 表示向上，1 表示右侧，2 表示向下，3 表示左侧）。因此，对于每条初始路径，我都会推动相应的起始动作。我还将设置网格位置的“搜索”
然后，我将遍历每条路径，遍历该移动序列以到达最近添加的位置。我会检查该位置是否是目标位置。如果不是，我会将该位置标记为已搜索，然后检查哪些方向可用，忽略已搜索的位置。如果不可用，则路径将被关闭并从路径数组中“拼接”。
否则，为每个可用的移动选项制作了当前路径数组的 ByteArray“深拷贝”，超过了第一个移动选项。在当前路径和新路径各自的方向上添加了一个方向的移动。
如果路径数达到 0，则这两个位置之间没有路径。我想就是这样。我希望这会有所帮助。
请注意，搜索不需要“定向”到目标；我所建议的搜索所有可能的路径，只是“碰巧”通过杀死试图检查已经搜索过的位置的路径来找到最直接的路径（这意味着一些其他路径首先到达那里，因此更短）。

于 2013-09-23T08:00:24.420 回答