Create a 10k tiles maze in unreal engine 4

Hello,
This tutorial shows how to create an orthogonal random maze using a basic growing tree algorithm and an instanced mesh grid. It creates or a perfect maze (with dead ends) or a braid maze (without dead ends) and uses a backtracker recurse but can use a prim's like one too, and others if you want.

This is a 10x10 maze of 10x10 tiles mazes which needs less than 4 s to spawn :

Reasons of this choice :
1 : Higher mazes are longer to create (a single 40 * 40 will be longer to spawn than this 10k one)
2 : Instanced meshes have collision fine to 128 instances. This system spawns 100 instances by maze. There is no need to add a box collision spawn.

By modifying a bit the system (mainly by using some construction script to not have infinite loop alert) i have been able to spawn a 16x16 mazes of 16x16 rooms of 16 squares each (so a million squares) but i am quite sure that it can't be decently populate by props and mobs, and it took like 30 s to spawn. (I'll show a pic of room spawning possibility at the end of this.)

To do the maze :

Create a third person blueprint project. Go to Edit / Project settings / Engine / General settings : Down of the list : Blueprints : Maximum Loop Iteration Count : add a 0.

In starter content / architecture : Duplicate the floor_400x400 and set build scale x and y to 10. Apply changes and save. Other meshes used are wall 400x400 and floor 400x400. If you use material for them, don't forget to check "used with instanced mesh" box in Usage of the material.

Create a new level with default and delete the floor. We will create 5 blueprints to create our maze. There is only one variable wich needs to be set : "Roomref". All others go with initial value.

1 : Bp_Exit is a blueprint with a floor400x400 only. We'll use it as floor for our start and exits places.

2 : Bp_Ground is an instanced floor using the duplicated : floor400x4002. It has the basic instancing system we'll use for all our instanced meshes. Once compiled and saved, set it in your level at 0,0,0.

Construction script

3 : Bp_Border is the blueprint we'll use to create our south and west walls / exits not created by the main grid. Quite the same instancing system, except that it spawns two lines of meshes instead of a grid.

Function "Spawned" (called by Bp_Maze blueprint)

4 : Bp_Wall ( the big one )
In Event Graph : Event Begin Play linked to a function "Spawned" (to visualise the maze)

RoomRef is an array with 15 elements :

Function "Spawned" where we first set our needed values, then create our grid, then spawn our walls from grid values.

 

 Zoom 1

Zoom 2

Zoom 3

There are three new functions in "spawned" : "Create Grid" which will fill the array used to create our perfect maze, "Dirt It" wich will create a braid maze from the perfect maze, and "Set Exits" which will set the exits.

Function "Create Grid"

 

 Function "Create Grid" Sets the size of grid array, selects first room and creates a whileloop to repeat as long as array is not completed : Select a room near start room. If room is usable to be connected, connect it and set it as start room. If not, (recurse) get back in the array to the last start room.

When array is completed, Come back to first room to set it.

There are three other functions in "Create Grid" : "New Room Select" which select the room added to the maze, "Set Last Room" which set the last room when maze is done (quite the same function as "New Room Select" ), and "Set Opened" which set the value of contiguous array elements.

Function "New Room Select"

There is one last function in "New Room Select" : "Check Near Last Room" which check the four rooms around the selected one.

Function "Check Near Rooms"

Function "Set Last Room"

Its function "Check Near Last Room"

Function "Set Opened"

If you set a Bp_Wall in your level, you spawn a perfect maze :

Function "Dirt It":

Zoom 1

Zoom 2

Zoom 3

 

Functions "CheckNorth" "CheckSouth" "CheckWest" and "CheckEast" 

Now if you spawn your Bp_Wall, you have a braid maze :

Last function is "Set Exits"

Zoom 1

Zoom 2

West and South values are not used but i have let them to show where set them.

This was the big part. Exits are not set. They will be in Bp-Maze.

5 : Bp_Maze (The last, not the least)
Duplicate Bp_Wall and name it Bp_Maze. There are a few modifications to do :

In event graph, we spawn wall blueprints, add border blueprint, add exits blueprints, and set player on start place.

Event graph

Zoom 1

Zoom 2

Function "Spawn Exits"

Last modification is in Function "Set Exits"

 As the first one, south and west are not set but shown to know how set them.

Now, delete the event begin play / spawned in event graph of Bp_Wall, delete Bp_wall from your level and add Bp_Maze. hit play and have fun in your 10 k maze ^^

I promised to show you : Using my 3 room types 5*5 room spawning system (not yet working fine for access and collision) here is the same maze :

The floor on the left is Bp_Ground and it took less than 5 s to spawn this 160 k tiles maze.

To upgrade : You can set grid x and grid y instead of grid and size x and size y instead of size, but you'll have to change the grid maker. You can add  a main x and a main y to be able to have different numbers of mazes independant to the numbers of tiles in mazes. But there again a grid maker work will be needed. You can spawn on z axis and set lifts or stairs at exits to have a building maze. you can use "roomgrid" as a basis to populate your maze with props as i did here : https://www.youtube.com/watch?v=0l-X-wIr1GE

Here is a link to download the 5 blueprints :

https://drive.google.com/file/d/0By9tRWwL9dfAcGxOZml3TnJwVFk/view?usp=sharing

Copy them in your content folder and create floor400x400. Don't forget to up your infinite loop limit and set used with instanced to your materials ;-)