我搜索甚至訪問了一個收集迷宮演算法的網站，但沒有任何內容符合我要求的以下陳述。
為了說清楚，我需要一個無限迷宮生成演算法
- 使 a
perfect maze，也就是說，2d,grid-based- 每個方塊都是空間/墻
- 每 2 個空格相連，只有一個路徑
- 沒有 2x2 正方形就是所有空間/墻壁
- 提供
f(s,x,y), wheres用于random seed或 sth 像這樣- 回傳 (x,y) 處的正方形型別
- 對于
s0~(32768 or sth) 內的不同，給出不同的結果
- 無限（雖然可能受 64 位 int 的限制）
- 允許額外的空間（我的意思是在程式中）
編輯：
- 這里無限的意思：像這樣的東西
function f(s,x,y){
// for each x,y it gives a result, so we consider it "infinite"
return (s*x y)%32768<30 ? "wall" : "space";
}
- 這是一個有限演算法（滿足1）
init:all walls
choose a square,flag it and add to list
while(list not empty)
{
chose randomly from list
delete from list
if(there's a flag)
{
delete it
continue
}
make a flag
if(surrounding wall num≤1)
{
add 4 surrounding walls to list
}
}
- 某些東西滿足 1 和 3
我們從 Eller 演算法開始
it is generated row by row, and saves a set of regions
first row:all regions into a set,wall between regions(randomly)
while(not last row){
foreach(neighbour regions){
if(not in the same set){
break their wall and merge the regions(randomly)
}
}
foreach(region){
break the wall below(randomly,and at least one does this)
}
generate next row
for this row:{
foreach(region){
if(connected with above){
merge to prev-set
}
}
throw away prev-prev-set
}
}
last row:connect all regions that are not in the same set
if we start from the centre and generate it circle by circle, it can be infinite
sadly we have rule2
uj5u.com熱心網友回復：
這個問題似乎有點難以解決：無限多的無限迷宮，這樣我們就可以將自己限制在多個不同的范圍內（例如，如果我們想要一個大約 100 萬 x 100 萬的正方形），并且在任何兩個空間之間仍然有唯一的路徑（和您的其他條件）。讓我們把它分解成更小的部分。
假設我們可以建造一個 7 x 7 的方形迷宮塊，并且能夠在它周圍制作墻壁邊界，在我們想要的邊界上有一兩個門。然后我們所要做的就是將這些方塊連接成一個螺旋：一個中心方塊，頂部有一個門，逆時針螺旋的方塊，每個都有兩個門，在螺旋的方向上：
（每個編號的盒子是一個 7x7 的迷宮）
一般有兩種情況：
- “直”件，其中兩個門位于相對的兩側，以及
- “角”件，其中螺旋形轉彎和門位于相鄰的兩側。
我們想讓這些部分通用，這樣我們就可以混合和匹配迷宮并將它們組合在一起。為此，我們將使用此模板：
- 邊界規則：每個正方形的底部和左側都是墻壁，除了每邊的中心。
- 自由空間規則：除非規則 1 或 3 要求，迷宮方塊的頂部和右側不允許有墻壁。
- 門規則：在兩個迷宮相遇的地方，如果相遇是螺旋的一部分，則中心兩側將是開放的（換句話說，交叉發生在邊界的中心）。否則，位于另一個迷宮下方或左側的迷宮應在此邊界的中心有一堵墻。
這太多了，讓我們看一個例子。這里我們有一個“直”水平連接器的模板，以藍色突出顯示（所有迷宮都是 7 x 7）。X 表示墻壁，O 表示需要打開（兩個迷宮之間的交叉點/打開的門）。紅色 X 是規則 1 中的邊界，紫色 X 是規則 3 中的封閉門。
每個迷宮的中心 5 x 5 是可定制的。我們必須確保在我們的迷宮中沒有無法訪問的正方形或等于 2x2 的正方形，因為上面的規則保證了迷宮相遇的地方是正確的。
適合上述模板的一種可能的迷宮（有很多）：
以角件為例：
I've similarly drawn examples of each possible connection to make sure it's always possible: there are many possible ways to do this for each piece type (including the special center piece).
Now, for how to generate infinitely many infinite mazes based on a seed. Suppose you created at least 2 examples of each connection piece (there are 2 straight connectors and 4 corners), although you can just make one of each and reflect it. (Really you only need 2 different examples of one connection type.)
Given any seed binary string, e.g. 10110, let this denote our choices of which example piece to use while we make the maze spiral, counting up as in the first picture. A '0' means means use our 1st example for this connector; a '1' means we use the second. You can then repeat this/extend the binary string infinitely (10110 10110 ...). Since this is periodic, we can, using some math, figure out the piece type at any point in the sequence.
I've left out the math for the pattern of connection types: this is easy to work out for a counterclockwise spiral. Given this pattern, and a convention that the point x,y = (0,0) is the bottom left corner of the spiral-start-maze-block, you can work out 'wall or space' for arbitrary x and y. This maze is infinite: you can also restrict the borders to any full odd square of mazes in the spiral, i.e. (7*(2n 1))^2 cells for positive n.
This framework pattern for a maze is customizable, but not very difficult to solve, as the regularity means you only need to solve it locally. There's nothing special about 7; any odd number at least 7 should work equally well with the same rules, if you want to make local maze blocks larger and more complex.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350535.html
上一篇：O(n)加權樹中的最大匹配