C++、A* 搜索程序无法正确计算距出口的距离

Question

我一直在使用 Visual Studio 时遇到问题，所以提前致歉，但我一直在使用在线网站进行编译，但不能使用断点，尽管我很想这样做现在的程序。

我仍在努力，但现在获取 A*Star 的 H 值，即距出口的距离，似乎无法正确显示/计算。

它工作到一定程度，然后似乎开始倒退。

我认为问题出在我的搜索中，尽管它为节点提供了它们的值，并且它显示正确但与预期不符。点110起。例如：

int start = 0;
bool search = true;
aStarArray[myCoord.endY][myCoord.endX].h = 0; // End cell coord, written as 0 for the H array. (0 distance to exit)

while (search == true) // Will end as soon as all nodes have been valued. 
{
    for (myCoord.y = 0; myCoord.y < HEIGHT; ++myCoord.y)
    {
        for (myCoord.x = 0; myCoord.x < WIDTH; ++myCoord.x)
        {
            if (aStarArray[myCoord.y][myCoord.x].h == start) // Is value we're looking for.
            {
                if (myCoord.y + 1 <= HEIGHT)
                {
                    if (aStarArray[myCoord.y+1][myCoord.x].h == -1) // Not blocked, but not distanced yet and is a valid cell.
                    {
                        aStarArray[myCoord.y+1][myCoord.x].h = start + 1; // Then give it a value of parent cell + 1. (start + 1)
                        search = false;
                    }
                }

                if (myCoord.y - 1 >= 0)
                {
                    if (aStarArray[myCoord.y-1][myCoord.x].h == -1)
                    {
                        aStarArray[myCoord.y-1][myCoord.x].h = start + 1;
                        search = false;
                    }
                }

                if (myCoord.x + 1 <= WIDTH)
                {
                    if (aStarArray[myCoord.y][myCoord.x+1].h == -1)
                    {
                        aStarArray[myCoord.y][myCoord.x+1].h = start + 1;
                        search = false;
                    }
                }

                if (myCoord.x - 1 >= 0)
                {
                    if (aStarArray[myCoord.y][myCoord.x-1].h == -1)
                    {
                        aStarArray[myCoord.y][myCoord.x-1].h = start + 1;
                        search = false;
                    }
                }
            }
        }
    }

    start = start + 1;

    if (search == false) // A change was made to a node on this loop of the array.
    {
        search = true; // Then assume more nodes await values, keep searching.
                       // Now we're moving on to one of those new distanced cells, so the parent changes and thus search terms. 
                       // Start gets +1, so it's start searching for the new cells. And then it'll distance their neighbour cells to start+1, cycle repeats.
    }
    else // No changes.
    {
        search = false; // No need to search anymore, theoretically. 
    }
}
}

目前的结果是这样的：

Get H values for every node
6  7  6  5  4
5  6  5  4  3
4  5  4  3  2
3  4  3  2  1
2  3  2  1  0

当我想要它是这样的时候，例如：

Get H values for every node
8  7  6  5  4
7  6  5  4  3
6  5  4  3  2
5  4  3  2  1
4  3  2  1  0

完整代码可以在这里找到： cpp.sh/8iykn

如果有人有任何建议来解决获取 H 的问题，或者只是任何一般性错误，我们将不胜感激。谢谢

Answer 1

您的支票

if (myCoord.y + 1 <= HEIGHT)

错了。应该是

if (myCoord.y + 1 < HEIGHT)

WIDTH

也一样

C++、A* 搜索程序无法正确计算距出口的距离

C++, A* Search Program doesn't calculate distance from exit correctly

c++

a-star