青蛙旅行是如何選擇旅行路徑的?旅行青蛙相信有很多小伙伴都有不少疑問，網(wǎng)上的攻略很多也語焉不詳，那么實際上到底是怎么樣的呢?有這樣一個程序員大佬，花了五個晚上逆向游戲程序邏輯，提取各種數(shù)據(jù)。得出了下面的結(jié)論。

呱是如何選擇旅行路徑的?

程序內(nèi)建東、西、南、北四個區(qū)域，呱會選擇一個地區(qū)旅行

每個區(qū)域的設(shè)計都是一個連通的無向圖 (connected undirected graph)，而呱的旅行路線就是在圖上某兩個點之間走出一條路徑 (p ath)。

通過逆向手段，提取出了程序中的信息，花了一些時間用 Graphviz 生成了每個地圖的樣子。

圖上的每個節(jié)點 (vertex) 都代表了一個地點。每個地點都有可能被蛙經(jīng)過，并觸發(fā)一些事件。

除了普通的地點外，還有四種特殊的地點會影響呱旅行的路線：

START 起始點(帽綠色)

GOAL 目的地(桃紅色)

P ATH 途徑地(橘黃色)

DETOUR 繞路地(淺黃色)

連接節(jié)點之間的是邊 (edge)，代表連接地點的路，這些路上也會觸發(fā) 遇上伙伴、拍攝照片 等事件。

每次開始旅行的時候，根據(jù)老母親(?)打包的物品，呱都會：

選擇一個地區(qū)

攜帶特點食物或道具可以影響到區(qū)域的選擇，有些物品可以增加特定地區(qū)的被選概率，甚至可以直接確定選擇的地區(qū)，具體每件物體效果會在后面提到。

選擇目的地

同樣地，在一個區(qū)域內(nèi)的目的地的選擇取決于所攜帶的道具。

選擇途徑地

途徑地由目的地決定，每個地點都有對應(yīng)的途徑地，代碼中對此的描述是當(dāng)?shù)氐目h府/交通樞紐。

選擇繞路地

這個很有意思，猜測作者的目的是為了讓旅途更有多樣性，每次路途會額外添加幾個地區(qū)內(nèi)繞路地點，攜帶物品對決定繞路地似乎沒有影響。

生成經(jīng)過所有地點的旅行路徑

運用了圖論很經(jīng)典的連通圖找最短路徑 Dijkstra 算法，配合途徑地和繞路地的邏輯，最終計算出旅行路徑。

目的地是怎么選擇的?

在決定了地區(qū)之后，具體目的地的選擇就和攜帶的道具相關(guān)，每個物品的概率疊加就能獲得每個地點被選擇的概率。

旅行青蛙常見問題解答

旅行青蛙蛙蛙出門沒有四葉草和鈴鐺要緊嗎?

旅行青蛙入門攻略 青蛙旅行超詳細(xì)玩法詳解

旅行青蛙四葉草獲取途徑/方法

旅行青蛙開啟提醒通知

旅行青蛙收拾桌子出門便當(dāng)盒/背包準(zhǔn)備方法