在迷宫中找到一条最短路径，然后行动

Question

我正在制作一款胭脂游戏，其中一个怪物的行为是这样的。在迷宫中，如果怪物能够在15步或更短的时间内到达玩家身边，那么这便是最理想的移动方式。为了实现这一点，我编写了一个小程序来模仿游戏中将要发生的事情。我的程序的工作方式是，它能够检查x次移动是否能让他到达目的地。我唯一不确定的部分是如何获得第一步，所以我可以将该信息传递给我的怪物移动函数。这是我到目前为止写的程序。

#include <iostream>
using namespace std;

bool pathExists(char maze[][10], int sr, int sc, int er, int ec, int distance)
{
    if (maze[sr][sc] != '.')
        return false;
    if (sr == er  &&  sc == ec)
        return true;
    if(distance ==15)
    {
        cout<<"Cant make it in 15 steps"<<endl;
        return false;
    }
    maze[sr][sc] = '@';  // anything non-'.' will do
    if (pathExists(maze, sr-1, sc, er, ec, distance+1))
        return true;
    if (pathExists(maze, sr+1, sc, er, ec,distance+1))
        return true;
    if (pathExists(maze, sr, sc-1, er, ec, distance+1))
        return true;
    if (pathExists(maze, sr, sc+1, er, ec, distance+1))
        return true;
    return false;
}


int main()
{
    char maze[10][10] = {
        { 'X','X','X','X','X','X','X','X','X','X'},
        { 'X','.','.','.','.','.','.','.','.','X'},
        { 'X','.','X','X','X','X','.','X','X','X'},
        { 'X','.','.','X','.','X','.','.','.','X'},
        { 'X','.','.','X','.','.','.','X','.','X'},
        { 'X','.','X','X','.','X','X','X','.','X'},
        { 'X','.','X','.','.','.','.','X','X','X'},
        { 'X','.','.','X','X','.','X','X','.','X'},
        { 'X','.','.','x','.','.','.','.','.','X'},
        { 'X','X','X','X','X','X','X','X','X','X'}
    };
    if (pathExists(maze, 8,8, 1,1,0))
        cout << "Solvable!" << endl;
    else
        cout << "Out of luck!" << endl;
}

总结一下，我希望获得关于这个怪物迈出的第一步的信息。我知道这有点容易问，但我不熟悉递归，有点迷失在我的代码。

感谢c++的上帝。

Answer 1

选择*算法。尽管你需要计算出墙的碰撞。但既然你使用网格，我会说用A*算法。维基百科解释了这个算法。(伪代码)

你需要使用vector，因为它是c++。如果你仍然不理解维基百科上的代码，那么你可以使用我几个月前做的一个库。(不是一个库，但你可以称之为类似的代码。您将不得不更改一些值来使其工作。我把它做成了20x20的迷宫;你需要10x10)