※ 引述《yokann ( )》之銘言：
: 以前玩暗黑破壞神 玩世紀帝國
: 甚至是更早的如勇者鬥惡龍怪物仙境
: 都有隨機地城系統
: 但是暗黑開一場關非常快
: 要馬上能按規律亂數生成所有物件/掉寶/怪物
: 感覺很吃運算？
: 還是其實這個難度很低且不吃效能？
: 畢竟Gameboy的勇者鬥惡龍怪物仙境都能有亂數地圖了
: 有沒有相關背景的人能說明一下
產生地下城的做法在 1980 左右就有了，你去找 roguelike 建立地下城的
演算法就能看到好幾種不同做法。
最簡單的難度是真的很低，1980 年代就能做到移動到下層才產生新地下城
了，以現在的機器來說，除非你建立一張超大地圖像 CDDA 那樣，才有可能
在建立地圖的時候就有效能問題。
我這邊舉例兩個最簡單的演算法。
第一種很直覺，先隨機建立兩個房間，然後將兩個房間用通道連起來，從
第三個房間開始，一建立好就跟上一個房間用通道連起來。
這種做法可能做出兩個重疊一部分的房間，如果你想確保房間都不會重疊，
建立好房間就檢查有沒有碰撞發生，有就刪掉新房間。
第二種就把一個空白地圖做分割，每一刀都把一個區塊分成兩個空白區塊，
完成之後你會得到一張有很多不同大小的長方形的地圖，把長方形當成房間
再用通道相連，就能得到一個保證不會碰撞的地下城了。
這個你用 BSP trees 下去找就能找到範例。

房間內物件也也可以用機率權重計算敵人/寶物/陷阱的數量

之前是看到用波函數塌陷演算法

所以瑪奇的地下城具體來說是怎麼生出來的?好像不完全是這兩種?

瑪奇偏1，先構築房間再找道路

我想不太到要怎麼自動生成鑰匙房跟鎖房而不會彼此卡死

首先一定要現有一個入口側跟出口側，而鑰匙一定要在入口側區域能連通的地方，就不會卡死了

當然以瑪奇地下城的做法，應該在構築時先生出房間與通路，再一個個去算合理鎖上的門，並確保所有開啟機關都是與入口側相鄰就好從頭目房開始上鎖，只要被上鎖的區域就不允許生出下一道鎖門的鑰匙大概就行了

瑪奇以前常常生一堆垃圾圖，走了大老遠結果是死路

大概有想法了 先生出地圖後 從BOSS的鎖開始隨機決定每個房間是鎖還是鑰匙還是燈柱 並確保一定要先有鎖才有鑰匙倒著把整個地城走完就做完了 感謝

瑪奇經常繞了地圖最外圈結果啥都沒有不然就是鑰匙和門在最遠的兩頭

先生成「路徑」再去生成房間跟鎖就好了