前言： 当我开始这个项目时，除了了解基本概念外，我从未使用或研究图论。 我认为为这个庞大的棋盘游戏绘制图表可以用来计算站点之间的最佳路线，但大多数情况下似乎很有趣。 我一直在使用Python，并且 NetworkX 模块看起来易于使用且成熟。 这个故事是关于我制作图表的过程以及我在此过程中学到的所有知识。
在棋盘游戏“高边疆”中，玩家建造火箭飞船以旅行并探视太阳系。 木板上的空间代表着地点（像月球或小行星那样去的地方），危险（如辐射或金星的酸云之类的东西），拉格朗日点（两个大物体之间的稳定重力囊），最重要的是，洋红色燃烧空间，这代表了加速燃料消耗的增量V成本。 每个大型机体还具有相应的飞越空间，使玩家可以“自由燃烧”一些数量，以通过他们随后在转身遇到的洋红色空间。
自然地，我们可以想象将空间描述为代表板的一组节点 （及其连接，称为edge ，可以是有向的也可以是无向的 ）。 我们可以通过加权相应的边来定义在两个节点之间遍历的成本。 从这些简单的公理中出现了图论的全部学科，可以将其应用于互联网，语言学，道路或社会网络，甚至量子场论。
对于High Frontier，该图需要是一个有向图，因为尽管大多数连接都是双向的（或实际上是无向的），但有些表示航空制动的路径严格是单向的。 后来，我还弄清楚该图将需要是一个多图，因为在某些情况下，同一两个节点之间既有常规的着陆边又是航空制动的边。
G = nx.MultiGiGraph（）
当玩家沿着代表各种轨迹的路线在棋盘上移动时，他们可能会遇到两条路线的交叉点。 直行穿过交叉点是代表滑行的自由移动。 玩家还可以花费2次灼伤来改变方向，并在路口旋转以继续移动该弯道。 或者，他们可以在相交处结束转弯，然后在随后的转弯中沿任何方向免费继续行驶。
我的直觉是将这些交点表示为图上的节点。 毕竟，它们是玩家可能会停下来的真正空间，并且可以通过我一直在Paint中跟踪的图像上的标签很容易地识别（带有一些非常宽松的命名约定-看起来，命名很难…）。
不幸的是，这注定要失败。 我以为我可以通过在直线路径上的每个节点之间创建一条边来模拟通过交叉点的直线路径的“自由”度（并很快意识到我在绘制图形时应该隐藏这些补充边缘，以免其变得更不易读）。 最终，这将在另一个相交的节点处创建自由边，而这并没有包含枢轴成本。
大约在同一时间，我为自己的理解感到困惑，因为边缘是图形的加权接口，而不是节点。 但是在高边疆，烧伤就是空间 。 我的模特全错了吗？
add_all_edges（’Flyby Luna Purple’，’HI_P0’，’HI_P1’，’HI_P2’，’HI_P3’，’Burn Purple 1’）
板上的空间是图形中的节点是很自然的，尝试以其他任何方式查看它都是具有挑战性的。 但是，如果我想计算任何最短的路径，则需要正确地完成这一部分，最好是在我对板子图做得太深之前。
当谈到霍曼交叉口时，将路线边缘作为节点确实非常好：很容易表示直行还是枢转。 图没有任何“直线”概念，只是连通性，因此，相交比看起来复杂得多。
如上所述，每个双向交叉点需要六个边缘和四个节点，以表示玩家可能经过的所有方式。 即使在游戏中玩家可以在十字路口停下来（并且我自己也没有在十字路口放置节点），但在计算成本时没有必要。 每个边都有刻录成本（2）和游戏回合成本（1）的属性，因此我可以根据这两个条件来计算最佳路线。
我还发现我确实可以对节点进行加权，因此板上的大多数空间都可以保持节点，这是一种缓解。 只有路线的交叉点会稍微复杂一些，但是我为我编写了一个精美的功能来照顾这一点，并在必要时在标注板上添加了一些基本指标。
add_turns（’Burn Lagrange Earth-Luna L3’，’HI_Venus_Signpost’，free =（’N’），exclude =（’S’），east =’Burn Lagrange Sol-Venus L4’，north =’Lagrange Sol-Venus L1 ‘）
为了计算图中节点之间的最短路径，有几种可用的算法比简单的蛮力要好。 Dijkstra的算法是已知最快的算法，但需要非负权重。 但是，请记住，木板上有许多可以自由燃烧的行星和较大卫星的Flyby空间。 例如，“飞越地球”空间可燃烧+2次； 我会在-2烧伤的图表中给它一个费用，因为在路线的尽头，由于飞越奖金，玩家确实少付了2烧伤。
所以，Dijkstra的行不通。 但是，图论已经很成熟，还有其他选择，Bellman-Ford算法（最初由Alfonso Shimbel提出，我指出是因为似乎运气不好他似乎没有被他认可）。重量。
不幸的是，还有另一个问题：负循环。
当我在“最前沿”图的最短路径上运行查询时，Bellman-Ford提出它在我的图中检测到负周期。 有趣的是，检测负周期的存在并知道它在哪里是完全不同的两件事。
向有关stackexchange的旧问题添加奖金后，我能够找到一个可以返回负循环的函数，因此可以在图形上运行它。
>>> find_negative_cycle（G，weight_func = burns_advanced）
[“辐射木星G1”，“飞越木星”，“辐射木星G1”]
什么？ 我们为什么在这里来回走动？
等等，不，太空飞船不能只是在飞行中反转方向 ！ 那是一个负循环！
但这不是图形关心的问题。 我的图是有向的，但是大多数节点都是通过两个方向上的边连接的，因为您当然可以在任何一个方向上走。 但是，您不能单步移动反向。
目前，这个问题仍未解决……我可能会以蛮力解决的方式返回它，但是目前我无法真正计算出包含负飞越奖金的最短路径。
首先，您可能会注意到该图看起来比以前的图表好很多 。 我发现有一种更好的算法，可以使用路径长度成本函数将节点放置在图中的Kamada＆Kawai。
其次，外部太阳系确实使事物倾斜。 实际上，这很有意义，因为“更年期”实际上与其他所有事物都相距甚远，它使图形具有真实的比例感，这是Eklund肯定要考虑的许多游戏规则的逼真度。
这只是内部的太阳系，包括木星：
毫不奇怪，木星的彗星和卫星现在正对着水星和太阳上天飞翔。 密集的相交路线网络散布着许多小行星，因此杂乱无章。
我试图尽我所能进行错误检查，尽管这本身就是一项棘手的任务。 我做的一件事是寻找只有一个邻居但不是站点的节点（因为大多数站点都是终端站点）。 我通过这种方式发现了一些错别字和被遗忘的联系，并且只有少数中度空气制动危险是该练习的例外。
我不确定该图的下一步内容，但是我已经迫不及待想再次玩实际的游戏，因为我对所有的路线和站点都非常熟悉！
