※ [本文轉錄自 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 個房間的區域。
以上一點分享，待續。
[email protected]