策略游戏求助：战争迷雾

Question

我正在尝试制作一个实时策略游戏，比如星际争霸或帝国时代。我的地图需要支持大约1500个实体。我的问题在于如何实现战争迷雾而不会使游戏卡顿。我最初尝试的方法是每次单位移动时简单地计算其周围区域的距离，但正如我所预料的那样，这会导致卡顿，因为许多单位会不断移动。如果有人知道更快的战争迷雾算法，请帮忙。地图将基于瓦片，并存储在数组中。

- Stas Jaro

Answer 1

一个相当基本的实现可以如下所示：

• 对于每个方块 (i,j)，都有一个值v[i,j]表示其可见性。任何低于某个特定阈值的值都在雾中。

• 使用以下两个步骤定期更新这些值（注意：除了非常特殊的情况外，此类事物不需要高精度或高频率）：

  1. 模糊当前地图v[i,j]
  2. 对于每个单位，将值v[unit_i, unit_j]增加一个固定量。如果一个单位在一个方块上（无论有多少个），还可以添加一个固定量。

- Howard

---

我并没有完全理解。我理解您的基本概念，我认为最终会使用它，但是您所说的“模糊地图”是什么意思？Unit_i和unit_j应该是什么？ - Stas Jaro

@stas，模糊处理更多地是将滤镜应用于您的数组（例如，请参见http://en.wikipedia.org/wiki/Box_blur）。您可能已经在图像中看到过它，其中图像被涂抹。使用unit_i和unit_j，我只想描述单位实际站立的地图块。 - Howard

为什么我要模糊它呢？ - Stas Jaro

为了在一定半径内影响可见性。例如，在一维情况下，单位将把地图设置为 [0,0,0,1,0,0,0]，一步之后看起来像 [0,0,0.25,1,0.25,0,0]。因此，根据阈值，您可以有一个可见的地图瓦片（其中单位位于）或三个。模糊是一种“扩散”单位到整个地图上而不实际计算距离的简单方法。 - Howard

Answer 2

另一个解决方案：对实体进行分组。

您可以创建一个相对简单的网格，甚至是四叉树。给定坐标 (x,y)，它允许您在 log(d) 步骤内找到所有在同一（或相邻）单元格中的实体，其中 d 是您的四叉树深度。

通过一些绳索的帮助（从叶节点指向相邻单元格的指针），可以在常数时间内访问邻居。

要了解给定地图块是否可见，只需查询您的四叉树即可。

此外，四叉树可能对与战争迷雾无关的其他任务有用。例如，您可能想找到最接近给定坐标 (x,y) 的“工人”，或者您想对区域中的所有单位应用某些区域伤害。

- CygnusX1

---

仍然写自己的东西（例如游戏）是学习新知识的绝佳机会 :) 只需谷歌或查看维基百科即可入门。有很多编程资源可供利用。 - CygnusX1

Answer 3

每次一个单位移动，你可以假设它移动到相邻的方格，对吧？在这种情况下，你也可以假设该单位的可见区域沿着同一方向移动了一个方格，因此你应该没有问题确定或更新一个应该可见的区域。根据单位的视野半径，只更新需要更新的值可能可以节省大量CPU功率。

问题在于模糊区域 - 可能有更多的单位看到同一个方格，但可以通过执行Howard建议的操作来解决。

- Robert Kolner

---

可能会起作用，但是我必须存储前一个点每个单位，因为它们不是按瓦片移动，而是瓦片就像地图块一样，它们可以在其中和之间移动。 - Stas Jaro

这实际上取决于瓷砖的大小。如果单位只在移动到另一个瓷砖时更新FOW，而不是在瓷砖内部更新，那么我在这里写的内容对您帮助不大。 - Robert Kolner