A*寻路不走最短路径

Question

我的 A* 寻路功能总是能到达预定的目的地，但它几乎总是有点偏离轨道。这是一个例子：

[我制作了一张漂亮的图片来展示我的问题，但显然它不会 post 直到我的声誉达到 10；对不起，我是新来的。 :P]

本质上，它尽可能地向左或向上拉，而不实际向路径添加更多的瓷砖。这听起来像是计算 gScore 的问题，或者可能是根据相邻图块的 gScore 重新分配图块父项的部分，但我就是不知道哪里出了问题。我已经梳理了数周的代码并浏览了数十个在线 posts，但我仍然卡住了。仅供参考，我必须使用的 compiler/debugger 不支持断点或逐步调试，所以我只能使用简单的文本输出。谁能发现我做错了什么？

这里是主要功能（注意：这都是在Angelscript中，它基于C++，但有一些小的差异）：

    int CARDINAL_COST = 10;
int DIAGONAL_COST = 14;    
array<vector2> findPath(vector2 startPosition, vector2 endPosition)
{
    //Translate the start and end positions into grid coordinates
    startPosition = _level.getTileGridPosition(startPosition);
    endPosition = _level.getTileGridPosition(endPosition);

    //The path to be returned
    array<vector2> path(0);

    //Create the closed
    array<vector2> closedSet(0);

    //Create the open set. These are nodes to be considered.
    array<vector2> openSet(0);
    //Add the startPosition to the open set.
    openSet.insertLast(startPosition);

    //Create the cameFrom (path) array. Each entry hods that tile's parent tile.
    array<array<vector2>> cameFrom;
    cameFrom = array<array<vector2>>(_level.width(), array<vector2>(_level.height()));

    //Create the gScore array. gScore is the cost to get from the start to the current tile.
    array<array<int>> gScore;
    gScore = array<array<int>>(_level.width(), array<int>(_level.height()));
    //Set the start position score to 0
    gScore[startPosition.x][startPosition.y] = 0;

    //Create the fScore array. fScore is the gScore + heuristic cost.
    array<array<int>> fScore;
    fScore = array<array<int>>(_level.width(), array<int>(_level.height()));
    //Set the start position score to the estimated (heuristic) cost.
    //gScore for start is 0, so that's not included in the equation.
    fScore[startPosition.x][startPosition.y] = getHeuristicCost(startPosition, endPosition);

    //Required variables
    bool searchComplete = false;
    vector2 currentTile = startPosition;
    int x = 0;
    int y = 0;
    string tileType = "";
    vector2 nextTile(0,0);
    vector2 neighborTile(0,0);
    int lowestScore = 0;
    int tempScore = 0;
    int index = 0;

    while(!searchComplete)
    {


        //Find the tile in the openSet with the lowest fScore.
        lowestScore = fScore[openSet[0].x][openSet[0].y];
        neighborTile = openSet[0];//May not actually be a "neighbor" in this case, just looking for the lowest fScore.

        for(int i = 0; i < openSet.length(); i++)
        {
            if(fScore[neighborTile.x][neighborTile.y] < lowestScore || i == 0)
            {
                lowestScore = fScore[neighborTile.x][neighborTile.y];
                nextTile.x = neighborTile.x;
                nextTile.y = neighborTile.y;
            }
        }

        //Drop the "nextTile" from the openSet and add it to the closedSet
        index = openSet.find(nextTile);
        openSet.removeAt(openSet.find(nextTile));
        closedSet.insertLast(nextTile);

        //Set the currentTile
        currentTile = nextTile;

        //Get the fScore for each neighboring tile
        for(x = currentTile.x - 1; x <= currentTile.x + 1; x++)
        {
            for(y = currentTile.y - 1; y <= currentTile.y + 1; y++)
            {
                //Safety: make sure x and y aren't out of bounds
                if(x < 0)
                    x = 0;
                else if(x > _level.width())
                    x = _level.width();

                if(y < 0)
                    y = 0;
                else if (y > _level.height())
                    y = _level.height();

                //Set this x,y pair to be the neighborTile
                neighborTile.x = x;
                neighborTile.y = y;

                //Get the tile type
                if(_level.tileArray()[neighborTile.x][neighborTile.y] != null)
                    tileType = _level.tileArray()[neighborTile.x][neighborTile.y].GetString("type");
                else
                    tileType = "";

                //Make sure we aren't looking at the current tile, the tile is not closed, and the tile is a floor or door.
                if(neighborTile != currentTile && closedSet.find(neighborTile) == -1 && (tileType == "floor" || tileType == "door"))
                {
                    //If the neighboring tile is already in the open set, check to see if the currentTile's gScore would be less if that tile was its parent.
                    //If it is, set the it as the currentTile's parent and reset the fScore and gScore for it.
                    if(openSet.find(neighborTile) != -1)
                    {                           
                        if(gScore[neighborTile.x][neighborTile.y] < gScore[cameFrom[currentTile.x][currentTile.y].x][cameFrom[currentTile.x][currentTile.y].y])
                        {
                            cameFrom[currentTile.x][currentTile.y] = neighborTile;

                            //If the tile is a diagonal move
                            if(neighborTile.x - currentTile.x != 0 && neighborTile.y - currentTile.y != 0)
                                gScore[currentTile.x][currentTile.y] = gScore[neighborTile.x][neighborTile.y] + DIAGONAL_COST;
                            else//If the tile is a cardinal (N,S,E,W) move
                                gScore[currentTile.x][currentTile.y] = gScore[neighborTile.x][neighborTile.y] + CARDINAL_COST;

                            fScore[currentTile.x][currentTile.y] = gScore[currentTile.x][currentTile.y] + getHeuristicCost(currentTile, endPosition);
                        }
                    }
                    else//Add this tile to the open set
                    {
                        openSet.insertLast(neighborTile);

                        //Record this tile's parent
                        cameFrom[neighborTile.x][neighborTile.y] = currentTile;

                        //If the tile is a diagonal move
                        if(neighborTile.x - currentTile.x != 0 && neighborTile.y - currentTile.y != 0)
                            gScore[neighborTile.x][neighborTile.y] = gScore[currentTile.x][currentTile.y] + DIAGONAL_COST;
                        else//If the tile is a cardinal (N,S,E,W) move
                            gScore[neighborTile.x][neighborTile.y] = gScore[currentTile.x][currentTile.y] + CARDINAL_COST;

                        //Get the fScore for this tile
                        fScore[neighborTile.x][neighborTile.y] = gScore[neighborTile.x][neighborTile.y] + getHeuristicCost(neighborTile, endPosition);
                    }

                }
            }
        }


        //Check to see if we have arrived at the endTile
        if(currentTile == endPosition)
        {
            searchComplete = true;
            path = reconstructPath(cameFrom, startPosition, endPosition);
        }
        else
        {
            //Check to see if the openSet is empty
            if(openSet.length() == 0)
                searchComplete = true;
        }   

    }//while(!searchComplete)

    return path;
}

我的启发式使用曼哈顿方法：

    int getHeuristicCost(vector2 startPosition, vector2 endPosition)
{
    //Using Manhattan method:
    int x = abs(startPosition.x - endPosition.x)*10;
    int y = abs(startPosition.y - endPosition.y)*10;

    return x+y;
}

最后，这是我的路径重构函数：

    array<vector2> reconstructPath(array<array<vector2>> &in cameFrom, vector2 &in startPosition, vector2 &in endPosition)
{       
    //Start by adding in the end position
    array<vector2> totalPath(1);
    vector2 currentTile = endPosition;
    totalPath[0] = endPosition;

    int x = endPosition.x;
    int y = endPosition.y;
    int angle = 0;
    while(vector2(x, y) != startPosition)
    {           
        currentTile = cameFrom[x][y];
        totalPath.insertAt(0,currentTile);
        x = currentTile.x;
        y = currentTile.y;
    }

    return totalPath;
}

Answer 1

    for(int i = 0; i < openSet.length(); i++)
    {
        if(fScore[neighborTile.x][neighborTile.y] < lowestScore || i == 0)
        {
            lowestScore = fScore[neighborTile.x][neighborTile.y];
            nextTile.x = neighborTile.x;
            nextTile.y = neighborTile.y;
        }
    }

这个循环只是一遍又一遍地查看 neighborTile。您是要查看 openSet 的元素吗？

A*寻路不走最短路径

A* pathfinding not taking shortest path

c++

a-star

path-finding

angelscript