来刷新新的个人 Dronenet 飞行记录吧

点击上方蓝字关注 Ingress Beijing

自从 Ingress 出了无人机 Dronenet 以后，Agent 的数据统计界面上也出现了一个新的数据：无人机的最远飞行距离。作为一个会写代码的人（大雾），我，便在思考能不能求出全世界范围内无人机的最远飞行距离。说干就干！

首先我们得先得到全球所有 Portal 的数据。这步本来想从 Mission Authoring Tool 下手，但我实在是太懒了不想造重复轮子，于是联系了 @Ingressportalbot 的作者并获得了这方面的数据，共 1.31G，Portal 总数 11475124。这个数字虽然和 Mission Authoring Tool 所得到的官方数据 11500633 还有点差距，但也够全了（数据统计截止到 2020.06.12）

接着就是预处理数据了。因为 Dronenet 的计算和 S2Cell 有关，为了不写任何数据结构，我按每个 Portal 的 S2Cell ID 前十级，将所有 Portals 分开储存在几十万个文件内（你要永远相信 OS 的文件管理系统）。接着写了个十分暴力的并查集，就是对于某一个点 A，画个 500m 半径的圆，并计算出其覆盖到的 S2Cells，然后根据 S2Cells 去找 Portals，设为集合 S，那么 Dronenet 在 Portal A 时便能经过一次移动跳到集合 S 中的任何一个 Portal 上，这样就不用判断球面两点距离了。

好了，我们得到了每个 Portal 可到达的 Portals 集合，然后把每一对互相可到达的 Portals 都连上线，这就是一张无向图啦！我们需要做的就是求所有连通集集合！并查集！完事！

PS：并不是所有的 Portal A 能到达 Portal B，Portal B 都能到达 Portal A 的，但我处理的时候为了方便是直接把单向边处理成无向边的

PPS：500m 不是上限，结合 Portal Key 的预加载区块等操作可以让一次跳跃的最远距离达到  1km 以上，但同样是为了简化问题我并没有考虑这种情况。

在经过了长达 4 个小时的计算之后，我终于得到了全世界 Portals 的连通集。

那么我们就来看看全球前十大 Dronenet 连通集都在哪吧！

第十位：日本，静岡，直径 78.7km

第九位：日本，長野，直径 80.9km

第八位：日本，香川，直径 81.1km

第七位：日本，富山，直径 83.4km

第六位：英国，伦敦，直径 84.2km

第五位：美国，旧金山+圣荷西，直径 86.5km

第四位：美国，洛杉矶，直径 105.3km

第三位：日本，名古屋，直径 120km

第二位：日本，京都＋大坂＋神戸，直径 133.9km

第一位：日本，東京，直径 169.3km

日本前十占了七个……

接着看看中文区情况如何：

第 20 位，台北+桃园，63km

第 22 位，香港+深圳，61km

第 72 位，北京，41km

全球前 100 位的连通集（https://paste.ubuntu.com/p/P4Rn7Jcqtx/）和国内连通集直径 > 9.4km（https://paste.ubuntu.com/p/Kp7rZymrGt/）的集合我都列出来了，需要可以自取~

OK，那么光有连通集还不够，我们还需要知道无人机该怎么飞，而且有人就想知道从家出发最远能飞多远。所以我还写了个定点查询最远飞行距离的工具。比如说我们可以查询下日本东京那条 169.3km 的路是怎么走的：

工具源码和使用方法我会放在 https://github.com/Konano/dronenet-distance-challenge 内。

那么，来刷新新的个人 Dronenet 飞行记录吧！