對于Roguelike類游戲而言，隨機(jī)地圖是一個(gè)非常核心的元素，而在很多Diablolike游戲中，隨機(jī)地圖也依然表現(xiàn)得非常活躍。我們可能看到過很多隨機(jī)地圖的生成算法，包括且不限于GDC以及GMTK等知名的游戲交流媒體的分享。但是絕大多數(shù)隨機(jī)算法都會(huì)要求手工預(yù)設(shè)關(guān)卡的大多內(nèi)容，包括Diablo等著名的游戲在內(nèi)，都是預(yù)先拼好了一些地圖，然后只是在隨機(jī)位置隨機(jī)挑選了這些地圖中的幾個(gè)用上。畢竟這樣做的好處是：地圖看起來是美的，而且不會(huì)有死圖（即發(fā)生入口無法通向出口的情況），并且刷怪位置相對合理。

隨機(jī)地圖生成算法，是Roguelike游戲的重要課題

那么有沒有一種不需要手動(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ī)地圖生成算法，并且對精通于設(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值，然后對于地圖上每一個(gè)格子都算出走進(jìn)這個(gè)格子的最短路徑，即Cost值最小的從起點(diǎn)點(diǎn)通向通向這個(gè)格子路線，最終遍歷完所有的格子之后，獲得最短的路線。如圖所示：

五角星是起點(diǎn)，叉是終點(diǎn)，格子里的數(shù)字就是進(jìn)入格子的最短路徑的Cost

大多情況下，Dijkstra的開銷都很大，所以在Greedy Best-First的思路結(jié)合之下，產(chǎn)生了AStar尋路。但是Dijkstra并沒有因?yàn)锳Star的出現(xiàn)就退出游戲開發(fā)的舞臺(tái)，他依然在戰(zhàn)棋類SLG中活躍：

圖為《火紋》的角色可移動(dòng)范圍顯示

在戰(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í)際上，對于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ù)越多，則迷宮對于玩家來說難度越大。因此對于我們生成地圖來說，房間的個(gè)數(shù)也是一個(gè)核心數(shù)據(jù)，不知道房間個(gè)數(shù)就沒法生成難度合適的隨機(jī)地圖了。
• 每個(gè)房間的最大、最小尺寸：這個(gè)尺寸的寬度高度是可以不同的，但是我們最好認(rèn)為他們是相等的，這樣可以讓房間的位置相對更加均勻一些。而最小尺寸應(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è)。然后我們對于每一行進(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è)“塊”，對每個(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ù)值策劃對于一些數(shù)學(xué)函數(shù)的設(shè)計(jì)。

當(dāng)深入了解一個(gè)算法的實(shí)際工作原理之后，思考并修改他的用法，從而做到一些“非大眾化”的用途，往往在游戲設(shè)計(jì)中是可以起到奇效的，關(guān)鍵看設(shè)計(jì)師有沒有能力運(yùn)用好——“沒有低等的法術(shù)，只有低等的法師”。