这个自定义的“寻路”算法有什么问题？

Question

（我希望这不是重复的，因为我遇到的许多问题都不适合我的需要）我正在开发一个基于 2D 网格的游戏，有 2 个带网格的玩家。有两个玩家：蓝色和红色，每个人在单元格中放置一块石头。所以我想找到一条穿过所有具有相同颜色的单元格回到起点的路径，但前提是至少有一个包含对手石头的单元格。从上面的屏幕截图中可以看出：右上角的红色石头不构成有效路径。那些在中心的人也没有形成一条路径，即使那应该是一条路径。我能够找到一条路径，但它以某种方式坏了，它没有按预期工作。

Answer 1

解决此类问题的或多或少的标准方法是“扫描线”算法。为简单起见，假设我们正在寻找包裹红点的蓝色路径。（您可以同时或第二次处理包裹蓝色点的红色路径，但您可以稍后解决。）

您可以搜索“扫描线算法”以查看它们在相关应用程序中的工作方式。在维基百科页面也不错。

对于这个问题，扫描线是一组 y 间隔。它使用最左边（最少 x）个蓝点进行初始化。每组垂直相邻的蓝点都有一个间隔。每个间隔代表通过潜在蓝色多边形的垂直切片。

算法的其余部分是设计当扫描线向右移动一个位置时更新扫描线所需的规则，增加 x。这将是更新每个间隔的问题。当一个步骤发现一组不连续的垂直相邻点时，会添加一个新的间隔。在某些情况下，间隔会“消失”，因为潜在的多边形边界死胡同（想想 C 形）。在其他情况下，它们会“合并”，因为在相应的 x 坐标处，有一组 1 个或多个垂直相邻的连接点。在其他情况下，多边形将通过最终的一组 1 个或多个垂直相邻点成功完成。

细节会很繁琐，但不难通过案例分析来解决。

为了追踪成功的多边形，区间可以包括两条前面的点链：多边形的上边界和下边界。

最后一个考虑是成功闭合的多边形是否包含至少一个红点。但这很容易。如果对于任何 x 坐标，表示多边形的区间用红点括起来，那么答案是肯定的。这可以记录为在间隔中维护的初始假布尔值，每次看到这样的红点时都会设置为真。成功关闭多边形后，检查标志以查看是否应使用它。

通过使用合适的数据结构：例如间隔树，对于非常大的网格，上述所有内容都可以变得高效。但是如果网格比较小，使用简单的列表应该没问题。无论如何，首先考虑使用扫描线列表对其进行原型设计，然后根据需要使用更复杂的数据结构进行优化。