FirstWins 路径查找算法
基于方向优先级的路径查找算法
引言
几年前，在我开发游戏引擎时，我产生了编写这个算法的想法。网络上关于寻路算法的资源非常多，尤其是 A* 算法，但我希望能自己实现一些东西，所以就有了它。希望你能觉得它有用。
演示程序
所附带的演示程序和代码是用 VB 2010 编写的，但是，“FirstWins”寻路算法的逻辑并不局限于特定语言。你应该可以将其改编到任何计算机语言中。
下面是关于演示程序界面的简要说明
设置或移除墙壁
启用此选项后，你可以“绘制”或“擦除”墙壁
- 鼠标左键 = 创建墙壁
- 鼠标右键 = 擦除墙壁
设置起点或终点
启用此选项后，你可以在游戏区域放置起点（A）和终点（B）
- 鼠标左键 = 设置点 A
- 鼠标右键 = 设置点 B
排序分支
这意味着所有活动的分支将按其到终点的距离进行排序，搜索将从离终点最近的分支开始。
完全优先
这意味着寻路将从满足分支完全优先条件的分支开始。
描述
为了到达终点，“FirstWins”寻路算法依赖于 2 个简单规则——“优先设置”和“优先切换”。以下是寻找路径所需执行的所有步骤
步骤 1：优先设置是简单的移动方向指令
我们设置两个点；一个起点和一个终点
如果 start.x > end.x，则 x 的优先方向是 X-，因为要到达 end.x，我们需要减小 start.x 的值。反之，如果 start.x < end.x，则 x 的优先方向是 X+。如果 start.x = end.x，则优先方向为 0，我们无需更改 start.x 的值即可到达终点。Y 轴也适用相同的规则。
示例
- 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”寻路框图
结论
根据算法逻辑，第一个到达终点的分支就是相对最短路径。然而，该解决方案可能并不总是与数学上的最短路径一致。“分支优先”机制使寻路过程更受控制，分支也更少。
所附演示程序（PathfindingDemo）中算法的实现非常基础，有时会存在 bug 和不准确之处，其主要目的是展示算法确实有效，仅此而已。演示程序中寻路的大部分问题与代码有关，而不是与“FirstWins”算法本身有关。我相信，由于其简单性，“FirstWins”可以从许多方面进行增强和优化。非常欢迎您提出任何建议和想法。
本次发布的新内容
2012 年 12 月 15 日
- 首次发布
最新发布 - 2013 年 3 月 17 日
- 增加了路径优化功能，该功能可减少所发现路径中的“跳跃”和“下降”。
- 添加了“跟踪对象”用于测试路径
界面和系统更改
新的菜单集位于图形界面的右下角附近
时间间隔：
移动寻路跟踪对象的速度：值越低，对象移动越快。
测试路径
单击此按钮，使用跟踪对象穿越目标节点来测试生成的路径
优化路径
“优化路径”功能可减少目标路径中的波动，即使路径线变直
