图论同步

当然，戏剧总是在终点线。 显然，建立斜边涉及大量的数学和计算机科学技巧，但一个重要功能就是主要的// TODO ，这才是真正使游戏产生的功能，该功能可以检测玩家何时构造规则的多边形，以便我能够正确地保持得分，我保存到最后。 当然，本来不打算在发布前的最后几天将其压缩到应用程序中的，但是……好吧，这是怎么回事：

在被接受2018年AmazeFest和柏林游戏周之后，我决定以实现斜边为目标。 在这里和那里还有很多事情要做，但是我对游戏的状态感觉很好。 因此，我认为是时候清理（使用程序员的术语进行重构 ）我的ShapeFinder算法，或者说是PolygonFinder算法。 我有一些工作可以检测绘制的多边形，但是，正如我去年夏天在访问慕尼黑时编写了大多数数学实用程序类，并且毫无疑问地回顾了在Englischer Gartens漫长的炎热天气之后，接着是几个巴伐利亚大小的Hofbräus，我认为我可能应该在柏林游戏节周之前及时发布一次代码。 我的临时技术是在线阵列中向后循环，并检查最后几行的长度和角度是否匹配。 很简单，对吧？ 所有多边形具有匹配的边并共享相同的角度。 但是这种方法仅允许玩家通过依次绘制线条来对多边形进行评分。 这不是一个很好的算法，但它是一个占位符，并且在代码中非常孤立，所以我一直在取消其他功能，希望一旦我花了很多时间，就不会花太多时间再次刺中它。 但是现在，随着最后期限的临近，我卷起袖子并开始编码。

因此，我需要解决的问题是最佳地找到遍历我所有绘制的点和线并发现其中所有可能的形状或多边形的最佳方法。

输入图论。

当我快速阅读Minko Gechev最近在JS网络世界中的出色表现时，很明显，我扩展了标题为“ 数学背景”的部分，即图论基础。 哦，对，我记得不久前在Mathigon上看到过，等等，我不是有图论书的pdf版本吗？ 我的直觉告诉我我正在做某事。 因此，我开始尽可能多地阅读有关图论的文章，​​突然间，我感到好像走进了衣柜，走进了纳尼亚。 图论中有很多很棒的东西。 欧拉的公式，不，不是那个，不是，不是，也不是那个，哦，是的，那个关于图形中的面孔的那个。 所有这些酷桥梁问题； 网络和搜索算法以及计算机科学的众多应用…但是，等等，让我们不要分心，我们在这里做几何。 那么图论如何解决我的几何问题？ 好吧，还记得点和线那些纯真的几何定义吗（请参阅上一篇文章）？ 事实证明，它们在图论地下世界中具有秘密的别名。 它们被称为“顶点”和“边缘”，它们共同构成了Graph帮。 而且，随着时间的流逝，每当有人创建一些很酷的几何设计时，他们也在构造一个可以应用图论规则的图。

好吧，总而言之，我花了很多个晚上试图推出自己的准深度-第一本特利-奥特曼-迪克斯特拉的递归-噩梦-多边形搜索算法，希望最终能获得更多的霍夫布鲁斯原来，我一直都坐在解决方案上。

GameplayKit的寻路工具为我们节省了很多时间，这就是为什么此游戏是为iOS制作的。 请参阅下面的文章。

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

剧透警报：您根本不写！

medium.com

最后，我可以用由GameplayKit背后的一些了不起的工程师设计的一些漂亮的数学代替我丑陋的，不易受Hofbräu影响的解决方案（“ 如果不是漂亮，那就不是数学 ”，这也适用于编程）。 有时编写自己的解决方案很令人满意，但有时使用别人制造的锤子砸烂那些讨厌的指甲也很令人满意。 而且，一如既往，我在此过程中学到了很多东西。

这是我偶然发现的众多资源中的一些，这确实让我对数学这个令人惊讶的超酷分支感到兴奋。

图论的温和介绍

如果没有需要解决的问题，那么世界上的许多事情将永远不会存在。

medium.com

揭开深度优先搜索的神秘面纱

一旦您对不同的数据结构有了足够的了解，您就开始对自己进行思考：对，那么……是什么……

开发到

并使用Bently-Ottmann线相交算法检查Swift算法俱乐部和多边形检测。