Creating a 'hard' maze using Prim's Algorithm

Question

I am using Prim's Algorithm to create a maze. I have successfully done so, but I am now trying to make it 'harder' by changing the way that it selects potential cells to be added to the maze. In my mind, 'hard' lies between two extremes:

Extreme #1 is a completely random selection of cells in the potential passage list, in which each branch develops at an approximately equal pace. This has a lot of different branches, but once you get to the point of origin you can pretty much follow a straight line towards the desired location. Here is a picture showing this approach:

Extreme #2 is where the last thing added to the list is selected, creating a long, tedious, easy maze. It is formed when you only pick the last item put into the potential passage list. Here is a picture showing this approach:

I am trying to put a balance on this by prioritizing cells placed most recently, but it is difficult to create branch-offs, as can be seen in the first, but still having a path that leads around the entire maze.

The most interesting way of attempting to do this was when I was trying to have a 50% chance of the last block added to be placed, then a 50 percent chance of the next if that one failed, and so on. However, I messed this up and tried to do the index of [-0] first, making a 50% chance of the first block to be added, then thee last, then the second last, and so on. This created an interesting maze, but when I 'fixed' it, the maze looked a lot like the second extreme.

Another approach I tried is the one used in my code:

for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])

This was to try and have a reasonable possibility of a block added to the potential_passage_list earlier on to be placed.

So, my question is, how can you create a 'hard' maze, containing lots of branch-offs, but a non-predictable pattern? What algorithms could be used to do this?

I am using python 3, and the pygame library to display everything.

Here is my code, if you can make sense of it:

import pygame
from random import shuffle, randint

# variables
######
# changeable variables
cell_size = 7  # cannot be less than 3
maze_length = 160 * cell_size + 1
maze_height = 100 * cell_size + 1
######

# colours
black = (0, 0, 0)
white = (245, 245, 245)
red = (255, 0, 0)
blue = (0, 0, 255)

# other variables
passage_list = []
potential_passage_list = []
impossible_passage = []
random_cell = []
done = False

# initialize pygame and display screen
pygame.init()
screen = pygame.display.set_mode((maze_length, maze_height))
pygame.display.flip()


def one_connection(cell_x, cell_y):
    # ensure that it will only touch one passage
    count = 0

    if [cell_x + cell_size, cell_y] in passage_list:
        count += 1
    if [cell_x - cell_size, cell_y] in passage_list:
        count += 1
    if [cell_x, cell_y + cell_size] in passage_list:
        count += 1
    if [cell_x, cell_y - cell_size] in passage_list:
        count += 1

    if count <= 1:
        return True
    else:
        return False


def valid_cell(cell_x, cell_y):
    # check if already in potential_passage_list
    if [cell_x, cell_y] in potential_passage_list:
        impossible_passage.append([cell_x, cell_y])
    # check if in impossible list
    elif [cell_x, cell_y] in impossible_passage:
        impossible_passage.append([cell_x, cell_y])
    # check if out of boundary
    elif cell_x < 0 or cell_x >= maze_length - cell_size or cell_y < 0 or cell_y >= maze_height - cell_size:
        impossible_passage.append([cell_x, cell_y])
    # ensure that it will only touch one passage
    elif not one_connection(cell_x, cell_y):
        impossible_passage.append([cell_x, cell_y])
    # check if it isolates any walls / cut off unconnected corners
    elif (([cell_x + cell_size, cell_y + cell_size] in passage_list and [cell_x + cell_size, cell_y] not in
           passage_list and [cell_x, cell_y + cell_size] not in passage_list) or
          ([cell_x + cell_size, cell_y - cell_size] in passage_list and [cell_x + cell_size, cell_y] not in
           passage_list and [cell_x, cell_y - cell_size] not in passage_list) or
          ([cell_x - cell_size, cell_y + cell_size] in passage_list and [cell_x - cell_size, cell_y] not in
           passage_list and [cell_x, cell_y + cell_size] not in passage_list) or
          ([cell_x - cell_size, cell_y - cell_size] in passage_list and [cell_x - cell_size, cell_y] not in
           passage_list and [cell_x, cell_y - cell_size] not in passage_list)):

        impossible_passage.append([cell_x, cell_y])
    # check if already in passage_list
    elif [cell_x, cell_y] not in passage_list:
        return True


# functions
def maze_passage(cell_x, cell_y):
    # reset block_passage_list
    block_passage_list = []

    # remove from list so it does not interfere with valid_cell procedure
    potential_passage_list.remove([cell_x, cell_y])
    if valid_cell(cell_x, cell_y):
        # display rectangle
        pygame.draw.rect(screen, white, [cell_x, cell_y, cell_size, cell_size])
        pygame.display.update()

        passage_list.append([cell_x, cell_y])

        # add valid walls to block_passage_list
        if valid_cell(cell_x + cell_size, cell_y):
            block_passage_list.append([cell_x + cell_size, cell_y])
        if valid_cell(cell_x - cell_size, cell_y):
            block_passage_list.append([cell_x - cell_size, cell_y])
        if valid_cell(cell_x, cell_y + cell_size):
            block_passage_list.append([cell_x, cell_y + cell_size])
        if valid_cell(cell_x, cell_y - cell_size):
            block_passage_list.append([cell_x, cell_y - cell_size])

        shuffle(block_passage_list)

        for j in block_passage_list:
            potential_passage_list.append(j)


# create initial cell
start_cell = [randint(0, int(maze_height / cell_size))*cell_size, randint(0, int(maze_height / cell_size))*cell_size]
potential_passage_list.append([start_cell[0], start_cell[1]])


# loop for creating maze
while not done:
    for event in pygame.event.get():
        # exit screen when exit pressed in pygame
        if event.type == pygame.QUIT:
            done = True

    # select cell
    for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])
            break

    # check if maze completion finished
    if not potential_passage_list:
        # create start and end
        passage_list.sort()
        pygame.draw.rect(screen, red, [passage_list[0][0] + 1, passage_list[0][1] + 1, cell_size - 2, cell_size - 2])
        pygame.draw.rect(screen, blue, [passage_list[-1][0] + 1, passage_list[-1][1] + 1, cell_size - 2, cell_size - 2])
        pygame.display.update()

Feel free to take my code, play around with it, and share what you have found works well.

Thanks!

Anemoscope

I think to help in answering your question you probably need to define some terms. What is 'hard', is it that we fix an algorithm for traversing a maze and determine which mazes take the longest while also being 'non-predictable', the other thing that needs definition, I'm not sure what to propose as a defintion for this. Sorry for the non answer, I think it's an interesting question. – Flocculate

'Hard' is what a human would find hard. To my understanding, this is composed of two things: 'unpredictability', and 'branch-offs'. 'Predictability' is how easy it is to guess where the maze will go. In the first image, it is extremely predictable, as there is pretty much a diagonal line from start to end, but the second is unpredictable, as it goes in random directions. 'Branch-offs' are the amount of times that it splits in to different paths, and the depth of said paths. The first one has lots of deep branch-offs, but the second one doesn't, making it easy to calculate the path. – Anemoscope

@Justin: I would posit that a reasonable definition of difficulty (in the absence of large-scale order) is the number of steps taken by A* (with the Euclidean heuristic) divided by the length of the correct path. – Nesta

@Davis Herring: To my understanding, wouldn't that always become 1, as A* always finds the optimal route? Correct me if I am wrong. – Anemoscope

@Justin: But it expands additional nodes that are not on the shortest path (and then backtracks when it gets stuck). I’m counting each as a “step”, as if the algorithm were tracing the various paths with a finger. – Nesta

OK, that makes sense. My only concern is that it may make mistakes that a human would easily see, and a human would make mistakes that it would easily see. I don't know, as I have not done anything with A*. In any case, it would be a nice way of quantifying 'hard'. Thanks. – Anemoscope

Prim's algorithm is probably the wrong approach. You don't want a minimum spanning tree; a hard maze would probably be based on a maximum spanning tree. (Well, larger spanning tree; a maximum spanning tree could be a single winding path.) – Ladykiller

I have a small writeup about that. You can use Depth-First Search to generate a harder maze. BFS for an easy maze, and a hybrid for a mild solution: n02870941.github.io/mazes/pages/backtrack.html – Embryologist

Stop making repetitive, trivial edits – Grahamgrahame

Answer 1

Instead of prioritizing recent vs. old cells, I like to use Kruskal's algorithm and specify different selection weights for removing edges in different configurations.

This lets you create mazes with a wide variety of different characteristics. There's a demo you can try here: https://mtimmerm.github.io/webStuff/maze.html

If you favor the options that extend existing paths (slider 1, 2, and 3) it will make harder mazes.

Anagram