I recently started working on a maze generation blueprint, and am about to submit it to the UE4 Marketplace. Maze Creator is equipped with various features:
• Generates completely random mazes, with absolutely no predetermined patterns.
• You are able to specify a custom seed (Optional), in order to generate the same maze consistently.
• You are able to specify the start and end of maze locations, or just let it pick locations randomly.
• Maze Creator is efficient. The maze you see in the screenshot above was generated in under a second (Blueprints, not c++ :D)
• You are able to specify the width and height of the maze, and can easily scale it using the editor scaling tools.
• You can choose whether or not you want the maze to be generated in construction script, or just when you play the game. You could even have the player specify the size of the maze, and then spawn and generate it in-game!
• You have the option to generate rooms (See pictures below), and can specify details about possible rooms such as size, and the frequency at which rooms will appear (Or just not have any rooms at all)
• Events are setup for when something overlaps the start and end of a maze, you can use this to setup your own behavior, like a timer when the player starts the maze!
• Fully compatible with Nav-Meshes, and AI are able to traverse through the maze as they would anything else.
• There are no limitations as to how many mazes there can be, or how big of a maze you can have.
• You can quickly swap out meshes & materials to use what you want!
• I still have more features planned, and am open to suggestions
As per Headclot’s suggestion, I worked on letting rooms be generated You can specify the Min/max size of rooms, and the frequency at which they occur (Or have no rooms, if you don’t want them). I guess when I say rooms, I really mean open areas, but here are some screenshots: (Was getting error, so here are the links) http://puu.sh/lTLur/82102dc30d.jpg
Wall spacing is generally meant to accommodate for if you want to have a longer wall mesh, and let the player have more space to walk around (though you can still use the editor scaling tools), but can be used to achieve an effect like you see in the screenshot above.
I almost overlooked this product. Procedural Maze generation is a core aspect of my Dungeon Crawler, thus, I read each and every post about them. I’ve developed a maze generator using the Depth-First Search Algorithm (wikipedia) applied to 2D Grid. I’m curious as to what algorithm your using. Is it 2D Cell-based? If so, can the raw data be dumped for other uses? Performance would be of concern
This Maze Creator is 2D cell-based. It first generates locations for every possible wall (regardless of Maze layout), then it picks a random starting point, and randomly picks new cells to move to until it hits a dead end. Once a dead end is reached, it searches for an unvisited cell with an adjacent visited neighbor, and sets that as the new starting point. When it moves to a new cell, it removes the wall location that is between the two cells. Here is a picture example:
Once all of the cells have been visited, the walls are placed based on that array of wall locations. Data is stored in arrays for visited cells, unvisited cells, outer wall locations, inner wall locations, etc.
To respond to some of the features you would like to see:
•Raw Data Output: I don’t quite understand what you mean
•(X, Y, Z) Maze generation: This of course is very possible, and with not too many changes as well, but I am concerned that if I included this in the blueprint, unknowing people would end up freezing their projects when generating large mazes on the Z axis as well, as that would exponentially decrease performance.
•Non orthogonal shaped room cells: For this you would essentially need to change how wall locations are generated, and then change the math that determines which wall to remove when changing cells.
•Flip/Mirror generation: This sounds like something a lot of people could use, and I will look into it.
•Walls Added/Remove at runtime: This can absolutely be done! As an example, if you line trace to the maze, you can do ‘Remove Instance’ for the ‘Hit Component’ and ‘Hit Item’ in order to remove whatever wall you trace to.
•Network Replication Support: UE4 currently does not support the replication of ISMs that are generated at runtime. If I place a maze in-editor, it will show up for everyone, but if I am spawning a maze in-game, you just need to spawn it with Multicast.
Edit: I did some editing in my algorithm, and there is one big obstacle for symmetrical mazes, and that is guaranteeing that the maze can still be solved/navigated. Here is an example of a symmetrical maze that exhibits this problem:
•Raw Data Output: In short, Raw data would a list of values that represent where and pattern of each cell in the maze. There are many ways this data could be formatted, so it require a detailed explanation of how to use it. A Maze Cell (Room) consists of 4 walls (assumes ceiling & floor are constant). From a Top-Down view the Walls are labeled West-South-East-North. With four (4) walls there are 16 possible patterns. Each pattern can be given a ID. In the technique I use, I use a Byte to hold a numerical representation of the Walls: West South East North. I use Bitwise math to add/remove walls from the numerical representation. I use the Bitwise Value as the ID.
•(X, Y, Z) Maze generation: Just stick a Performance Warning Label on the product, and optimize as much as possible. Perhaps a custom occlusion algo to spawn walls on-the-fly based on player view.
•Flip/Mirror generation: What I do is generate a single maze, then mirror/flip, connect them, then knock out a single edge wall between them. Using the DFS method guarantees no closed loops.
•Network Replication Support: I just replicate the RandomStream Seed to the all the clients to handle spawning the same maze structure.
Circular mazes as SE_JonF recommended, as well as Labyrinth style mazes. Multi-dimensional mazes would be pretty interesting as well
Any chance of a “Mesh re-placement” system where the generator could use “hierarchical instanced static meshes” (HISM) meshes instead of BSP brush meshes? This would allow for people to use other modular packs with your setup. If you do this, then it would also be beneficial to add in a way to use a random mesh styles for each type of wall piece: T, L, I,.
Hey mate, a few things I just thought about for your maze creator which might make it even more attractive:
circular mazes (or any shape maybe provided by user) edit: just noticed the above post - im aware you are aware
tweakable and randomized wall thickness and height. A few years ago I came across a way to convert texture maps to geometry in maya. I used that to make cool looking maze towns like this one:
form since the UVs for the walls are currently unitized and normalized with proportions preservation I can use those coordinates to procedurally place things like proper doorway geometries, lamps, balconies, random ornates and debris.
I can also use the main ground mesh and the first level houses mesh negative intersection to determine where streets are and place more stuff there like trash cans, street lamps, little merchant stands, trees, plants, random ornates and debris etc. etc.
Not sure how any of that would be able to transfer into an in-engine workflow, but that would be used to populate the level with additional meshes and make the mad maze city feel more alive.
Just a few inspirations for if you want to take this thing a step further…
Thanks for the suggestions! Wall thickness & height can already be tweaked. While it cannot already be randomized, you would literally just have to swap it out from using the variable, to using the variable + or - a random float. The files have already been submitted, but if I make any progress on other suggestions that people have given me, I will push those features out in an update, as the whole reason for this is so that YOU all can use it.