java - 如何制作一个选择最快方式并通过墙壁导航到特定网格点的 AI 系统

Question

基本上，我正在尝试改进我正在制作的吃 bean 人游戏中的 Ghosts。在原始的 pacman 中，当 Pacman 获得能量时 Ghost 被吃掉时，Ghost 的眼睛会导航回主区域，然后重新生成幽灵。我想这样做。它还可以帮助我实现 Ghost AI，让它们更智能地移动，然后只是随机移动。

所以基本上那些眼睛必须通过这个来导航:

板子是从下面的二维数组中绘制的:

  //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

只需使用预先计算好的墨迹。 “主”方 block 标记为零。然后，标记为 n 的方 block 的所有未分配的相邻方 block 都分配有标签 n +1。现在你所有“死去”的鬼魂所要做的就是移动到标签较低的相邻方格。最终他们会选择最短的路径回家。简单!