c - 如何防止随机游走算法得到 'stuck' ？

Question

我正在制作一款类似 rogue 的游戏，我正在使用网格内的随机游走来形成“洞穴”系统。然而，我提出的随机游走会卡住——尤其是当游走者靠近网格边缘并且被“洞”包围时。

这不是我在我的项目中使用的确切代码，我无法从工作中访问我的代码。但是，我重新编写了一个我在家里使用的相同算法的示例。

基本上，我采用了一个 20x20 的整数网格并用 1 填充它。当我走路时，我每走一步都打 0 分。

void walk(int grid[][20]){
  int x = rand() % 10 + 9;
  int y = rand() % 10 + 9;

  int walk_count;

  for(walk_count = rand() % 1000 + 500; walk_count >= 0; walk_count--){
    switch(rand() % 4){
      case 0: if(grid[x][y - 1] == 1 && y - 1 >= 1){ y--; grid[x][y] = 0;} break;
      case 1: if(grid[x][y + 1] == 1 && y + 1 < 20){ y++; grid[x][y] = 0;} break;
      case 2: if(grid[x - 1][y] == 1 && x - 1 >= 1){ x--; grid[x][y] = 0;} break;
      case 3: if(grid[x + 1][y] == 1 && x + 1 < 20){ x++; grid[x][y] = 0;} break;
      default: break;
    }
  }
}

Answer 1

首先，解释一下代码中的不对称性。在情况 1 中，您有 && y + 1 < 20 .在情况 3 中，您有 && x + 1 >= 1 ，我希望它是 && x + 1 < 20 .

我将把它记为转录错误/拼写错误，而不是问题的根源。据我了解，您的问题是您有一个随机行走者在地板上绘制(paint)并将自己涂在角落里。这种行为是预料之中的，不是吗？

问题在于您只是在随机游走，并期待一种比随机更智能的行为。如果你想避免把自己逼到墙角，就把它放到你的算法中。假设这些随机游走者希望能够到达玩家，只需检查每个方向(如果已填充)是否仍然有通往玩家的路径。然后从适用的方向中随机选择。