Re: [討論] 隨機地下城.物件.是很簡單的技術嗎？

[drm343 (一卡)]

※ 引述《yokann ( )》之銘言：
: 以前玩暗黑破壞神 玩世紀帝國
: 甚至是更早的如勇者鬥惡龍怪物仙境
: 都有隨機地城系統
: 但是暗黑開一場關非常快
: 要馬上能按規律亂數生成所有物件/掉寶/怪物
: 感覺很吃運算？
: 還是其實這個難度很低且不吃效能？
: 畢竟Gameboy的勇者鬥惡龍怪物仙境都能有亂數地圖了
: 有沒有相關背景的人能說明一下

產生地下城的做法在 1980 左右就有了，你去找 roguelike 建立地下城的
演算法就能看到好幾種不同做法。

最簡單的難度是真的很低，1980 年代就能做到移動到下層才產生新地下城
了，以現在的機器來說，除非你建立一張超大地圖像 CDDA 那樣，才有可能
在建立地圖的時候就有效能問題。

我這邊舉例兩個最簡單的演算法。


第一種很直覺，先隨機建立兩個房間，然後將兩個房間用通道連起來，從
第三個房間開始，一建立好就跟上一個房間用通道連起來。

這種做法可能做出兩個重疊一部分的房間，如果你想確保房間都不會重疊，
建立好房間就檢查有沒有碰撞發生，有就刪掉新房間。


第二種就把一個空白地圖做分割，每一刀都把一個區塊分成兩個空白區塊，
完成之後你會得到一張有很多不同大小的長方形的地圖，把長方形當成房間
再用通道相連，就能得到一個保證不會碰撞的地下城了。

這個你用 BSP trees 下去找就能找到範例。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.207.243 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1668011152.A.3B6.html
→ SangoGO: 房間內物件也也可以用機率權重計算敵人/寶物/陷阱的數量
推 greg90326: 之前是看到用波函數塌陷演算法
推 iamnotgm: 所以瑪奇的地下城具體來說是怎麼生出來的?好像不完全是
→ iamnotgm: 這兩種?
推 SangoGO: 瑪奇偏1，先構築房間再找道路
→ iamnotgm: 我想不太到要怎麼自動生成鑰匙房跟鎖房而不會彼此卡死
→ SangoGO: 首先一定要現有一個入口側跟出口側，而鑰匙一定要在入口
→ SangoGO: 側區域能連通的地方，就不會卡死了
推 greg90326: https://www.youtube.com/watch?v=2SuvO4Gi7uY
推 SangoGO: 當然以瑪奇地下城的做法，應該在構築時先生出房間與通路
→ SangoGO: ，再一個個去算合理鎖上的門，並確保所有開啟機關都是與
→ SangoGO: 入口側相鄰就好
→ SangoGO: 從頭目房開始上鎖，只要被上鎖的區域就不允許生出下一道
→ SangoGO: 鎖門的鑰匙大概就行了
推 turboshen: 瑪奇以前常常生一堆垃圾圖，走了大老遠結果是死路
推 iamnotgm: 大概有想法了 先生出地圖後 從BOSS的鎖開始隨機決定每個
→ iamnotgm: 房間是鎖還是鑰匙還是燈柱 並確保一定要先有鎖才有鑰匙
→ iamnotgm: 倒著把整個地城走完就做完了 感謝
→ Gravity113: 瑪奇經常繞了地圖最外圈結果啥都沒有
→ Gravity113: 不然就是鑰匙和門在最遠的兩頭
推 Reficuly: 先生成「路徑」再去生成房間跟鎖就好了