c# - (Euclidean Shortest Path) 检测平面内障碍物的角点

Question

问题历史/起源

最近，我在 Twitch.TV 上偶然发现了播放经典游戏速通的玩家的 channel 。其中一个演奏了The Legend of Zelda - A Link to the Past .我看到了许多低效的 Action ，我开始怀疑——如果有世界地图数据——是否有可能编写一个执行完美速通的机器人。一个经常出现的子问题是找到平面中两点之间的最短路径，我认为这是一个非常有趣的问题，因此我开始对此进行更多研究。

已发布类似的 Stackoverflow 问题

How can I can I detect the shortest path from point A to point B without going through the obstacles?

Finding path obstacles in a 2D image

Algorithm to detect corners of paper sheet in photo

……还有更多

其中的答案总是为 super 问题(如下所述)提供不同的解决方案，例如使用基于网格的方法，而不是我感兴趣的实际子问题(如下所述)。

super 问题解决方案描述

给定平面上的两个点 X=(x1,x2) 和 Y=(y1,y2) - 从 X< 的最短路径是什么 到 Y 如果飞机包含路径可能无法通过的障碍物/区域？

不同/更直观假设林克不能翻墙或穿过灌木丛，从他的当前位置到 map 上第二个红点的最短路径是什么？

这个问题通常被称为 Eucledian Shortest Path Problem可以在Polynomial time中解决在二维情况下。太棒了!

为了实现这一点，一个所谓的Visibility Graph用 V= {X,Y} U {"Corner-Points of obstacles}" 构建。当且仅当可以从 P 到 Q 而不跨越任何障碍物绘制一条直线时，在点 P 和 Q 之间插入边。每条边由 Eucledian Distance 加权在它连接的点之间。

在上面的示例中，可见性图表看起来像这样。为了便于阅读，我省略了一些边和权重。阴影区域表示障碍。

然后可以在可见性图上使用开发人员最喜欢的最短路径算法计算最短路径。

子问题描述

让我们首先将障碍定义为不可逾越地形的连续区域。如何找到所有障碍物所需角点的最少数量(以及角点的坐标)以构建执行最短路径计算所需的最小可能可见性图？

对于矩形障碍物，很容易找到拐角，因为只有少数尖锐边缘，如草图所示......

...或应用于游戏场景

但是，一旦障碍物具有对角线“正面”，由于诱导的拼图图案(无论角度如何)，获得角点就变得非常重要。下面的截图说明了这个问题:左边的图片显示了哪些坐标点应该被识别为角，而右边的图片显示了由于对角线的“拼图”模式，额外的点将被插入的位置。

现在的问题是:如何排除/防止这些不必要的角点(被插入到)可能非常大的可见性图中？

Answer 1

如何查看每个点周围的点，如果您发现两个完全相反方向但不穿过“实体”的点，那么您就知道您实际上有一个移除候选对象。在删除任何点之前对所有点执行此操作，然后一次性删除所有这些候选点。

这将处理水平、垂直和对角线。如果将半径扩展到两个或更多，您还可以检测到其他角度“线”上的冗余点。

时间复杂度几乎是 O(n)(当 n 是点数时)，因为您将检查每个点周围固定数量的点以找到移除候选对象，例如:

要检查每个点的半径 1 - 4 个相邻点对:

123
4X5
678

=> 检查对 (1 8), (2 7), (3 6), (4 5)

半径 2 - 每个点检查 8 个相邻点对:

 1 2
34567
 8X9
ABCDE
 F G

=> 检查对 (1 G), (2 F), (3 E), (4 D), (5 C), (6 B), (7 A), (8 9)