對(duì)于 Roguelike 類游戲而言，隨機(jī)地圖是一個(gè)非常核心的元素，而在很多 Diablolike 游戲中，隨機(jī)地圖也依然表現(xiàn)得非?；钴S。我們可能看到過很多隨機(jī)地圖的生成算法，包括且不限于 GDC 以及 GMTK 等知名的游戲交流媒體的分享。但是絕大多數(shù)隨機(jī)算法都會(huì)要求手工預(yù)設(shè)關(guān)卡的大多內(nèi)容，包括 Diablo 等著名的游戲在內(nèi)，都是預(yù)先拼好了一些地圖，然后只是在隨機(jī)位置隨機(jī)挑選了這些地圖中的幾個(gè)用上。畢竟這樣做的好處是：地圖看起來是美的，而且不會(huì)有死圖（即發(fā)生入口無法通向出口的情況），并且刷怪位置相對(duì)合理。
那么有沒有一種不需要手動(dòng)預(yù)設(shè)內(nèi)容的隨機(jī)算法，只需要調(diào)整一些參數(shù)，它就可以生成出看起來美觀，也不會(huì)產(chǎn)生死圖，還能確保生成的刷怪點(diǎn)位置合理的方法呢？今天我們就將深入地探索一下一個(gè)尋路算法 ——Dijkstra 算法，只要稍微調(diào)整一下使用的“手法”，這個(gè)奇妙的、被用于尋找最短路徑算法就會(huì)成為一個(gè)極其強(qiáng)大的隨機(jī)地圖生成算法，并且對(duì)精通于設(shè)計(jì)數(shù)學(xué)函數(shù)的數(shù)值策劃來說，可以輕松地用幾個(gè)參數(shù)就玩轉(zhuǎn)這個(gè)“Dijkstra 隨機(jī)地圖生成法”。
01、深度解讀 Dijkstra 算法
我們通常了解的 Dijkstra 是一個(gè)尋找 2 點(diǎn)之間最短路徑的算法，這個(gè)算法往往與他的兩個(gè)特殊形態(tài) Floyd 算法和 AStar 算法齊名。
Dijkstra 算法本身非常好理解，即在地圖中的某個(gè)點(diǎn)作為起點(diǎn)，然后向四面八方展開尋找，每進(jìn)入一個(gè)格子都累加一個(gè) Cost 值，然后對(duì)于地圖上每一個(gè)格子都算出走進(jìn)這個(gè)格子的最短路徑，即 Cost 值最小的從起點(diǎn)點(diǎn)通向通向這個(gè)格子路線，最終遍歷完所有的格子之后，獲得最短的路線。如圖所示：
大多情況下，Dijkstra 的開銷都很大，所以在 Greedy Best-First 的思路結(jié)合之下，產(chǎn)生了 AStar 尋路。但是 Dijkstra 并沒有因?yàn)?AStar 的出現(xiàn)就退出游戲開發(fā)的舞臺(tái)，他依然在戰(zhàn)棋類 SLG 中活躍：
在戰(zhàn)棋 SLG 中，角色的移動(dòng)范圍可以通過 Dijkstra 算法得出，畢竟每一個(gè)角色的行動(dòng)力是有限的，并且地圖中的地形會(huì)影響行動(dòng)力，同時(shí)敵方角色的臨近格子行動(dòng)力消耗也會(huì)進(jìn)一步提高，所以 Dijkstra 算法被巧妙地用于“不尋找目標(biāo)點(diǎn)，而是尋找到行動(dòng)力足以達(dá)到的點(diǎn)”。
到這里是最基礎(chǔ)的 Dijkstra 算法的介紹，接著我們需要更進(jìn)一步的去思考一些問題。我們通常使用 Dijkstra 算法的時(shí)候，檢查單元格的規(guī)則都是“周圍的格子”，但是假如有些格子是一個(gè)傳送門入口，走進(jìn)去以后可以從 n 個(gè)出口中選擇一個(gè)，這時(shí)候?qū)ぢ匪惴ㄐ枰龀鍪裁锤淖兡?？如圖所示：
如果綠色是起點(diǎn)，紅色是終點(diǎn)，通常我們的尋路法就會(huì)產(chǎn)生出一條黑線的路線，但是當(dāng)我們?yōu)榈貓D上增加了傳送門入口（藍(lán)色圓圈），走進(jìn)這個(gè)傳送門，就可以從 3 個(gè)橙色圓圈的傳送門出口中任意選擇一個(gè)作為出口的時(shí)候，問題就出現(xiàn)了，因?yàn)樗{(lán)色的格子一下子代表了 3 個(gè)其他格子。因此我們可以發(fā)現(xiàn)，事實(shí)上我們只把 Dijkstra 算法用于 Tilebased 游戲?qū)ぢ返臅r(shí)候，理所應(yīng)當(dāng)?shù)挠X得“周圍的格子”作為“下一個(gè)格子”是這個(gè)算法的一部分，但實(shí)際上，對(duì)于 Dijkstra 算法而言，如何選取“下一個(gè)格子”，是需要設(shè)計(jì)的一部分。
如上圖所示，Dijkstra 算法的“下一個(gè)格子”其實(shí)是“下一個(gè) node”，也就是根據(jù)一個(gè)規(guī)則加入到判斷列表里的，如果是傳送門他應(yīng)該是這樣的：
由于走進(jìn) B 相當(dāng)于走進(jìn) B1 或 B2 或 B3，所以我們打斷了 B 這個(gè)“不存在的格子”，鏈接了 B1\B2\B3。這正是 Dijkstra 算法的核心之一 ——“路徑的節(jié)點(diǎn)規(guī)則”。
02、隨機(jī)地圖的準(zhǔn)備工作
在了解了 Dijkstra 算法的性質(zhì)之后，我們就要開始準(zhǔn)備巧妙地使用它來生成隨機(jī)地圖了。但是在這之前，我們還需要一些步驟，這些隨機(jī)地圖生成的步驟其實(shí)是不需要 Dijkstra 算法的。
在這里我們需要數(shù)值策劃設(shè)計(jì)的第一個(gè)內(nèi)容是：地圖信息 = f (迷宮，層數(shù))，這個(gè)函數(shù)的本意也就是根據(jù)地圖的難度系數(shù)，來算出當(dāng)前地圖的一些信息，這些信息至少要包含：
房間的個(gè)數(shù)：我們知道大多 roguelike 地圖是需要房間的，房間個(gè)數(shù)越多，則迷宮對(duì)于玩家來說難度越大。因此對(duì)于我們生成地圖來說，房間的個(gè)數(shù)也是一個(gè)核心數(shù)據(jù)，不知道房間個(gè)數(shù)就沒法生成難度合適的隨機(jī)地圖了。
每個(gè)房間的最大、最小尺寸：這個(gè)尺寸的寬度高度是可以不同的，但是我們最好認(rèn)為他們是相等的，這樣可以讓房間的位置相對(duì)更加均勻一些。而最小尺寸應(yīng)該是小于最大尺寸的，如果相等一樣會(huì)影響一些隨機(jī)的效果。
房間之間的連線最小單元格數(shù)：房間之間還是需要有路線連接的，路線的最小長度是可以要求的，這應(yīng)該是個(gè)自然數(shù)，如果是 0，則可能生成出墻壁緊挨著的 2 個(gè)房間，會(huì)影響美觀，當(dāng)然這也可以在生成之后進(jìn)行補(bǔ)正，比如消除一堵墻壁等。
房間之間的連線最大單元格數(shù)：這應(yīng)該是一個(gè)大于最小 tile 數(shù)的存在，這樣才有了隨機(jī)的余地。
房間怪物數(shù)信息：這個(gè)信息將被用于生成怪物的刷新點(diǎn)。
最小經(jīng)過房間數(shù)：我們知道 Roguelike 地圖可能會(huì)有這樣的需求，就是我到達(dá)這一層之后，至少要走過多少個(gè)房間才能遇到去一下層的入口。如果這個(gè)值是 0，則有可能來到這一層的第一個(gè)房間就有下樓的樓梯；當(dāng)然這個(gè)數(shù)字肯定是不能大于等于房間數(shù)的，不然就走不通了，建議是取房間數(shù)的一半。
當(dāng)以上地圖數(shù)據(jù)得出之后，我們就可以確定出本層地圖橫向縱向需要的“塊”數(shù)，所謂的“塊”即每個(gè)隨機(jī)房間出現(xiàn)的范圍。為了確保地圖盡可能接近正方形范圍（這僅僅是為了“美觀”），可以這樣：橫向的塊數(shù) =（“房間的個(gè)數(shù)”的平方根）向上取整，縱向的塊數(shù) =（總房間數(shù) / 橫向塊數(shù)）向上取整。也就是說，比如是 7 個(gè)房間的地圖，在這里會(huì)被劃分為 3x3 個(gè)塊，如圖所示：
我們可以很簡單的算出一個(gè)“塊”的單元格數(shù)：橫向格數(shù) = 房間最大橫向格數(shù) + 橫向連線最大 tile 數(shù)；縱向格數(shù) = 房間最大縱向格數(shù) + 縱向連線最大 tile 數(shù)。而每個(gè)塊的格數(shù)乘以塊數(shù)，就能算出地圖橫向和縱向總共有多少個(gè)單元格。
當(dāng)確定完單元格之后，我們要解決一個(gè)問題就是塊數(shù) > 房間數(shù)的問題，如果是等于，就沒有什么問題，但是如果是大于，我們就首先要隨機(jī)取出（總塊數(shù)-房間數(shù)）行（或者列），然后在這些行（或者列）中取出 1 個(gè)“塊”刪除掉，如圖所示（圖中取行）：
我們隨機(jī)了第 1 行和第 3 行，各去掉一個(gè)“塊”。這樣房間數(shù)正好是 2+3+2=7 個(gè)。然后我們對(duì)于每一行進(jìn)行隨機(jī)分塊，這個(gè)分塊的過程，確定了每一個(gè)“塊”擁有的橫向、縱向單元格數(shù)量，這個(gè)最小單元格數(shù)應(yīng)該不小于房間的最小寬度（高度）+ 橫向（縱向）最短連接單元格數(shù)。均攤之后的塊很可能是這樣的：
從上圖我們可以看出，切塊之后，“塊”與“塊”之間的連接圖也產(chǎn)生了（上圖中只列出了 1 號(hào)“塊”的連接關(guān)系），而每個(gè)“塊”中僅有 1 個(gè)房間，所以“塊”的連接關(guān)系，也是房間的“初步連接關(guān)系”，之所以是初步的，因?yàn)槲覀兒笃谶€會(huì)打斷一些連接。
確定完連接之后，我們就要隨機(jī)找出每一個(gè)“塊”中的一個(gè)隨機(jī)點(diǎn)，作為這個(gè)“塊”的房間的“中心點(diǎn)”，這個(gè)中心點(diǎn)的范圍，至少得符合房間最終能在“塊”內(nèi)，且盡可能符合最長最短鏈接單元格的要求。到這里每一個(gè)“塊”的屬性、也就是每個(gè)房間的基礎(chǔ)數(shù)據(jù)就產(chǎn)生了，這個(gè)數(shù)據(jù)中包含了：
房間 id：這個(gè)房間的 id
“中心點(diǎn)”坐標(biāo)：這是用于生成房間的核心數(shù)據(jù)。
鏈接房間數(shù)組：這個(gè)房間可以連接到的房間的 id 數(shù)組。
到此，我們的準(zhǔn)備工作也就完成了，接下來就要開始生成房間的重要算法了。首先我們回顧一下，一個(gè)數(shù)值策劃要在這里具體做一些什么樣的工作呢？
1、根據(jù)迷宮和層數(shù)算出地圖信息：這是用于隨機(jī)地圖生成的最基本數(shù)據(jù)。
2、切塊算法：盡管在本文里舉了一個(gè)例子，但是這并不是惟一的例子，我們當(dāng)然可以用其他數(shù)學(xué)方法來確定切塊的方式和房間連線的方式，總之最后可以獲得每個(gè)“塊”的數(shù)據(jù)就行了。
03、妙用 Dijkstra 生成“房間”
當(dāng)我們完成了每一個(gè)“塊”的數(shù)據(jù)之后，就可以遍歷每個(gè)“塊”，對(duì)每個(gè)塊進(jìn)行房間的生成了。首先我們要拿出：
房間的中心點(diǎn)，這是我們用 Dijkstra 算法的“尋路起點(diǎn)”。
房間的尺寸：取寬度、高度中較大的一個(gè)，然后將其除以 2 后向下取整，作為一個(gè) Cost 值，賦值給起點(diǎn)。
有了這兩個(gè)信息之后，我們開始“取周圍 8 個(gè)格子作為下一格”的規(guī)則，作為 Dijkstra 算法的“下一格”規(guī)則。和戰(zhàn)棋類 SLG 搜索移動(dòng)范圍差不多，而唯一的不同則是，這個(gè)單元格的 Cost 消耗量是隨機(jī)的，而這個(gè)隨機(jī)并不是無腦的隨機(jī) 1-2，他應(yīng)該有一個(gè)算法，比如越接近起點(diǎn)的，越不容易是 2，這是最基礎(chǔ)的規(guī)則，如圖所示，是這樣“尋路”的：
Cost=f (...) 就是這個(gè)隨機(jī)算法，依據(jù)是這個(gè)房間（“塊”）的信息，當(dāng)然也可以傳入更多的需要的信息，這取決于游戲的設(shè)計(jì)。
之所以要用 Dijkstra 算法去生成房間，基礎(chǔ)的原因有 2 個(gè)：
其一是房間最終不一定是矩形的，當(dāng)然如果 cost 都是 1，那么最后是一個(gè)正方形的，這是特殊情況，通常我們還是希望房間不是矩形的，所以想需要利用 Cost 的算法配合 Dijkstra 算法產(chǎn)生出“非矩形”的房間，如圖所示：
把 cost=0（紅色）的格子當(dāng)做墻壁，就生成了房間。當(dāng)然我們只要調(diào)整一下這個(gè) Cost=f (...) 的函數(shù)，就可以發(fā)生有趣的變化：
比如 y 方向上更容易抽到高 cost，就可以讓地圖更接近扁的：
再比如當(dāng)格子的 y 值大于起點(diǎn) y 值（下方格子），則 cost = 初始 cost：
可見，只要調(diào)整 Cost=f (...)，就能讓地圖的形狀接近設(shè)計(jì)的預(yù)期效果，而這里還會(huì)追加一個(gè)問題，房間內(nèi)的阻擋和刷怪點(diǎn)是如何產(chǎn)生的。事實(shí)上我們已經(jīng)有了從中心展開的規(guī)則，那么刷怪點(diǎn)和阻擋完全是可以符合：IsPoint = f (x, y, cost) 這樣一個(gè)數(shù)學(xué)函數(shù)的，即是否這個(gè)點(diǎn)刷怪或者阻擋，由參數(shù) x,y 和這個(gè)格子的剩余 cost 值來決定的。比如“所有 Cost=3 的格子中抽取隨機(jī) 3 個(gè)作為刷怪點(diǎn)”，這些刷怪點(diǎn)就會(huì)接近于中間，這樣玩家走進(jìn)房間，不論是從哪個(gè)方向走過來的，都不至于遭遇“被怪貼臉”的情況（當(dāng)然也并不是所有游戲第一時(shí)間都需要刷怪的）。
到此，一個(gè)房間的生成就完成了，我們從這個(gè)生成過程中得出了：
房間的形狀：整個(gè)房間占了那些格子，其中哪些是阻擋單元格。
刷怪點(diǎn)：房間里的刷怪單元格，至于上面刷什么怪，不是房間說了算的，是由樓層信息、難度等算出刷什么怪，這里只是提供給怪物他們的出生位置。
在這步，數(shù)值策劃的核心工作就是：
每個(gè)格子的 Cost 算法，即 Cost=f (...) 的函數(shù)，包括其參數(shù)以及計(jì)算過程。
刷怪點(diǎn)、阻擋的算法，根據(jù)每個(gè)格子的情況，算出當(dāng)前格子是阻擋還是刷怪點(diǎn)。
只要算法設(shè)計(jì)得好，就可以用來生成任何玩法的 Roguelike 游戲的地圖，甚至用在橫版動(dòng)作游戲的地圖生成也不是問題。
04、妙用 Dijkstra 生成“路線”
當(dāng)房間生成完之后，我們可以用 AStar 來生成 2 個(gè)房間之間的連線單元格，這是非常簡單的一件事情，但是在此之前，我們還有一個(gè)工作。還記得開始的時(shí)候說的“最小經(jīng)過房間數(shù)”嗎？滿足這個(gè)需求的方式，是把房間之間的一些連線關(guān)系打斷，以確保路線能達(dá)標(biāo)。
首先我們要將房間（或者原本的“塊”）之間的連線確定，制作成“地圖”：
然后我們通過這個(gè)地圖，得出隨機(jī)的起點(diǎn)和終點(diǎn)，如果“最小經(jīng)過房間數(shù) > 0”，則代表起點(diǎn)和終點(diǎn)必須是不同的 2 個(gè)格子，假設(shè)“最小經(jīng)過房間數(shù)”=3，起點(diǎn)為 3，終點(diǎn)為 6，那么我們就必須打斷一些連線：
我們需要打斷的是，讓起點(diǎn)到終點(diǎn)距離會(huì) < 3 的關(guān)鍵鏈接。在打斷了關(guān)鍵鏈接之后，我們可以在不關(guān)鍵的位置也打斷幾根，這個(gè)打斷的依據(jù)依然可以是一個(gè)數(shù)值策劃設(shè)計(jì)的算法。
總結(jié)
到此，一層樓的隨機(jī)地圖就算是產(chǎn)生完了，房間、怪物、阻擋、寶箱等等都可以通過 Dijkstra 算法的妙用來算出，而這一切的關(guān)鍵，在于數(shù)值策劃對(duì)于一些數(shù)學(xué)函數(shù)的設(shè)計(jì)。
當(dāng)深入了解一個(gè)算法的實(shí)際工作原理之后，思考并修改他的用法，從而做到一些“非大眾化”的用途，往往在游戲設(shè)計(jì)中是可以起到奇效的，關(guān)鍵看設(shè)計(jì)師有沒有能力運(yùn)用好 ——“沒有低等的法術(shù)，只有低等的法師”。
本文來自微信公眾號(hào)：千猴馬的游戲設(shè)計(jì)之道 （ID：baima21th），作者：猴與花果山
廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。