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.

Jung-Jen Chen 發表於 June 1, 2005 05:45 AM