java - 吃 bean 迷宫的广度优先搜索

Question

我目前正在建立一个程序，在吃豆子迷宫中吃掉所有食物。但是，每次Pacman进行新动作时，我的程序都会被调用，因此程序结束时不会保存任何内存，并且只会返回一个动作：L，R，U或Down。我是AI新手，也是Java编程新手。我知道，通过在Google上进行搜索，最好的方法是使用BFS。问题是：我该怎么做？我是否必须为我访问的每个位置创建一个LinkedList，其中包含将我带到那里的路径？例如：UULLDDLRRL。

我的另一个疑问是，如何让吃豆子寻找最近的食物？

这是我的代码，我删除了代码的输入部分，这与我的问题无关。我正在将Pacman上的地图保存在char [] []上。

class position{
    int pX=0;
    int pY=0;
    char direction;
    Boolean visited = false;


position(int pY, int pX, char direcao,Boolean visited)
{
    this.pX=pX;
    this.pY=pY;
    this.direcao=direction;
    this.direction=direction;
}

position()
{
    pX=0;
    pY=0;
    direction='N';
    visited=false;
}

}

    position current = new position(pacmany,pacmanx,'N',false);
    LinkedList<position> analise = new LinkedList<position>();

    analise.addLast(current);

    while(!analise.isEmpty())
    {
        if(m[current.pY-1][current.pX]!='#')
        {
            analise.addLast(new position(current.pY-1,current.pX,'U',false));
        }

        if(m[current.pY][current.pX+1]!='#')
        {
            analise.addLast(new position(current.pY,current.pX+1,'R',false));
        }

        if(m[current.pY+1][current.pX]!='#')
        {
            analise.addLast(new position(current.pY+1,current.pX,'D',false));
        }

        if(m[current.pY][current.pX-1]!='#')
        {
            analise.addLast(new position(current.pY,current.pX-1,'L',false));
        }

        analise.get(i).visited=true;
        current=analise.get(i);
        analise.remove();
    }

    }

}

Answer 1

有很多问题需要处理，一个小例子是“循环检查”功能。

循环检查
你怎么知道你的迷宫是否包含一个循环？例如，您的应用程序可能会在迷宫中找到一个循环，并且永远不会终止，或者会花费很长时间找到路径，从而导致计算机内存不足。

启发式功能
您可能需要启发式函数来帮助您找到最佳的下一步，例如使算法更快。同样，您应该了解什么是启发式函数，什么是允许的启发式等。

通常，当您是AI和编码方面的新手时，开始对搜索问题进行编码有点复杂。但这并不意味着放弃。但是您应该开始阅读一些书，以便首先理解Graph Theory的概念，然后理解不同的Graph Traversal Algorithms（例如BFS，DFS，A-Star等），然后您会发现自己更容易思考问题。

我认为提出和解决此类问题的更好方法是，首先从理论上学习概念，然后尝试将其付诸实践。

我发现一个与here一起使用的非常有用的资源。

最后，使用this可能有助于理解几种搜索算法的工作方式。您使用鼠标创建自己的迷宫，然后运行所需的算法，您将看到算法执行方式的直观方式。

查看如何更改每个搜索算法（包括启发式函数）的设置，以及如何观察性能差异。