How can I create a 2d procedurally generated circular maze like the following picture:
1 Answer
Any maze generation algorithm, that only relies on a set of nodes (pretty much all) will work. Instead of creating a grid, where each grid point is a node and they connect to their neighbours, you need to generate them in the circular shape.
So, first of all, the center is a node. Let's say the next layer has 6 nodes and the middle connects to all of them. To make sure the maze stays consistent, each layer (apart from the second) should have twice as much nodes, as the one before, because you need one neighbour for every node in the last layer and you need to put one extra node between them, so that the maze becomes more detailed the farther you go from the center.
Pseudo code for this:
nodes is an empty set of nodes
put central node in nodes
put the second layer's nodes in nodes
connect the first and second layer
let currentLayerCount be 12
for every layer
for i from 0 to currentLayerCount
create a node with a position
x: cos(2*pi / currentLayerCount) * layerId
y: sin(2*pi / currentLayerCount) * layerId
put node in nodes
if i is divisible by 2
connect the node to the neigbouring nodes in the same and last layer
else
only connect the node to the neighbouring nodes in the same layer
end if
end for
multiply currentLayerCount by 2
end for
-
\$\begingroup\$ twice as many per ring is probably too many, but certainly a decent starting point (the asker's example features 2 nodes -> 8 nodes after 7 layers). Additionally, for the 2 nodes that connect to a single inner node, you don't want both of them being open. Either one connects, the other connects, or neither do. \$\endgroup\$ Commented May 6, 2018 at 3:22
-
5\$\begingroup\$ I took a bit to analyze the sample. i.sstatic.net/waqCf.png Red cells are where there are more than on the previous layer, blue the same number. \$\endgroup\$ Commented May 6, 2018 at 3:36
-
\$\begingroup\$ @Draco18s I think this is meant as the input to a maze-generation algorithm, which will then cut out a great number of these edges. \$\endgroup\$– DraconisCommented May 6, 2018 at 5:16
-
2\$\begingroup\$ @Draconis Oh sure, I'm just saying that doubling the number of nodes every layer will lead to very tiny outlying nodes, as the circumference of a circle doubles as the radius doubles, not as the radius increases by 1. \$\endgroup\$ Commented May 6, 2018 at 5:18