隨機地圖產生器 - 聖殿英雄傳說 MUD

※ [本文轉錄自 mud 看板 #1R-xocVS ]

作者: laechan (揮淚斬馬雲) 看板: mud
標題: [閒聊] 隨機地圖產生器
時間: Mon Nov 26 17:28:02 2018


網頁好讀版：https://www.ptt.cc/bbs/mud_sanc/M.1543224853.A.20C.html


以前曾寫過相關的東西:

┌───────────────────────────────────┐
│ 文章代碼(AID): #1EjMKNIx (mud) [ptt.cc] [閒聊] 區域產生器 │
│ 文章網址: https://www.ptt.cc/bbs/mud/M.1320510743.A.4BB.html │
└───────────────────────────────────┘

以上面的做法所產生的地圖，有個缺點，就是很難靠程式產生一條
明確的移動路徑(註: 並非指最短路徑)。

在大部份時候這其實沒什麼問題，但有視障玩家曾反映，在這樣的
地圖容易迷路。

因此直覺的想法就是，改成，先產生一條明確的移動路徑，再從這
條路徑上生出複數的分支，以此構成一張地圖，然後將移動路徑標
示在地圖指令上，視障玩家只需讀取移動路徑那一行，就能從地圖
的起點走到地圖的終點。

以下就說明做法。

首先，讓使用者先決定地圖的範圍，例如寬度 10，高度 10，則假
設地圖的最左上角座標是 (0, 0)，那最右下角座標就是 (9, 9)。

(0, 0)
┌────┐
│ │
│ │
│ │
└────┘
(9, 9)

接下來假設將 (0, 0) 當成起點，然後做如下判斷:

random(2)==1 ? nexts=({1,0}) : nexts=({0,1});

它的意思就是說，從 (0, 0) 開始移動，50% 的機率往右走，50%
的機率往下走。假設是往右，那一開始的路徑就如下

x-x

假設是往下，那一開始的路徑就如下

x
|
x

接下來持續做以下的判斷:

while(nexts!=ends) // 迴圈持續執行，直到抵達終點
{
lasts=nexts;
switch(random(4))
{
// 往左或往右移動(y軸座標不變)
case 0: nexts=({nexts[0]+1,nexts[1]}); break;
case 1: nexts=({nexts[0]-1,nexts[1]}); break;

// 往上或往下移動(x軸座標不變)
case 2: nexts=({nexts[0],nexts[1]+1}); break;
case 3: nexts=({nexts[0],nexts[1]+1}); break;
}
}

並且設計不走回頭路:

// 如果移動點=上一座標點時，就重新跑新的點
if(lasts==nexts)
{
nexts=lasts;
continue;
}


我們以範圍 10 x 8 為例，展示某兩次的執行結果:

█　███████　　　　　　　　　　
█　█　　　　　█　　　　　　　　　　
█　█　█████　　　　　　　　　　
█　█　█　　　　　　　　　　　　　　
███　█　　　　　　　　　　　　　　
　　　　█　　　　　　　　　　　　　　
　　　　█　　　　　　　　　　　███
　　　　█　　　　　　　　　　　█　█
█████　███　　　　　　　█　█
█　　　　　█　█　　　　　　　█　█
███　███　███████　█　█
　　█　█　　　　　　　　　█　█　█
　　███　　　　　　　　　███　█
　　　　　　　　　　　　　　　　　　█
　　　　　　　　　　　　　　　　　　█

移動路徑：2s e 2n 3e s 2w 3s 2w s e s e n e n e s 3e s e 3n e 4s
↑
這一行就是給視障朋友看的

█　　　　　　　　　　　　　　　　　　
█　　　　　　　　　　　　　　　　　　
███　　　███　　　　　　　　　　
　　█　　　█　█　　　　　　　　　　
　　███　█　█　　　　　　　　　　
　　　　█　█　█　　　　　　　　　　
　　　　███　█████████　　
　　　　　　　　　　　　　　　　█　　
　　　　　　　　　　　　█████　　
　　　　　　　　　　　　█　　　　　　
　　　　　　　　　　　　█　　　　　　
　　　　　　　　　　　　█　　　　　　
　　　　　　　　█████　　　███
　　　　　　　　█　　　　　　　█　█
　　　　　　　　█████████　█

移動路徑：s e s e s e 2n e 2s 4e s 2w 2s 2w s 4e n e s
↑
這一行就是給視障朋友看的

我們並不是要找「最短路徑」，所以路徑有很多條；地圖範圍越
大，可產生出的路徑就越多，但相對的產生時間就會越久。

接著就以上面的圖為例，我們現在有了明確的起點與終點，也有
了明確的移動路徑(註: 並非指最短路徑)。

然後我們希望以這張圖為基礎，令它產生數條分支。分支的選擇
法我是採:

分支起點: 地圖邊界空白點 例如 (0, 7) 是空白的
分支終點: 地圖上隨機一個非空白點 例如 (3, 3) 不是空白

然後就可以重覆上面的迴圈判斷做法，以下是範例:

原地圖 產生第一條分支後的地圖

█　　　　　　　　　　　　　　　　　　 █　　　███　　　█　　　　　　　　
█　　　　　　　　　　　　　　　　　　 █　　　█　█　　　█　　　　　　　　
███　　　███　　　　　　　　　　 ███　███████　　　　　　　　
　　█　　　█　█　　　　　　　　　　 　　█　　　█　█　　　　　　　　　　
　　███　█　█　　　　　　　　　　 ███████　█　　　　　　　　　　
　　　　█　█　█　　　　　　　　　　 █　　　█　█　█　　　　　　　　　　
　　　　███　█████████　　 █　█████　█████████　　
　　　　　　　　　　　　　　　　█　　 █　█　　　　　█　　　　　　　█
　　　　　　　　　　　　█████　　 ███　　　　　█　　　█████　　
　　　　　　　　　　　　█　　　　　　 　　　　　　　　█　　　█　　　　　　
　　　　　　　　　　　　█　　　　　　 　　　　　　　　█　█　█　　　　　　
　　　　　　　　　　　　█　　　　　　 　　　　　　　　█　█　█　　　　　　
　　　　　　　　█████　　　███ 　　　　　　　　█████　　　███
　　　　　　　　█　　　　　　　█　█ 　　　　　　　　█　█　█　　　█　█
　　　　　　　　█████████　█ 　　　　　　　　█████████　█

移動路徑：s e s e s e 2n e 2s 4e s 2w 2s 2w s 4e n e s
↑
給視障朋友看的這一行是不會變的

這個意思就是說，雖然地圖上產生了一條分支，但視障朋友仍然
可以從原本的起點走原本的移動路徑來抵達原本的終點，走法是
一樣的，不管分支有幾條，都可以照原本的走法。

以下再 demo 第二條分支:

產生第一條分支後的地圖 產生第二條分支後的地圖

█　　　███　　　█　　　　　　　　 █　　　███　　　█　　　　　　　　
█　　　█　█　　　█　　　　　　　　 █　　　█　█　　　█　　　　　　　　
███　███████　　　　　　　　 ███　███████　　　　　　　　
　　█　　　█　█　　　　　　　　　　 　　█　　　█　█　　　　　　　　　　
███████　█　　　　　　　　　　 ███████　█　　　　　　　　　　
█　　　█　█　█　　　　　　　　　　 █　　　█　█　█　　　　　　　　　　
█　█████　█████████　　 █　█████　█████████　　
█　█　　　　　█　　　　　　　█　　 █　█　　　　　█　　　　　　　█　　
███　　　　　█　　　█████　　 ███　　　　　█　█　█████　　
　　　　　　　　█　　　█　　　　　　 　　█　　　　　█　█　█　█　█　　
　　　　　　　　█　█　█　　　　　　 █████████████████　　
　　　　　　　　█　█　█　　　　　　 █　　　█　　　█　█　█　　　　　　
　　　　　　　　█████　　　███ █　███　　　█████　　　███
　　　　　　　　█　█　█　　　█　█ 　　█　█　　　█　█　█　　　█　█
　　　　　　　　█████████　█ 　　███　　　█████████　█

移動路徑：s e s e s e 2n e 2s 4e s 2w 2s 2w s 4e n e s
↑
給視障朋友看的這一行仍是不會變的

右邊那張圖，就很像是一般的區域地圖了。


以下是以 javascript 來寫的話，跑出來的樣子:

https://i.imgur.com/auK92fK.jpg


這支程式我日後會將它放在我的網頁空間供所有人下載，對 sanc
來說，則是只需要 x-x 圖，就能透過 sanc 目前已存在的程式，
將 x-x 圖轉成區域所需要的所有房間，如下:

001 002-003 004
| | | |
005-006 007-008-009-010
| | |
011-012-013-014 015
| | | |
016 017-018-019 020-021-022-023-024
| | | |
025-026 027 028 029-030-031
| | | | | |
032-033-034-035-036-037-038-039-040
| | | | |
041 042-043 044-045-046 047-048
| | | | | | |
049-050 051-052-053-054-055 056

上面代表這是一張大小 10x8、擁有 56 個房間的區域。

以上一點分享，待續。


Laechan@Sanc

--