May 31, 2005
迷宮產生器
剛剛閱讀 [reality's blog]，瞥見這篇 [隨機迷宮]，展示了一個沒有死結、一定會有出路的迷宮產生器。一般來說，迷宮的建構過程就是 Minimum Spanning Tree，而且有三種可能的途徑：
. Depth-first search
. Prim's Algorithm
. Kruskal's Algorithm
Chris Okasaki 提醒了我們：
None of these algorithms make any assumptions about the topology of the maze. They will work with 2-d or 3-d grids, toroids, hexagons, whatever. However, in the more highly connected topologies (such as 3-d grids), the deficiencies of the first algorithm will become even more apparent (it will tend to produce long, winding paths with very little branching).
其中，Prim's algorithm 是最容易實做且有效率的演算法，詳情可參閱 [Prim's Algorithm]。
由 jserv 發表於 May 31, 2005 01:15 PM迴響
我沒有記錯的話, DFS算是最花時間的... in the worse case, it would search the whole tree.
--
However, these algorithms are suitable for single "entry". To make the problem more interesting, thinking about how to make a multi-entry generator.