3

我有一个包含外墙（标记为 W）、环境块（E）、开放空间（o）和活动点（A）的网格（下面的示例）。目前，该网格存储在 [,] 中，所有数据都与给定点相关联。我试图确定一个活动点是否被封闭（定义为无法到达网格的顶部，因为它被环境块阻挡），但我很难找到解决这个问题的简单方法。我知道我可以实现 A* 并且使用所有示例代码或多或少会很容易，但我认为对于这样一个看似微不足道的操作来说，性能损失真的是必要的或值得的。

W--Top Of Grid--W
W---------------W
W-EEAEE-----EEE-W
WEEEEEEE-EEEEAEEW
WEEEEEEE--EEEEEEW
WEEEEEEEE-AEEEEEW
WWWWWWWWWWWWWWWWW

向下第三行的 A 可以绘制到网格顶部的路径，最后一行的 A 也可以，但是向下第四行的 A 不能。我不关心实际路径，我只需要确定对象是否被困。这个项目的最佳解决方案是什么？

对于它的价值，它是一个用于回合制网格游戏的 C# 项目，如果有帮助的话。

预先感谢您提供的任何帮助，非常感谢。

4

1 回答 1

2

我认为顶部网格的洪水填充将解决所有问题。从顶部泛滥，然后检查哪个“A”被泛滥:)

该算法保证在整个过程中只访问每个节点一次，在最坏的情况下不能更快。而且用任何语言都可以很容易地实现。

这是来自维基百科的算法：

 Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.

...它看起来像：（来自维基）

洪水填充

简而言之：

  1. 从顶部网格泛滥，“W”和“E”阻挡泛洪（就像图片中的黑色单元格）
  2. 洪水过后，检查有多少包含“A”的地方被洪水淹没。
于 2012-08-02T08:48:29.233 回答