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

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

那么有沒有一種不需要手動預(yù)設(shè)內(nèi)容的隨機算法，只需要調(diào)整一些參數(shù)，它就可以生成出看起來美觀，也不會產(chǎn)生死圖，還能確保生成的刷怪點位置合理的方法呢？今天我們就將深入地探索一下一個尋路算法——Dijkstra算法，只要稍微調(diào)整一下使用的“手法”，這個奇妙的、被用于尋找最短路徑算法就會成為一個極其強大的隨機地圖生成算法，并且對精通于設(shè)計數(shù)學(xué)函數(shù)的數(shù)值策劃來說，可以輕松地用幾個參數(shù)就玩轉(zhuǎn)這個“Dijkstra隨機地圖生成法”。

01 深度解讀Dijkstra算法

我們通常了解的Dijkstra是一個尋找2點之間最短路徑的算法，這個算法往往與他的兩個特殊形態(tài)Floyd算法和AStar算法齊名。

Dijkstra算法本身非常好理解，即在地圖中的某個點作為起點，然后向四面八方展開尋找，每進入一個格子都累加一個Cost值，然后對于地圖上每一個格子都算出走進這個格子的最短路徑，即Cost值最小的從起點點通向通向這個格子路線，最終遍歷完所有的格子之后，獲得最短的路線。如圖所示：

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

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

圖為《火紋》的角色可移動范圍顯示

在戰(zhàn)棋SLG中，角色的移動范圍可以通過Dijkstra算法得出，畢竟每一個角色的行動力是有限的，并且地圖中的地形會影響行動力，同時敵方角色的臨近格子行動力消耗也會進一步提高，所以Dijkstra算法被巧妙地用于“不尋找目標點，而是尋找到行動力足以達到的點”。

到這里是最基礎(chǔ)的Dijkstra算法的介紹，接著我們需要更進一步的去思考一些問題。我們通常使用Dijkstra算法的時候，檢查單元格的規(guī)則都是“周圍的格子”，但是假如有些格子是一個傳送門入口，走進去以后可以從n個出口中選擇一個，這時候?qū)ぢ匪惴ㄐ枰龀鍪裁锤淖兡?？如圖所示：

如果綠色是起點，紅色是終點，通常我們的尋路法就會產(chǎn)生出一條黑線的路線，但是當(dāng)我們?yōu)榈貓D上增加了傳送門入口（藍色圓圈），走進這個傳送門，就可以從3個橙色圓圈的傳送門出口中任意選擇一個作為出口的時候，問題就出現(xiàn)了，因為藍色的格子一下子代表了3個其他格子。因此我們可以發(fā)現(xiàn)，事實上我們只把Dijkstra算法用于Tilebased游戲?qū)ぢ返臅r候，理所應(yīng)當(dāng)?shù)挠X得“周圍的格子”作為“下一個格子”是這個算法的一部分，但實際上，對于Dijkstra算法而言，如何選取“下一個格子”，是需要設(shè)計的一部分。

如上圖所示，Dijkstra算法的“下一個格子”其實是“下一個node”，也就是根據(jù)一個規(guī)則加入到判斷列表里的，如果是傳送門他應(yīng)該是這樣的：

由于走進B相當(dāng)于走進B1或B2或B3，所以我們打斷了B這個“不存在的格子”，鏈接了B1\B2\B3。這正是Dijkstra算法的核心之一——“路徑的節(jié)點規(guī)則”。

02 隨機地圖的準備工作

在了解了Dijkstra算法的性質(zhì)之后，我們就要開始準備巧妙地使用它來生成隨機地圖了。但是在這之前，我們還需要一些步驟，這些隨機地圖生成的步驟其實是不需要Dijkstra算法的。

在這里我們需要數(shù)值策劃設(shè)計的第一個內(nèi)容是：地圖信息=f(迷宮,層數(shù))，這個函數(shù)的本意也就是根據(jù)地圖的難度系數(shù)，來算出當(dāng)前地圖的一些信息，這些信息至少要包含：

• 房間的個數(shù)：我們知道大多roguelike地圖是需要房間的，房間個數(shù)越多，則迷宮對于玩家來說難度越大。因此對于我們生成地圖來說，房間的個數(shù)也是一個核心數(shù)據(jù)，不知道房間個數(shù)就沒法生成難度合適的隨機地圖了。
• 每個房間的最大、最小尺寸：這個尺寸的寬度高度是可以不同的，但是我們最好認為他們是相等的，這樣可以讓房間的位置相對更加均勻一些。而最小尺寸應(yīng)該是小于最大尺寸的，如果相等一樣會影響一些隨機的效果。
• 房間之間的連線最小單元格數(shù)：房間之間還是需要有路線連接的，路線的最小長度是可以要求的，這應(yīng)該是個自然數(shù)，如果是0，則可能生成出墻壁緊挨著的2個房間，會影響美觀，當(dāng)然這也可以在生成之后進行補正，比如消除一堵墻壁等。
• 房間之間的連線最大單元格數(shù)：這應(yīng)該是一個大于最小tile數(shù)的存在，這樣才有了隨機的余地。
• 房間怪物數(shù)信息：這個信息將被用于生成怪物的刷新點。
• 最小經(jīng)過房間數(shù)：我們知道Roguelike地圖可能會有這樣的需求，就是我到達這一層之后，至少要走過多少個房間才能遇到去一下層的入口。如果這個值是0，則有可能來到這一層的第一個房間就有下樓的樓梯；當(dāng)然這個數(shù)字肯定是不能大于等于房間數(shù)的，不然就走不通了，建議是取房間數(shù)的一半。

當(dāng)以上地圖數(shù)據(jù)得出之后，我們就可以確定出本層地圖橫向縱向需要的“塊”數(shù)，所謂的“塊”即每個隨機房間出現(xiàn)的范圍。為了確保地圖盡可能接近正方形范圍（這僅僅是為了“美觀”），可以這樣：橫向的塊數(shù)=（“房間的個數(shù)”的平方根）向上取整，縱向的塊數(shù)=（總房間數(shù)/橫向塊數(shù)）向上取整。也就是說，比如是7個房間的地圖，在這里會被劃分為3x3個塊，如圖所示：

我們可以很簡單的算出一個“塊”的單元格數(shù)：橫向格數(shù)=房間最大橫向格數(shù)+橫向連線最大tile數(shù)；縱向格數(shù)=房間最大縱向格數(shù)+縱向連線最大tile數(shù)。而每個塊的格數(shù)乘以塊數(shù)，就能算出地圖橫向和縱向總共有多少個單元格。

當(dāng)確定完單元格之后，我們要解決一個問題就是塊數(shù)>房間數(shù)的問題，如果是等于，就沒有什么問題，但是如果是大于，我們就首先要隨機取出（總塊數(shù)-房間數(shù)）行（或者列），然后在這些行（或者列）中取出1個“塊”刪除掉，如圖所示（圖中取行）：

我們隨機了第1行和第3行，各去掉一個“塊”。這樣房間數(shù)正好是2+3+2=7個。然后我們對于每一行進行隨機分塊，這個分塊的過程，確定了每一個“塊”擁有的橫向、縱向單元格數(shù)量，這個最小單元格數(shù)應(yīng)該不小于房間的最小寬度（高度）+橫向（縱向）最短連接單元格數(shù)。均攤之后的塊很可能是這樣的：

從上圖我們可以看出，切塊之后，“塊”與“塊”之間的連接圖也產(chǎn)生了（上圖中只列出了1號“塊”的連接關(guān)系），而每個“塊”中僅有1個房間，所以“塊”的連接關(guān)系，也是房間的“初步連接關(guān)系”，之所以是初步的，因為我們后期還會打斷一些連接。

確定完連接之后，我們就要隨機找出每一個“塊”中的一個隨機點，作為這個“塊”的房間的“中心點”，這個中心點的范圍，至少得符合房間最終能在“塊”內(nèi)，且盡可能符合最長最短鏈接單元格的要求。到這里每一個“塊”的屬性、也就是每個房間的基礎(chǔ)數(shù)據(jù)就產(chǎn)生了，這個數(shù)據(jù)中包含了：

• 房間id：這個房間的id
• “中心點”坐標：這是用于生成房間的核心數(shù)據(jù)。
• 鏈接房間數(shù)組：這個房間可以連接到的房間的id數(shù)組。

到此，我們的準備工作也就完成了，接下來就要開始生成房間的重要算法了。首先我們回顧一下，一個數(shù)值策劃要在這里具體做一些什么樣的工作呢？

1. 根據(jù)迷宮和層數(shù)算出地圖信息：這是用于隨機地圖生成的最基本數(shù)據(jù)。
2. 切塊算法：盡管在本文里舉了一個例子，但是這并不是惟一的例子，我們當(dāng)然可以用其他數(shù)學(xué)方法來確定切塊的方式和房間連線的方式，總之最后可以獲得每個“塊”的數(shù)據(jù)就行了。

03 妙用Dijkstra生成“房間”

當(dāng)我們完成了每一個“塊”的數(shù)據(jù)之后，就可以遍歷每個“塊”，對每個塊進行房間的生成了。首先我們要拿出：

房間的中心點，這是我們用Dijkstra算法的“尋路起點”。

房間的尺寸：取寬度、高度中較大的一個，然后將其除以2后向下取整，作為一個Cost值，賦值給起點。

有了這兩個信息之后，我們開始“取周圍8個格子作為下一格”的規(guī)則，作為Dijkstra算法的“下一格”規(guī)則。和戰(zhàn)棋類SLG搜索移動范圍差不多，而唯一的不同則是，這個單元格的Cost消耗量是隨機的，而這個隨機并不是無腦的隨機1-2，他應(yīng)該有一個算法，比如越接近起點的，越不容易是2，這是最基礎(chǔ)的規(guī)則，如圖所示，是這樣“尋路”的：

Cost=f(...)就是這個隨機算法，依據(jù)是這個房間（“塊”）的信息，當(dāng)然也可以傳入更多的需要的信息，這取決于游戲的設(shè)計。

之所以要用Dijkstra算法去生成房間，基礎(chǔ)的原因有2個：

其一是房間最終不一定是矩形的，當(dāng)然如果cost都是1，那么最后是一個正方形的，這是特殊情況，通常我們還是希望房間不是矩形的，所以想需要利用Cost的算法配合Dijkstra算法產(chǎn)生出“非矩形”的房間，如圖所示：

把cost=0（紅色）的格子當(dāng)做墻壁，就生成了房間。當(dāng)然我們只要調(diào)整一下這個Cost=f(...)的函數(shù)，就可以發(fā)生有趣的變化：

比如y方向上更容易抽到高cost，就可以讓地圖更接近扁的：

再比如當(dāng)格子的y值大于起點y值（下方格子），則cost=初始cost：

可見，只要調(diào)整Cost=f(...)，就能讓地圖的形狀接近設(shè)計的預(yù)期效果，而這里還會追加一個問題，房間內(nèi)的阻擋和刷怪點是如何產(chǎn)生的。事實上我們已經(jīng)有了從中心展開的規(guī)則，那么刷怪點和阻擋完全是可以符合：IsPoint = f(x, y, cost)這樣一個數(shù)學(xué)函數(shù)的，即是否這個點刷怪或者阻擋，由參數(shù)x,y和這個格子的剩余cost值來決定的。比如“所有Cost=3的格子中抽取隨機3個作為刷怪點”，這些刷怪點就會接近于中間，這樣玩家走進房間，不論是從哪個方向走過來的，都不至于遭遇“被怪貼臉”的情況（當(dāng)然也并不是所有游戲第一時間都需要刷怪的）。

到此，一個房間的生成就完成了，我們從這個生成過程中得出了：

• 房間的形狀：整個房間占了那些格子，其中哪些是阻擋單元格。
• 刷怪點：房間里的刷怪單元格，至于上面刷什么怪，不是房間說了算的，是由樓層信息、難度等算出刷什么怪，這里只是提供給怪物他們的出生位置。

在這步，數(shù)值策劃的核心工作就是：

• 每個格子的Cost算法，即Cost=f(...)的函數(shù)，包括其參數(shù)以及計算過程。
• 刷怪點、阻擋的算法，根據(jù)每個格子的情況，算出當(dāng)前格子是阻擋還是刷怪點。
• 只要算法設(shè)計得好，就可以用來生成任何玩法的Roguelike游戲的地圖，甚至用在橫版動作游戲的地圖生成也不是問題。

04 妙用Dijkstra生成“路線”

當(dāng)房間生成完之后，我們可以用AStar來生成2個房間之間的連線單元格，這是非常簡單的一件事情，但是在此之前，我們還有一個工作。還記得開始的時候說的“最小經(jīng)過房間數(shù)”嗎？滿足這個需求的方式，是把房間之間的一些連線關(guān)系打斷，以確保路線能達標。

首先我們要將房間（或者原本的“塊”）之間的連線確定，制作成“地圖”：

然后我們通過這個地圖，得出隨機的起點和終點，如果“最小經(jīng)過房間數(shù)>0”，則代表起點和終點必須是不同的2個格子，假設(shè)“最小經(jīng)過房間數(shù)”=3，起點為3，終點為6，那么我們就必須打斷一些連線：

我們需要打斷的是，讓起點到終點距離會<3的關(guān)鍵鏈接。在打斷了關(guān)鍵鏈接之后，我們可以在不關(guān)鍵的位置也打斷幾根，這個打斷的依據(jù)依然可以是一個數(shù)值策劃設(shè)計的算法。

總結(jié)

到此，一層樓的隨機地圖就算是產(chǎn)生完了，房間、怪物、阻擋、寶箱等等都可以通過Dijkstra算法的妙用來算出，而這一切的關(guān)鍵，在于數(shù)值策劃對于一些數(shù)學(xué)函數(shù)的設(shè)計。

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