青蛙旅行是如何选择旅行路径的?旅行青蛙相信有很多小伙伴都有不少疑问，网上的攻略很多也语焉不详，那么实际上到底是怎么样的呢?有这样一个程序员大佬，花了五个晚上逆向游戏程序逻辑，提取各种数据。得出了下面的结论。

呱是如何选择旅行路径的?

程序内建东、西、南、北四个区域，呱会选择一个地区旅行

每个区域的设计都是一个连通的无向图 (connected undirected graph)，而呱的旅行路线就是在图上某两个点之间走出一条路径 (p ath)。

通过逆向手段，提取出了程序中的信息，花了一些时间用 Graphviz 生成了每个地图的样子。

图上的每个节点 (vertex) 都代表了一个地点。每个地点都有可能被蛙经过，并触发一些事件。

除了普通的地点外，还有四种特殊的地点会影响呱旅行的路线：

START 起始点(帽绿色)

GOAL 目的地(桃红色)

P ATH 途径地(橘黄色)

DETOUR 绕路地(浅黄色)

连接节点之间的是边 (edge)，代表连接地点的路，这些路上也会触发 遇上伙伴、拍摄照片 等事件。

每次开始旅行的时候，根据老母亲(?)打包的物品，呱都会：

选择一个地区

携带特点食物或道具可以影响到区域的选择，有些物品可以增加特定地区的被选概率，甚至可以直接确定选择的地区，具体每件物体效果会在后面提到。

选择目的地

同样地，在一个区域内的目的地的选择取决于所携带的道具。

选择途径地

途径地由目的地决定，每个地点都有对应的途径地，代码中对此的描述是当地的县府/交通枢纽。

选择绕路地

这个很有意思，猜测作者的目的是为了让旅途更有多样性，每次路途会额外添加几个地区内绕路地点，携带物品对决定绕路地似乎没有影响。

生成经过所有地点的旅行路径

运用了图论很经典的连通图找最短路径 Dijkstra 算法，配合途径地和绕路地的逻辑，最终计算出旅行路径。

目的地是怎么选择的?

在决定了地区之后，具体目的地的选择就和携带的道具相关，每个物品的概率叠加就能获得每个地点被选择的概率。

旅行青蛙常见问题解答

旅行青蛙蛙蛙出门没有四叶草和铃铛要紧吗?

旅行青蛙入门攻略 青蛙旅行超详细玩法详解

旅行青蛙四叶草获取途径/方法

旅行青蛙开启提醒通知

旅行青蛙收拾桌子出门便当盒/背包准备方法