SaxonRahs Tutorial Thread - Random Maze Generation & Solving

Welcome to my tutorial thread. maze generator is dedicated to Rama; as in I’m providing it for free. Since he’s helped me so much. <3 Thanks mate.

Here’s some videos of what were going to do.

Random Maze Generationhttps://youtube.com/watch?v=sMZI4Ja8W44
Maze Solvinghttps://youtube.com/watch?v=5Zvdwagin_Y

You are going to need some types of blueprint tiles in order to use the code in the next post, mine are called TileGroundBP TileBlockBP TilePillarBP TileStartBP TileEndBP these are StaticMeshActor blueprints with a static mesh and texture applied, referenced in the blueprint of the my MazeHUD class.* I choose to extend the HUD Class because I wanted to show you can do pretty much anything anywhere in UE4 C++. YOU’LL PROBABLY WANT TO USE A DIFFERENT CLASS LIKE AACTOR*

Mind you the source is not just copy paste-able, you must rename some of stuff in order to get it to function properly. like yourproject.h

[]
Dynamic Navigational Meshes
add



[/Script/Engine.RecastNavMesh]
 bRebuildAtRuntime=true


in your DefaultEngine.ini

Also add a Navigational Mesh into your level and make sure its bounds will cover the entire generated maze.
Only if you’re using ai/moveto(); you don’t need navmeshes to use in a firstperson or thirdperson game since there should be collision meshes on your models

[/]

Source Code
MazeHUD.h


// Copyright 1998-2014 Epic Games, Inc. All Rights Reserved.

#pragma once


#include "GameFramework/HUD.h"
#include "MazeHud.generated.h"


UCLASS()
class AMazeHud : public AHUD
{
    GENERATED_UCLASS_BODY()


    UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = MazeHUD)
        bool ShowTests;
    UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = MazeGen101isMax)
        float MazeXKeepODD;
    UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = MazeGen101isMax)
        float MazeYKeepODD;
    UPROPERTY(EditDefaultsOnly, BlueprintReadOnly, Category = MazeTiles)
        UClass* TileGroundBP;
    UPROPERTY(EditDefaultsOnly, BlueprintReadOnly, Category = MazeTiles)
        UClass* TileBlockBP;
    UPROPERTY(EditDefaultsOnly, BlueprintReadOnly, Category = MazeTiles)
        UClass* TilePillarBP;
    UPROPERTY(EditDefaultsOnly, BlueprintReadOnly, Category = MazeTiles)
        UClass* TileStartBP;
    UPROPERTY(EditDefaultsOnly, BlueprintReadOnly, Category = MazeTiles)
        UClass* TileEndBP;
    UFUNCTION(BlueprintCallable, Category = MazeGen)
        void GenMaze(float tileX, float tileY);
    public:
    virtual void DrawHUD() OVERRIDE;
    virtual void PostInitializeComponents() OVERRIDE;
};


template <typename AMazeGen>
FORCEINLINE AMazeGen* SpawnBP(
    UWorld* TheWorld,
    UClass* TheBP,
    const FVector& Loc,
    const FRotator& Rot,
    const bool bNoCollisionFail = true,
    AActor* Owner = NULL,
    APawn* Instigator = NULL
    ){
    if (!TheWorld) return NULL;
    if (!TheBP) return NULL;
    //~~~~~~~~~~~


    FActorSpawnParameters SpawnInfo;
    SpawnInfo.bNoCollisionFail = bNoCollisionFail;
    SpawnInfo.Owner = Owner;
    SpawnInfo.Instigator = Instigator;
    SpawnInfo.bDeferConstruction = false;


    return TheWorld->SpawnActor<AMazeGen>(TheBP, Loc, Rot, SpawnInfo);
}

MazeHUD.cpp


// Copyright 1998-2014 Epic Games, Inc. All Rights Reserved.

#include "YourProject.h"
#include "MazeHud.h"

const int MazeSizeMax = 101;

AMazeHud::AMazeHud(const class FPostConstructInitializeProperties& PCIP)
    : Super(PCIP)
{
    MazeXKeepODD = MazeSizeMax;
    MazeYKeepODD = MazeSizeMax;
}
void AMazeHud::PostInitializeComponents(){
    Super::PostInitializeComponents();
    //Initial Message
    if (ShowTests){
        GenMaze(MazeXKeepODD, MazeYKeepODD);
    }
}
void AMazeHud::DrawHUD(){
    Super::DrawHUD();
}
void AMazeHud::GenMaze(float tileX, float tileY){
    float CaptureX = 0.0f;
    float CaptureY = 0.0f;
    float offset = 400.0f;
    float iter = 0;
    int tileID = 0;
    int RandomEndTileLoc = rand() % ((int)tileX - 1) + 1;

    AStaticMeshActor* grid[MazeSizeMax][MazeSizeMax];

    for (int x = 0; x<tileX; x++){
        for (int y = 0; y<tileY; y++){
            if (y == 0 || x == 0 || y == tileY - 1 || x == tileX - 1 || y % 2 == 0 && x % 2 == 0){
                //                          (X.Xf,Y.Yf,Z.Zf)
                const FVector  GenSpawnLoc(CaptureX, CaptureY, 0.0f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);
                AStaticMeshActor* BlockTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileBlockBP, GenSpawnLoc, GenSpawnRot);

                grid[x][y] = BlockTile;
            }
            else{
                const FVector  GenSpawnLoc(CaptureX, CaptureY, 0.0f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);

                AStaticMeshActor* GroundTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileGroundBP, GenSpawnLoc, GenSpawnRot);

                grid[x][y] = GroundTile;
            }
            //-------------Starting Tile Spawn---------------
            if (CaptureX == offset && CaptureY == offset){
                grid[1][1]->Destroy();

                const FVector  GenSpawnLoc(400.0f, 400.0f, 0.0f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);
                //Tile Start
                AStaticMeshActor* StartTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileStartBP, GenSpawnLoc, GenSpawnRot);

                grid[1][1] = StartTile;
            }
            //-------------Ending Tile Spawn---------------
            if (y == tileY - 1 && x == tileX - 1){
                grid[x - 1][y - 1]->Destroy();

                const FVector  GenSpawnLoc(((tileX - 2) * offset), ((tileY - 2) * offset), 0);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);
                // Tile End
                AStaticMeshActor* EndTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileEndBP, GenSpawnLoc, GenSpawnRot);

                grid[x - 1][y - 1] = EndTile;
            }
            CaptureY += offset;
            if (CaptureY >= offset * tileY){ CaptureY = 0; }
        }
        CaptureX += offset;
        if (CaptureX >= offset * tileX){ CaptureX = 0; }
    }
    //-----------------------------------------------------------------------------------------------------------------------------------------------
    for (int y = 2; y < tileY - 1; y += 2) {
        int dx = 2;
        int dy = y;
        int rnd4;

        switch (rnd4 = rand() % 4){
        case 0: dx++; break;
        case 1: dx--; break;
        case 2: dy++; break;
        case 3: dy--; break;
        }
        //if (bd.getPixel(dx, dy) != Status.WALL) {
        if (grid[dx][dy]->GetActorLabel() != "Block") {
            FVector f = grid[dx][dy]->GetActorLocation();
            grid[dx][dy]->Destroy();

            const FVector  GenSpawnLoc(f);
            const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);

            AStaticMeshActor* BlockTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileBlockBP, GenSpawnLoc, GenSpawnRot);
            grid[dx][dy] = BlockTile;
        }
        else{
            y -= 2;
        }
    }
    for (int x = 4; x < tileX - 1; x += 2) {
        for (int y = 2; y < tileY - 1; y += 2) {
            int dx = x;
            int dy = y;
            int rnd3;

            switch (rnd3 = rand() % 3){
            case 0: dy++; break;
            case 1: dy--; break;
            case 2: dx++; break;
            }
            //if (bd.getPixel(dx, dy) != Status.WALL) {
            if (grid[dx][dy]->GetName() != "Block") {
                FVector f = grid[dx][dy]->GetActorLocation();
                grid[dx][dy]->Destroy();

                const FVector  GenSpawnLoc(f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);

                AStaticMeshActor* BlockTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileBlockBP, GenSpawnLoc, GenSpawnRot);
                grid[dx][dy] = BlockTile;
            }
            else{
                y -= 2;
            }
        }
    }
}

Explanation of Maze Generation.
Explanations will head the Code (comments are on top of the describing line)

[]

Function GenDebugCoord() takes a float tileX and a float tileY, these are the for each side, note we use an odd number @ GenDebugCoord(x,y); ( because we have a center block/ a better way of thinking of it, the maze starts at 1,1 and goes till the maze size and each side has a bounding wall)

**You need to set your tiles, x max,y max, in the hud blueprint and link that hud blueprint to your gamemode blueprint

You should probably set the variables for MazeX and MazeY in your hud blueprint before you simulate or play as they are set to 101 the and is currently spawning StaticMeshActors NOT Instanced (huge optimization if you use InstancedStaticMeshes)**


void AMazeHud::GenMaze(float tileX, float tileY){
    float CaptureX = 0.0f;
    float CaptureY = 0.0f;
    float offset = 400.0f;
    float iter = 0;
    int tileID = 0;
    int RandomEndTileLoc = rand() % ((int)tileX - 1) + 1;

 //-------------An Array called 'grid' that will hold AStaticMeshActor*---------------
    AStaticMeshActor* grid[MazeSizeMax][MazeSizeMax];

//-------------Build a Squares X----------------
    for (int x = 0; x<tileX; x++){
//-------------Build a Squares Y---------------
        for (int y = 0; y<tileY; y++){
            if (y == 0 || x == 0 || y == tileY - 1 || x == tileX - 1 || y % 2 == 0 && x % 2 == 0){
                //                          (X.Xf,Y.Yf,Z.Zf)
                const FVector  GenSpawnLoc(CaptureX, CaptureY, 0.0f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);
                AStaticMeshActor* BlockTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileBlockBP, GenSpawnLoc, GenSpawnRot);


                grid[x][y] = BlockTile;
            }
            else{
                const FVector  GenSpawnLoc(CaptureX, CaptureY, 0.0f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);


                AStaticMeshActor* GroundTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileGroundBP, GenSpawnLoc, GenSpawnRot);


                grid[x][y] = GroundTile;
            }
            //-------------Starting Tile Spawn---------------
            if (CaptureX == offset && CaptureY == offset){
                grid[1][1]->Destroy();


                const FVector  GenSpawnLoc(400.0f, 400.0f, 0.0f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);
                //Tile Start
                AStaticMeshActor* StartTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileStartBP, GenSpawnLoc, GenSpawnRot);


                grid[1][1] = StartTile;
            }
            //-------------Ending Tile Spawn---------------
            if (y == tileY - 1 && x == tileX - 1){


                grid[x - 1][y - 1]->Destroy();

                const FVector  GenSpawnLoc(((tileX - 2) * offset), ((tileY - 2) * offset), 0);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);
                // Tile End
                AStaticMeshActor* EndTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileEndBP, GenSpawnLoc, GenSpawnRot);


                grid[x - 1][y - 1] = EndTile;
            }
            CaptureY += offset;
            if (CaptureY >= offset * tileY){ CaptureY = 0; }
        }
        CaptureX += offset;
        if (CaptureX >= offset * tileX){ CaptureX = 0; }
    }
    //-----------------------------------------------------------------------------------------------------------------------------------------------
    for (int y = 2; y < tileY - 1; y += 2) {
        int dx = 2;
        int dy = y;
        int rnd4;


        switch (rnd4 = rand() % 4){
        case 0: dx++; break;
        case 1: dx--; break;
        case 2: dy++; break;
        case 3: dy--; break;
        }
        //if (bd.getPixel(dx, dy) != Status.WALL) {
        if (grid[dx][dy]->GetActorLabel() != "Block") {
            FVector f = grid[dx][dy]->GetActorLocation();
            grid[dx][dy]->Destroy();


            const FVector  GenSpawnLoc(f);
            const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);

            AStaticMeshActor* BlockTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileBlockBP, GenSpawnLoc, GenSpawnRot);
            grid[dx][dy] = BlockTile;
        }
        else{
            y -= 2;
        }
    }
    for (int x = 4; x < tileX - 1; x += 2) {
        for (int y = 2; y < tileY - 1; y += 2) {
            int dx = x;
            int dy = y;
            int rnd3;

            switch (rnd3 = rand() % 3){
            case 0: dy++; break;
            case 1: dy--; break;
            case 2: dx++; break;
            }
            //if (bd.getPixel(dx, dy) != Status.WALL) {
            if (grid[dx][dy]->GetName() != "Block") {
                FVector f = grid[dx][dy]->GetActorLocation();
                grid[dx][dy]->Destroy();


                const FVector  GenSpawnLoc(f);
                const FRotator GenSpawnRot(0.0f, 0.0f, 0.0f);

                AStaticMeshActor* BlockTile = SpawnBP<AStaticMeshActor>(GetWorld(), TileBlockBP, GenSpawnLoc, GenSpawnRot);
                grid[dx][dy] = BlockTile;
            }
            else{
                y -= 2;
            }
        }
    }
}

[/]

I updated the codes, apparently the copy paste from the old forums didnt work exactly.

I’m updating the other posts right now too EDIT Done

I will definitely put some time aside in the future to look into this.
Thank you for sharing!

-Jeremy-

I haven’t had a to comb through the code, but is there a way to adjust the maze complexity, and how many entrances / exits there are? Thanks for posting your work - definitely appreciated!

[=JBaldwin;9656]
I will definitely put some time aside in the future to look into this.
Thank you for sharing!

-Jeremy-
[/]

[=;11117]
I haven’t had a to comb through the code, but is there a way to adjust the maze complexity, and how many entrances / exits there are? Thanks for posting your work - definitely appreciated!
[/]

Hey thanks for checking it out guys! :smiley:

Currently there is no way to change the way the maze is spawned like complexity or rooms or levels yet but you can change the size by a simple number change in the HUD Blueprint :wink:

im working on other algorithms that are far superior so you can generate rouge-like dungeons and multilevel levels too, i think with everything combined i.e. mazes, rooms, halls, pits, prefab roobs + multilevelness there will be enough parameters exposed to get something nice for .

[=SaxonRah;11531]
Hey thanks for checking it out guys! :smiley:

Currently there is no way to change the way the maze is spawned like complexity or rooms or levels yet but you can change the size by a simple number change in the HUD Blueprint :wink:

im working on other algorithms that are far superior so you can generate rouge-like dungeons and multilevel levels too, i think with everything combined i.e. mazes, rooms, halls, pits, prefab roobs + multilevelness there will be enough parameters exposed to get something nice for .
[/]

That’s exactly the intent behind my question; is a substantial addition as is to the community, and very much appreciated. I imagine could be used to procedurally generate side scrolling platformers as well. If it counts for anything, I’d love to see the addition of prefabs and complexity, as those are the biggest hurdles for using in broad gaming applications. Anticipating your next release :slight_smile:

It’s amazing how can turn into a great roguelike, kudos my friend! Greatly done :smiley:

I’m super excited to announce I’m almost done programming the rest of the dungeon generation.

right now i have a dungeon generator + 2 different types of ‘room generation’ a House Layout(Room with mini-rooms it has a random value of 0.0 - 1.0 of room vastness) and a Maze

Currently I’m trying to make it so mazes and the house layout can be rooms inside the dungeon gen currently it just spawns empty rooms.

A silly little picture to help visualize.

&stc=1

Very cool, SaxonRah! Looking forward to your next update.

&stc=1

Dungeons are now generated as a text file with defined characters per tile.
*is due to people wanting a marketplace plugin / also massive performance increase! *

There also have been massive improvements to the way dungeons are made, you can place things inside rooms and in halls, rooms aren’t as far away, a dungeon can now be a room (so soon that means a room can be a maze, a template room, or a house-layout )

also soon mazes can either be perfect(random) or linear a % between the two and has sparseness value

I’ve gotta change all the rest of the algorithms to test based. The house-layout is going to be a b!t*h.

More to come shortly.

[=SaxonRah;21559]

&stc=1

Dungeons are now generated as a text file with defined characters per tile.
*is due to people wanting a marketplace plugin / also massive performance increase! *

There also have been massive improvements to the way dungeons are made, you can place things inside rooms and in halls, rooms aren’t as far away, a dungeon can now be a room (so soon that means a room can be a maze, a template room, or a house-layout )

also soon mazes can either be perfect(random) or linear a % between the two and has sparseness value

I’ve gotta change all the rest of the algorithms to test based. The house-layout is going to be a b!t*h.

More to come shortly.
[/]

Hey SaxonRah,

when you say template room, is that a prefab room? Looking great. Any idea when we’ll be able to use the plugin?

[FONT=Comic Sans MS]Woohoo!

The dungeon maker sounds awesome!

I request video of a generated dungeon with AI running around in it!

:slight_smile:

Rama

I’ve fixed it :slight_smile:

I’m recording a video today.

&stc=1

&stc=1

&stc=1

[COLOR=“#0000FF”]Code for You SaxonRah![/COLOR]

and others!

I made my own USTRUCT system for having a multi-dimensional UPROPERTY() friendly dynamic array version of your maze data structure.

Here’s that code for you and others to enjoy!

.h


USTRUCT()
struct FMazeGridRow
{
	GENERATED_USTRUCT_BODY()

	UPROPERTY()
	TArray<AStaticMeshActor*> Columns;
	
	void AddNewColumn()
	{
		Columns.Add(NULL);
	}
	//default properties
	FMazeGridRow()
	{
		
	}
};




USTRUCT()
struct FMazeGrid
{
	GENERATED_USTRUCT_BODY()

	UPROPERTY()
	TArray<FMazeGridRow> Rows;
	
	void AddNewRow()
	{
		Rows.Add(FMazeGridRow());
	}
	
	void AddUninitialized(const int32 RowCount, const int32 ColCount)
	{
		//Add Rows
		for(int32 v = 0; v < RowCount; v++)
		{
			AddNewRow();
		}
		
		//Add Columns
		for(int32 v = 0; v < RowCount; v++)
		{
			for(int32 b = 0; b < ColCount; b++)
			{
				Rows[v].AddNewColumn();
			}
		}
	}
	
	void Clear()
	{
		if(Rows.Num() <= 0) return;
		//~~~~~~~~~~~~~~~
		
		//Destroy any walls
		const int32 RowTotal = Rows.Num();
		const int32 ColTotal = Rows[0].Columns.Num();
		
		for(int32 v = 0; v < RowTotal; v++)
		{
			for(int32 b = 0; b < ColTotal; b++)
			{
				if(Rows[v].Columns** && Rows[v].Columns**->IsValidLowLevel() )
				{
					Rows[v].Columns**->Destroy();
				}
			}
		}
		
		//Empty
		for(int32 v = 0; v < Rows.Num(); v++)
		{
			Rows[v].Columns.Empty();
		}
		Rows.Empty();
	}
	//default properties
	FMazeGrid()
	{
		
	}
};


**Maze Grid Var Declaration for Persistence and Global Access**



```

//Now you have dynamic array benefits and also UPROPERTY()!
UPROPERTY()
FMazeGrid JoyMazeGrid;

```


	
.Cpp



```

//Init Maze
JoyMazeGrid.Clear();
JoyMazeGrid.AddUninitialized(tileX, tileY);
	
//Sample usage
//JoyMazeGrid.Rows[x].Columns[y] = SpawnBP<AStaticMeshActor>(GetWorld(), ...

```



Summary

The final result of all of is that you have

  1. dynamic array benefits (easily change the maze size and regenerate during runtime)

  2. global access to the MazeGrid Actors, even from other classes

  3. GC protection from the UPROPERTY() (if not using actors/objects for some reason)

  4. And yet the syntax for 2D array using UPROPERTY() and TArray is still clean and clear and precise

JoyMazeGrid.Rows[x].Columns[y]

Enjoy!

Rama

PS:

I also wrote a function to clear the maze / destroy any actors.

You have to pre-initialize the array to use the intuitive 2D array accessor method.

[=Rama;27139]
[COLOR=#0000FF]Code for ![/COLOR]
Enjoy!

Rama

[/]

O_O! is very awesome and useful stuff. :slight_smile: Thanks allot!

I’ve been so reluctant to update everything to a proper format ie wiki + the new code i have; is that ever since 4.1 - The Navmesh seems to be broken in type of usage.
I cannot get any type of ai to work in kind of environment. Thus I’ve been doing nothing but trying to get ai to work again with it.
If anyone can get an ai working with spawned at runtime bp’s maze let me know how you’ve done this. I’ve done it seemingly 101 different ways and none of them work anymore in 4.1)

Just chiming in to say that is Cool™. I’ve done some random generated terrain and rooms way back when, and is nostalgic. :slight_smile:

[=SaxonRah;27990]
O_O! is very awesome and useful stuff. :slight_smile: Thanks allot!

I’ve been so reluctant to update everything to a proper format ie wiki + the new code i have; is that ever since 4.1 - The Navmesh seems to be broken in type of usage.
I cannot get any type of ai to work in kind of environment. Thus I’ve been doing nothing but trying to get ai to work again with it.
If anyone can get an ai working with spawned at runtime bp’s maze let me know how you’ve done this. I’ve done it seemingly 101 different ways and none of them work anymore in 4.1)
[/]

Dynamic Nav Meshes broken?!?!!?!

you should post about on the Answerhub!

:slight_smile:

Rama

[=Rama;44012]
Dynamic Nav Meshes broken?!?!!?!

you should post about on the Answerhub!

:slight_smile:

Rama
[/]

I thought I should ! I wasn’t sure if was just me being an idiot, But im pretty sure they are broken now. I’ll make an Answerhub question asap. :slight_smile:
questions/44001/is-the-dynamic-navmesh-broken.html