FirstWins路径查找算法解析

在开发游戏引擎的几年中，发现网络上关于路径查找的资源非常丰富，尤其是A*算法。然而，更想自己创造一种算法，因此设计了FirstWins路径查找算法。希望能发现它很有用。

演示程序

演示程序和代码是用VB 2010编写的，但是'FirstWins'路径查找的逻辑并不局限于特定程序。应该能够将这里的逻辑适应到任何计算机语言。

以下是演示程序界面的简短描述：

• 设置或移除墙壁：启用此选项后，可以在游戏场地上“绘制”或“擦除”墙壁。左键点击创建墙壁，右键点击擦除墙壁。
• 设置起点或终点：启用此选项后，可以在游戏场地上放置起点(A)和终点(B)。左键点击设置点A，右键点击设置点B。
• 排序分支：这意味着所有活动分支将根据它们与终点的距离进行排序，搜索将从最接近终点的分支开始。
• 全优先级：这意味着路径查找将从满足分支全优先级的分支开始。

算法描述

为了到达终点，'FirstWins'路径查找依赖于两个简单的规则——'优先级设置'和'优先级切换'。以下是执行路径查找的所有步骤：

步骤1：优先级设置是简单的移动方向指令。让设置两个点；起点和终点：

示例：

• start.x = 4, end.x = 10, x的优先级是 X+
• start.y = 3, end.y = 1, y的优先级是 Y-
• 分支的优先级是：X+,Y-

步骤2：检查空闲位置。如果优先级是 X+,Y-，那么分支将朝向东北方向，让找到所有符合此优先级的空位。

如所见，为了成为下一个分支的合适位置，正方形不需要满足优先级相同的方向。只要有一个轴的方向相同就足够了。

接下来的子步骤是检查优先级点是否空闲，例如，没有墙壁、其他物体，或者这些点没有被同一家族的其他路径搜索分支检查过。

接下来，分支到空闲位置。每个新分支都记得其父位置。这很重要，因为这些数据将帮助追溯到终点，当该分支到达终点时。

可选步骤3：如果没有任何优先级位置空闲，那么分支将切换其优先级。'+'将变为'-'，'-'将变为'+'，然后再次执行步骤2，但这次使用新的优先级。

最终步骤 - 停用。不活动的分支是没有合适的位置到达，或者其分支已经散布到合适的位置，没有更多的操作可以执行的分支。如果分支到达了终点，它也将停用所有其他分支，并检索到终点的路径。

示例

'FirstWins'寻找路径的图形示例：

'FirstWins'路径查找块图：

根据算法的逻辑，第一个到达终点的分支是相对最短的路径。然而，解决方案可能并不总是与数学上最短的路径一致。'分支优先级'是使路径查找过程更加可控和分支较少的机制。

在应用的演示程序中实现的算法非常基础，有时会出现错误和不准确的情况，其主要目的是展示算法确实有效，仅此而已。大多数与演示程序中的路径查找相关的问题都与编码有关，而不是'FirstWins'算法。相信，由于其简单性，'FirstWins'可以在许多方面得到增强和优化。任何来自建议和想法都非常受欢迎。