本帖大部分篇幅将以寻路模式最简单的哈奇为例。哈奇的寻路表如图。这些是哈奇一步可到达的目的点。黄色数字代表路径的编号。

从最简单的例子开始了解搜索过程：图中一共5个点位L1, L2, C, R1, R2

可达集合可以看作是一个优先队列（实际情况更复杂，后面再讲）
初始在可达集合中加入C（当前位置）
第一步从队列中移除C，并加入临近的L1和R1。由于C可以到达R1和L1，并且R1的编号比L1小（根据上面的路径表），因此R1先入队，L1后入队
第二步队列中移除首项R1，加入R2，此时队列中还有L1和R2
第三步移除L1，加入R2
第四步移除R2
第五步移除L2
最重要的是出队的顺序，依次为：C, R1, L1, R2, L2

前排

快住手 这不是链表课

路线选择与出队顺序密切相关。从出队序列中移除初始位置C后：
如果出队序列的长度n≤5，那么始终选择最后一个出队的点位。例如下面图中哈奇下一步必定走到第三个出队的点位

如果出队序列的长度n>5，那么第5到第n-1个点位均有4%的概率，其余概率分配到最后一个点位。
出队序列的长度最高计算到24。例如在下面的开阔地带，哈奇下一步可能走到方框中的任意一个位置（概率都是4%）

闲逛第一定律：如果可达地点的数目不高于5，那么闲逛的目的地是唯一确定的

例如这样的构造，只有5个点位，那么哈奇每一步走到哪里都是固定的，不会受到随机数的影响

等一个飞行动物的液锁。

水锁：如果在搜索时遇到深水（达到0.35倍默认量的可达液体）即将出位，则立即停止计算，队列作废，并选取目的地（不包括深水点位）
例子1：C即将出队，C是深水，所以停止计算，出队序列为空，闲逛失败留在原地

例子2：深水R1即将出队，停止计算，出队序列为C，停在原地

例子3：深水4即将出队，停止计算，出队序列为C, 1, 2, 3，那么下一步必定走到3（后续的5，6点位不再计算）

下面介绍一个特殊点位：建造中的门。所有动物永远不会闲逛到建造中的门中。
在点位即将出队时，如果它是一个建造中的门，则直接忽略（不加入出队序列中，不占用队列上限）。

例如这张图中，出队序列是1, 2, 3, 4，则必定走到4

岔路：开始加速了
如图，橙色数字代表**入队**顺序，那么如何计算出队顺序呢？

优先队列本质上是一个堆。在堆顶元素出队时，队尾元素来到堆顶，并且重新整理堆(heaplify)。这里的知识不是重点，可以自行百度堆的实现算法。
这里的出队顺序为1-6-5-4-3-2，哈奇有4%的概率走到3号位，96%的概率走到2号位。

需要注意的是，只有距离相同的点位共享一个堆（对于哈奇而言如此，但其他动物更复杂），例如7号位是不参与2，3号堆的。所以出队顺序的5,6,7号位是2,3,7，下一步2,3各有5%的概率，7号位为90%

应用1：螃蟹泡澡

螃蟹闲逛时的出队顺序是1,2,3，下一步闲逛目的地是3号位，简单推理可知螃蟹永远不会以岸上作为闲逛的终点，也就是说大部分时间泡在水里。

哈奇部分施工完毕，等会发陆地动物和飞行动物的

太抽象了，我直接后排欢呼开香槟，然后躺床上等大佬把模块端上来