algorithm - 什么是查找两个对象是否在 2D 网格中连接的好算法？

Question

我目前正处于开发游戏的早期阶段，在该游戏中，玩家通过将单个系统（货舱、武器控制、船员宿舍等）放置在 2D 网格上来建造宇宙飞船。船的“根”部分是船长坐下指挥周围人的桥。

我需要的是一种算法，可以检查以确保每个部件都直接连接到桥上，或者通过连接到可以追溯到桥的另一系列部件。

自然地，部分将被删除，因为它没有以某种方式连接到网桥。

有人知道可以做到这一点的算法吗？

Answer 1

这是您想要的一种简单的“洪水填充”方法

• 将点 A 添加到名为scanning

• 还创建一个名为的集合checked（在开始时将其留空）

• 而未找到 B 点且集合scanning不为空：

• 对于scanning集合中的每个点，请执行以下操作：
• 如果是 B 点，则停止。
• 从scanning集合中删除点并添加到checked
• 对于每个邻居，如果它没有被添加到checked 或scanning然后将邻居添加到scanning