koobas.hobune.stream
2D or 3D non-"perfect" maze generator
summery:
I'm looking for any kind of documentation on how to make a 2d or 3d maze in a specific style. in particular i'm looking for paths that can be wider than 1 block, areas that can loop, and parts of a floor that are isolated from everything but the the layer above or below.
details:
i'm trying to auto generate a maze.
the maze setup is in a style where their is either a wall or an open space, both of witch take up the same amount of space.
the paths should be able to have loops.
their should be sections of the maze that are cut-off and must be accessed from another floor or teleporter.
the block maze should be able to have even number halls as well as odd.
pitfalls i've found in my searches:
block based generators build everything in odd numbers. seem to always start like this and just break out the single connecting wall between them.
They never seem to have loops in the path.
They never seem to have wide halls.
many only make a single path then fill the rest of the area with tiny dead ends that are too obvious.
this is about as close as i've found info on generating, but it's done in such a way that makes even hall lengths impossible while using that as a base of any kind.
Cool question. After weeks of tedious work, I'm jealous of the problem. I mustn't be so easily distracted as to really dig into it, but still. ;)
Because so many of your requirements are unique apart from the quintessential maze generator solution(s), I'd suggest taking several steps back instead of trying to bend this approach to fit. Your ultimate approach may be very similar to classic generators, but it's worth investigating a nontraditional method if only for ideas.
The biggest, scariest part of a made-to-order solution is the desired aesthetic. Decide this first, then imagine ways in which an algorithm could hand it to you. One thing that comes to mind involves a high degree of randomness, and a-star. You could build something that qualifies as a maze by carving into (walking through) an array of unwalkable cells in a heavily randomized but clever fashion. The clever part would be maintaining your desired aesthetic by examining both the surrounding cells near the walker/cursor and the overall path traversed on a macro scale, prior to making direction change decisions. The first ensures little or no rule-breaking e.g. loops, while the later focuses on area coverage and creating interesting shapes.
You could get wide halls by changing the shape of the walker cursor. (Multiple layers of these walkability maps could even be blended together, and/or you can "brush" shapes into the map to achieve certain aesthetic goals.) A-star will help ensure at least one valid path to the exit exists. Once you establish one respectably convoluted path to the exit, the rest of the generation process could be area-filling with useless distraction routes. You could a-star check after each space-filling edit, and if the shortest path to the exit is significantly shortened, reject the latest change to maintain a desired difficulty level.
Getting multiple floors that connect in multiple places is essentially a 3-dimensional array. So make your array and algorithm work in 3 dimensions. (4, aka teleporters, starts getting really weird, but could work on the same principles if you introduce teleportation routes as meta information on your cells.) The cursor should get some setting that strongly prefers X, Y travel over Z / teleportation travel.
Also worth mentioning, don't forget about user fun. Unless the game's selling point is all about solving infuriating mazes, it's worth considering just how frustrated you want your users to be. The difficulty can be dialed in using the same variables this suggested outline would use anyway, if you plan for that ahead of time.
You might also search through information about generating rogue-like dungeons. There is a lot of information about that topic and many techniques for generating good random dungeons that you can probably adapt to your needs.
