如何让AI系统选择最快的方式，并通过墙导航到某个网格点

Question

基本上，我正在尝试改进我正在制作的一款吃豆人游戏中的幽灵。在最初的“吃豆人”中，当一个鬼魂被吃掉时，当“吃豆人”拿起异能时，鬼眼就会导航回到主场，然后再把生出来。我想这样做。这也会帮助我实现一个幽灵AI，让他们更智能地移动，而不是随机移动。

所以基本上，这些眼睛必须通过这个导航：

​

​

而棋盘是从下面的2D数组中提取的：

  //0's = Walls or location not allowed to go
  //1's = Dot Spot
  //2's = Clear Path nothing on it but safe to move
  //3's = Power Dot
  //-1's = only ghosts can go through
  //5= Top entry spot
  //6= bottom entry point
  //7 = Cherry
  //(Spots = row - 1 same with columns = - 1. First # is row. Second is col
  public int board[][] =
  {{2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, //1
    {2, 0, 3, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 3, 0, 2}, //2
    {2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 2}, //3
    {2,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,2}, //4
    {2,0,1,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,2}, //5
    {2,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,2}, //6
    {2,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,2}, //7
    {2,2,2,2,0,1,0,1,1,1,1,1,1,1,0,1,0,2,2,2,2}, //8
    {0,0,0,0,0,1,0,1,0,0,-1,0,0,1,0,1,0,0,0,0,0}, //9
    {5,2,2,2,2,1,1,1,0,2,2,2,0, 1 ,1,1,2,2,2,2,6}, //10 - cherry
    {0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0}, //11
    {2,2,2,2,0,1,0,1,1,1,2,1,1,1,0,1,0,2,2,2,2}, //12
    {2,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,2}, //13
    {2,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,2}, //14 - pacman on this row
    {2,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,1,0,2}, //15
    {2,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,2}, //16 
    {2,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,2}, //17
    {2,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,2}, //18
    {2,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,2}, //19
    {2,0,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,0,2}, //20
    {2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2}}; //21

所以我的问题是，我应该如何让眼睛在不穿墙的情况下以最快的方式到达中心主点？

Answer 1

只需使用预计算墨迹即可。“主”方块被标记为零。然后，一个标记为n的正方形的所有未分配的相邻正方形都被分配了标号n +1。现在你所有的“死”幽灵要做的就是移动到一个标号较低的相邻正方形。最终，他们会走最短的路回到家。简单！

Answer 2

您可以在Lee's algorithm中查找带有障碍物的矩阵中的最短路径。