title: Creating a 'hard' maze using Prim's Algorithm
body: <p>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:</p>
  
  <p>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:</p>
  
  <p><a href="https://i.stack.imgur.com/ApUR6.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ApUR6.png" alt="enter image description here"></a></p>
  
  <p>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:</p>
  
  <p><a href="https://i.stack.imgur.com/2m4JJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/2m4JJ.png" alt="enter image description here"></a></p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Another approach I tried is the one used in my code:</p>
  
  <pre><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])
  </code></pre>
  
  <p>This was to try and have a reasonable possibility of a block added to the potential_passage_list earlier on to be placed.</p>
  
  <p>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?</p>
  
  <p>I am using python 3, and the pygame library to display everything.</p>
  
  <p>Here is my code, if you can make sense of it:</p>
  
  <pre><code>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 &lt;= 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 &lt; 0 or cell_x &gt;= maze_length - cell_size or cell_y &lt; 0 or cell_y &gt;= 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()
  </code></pre>
  
  <p>Feel free to take my code, play around with it, and share what you have found works well.</p>
  
  <p>Thanks!</p>