關於路徑生成算法

我需要建立一個2維空間（用於所有實際目的，2-D數組）路徑.. 每個索引[y] [x]包含一個路徑..例如關於路徑生成算法

+-- --+ +-- --+ 
| || | | || | 
| | ==  ==++== 
| || | |  | 
+-- --+ +------+

雖然我可以隨機初始化此空間，但我希望能夠生成一系列路徑，以確保每個座標都可以從每個其他座標到達。

我應該看什麼算法來解決這個問題？

我已經學到了很多路發現算法，比如Dijkstra的或A *，但我不認爲這是我的問題可用。

蠻力法就是像小孩一樣解決迷宮。在開幕處開始並在不擡起筆的情況下在每個區域劃一條線。如果在你耗盡了所有路徑的可能性之後還有未塗漆的區域，那麼你有一個無法到達的區域。 – 2013-04-23 16:59:46

我一直在尋找比蠻力更好的方法。我認爲蠻力將成爲O（n^2） – 2013-04-23 17:00:38

你想要[迷宮生成算法]（http://en.wikipedia.org/wiki/Maze_generation_algorithm）？那麼，你去。 – Dukeling 2013-04-23 17:18:10

你的問題基本上等於找到一個spanning tree，這可以使用深度優先搜索或寬度優先搜索在O（n）中完成。提示：請注意，如果A可從B到達，而B可從C到達，則A可從C（可傳遞性）到達;也只要你沒有單向走廊，那麼如果A可以從B到達，那麼B也可以從A（反身性）到達。

爲了生成迷宮，一旦你生成了一個跨度，那麼你可以開始添加額外的邊緣來添加一些變化（儘管額外的邊緣通常會使迷宮更容易解決）。跨度保證連接。

2013-04-23 17:45:32

回答