Creating a 'hard' maze using Prim's Algorithm

Multi tool use
Multi tool use












8















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:



enter image description here



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:



enter image description here



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!










share|improve this question




















  • 3





    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.

    – Countingstuff
    Dec 21 '18 at 18:53








  • 1





    '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.

    – Justin
    Dec 21 '18 at 19:21






  • 1





    @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.

    – Davis Herring
    Dec 22 '18 at 0:47






  • 1





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

    – Justin
    Dec 22 '18 at 1:49






  • 2





    @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.

    – Davis Herring
    Dec 22 '18 at 3:33
















8















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:



enter image description here



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:



enter image description here



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!










share|improve this question




















  • 3





    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.

    – Countingstuff
    Dec 21 '18 at 18:53








  • 1





    '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.

    – Justin
    Dec 21 '18 at 19:21






  • 1





    @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.

    – Davis Herring
    Dec 22 '18 at 0:47






  • 1





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

    – Justin
    Dec 22 '18 at 1:49






  • 2





    @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.

    – Davis Herring
    Dec 22 '18 at 3:33














8












8








8


4






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:



enter image description here



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:



enter image description here



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!










share|improve this 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:



enter image description here



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:



enter image description here



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!







python maze prims-algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 30 '18 at 0:27







Justin

















asked Dec 21 '18 at 16:21









JustinJustin

1567




1567








  • 3





    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.

    – Countingstuff
    Dec 21 '18 at 18:53








  • 1





    '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.

    – Justin
    Dec 21 '18 at 19:21






  • 1





    @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.

    – Davis Herring
    Dec 22 '18 at 0:47






  • 1





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

    – Justin
    Dec 22 '18 at 1:49






  • 2





    @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.

    – Davis Herring
    Dec 22 '18 at 3:33














  • 3





    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.

    – Countingstuff
    Dec 21 '18 at 18:53








  • 1





    '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.

    – Justin
    Dec 21 '18 at 19:21






  • 1





    @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.

    – Davis Herring
    Dec 22 '18 at 0:47






  • 1





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

    – Justin
    Dec 22 '18 at 1:49






  • 2





    @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.

    – Davis Herring
    Dec 22 '18 at 3:33








3




3





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.

– Countingstuff
Dec 21 '18 at 18:53







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.

– Countingstuff
Dec 21 '18 at 18:53






1




1





'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.

– Justin
Dec 21 '18 at 19:21





'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.

– Justin
Dec 21 '18 at 19:21




1




1





@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.

– Davis Herring
Dec 22 '18 at 0:47





@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.

– Davis Herring
Dec 22 '18 at 0:47




1




1





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

– Justin
Dec 22 '18 at 1:49





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

– Justin
Dec 22 '18 at 1:49




2




2





@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.

– Davis Herring
Dec 22 '18 at 3:33





@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.

– Davis Herring
Dec 22 '18 at 3:33












1 Answer
1






active

oldest

votes


















0














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.






share|improve this answer























    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53887926%2fcreating-a-hard-maze-using-prims-algorithm%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0














    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.






    share|improve this answer




























      0














      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.






      share|improve this answer


























        0












        0








        0







        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.






        share|improve this answer













        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.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Dec 22 '18 at 19:14









        Matt TimmermansMatt Timmermans

        19.3k11632




        19.3k11632






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53887926%2fcreating-a-hard-maze-using-prims-algorithm%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            UbHD4 kk43NxdjktWtZFruim7c9f9uY8qnuG9 NmRA 0c1ozt5Zhqp1eFDJY2icb3i7BVh3bp4t e1ufl,piJOr 8XU4FPJrJf
            Tl5md,jAlZT,H8 7TlS2577QUXgfICf,AkN,uSfG,7htd XPtCVlfYysnvtciS6LL KUIsFY VWu1nObxzK1E

            Popular posts from this blog

            Monofisismo

            Angular Downloading a file using contenturl with Basic Authentication

            Olmecas