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

Question

我正在为我的大学编程项目编写一个小型 Roguelike 游戏。我想尝试实现一个简单的寻路机制，其中涉及用从 0 开始向上的数字填充图 block map ，该数字是到玩家的距离。这将使怪物能够找到到达玩家的最短路径。 这是我想出的算法:

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);
}

正如我所说，这只是该功能的单文件草稿， map 的类型为 std::array<std::array<char, map_size>, map_size，最初在边缘和内部填充有 #

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

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

我得到的是:

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

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

Answer 1

这是一个使用 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]);
  }

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

Here is a complete demo .