How can I create a 2d procedurally generated circular maze like the following picture:
1
- 2\$\begingroup\$ What have you tried so far? Or are you just asking for a possible implementation? \$\endgroup\$liggiorgio– liggiorgio2018-05-06 15:06:33 +00:00Commented May 6, 2018 at 15:06
Add a comment |
1 Answer
\$\begingroup\$ \$\endgroup\$
4 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\$Draco18s no longer trusts SE– Draco18s no longer trusts SE2018-05-06 03:22:40 +00:00Commented 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\$Draco18s no longer trusts SE– Draco18s no longer trusts SE2018-05-06 03:36:59 +00:00Commented 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\$Draconis– Draconis2018-05-06 05:16:59 +00:00Commented 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\$Draco18s no longer trusts SE– Draco18s no longer trusts SE2018-05-06 05:18:58 +00:00Commented May 6, 2018 at 5:18