Instanced mesh random maze generator

As yesterday i helped for instanced meshes it kept me back to my dungeon / underground chaotic maze (not a one way only one) and i have set it too for outside settings like city or village.
The underground :

The outside :

Ah kickass! Reminds me of many many hours lost tweaking my procedural dungeon generation algorithms for old roguelike projects. :slight_smile:

Looking beautiful! Any way to make it work in BP?

Thanks ^^
@Pak : I did them with blueprint only.

Hi Fen. Do you plan on sharing the BP with the community?

@Fen that’s beautiful! I also would love to learn more about the logic behind it, of course only if you want to share.

@TechLord : Considering SaxonRah’s thread : SaxonRahs Tutorial Thread - Random Maze Generation & Solving - Community Content, Tools and Tutorials - Unreal Engine Forums i will not but i send you a pm.

@Pak : I followed a different logic than SaxonRah’s one (which you would check too, and Think Labyrinth! for infos
and especially this one : Maze Algorithms which is really cool to see what who will do by using this algorithm or not. I finally used a “binary tree / sidewinder personal style algorithm (without a first blank line)” mainly because of instanced limitations.
I build a 9 x 9 grid room line by line.
Each room is a 5 x5 squares piece with 2 to 4 entrances (and 1 too but used only when dead end is needed to reduce dead ends) and can be set to 3 different styles : corridor (only middle squares are open), room (only walls around are spawn with entrances set) and plane (only needed stuff to fit in maze is spawn)
Entrances are checked in maze creation and style is random in spawn blueprint where you can choose one, two or all styles with an add to last spawn to have a “similar near style”

i build line by line because when you instance a mesh only the first 128 instances have a collision set and my 9 x ( 5x 5 room ) is always under 128 instances.

So i first spawn a start line with one entrance where is my player start and do arrays old line / new line.
Two things to solve :
1 : My first line have only one entrance so i had to make a check back on new lline creation considering last line connections to new line and only then spawn last line.
2 : Those mazes are usually too much linear, so i added some breaks and random add entrances for more chaotic.

This is a bit crazy but it was really fun to go deep and deep ^^ I always have an issue where i sometimes spawn a 4 entrances room (which is my default spawn in case of bug to make things be ok even when they are not ^^) when i would spawn a 2 entrances one on last room set, but as it only adds dead ends i haven’t yet checked it. If i do i will certainly do new for some parts to have a cleaner / faster system.

Awesome. Thanks for the links and explanation as well. Back in the UDK days I wrote a couple of Maze Generators in Unrealscript.

And i clearly remember having read and bookmark for infos check back this thread when i began my preparation before my random level system creation ^^

Awesome work mate ! :slight_smile: I always love to see new generators!

Fantastic work Fen! Keep up the great work and be sure to keep us updated as you progress along in the development of your project!

Thanks a lot SaxonRah and Sean. I’ll do new updates as regularly as possible.

Work of the week on this project : I added a line trace sytem based on tom looman’s one for allies, ennemies, loot and activable blueprints. A short video to show mainly a code panel and a procedural “2 to 10 floors lift” blueprint with box block/overlap update added to not stop timeline event in the blueprint when you go near door.

A new video because i destroyed the old system and built a new one based on the growing tree algotithm and i added a braid system to have more communicating areas. I added props, doors and mobs too (props are instanced and others spawned) With a basic grenade launcher / death anim basic system for fun.

New stuff from this new growing tree algorithm, a massive maze for TechLord ^^
This one is a 10 * (10* 10) tiles so 10k tiles maze. There is some add to do on exits to have it more random but it spawns less than 3s (this one been less than 2 but it was the only one time it happened. It is ok to 20k but take like 6s so i work on another way to spawn the million TechLord wants ^^

Very Nice videos. Maze generation with Interactive Objects = Awesome. Watching the videos is really getting me excited to work on Procedural Level Construction. I cannot wait, but, I’m forcing myself to focus on GOLEM Construction System (as I’m easily distracted). So, please forgive the barrage of questions that follow:

  1. Are you preforming custom occlusion to maintain a decent frame rate? Is it even necessary?
  2. Any considerations for network replication?
  3. Any ideas for Non-orthogonal Construction or simulation there of?

Thanks TechLord. This is the big advantage of the array. From it i can have infos to random populate with instanced props and spawned blueprints / actors.

About occlusion : for this new 10k tiles maze with nothing more, my fps is always upon 60 and regularly to 90. It goes down for the populated own but mostly because of the lights (then i separated lights in 2 : the instanced mesh and a blueprint with an overlap toggling visibility box and it goes down to 40 on fights but is usually around 50 (with a phenom 2 x4 955 3.20 ghz 16 mo ram) both in full screen. For both i added only a basic lightmassvolume / postprocess (for no blur and custom depth blendable) and precomputed visibility (not sure why i did now ^^)

I haven’t check the replication because i haven’t do nothing with replication yet (so much to learn and so little time :p) but as all is ready to transfert, i suppose it is a doable thing.

For now i have only an orthogonal 2d set where you can change x or y. But with few changes in algorithm it would be doable.
For the generating array system you can for example if this is for a tree, use a ranged value for each type of tree part and use it as a relative location / rotation from its parent. like range 1000 for trunk, 100 for large branch 10 for branch and 1 for flowers. with a 1 to 9 value so 9 relative positions to parents. Then, you do 4 instanced grid and each time you find a ranged value you add instance to the relative location of the parent (it will may need an added value or a second array, not sure). but it needs some prepared meshes with origins / ends well fitting to not have a lot of hardcoded variations. (as i write this i think that it seems really cool lol, i’ll have to give a try to this idea ^^) of course some variations need to be added like have 0/3 branches and 2 / 6 flowers on each but it looks funny to try.
And it will be the same way for all other types of maze, with adjustments.

Only main issue is the infinite loop generating array which does limitation for a “do all at start” stuff. I have been able to go 50k for now. (15 * 15 mazes of 15 *15) and it goes 60 fps as the other. This is not bad but it needs a another * 20 to reach the million tiles epic level ^^.

I just realised that i forgot to share a pic of the 50k tiles maze. (15 * 15 mazes of 15 * 15 tiles)

Yeepee !

To let you know that i finally reached the million squares maze on begin play. Ok it needs 25 to 30 s to spawn and it is a 16 * 16 mazes of 16 * 16 rooms of 16 squares each (256 mazes of 256 rooms with 5 * 5 squares (only 4 * 4 spawned) so not a million tiles maze but a million squares one, but i am really happy ^^ (i need to fix one thing and i begin the share post)