My 'Ghost of Mad Man Max' story is a variation of something called the Randomized Prim's algorithm. Max is a character that I created several years ago to explain to my students, in very easy to understand terms, how to create video game mazes. No mind blowing logic, fancy math, or complicated code. Just a simply story of a ghost, a broken water pipe, and a VERY large magic hammer.
(What??)

So....Lets start by explaining what Max's job is all about.

Figure 1 is a view of a bunch of very large concrete blocks, as seen from high above. These blocks are about 8 foot by 8 foot square, and are arranged in such a way that there are 100 empty spaces in-between them, called rooms.

One of these rooms, we will call it Room-A, has a broken water pipe under it. It looks like the sub-contractor may have broken an underground pipe when they put these heavy blocks into place. So, water is now gushing up from the ground, and Room-A is FLOODING!! (and of course, the sub-contractor is no where to be found.)

Now Max, being a ghost, can walk though blocks as easy as walking across an empty kitchen. And, having a very large magic hammer, Max can also smash and remove blocks.

Max's job, is to wander around in the blocks, and randomly check if a block has a flooded room on one side, and a dry room on the other. When Max finds a block that is wet on one side, and dry on the other, he is to use his magic hammer to smash and remove that block, allowing the flood water to flow into the dry room.
IMPORTANT: He is only allowed to smash a block that has a flooded room on one side, and a dry room on the other.
See figure 2.

He is to continue to wonder around at random, smashing blocks that meet this criteria. The flood waters will flow from one room, to the next, and then to the next, as Max smashes more and more blocks. Until at last, there are no dry rooms left.

When there are no dry rooms left, Max is to drain the water, fix the broken pipe, clean up the mess, and then he can go home for the day. See figure 3.

So, at this point there are two very important things we can say about our blocks and rooms:

1. Since water was able to flow from Room-A to all the other rooms, then the water must have followed a path, and only ONE path, from Room-A to each of the other rooms. It may have flowed OUT of this room to other rooms , but it flowed IN to the room through ONLY ONE OPENING. This is because Max is only allowed to smash a wall if it is dry on one side, and wet on the other (prevents him from letting water flow into a room if that room is already flooded).
So now any explorer could walk from any of these rooms, following the path that the water took, to get to Room-A (the source of the water).

2. Since there is only one path from each room to Room-A, then there must be a path, and only ONE path, between any two rooms.
That path may, or may not, go through Room-A.
So now our explorer could walk from any room, to any other room, but there will be only ONE path that they can uses to reach that other room.

In short, we have a MAZE!

And that ladies and gentlemen, is the Randomized Prim's algorithm explained. With the help of a ghost, a hammer, a broken water pipe, and a whole lot of concrete.

About the code.

Bellow, I'm including two python scripts.
The first one (MadManMax01.py) generates a game maze, using the Random Prim's algorithm, as described by the 'Ghost of Mad Man Max' story. The maze will be saved as a json file, which can then be used by other scripts. This script can be changed to generate mazes of different sizes.
The second script (Maze2Image.py) is something that I just threw together at the last minute, to draw the maze created by MadManMax01.py on the screen. It's using the turtle module, but you could easily used PyGame, svgwrite, or any other graphics package or game engine. The images of mazes that I am including in this blog post, were created using this script.

Taking it to the next level.

OK, so that creates a simply maze that started with 100 rooms. It looks pretty simply; easy to find a path from a starting room to a finishing room.
But what if we now do the same thing starting with 100,000 rooms?
Ah, now things are getting interesting. A maze generated from 100,00 rooms is truly a maze that our avatar can get lost in.

OK, now think about this. Lets say that instead of being stacked on the ground, our concrete blocks are stacked on the floors of a 20 story building. There is still a Room-A someplace in the building, but Max is now allowed to smash blocks, floors, and ceilings, if there is water on one side, and none on the other. He should also install some ladders where needed so that our avatars can get up and down. We now have a 3D maze.

OK, now lets add to our maze some portals that will take us, and the water, into other buildings (one to the North, South, East, and West). We now have a 4D maze. Lets now add more portals that go to buildings in other cities; we now have a 5D maze. There is no upper limit, but care should be taken or the player may become frustrated with an overly complicated game.

A few last notes.

As I said in the beginning, there are at least 6 completely different ways (algorithms) that can be used to generate a game maze. This blog post describes a variation of just one.

This wikipedia page descibes several others.
https://en.wikipedia.org/wiki/Maze_generation_algorithm

It may be worth the time to look at these other algorithms as well.

import random
import json

"""
MadManMax01.py
Written by Joseph Roten, 2019-01-26.
This script demistrates how to generate a game maze using
the Random Prim's algorithm, as descripbed by the
'Ghost of Mad Man Max' story.
The maze will be saved as a json file, which can then be used
by other scripts.
This script can be changed to generate mazes of different sizes.
"""

# Define a dictinary to hold the maze.
TheMaze = {}

def IsEven(value):
    """Returns True if the value is an even number."""
    return ((value % 2) == 0)

def IsOdd(value):
    """Returns True if the value is an odd number."""
    return ((value % 2) >0 )

def SetCell(x, y, value = "undefined"):
    """Set the value of a cell of the maze."""
    n = "Cx" + str(x).strip() + "y" + str(y).strip()
    TheMaze[n] = value

def GetCell(x, y):
    """Returns the value of a cell of the maze."""
    n = "Cx" + str(x).strip() + "y" + str(y).strip()
    return TheMaze.get(n, "undefined")

def CheckBlock(x1, y1, x2, y2, x3, y3):
    """Check if the block meets the criteria. If so, Max will smash it."""
    if GetCell(x1, y1) == "block":
        if GetCell(x2, y2) == "empty":
            if GetCell(x3, y3) == "water":
                print (x,y,"Block meets the criteria, smash it.....WACK!")
                SetCell(x1, y1, "water")
                SetCell(x2, y2, "water")
                SetCell(x3, y3, "water")

if __name__ == "__main__":

    # Define the size of the maze.
    # Both of these values should be odd numbers.
    MazeWidth = 21
    MazeHeight = 21

    # Define the name of the file to save the maze into.
    FileName = "Maze1.json"


    # Populate the maze with concrete blocks and empty rooms.
    for x in range(0, MazeWidth):
        for y in range(0, MazeHeight):
            if IsEven(x) or IsEven(y):
                SetCell(x, y, "block")
            else:
                SetCell(x, y, "empty")

    # Fill Room-A with water.
    # The x and y values for Room-A should be odd numbers.
    SetCell(5, 5, "water")
    
    # Do a bit of housekeeping.
    TheMaze['MazeWidth'] = MazeWidth
    TheMaze['MazeHeight'] = MazeHeight
    EmptyRoomFlag = True
    LoopCounter = 0

    # Send Mad Man Max to smash blocks. Let the concret chunks fly !!
    while EmptyRoomFlag:
        EmptyRoomFlag = False
        LoopCounter = LoopCounter + 1
        print ("   LoopCounter = ", LoopCounter)
        for x in range(0, MazeWidth):
            for y in range(0, MazeHeight):
                R = random.randint(1,5)
                if R == 1:
                    CheckBlock(x, y, x+1, y, x-1, y)
                if R == 2:
                    CheckBlock(x, y, x-1, y, x+1, y)
                if R == 3:
                    CheckBlock(x, y, x, y+1, x, y-1)
                if R == 4:
                    CheckBlock(x, y, x, y-1, x, y+1)
                if GetCell(x, y) == "empty":
                    EmptyRoomFlag = True

    # Drain the water from the maze.
    for x in range(0, MazeWidth):
        for y in range(0, MazeHeight):
            if GetCell(x,y) == "water":
                SetCell(x, y, "empty")

    # Save the maze to a json file.
    with open(FileName, 'w') as outfile:
        json.dump(TheMaze, outfile, indent=4)

import json
import turtle

"""
Maze2Image.py
Written by Joseph Roten, 2019-01-26.
This script will read the json file created by MadManMax.py,
and will draw it on the screen.
It's using turtle.py, but you could easily used PyGame,
svgWrite, or any other graphics package.
"""

def SetCell(x, y, value = "undefined"):
    """Set the value of a cell of the maze."""
    n = "Cx" + str(x).strip() + "y" + str(y).strip()
    TheMaze[n] = value

def GetCell(x, y):
    """Returns the value of a cell of the maze."""
    n = "Cx" + str(x).strip() + "y" + str(y).strip()
    return TheMaze.get(n, "undefined")

if __name__ == "__main__":

    # Define the name of the file that holds the info.
    FileName = "Maze1.json"

    # Define the size of the cell on the screen.
    CellSize = 16

    # Load the maze from the file.
    with open(FileName) as InputFile:
        TheMaze = json.load(InputFile)

    # Define our old friend 'Bob the Turtle'.
    Bob = turtle.Turtle()
    Bob.penup()
    Bob.speed(9)

    # Get the Width and Height values from the maze.
    MazeWidth = TheMaze['MazeWidth']
    MazeHeight = TheMaze['MazeHeight']

    # Draw the maze on the screen.
    for x in range(0, MazeWidth):
        for y in range(0, MazeHeight):
            xg = (y * CellSize) - 200
            yg = MazeWidth - (x * CellSize) + 200
            Bob.setpos(xg, yg)
            if GetCell(x,y) == "block":
                Bob.color("black", "grey")
                Bob.pendown()
                Bob.begin_fill()
            if GetCell(x,y) == "water":
                Bob.color("black", "blue")
                Bob.pendown()
                Bob.begin_fill()
            for k in range(4):
                Bob.forward(CellSize)
                Bob.right(90)
            Bob.end_fill()
            Bob.penup()

    # Add a title to the bottom.
    Bob.setpos(-175, -150)
    Bob.write("Figure 3", font=("Arial", 18, "normal"))
    Bob.hideturtle()

Last updated: 2019-01-26

Written by Joe Roten

Computer tech, Graphic Artist, Photographer, Writer, Educator, Programmer, Jack of many trades, Social gadfly, and Scholar without portfolio. http://www.gsw7.net/joe/

Written by Joe Roten

http://www.gsw7.net/joe/

As always

The information on my website is FREE.
But donations to help pay for Coffee and Beer are always welcomed.
Thanks.