用Swift编写Dijkstra算法的正确方法

剧透警报：您根本不写！

⭐️⭐️⭐️️⭐️⭐
嗨！ 此帖已移至新博客！ 来到Fivestars.blog以获得最新文章！
⭐️⭐️⭐️️⭐️⭐

上周，我写了关于如何在Swift中编写著名的Dijkstra算法的代码：本文是其后续内容。

我的原因

我没有写上一篇文章，而是花时间做文章研究：我所有的Metro Metro应用程序都实现了类似的算法。

在本文中，我将向您展示为什么您不需要利用我的相同方法，即利用Apple提供的工具并以更少的努力获得相同的结果 （同时获得其他好处）。

介绍GameplayKit

在Apple的数十种框架中，有GameplayKit：无论您的应用程序是否为游戏，该框架始终可供您使用。

但是什么是GameplayKit？ 我很高兴你问！ 我将让Apple的GameplayKit指南为您解答：

GameplayKit是用于在iOS，OS X和tvOS中构建游戏的基础工具和技术的集合。 构建，发展和维护复杂的游戏需要精心计划的设计-GameplayKit提供了一些架构工具，可帮助您以最小的努力设计模块化，可扩展的游戏架构。

哇，这个框架听起来很多东西！

GameplayKit核心

让我们使用分而治之范例更好地理解此GameplayKit，以下是其主要核心（摘自Apple的GameplayKit指南）：

1. 随机化 。 使用标准算法的这些强大，灵活的实现方式作为多种游戏机制的构建块。
2. 实体和组件 。 通过在此架构上构建，设计更多可重用的游戏代码。
3. 状态机 。 使用此体系结构可以解开游戏设计中的复杂程序代码。
4. Minmax策略家 。 为基于回合的游戏和AI玩家对象创建模型，并使用该模型计划最佳移动。
5. 寻路 。 用图形描述游戏世界，允许GameplayKit规划游戏角色遵循的最佳路线。
6. 代理人，目标和行为 。 使用此模拟可以使游戏角色根据高级目标移动自己并对周围环境做出反应。
7. 规则系统 。 将游戏设计与可执行代码分开以加快游戏开发周期，或实施模糊逻辑推理以向游戏中添加逼真的行为。

等等…又是什么第五点？

5.寻路 。 将[…]世界描述为图表 ，[…] 规划最佳路线 […]

这听起来很像我们正在尝试做的事情！ 让我们深入研究。

GameplayKit 寻路

如果您阅读了完整的寻路介绍，您会发现我们可以在三种情况下使用它：

• 情况1 —被障碍物打断的连续空间

• 情况2-离散的二维网格，其中唯一有效的位置是具有整数坐标的位置

• 情况3-离散位置及其之间的连接的集合。

哇！ 第三种情况听起来恰恰是我们想要做的！ 🙌🏻
让我们实现它！

GameplayKit实体

图形

首先，GameplayKit希望我们创建一个新的图形，这是通过创建一个新的GKGraph实例来完成的：

节点数

其次，我们需要定义节点：再次，GameplayKit为其覆盖了GKGraphNode类：

请不要忘记将它们添加到我们的图表中：

节点连接

当我为Connections创建了一个不同的类时，GameplayKit采取了一种更为简单的方法，并且仅提供了一个GKGraphNode方法addConnection(to:[GKGraphNode], bidirectional: Bool) ：

GameplayKit的方法比我的简单得多：这是因为Apple的框架假定每个连接权重始终相同 （我将在本文结尾处讨论这一点）。

Dijkstra的算法

现在我们已经定义了整个图！ 唯一缺少的是最短路径查找器算法：如何从nodeA转到nodeE ？ 好…

是的，那是一行。

等一下 而已？ 是的， findPath方法返回一个数组，该数组描述了从起始节点到目标节点的路径，如果两个节点之间没有路径，则返回一个空数组。 🎉🎉

完整的代码

为了让您了解GameplayKit的惊人之处，以下是我们到目前为止编写的完整代码（您可以在Xcode / Swift Playground中运行它）：

现在，我们的整个应用程序比我的shortestPath算法需要更少的代码行，这框架多么强大！ 🚀🚀🚀

加权连接

GameplayKit的缺点之一是节点之间缺少加权连接。

我已经解决了这个问题，并找到了一个优雅的最小解决方案：子类化GKGraphNode并重写cost(to node: GKGraphNode)方法。 这是我的快速实施方法。

简而言之，每个节点都将其连接成本存储在其（新的） travelCost属性中：其他所有内容保持不变

最后说明

GameplayKit的妙处在于我们不知道它使用哪种shortestPath算法：可能是Dijkstra的算法，可能是Bellman-Ford的算法，或者可能完全是其他算法。

而且， 您不必在意 ，这已经由Apple的非常有才华的人来照顾，问题得以解决：通过让他们照顾好这些，我们可以专注于开发更好的产品 💯。

在相同的氛围下：您是否想知道Swift在调用sort时使用哪种算法？

结论

本文和我之前的文章都向您展示了一种在代码中实现shortestPath finder算法的方法。

我之所以比后者更喜欢后者的主要原因是，因为此选项的大多数核心代码都是由数十个人组成的，这些人常年工作，以使其尽可能快和高效地运行，而始终利用最新的Apple硬件等优势。

如果您自己编写代码，那么您就是在维护代码：没有其他人可以帮助您改进它，如果有错误，则只能找到并修复它。 如果您从事其他工作，那么该代码将永远无法改进（ 除非它是开源的 ）。

如果这篇文章有一个要点，那就这样：
利用提供给您的工具：您对自己的依赖越少，您的功能就越强大。

在下一篇文章中找到您！ 👋🏻