为什么我对数组中的图块进行评分的函数不起作用？

Question

我正在为我的大学编程项目编写一个类似 roguelike 的小游戏。我想尝试实现一个简单的寻路机制，这将涉及用从 0 开始向上的数字填充瓦片地图，数字是到玩家的距离。这将允许怪物找到玩家的最短路径。 这是我想出的算法：

void monster_vision(int player_x, int player_y, int score = 0)
{
    if (map[player_x][player_y] == '.')
    {
        map[player_x][player_y] = score;
    }
    else
        return;

    monster_vision(player_x - 1, player_y, score + 1);
    monster_vision(player_x + 1, player_y, score + 1);
    monster_vision(player_x, player_y - 1, score + 1);
    monster_vision(player_x, player_y + 1, score + 1);
}

正如我所说，这只是该功能的单文件草稿，地图类型为

std::array<std::array<char, map_size>, map_size

，最初在边缘和内部填充了#

我希望地图看起来像这样： 例如，如果地图的大小设置为 5，函数调用为：monster_vision(2, 2)

#####
#212#
#101#
#212#
#####

我得到的是：

#####
#218#
#307#
#456#
#####

根据我的理解，一些递归调用必须以某种方式重叠，但我认为我放置的防护装置应该足以防止写入已经得分的单元格。

Answer 1

问题是你的算法是递归的。想象一下它真正做了什么，它在你的地图中设置值

0

（如果

.

），然后它调用

monster_vision

来获取下一个坐标但为值

1

。现在奇迹发生了。您仍在对

monster_vision

的第二次调用中，但现在它再次调用

monster_vision

（深度 2）以获得下一个位置，但值为

2

等

因此，在您的代码中对

monster_vision

的四个调用不会按顺序调用。这个序列是迭代的，只有当你在所有四个“方向”上击中第一个非

.

时才会被打破......这正是你所观察到的。

迭代算法听起来不错，但行不通。

根据您的游戏逻辑，您必须决定如何计算距离/分数，例如怪物可以斜向移动吗？

我建议一个简单的纯 x/y 运动和：

// map dimension is nx in first dimension and ny in second dimension here
void monster_vision(int player_x, int player_y)
    {
    for (int i=0; i<nx; ++i) 
      for (int j=0; j<ny; ++j) {
         map[player_x][player_y] == std::abs(player_x-i) + std::abs(player_y-j);
}

Answer 2

改变

if (map[player_x][player_y] == '.')

到

if (map[player_x][player_y] == '.' || map[player_x][player_y]-char('0') > score)

在更快访问的情况下也设置新分数，而不仅仅是在第一次访问的情况下。

Answer 3

这里是一个使用

std::deque

实现 bfs 的实现：

  void computeDistances(Pos pos) {
    reset();
    std::deque<std::tuple<Pos, C>> q;
    q.emplace_back(pos,0);
    while (!q.empty()) {
      auto const [p, score] = q.front();
      q.pop_front();
      if (!(*this)[p]) {
        (*this)[p] = score;
        if (p[0] > 0) q.emplace_back(Pos{static_cast<C>(p[0]-1),p[1]}, score+1);
        if (p[1] > 0) q.emplace_back(Pos{p[0],static_cast<C>(p[1]-1)}, score+1);
        if (p[0] < N-1) q.emplace_back(Pos{static_cast<C>(p[0]+1),p[1]}, score+1);
        if (p[1] < N-1) q.emplace_back(Pos{p[0],static_cast<C>(p[1]+1)}, score+1);
      }
    }
    (*this)[pos] = 0;
  }

它依赖于这些帮手：

  using C = std::uint16_t;
  using Pos = std::array<C,2>;
  std::array<std::array<C, N>, N> map;

  C& operator[](Pos pos) {
    return map[pos[0]][pos[1]];
  }

  void reset() {
    std::fill(begin(map[0]), end(map[0]), 0);
    std::fill(begin(map), end(map), map[0]);
  }

请注意，您不需要“#”字符形式的边界守卫，因为您知道棋盘的大小。相反，零分用于标记未访问的单元格。不幸的是，这引入了很多分支条件，可以进一步改进。

这是一个完整的演示.