Search code examples
pythonrecursive-backtracking

Implementing a recursive backtracker to generate a maze

I'm trying to make a recursive create maze function, however, I am stuck as I do not know how to recursively call it and place the walls.

Can someone tell me how to edit my code to make it work? Thanks

EDIT: Since I didn't add my maze class in, I thought I'd add it in to help see the entire code.

class Maze:
    def __init__(self, Width, Height):
        assert Width>= 1 and Height>= 1

        self.Width= Width
        self.Height= Height
        self.board = np.zeros((Width, Height), dtype=WALL_TYPE)
        self.board.fill(EMPTY)

    def set_borders(self):
        self.board[0, :] = self.board[-1, :] = WALL
        self.board[:, 0] = self.board[:, -1] = WALL

    def is_wall(self, x, y):
        assert self.in_maze(x, y)
        return self.board[x][y] == WALL

    def set_wall(self, x, y):
        assert self.in_maze(x, y)
        self.board[x][y] = WALL

def create_maze(Width, Height, seed=None):
        Width = (Width // 2) * 2 + 1
        Height = (Height // 2) * 2 + 1

        if seed is not None:
            np.random.seed(seed)

        maze = Maze(Width, Height)
        maze.set_borders()

        x, y = rand(0, Width // 2) * 2, rand(0, Height // 2) * 2
        maze.set_wall(x, y)

        visited = []

        visited.append((x,y))

        while len(visited):
            start = visited[-1]

            if maze.in_maze(x - 2, y):
                visited.append((x - 2, y))

            if maze.in_maze(x + 2, y):
                visited.append((x + 2, y))

            if maze.in_maze(x, y - 2):
                visited.append((x, y - 2))

            if maze.in_maze(x, y + 2):
                visited.append((x, y + 2))

            visited.remove(start) # This goes somewhere but I don't know where

            if not maze.is_wall(x,y):
                maze.set_wall(x,y)


        create_maze() #recurse?
Solution

  • Initial issues

    Okay, so to begin with you usually wouldn't setup your recursive function like this. Since you need to call the same function over and over again, you don't want to re-create your maze object each call. You want to perform all of the setup and calculation outside of the recursive function call, and only do one very specific job recursively.

    Setup

    I'm assuming your setup for the maze class is a little like this:

    import random

class Maze:
    def __init__(self, width, height):

        self.width = width // 2 * 2 + 1
        self.height = height // 2 * 2 + 1

        # this creates a 2d-array for your maze data (False: path, True: wall)
        self.cells = [
                      [True for x in range(self.width)] 
                      for y in range(self.height)
                     ]

    def set_path(self, x, y):
        self.cells[y][x] = False

    def set_wall(self, x, y):
        self.cells[y][x] = True

    Ways to think about our maze

    Okay, so now I can begin on the recursive generation itself. Now rather than taking the approach of adding walls, I instead fill the entire maze with walls and "dig" myself the paths.

    In our maze, even though we're treating it like a simple on/off 2d grid with walls and paths, its helpful to picture it more like a series of nodes (junctions) and links between those. I can see you begun to implement this with the way you made sure your maze width and height were odd numbers with (Width // 2) * 2 + 1 for example, and that you only chose even cells (albeit it I couldn't figure out what for).

    Here's a quick diagram to visualise what I mean:

    Maze with nodes

    Each red circle is a node, and as you can see every single odd tile contains a node and is always a path tile. We will automatically assume that every odd tile will contain a path (and therefore a node). This means that when generating our maze, when we "dig" our way through, we will be moving two cells at a time, so that we create a link between nodes (the cells in grey).

    The algorithm

    The essence of the algorithm I will implement will be as follows:

    1. Move in random directions, "digging" my way forward, keeping track of the places I've been
    2. Repeat until I reach a dead end
    3. 'Backtrack' through the places I've been until I find a path with at least one viable path. Go to step 1


    Here's those same steps, in more detail:

    1. Move in random directions, keeping track of where I've been

      1.1. We look around each direction, and see where our move options are

      1.2. Pick a random direction where there is a valid path

      1.3. Move to the new node (remember, we're moving by two cells)

    2. Repeat until I reach a dead end

      2.1. Keep on repeating the process in step one

      2.2. If during step one, you found no path options, you've reached a dead end

    3. Backtrack through the places I've been

      3.1. Follow your footsteps (backtrack) through the nodes previously visited

      3.2. Repeat until you've found a node with at least one unvisited path to try

      3.3. Go to step one (as in, start walking in random directions through the new path)


    Now to implement these steps with a recursive function. Every step we take to a new node (by moving two cells) will be a new function call, with new x-y coordinates. Here's the same steps, but recursively:

    1. Move in random directions keeping track of where I've been

      1.1. Randomly pick a direction and check it hasn't already been visited (eg if we had already walked down it, we would have already "dug" through so it would be a path). So pick any direction which is a wall (eg unvisited)

      1.2. Now move two cells in that direction (but remember to set both the node cell and the link cell between the two nodes to paths, otherwise you've just jumped over a wall). Remember, when 'moving' to a new cell, we are going to call the function again with the new node's x-y coordinates

    2. Repeat until you reach a dead end

      2.1. If during step one, you found that all of your directions contained paths (eg you had already visited every single direction at that node), you need to backtrack

      2.2. Now to backtrack, we are going to exit the current function call. This means we are moving backwards into the previous function which had initially moved us into this current node

    3. Backtrack until you find a path

      3.1. After exiting out of the function call you have now moved back into the previous node, with the previous x-y coordinates. You now go to step one, where you look for potential directions, and if none you go to step two and backtrack even more

    The code

    Okay, so with all of the theory and planning finished, we can now implement our design into code.

    I'm going to create the recursive function as a method of our Maze class like so:

    class Maze:
    # ...
    # constructor and other methods go here
    # ...

    def create_maze(self, x, y):
        # our recursive function goes here

    This means to fully create our maze, we call maze.create_maze(1, 1) (replacing 1, 1 with whatever your starting coordinates are).

    So lets walk through each of the steps we designed earlier, and turn them into code.

    1.1 Pick a random, viable direction

    def create_maze(self, x, y):
    # set the current cell to a path, so that we don't return here later
    self.set_path(self, x, y)

    # we create a list of directions (in a random order) we can try
    all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    random.shuffle(all_directions)

    # we keep trying the next direction in the list, until we have no directions left
    while len(all_directions) > 0:

        # we remove and return the last item in our directions list
        direction_to_try = all_directions.pop()

        # calculate the new node's coordinates using our random direction.
        # we *2 as we are moving two cells in each direction to the next node
        node_x = x + (direction_to_try[0] * 2)
        node_y = y + (direction_to_try[1] * 2)

        # check if the test node is a wall (eg it hasn't been visited)
        if self.is_wall(node_x, node_y):
            # success code: we have found a path
    # failure code: we find no paths

# a function to return if the current cell is a wall, and if the cell is within the maze bounds
def is_wall(self, x, y):
    # checks if the coordinates are within the maze grid
    if 0 <= x < self.width and 0 <= y < self.height:
        # if they are, then we can check if the cell is a wall
        return self.cells[y][x]
    # if the coordinates are not within the maze bounds, we don't want to go there
    else:
        return False

    1.2. Move two cells in that direction, and create the link path cell

    So now the question is, what do we do once we've found a viable path option? The answer: we turn the link cell into a path (so we're not jumping over a wall to our new node), and move two cells in our new direction.

    This becomes:

    # success code: we have found a path

# set our linking cell (between the two nodes we're moving from/to) to a path
link_cell_x = x + direction_to_try[0]
link_cell_y = y + direction_to_try[1]
self.set_path(link_cell_x, link_cell_y)

# "move" to our new node. remember we are calling the function every
#  time we move, so we call it again but with the updated x and y coordinates
self.create_maze(node_x, node_y)

    and then to integrate our success code into our create_maze function, it becomes:

    def create_maze(self, x, y):
    self.set_path(x, y)
    all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    random.shuffle(all_directions)
    while len(all_directions) > 0:
        direction_to_try = all_directions.pop()
        node_x = x + (direction_to_try[0] * 2)
        node_y = y + (direction_to_try[1] * 2)
        if self.is_wall(node_x, node_y):
            # success code: we have found a path

            # set our linking cell (between the two nodes we're moving from/to) to a path
            link_cell_x = x + direction_to_try[0]
            link_cell_y = y + direction_to_try[1]
            self.set_path(link_cell_x, link_cell_y)

            # "move" to our new node. remember we are calling the function every
            #  time we move, so we call it again but with the updated x and y coordinates
            self.create_maze(node_x, node_y)
    # failure code: we find no paths

    2.1. If all of our directions contain paths (they have been visited), then we need to backtrack

    2.2. To backtrack, we exit the function call, which brings us to the previous node

    A simple way to end a function, is to call return. This stops any further code from being run in the function, and returns to the previous function which had called it.

    # failure code: we find no paths

return

    And to add this into our recursive function, it now becomes:

    def create_maze(self, x, y):
    self.set_path(x, y)
    all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    random.shuffle(all_directions)
    while len(all_directions) > 0:
        direction_to_try = all_directions.pop()
        node_x = x + (direction_to_try[0] * 2)
        node_y = y + (direction_to_try[1] * 2)
        if self.is_wall(node_x, node_y):
            link_cell_x = x + direction_to_try[0]
            link_cell_y = y + direction_to_try[1]
            self.set_path(link_cell_x, link_cell_y)
            self.create_maze(node_x, node_y)
    # failure code: we find no paths

   return

    3.1. Try step one again, if not go to step two

    Essentially we have now programmed a fully functional maze generation program, using (to the best of my ability) a fairly good recursive method. Once a function reaches a dead end, it will return, backtrack into the previous function, and continue the process until that function reaches a dead end etc..

    The final code

    import random

class Maze:
    def __init__(self, width, height):

        self.width = width // 2 * 2 + 1
        self.height = height // 2 * 2 + 1

        # this creates a 2d-array for your maze data (False: path, True: wall)
        self.cells = [
                      [True for x in range(self.width)] 
                      for y in range(self.height)
                     ]

    def set_path(self, x, y):
        self.cells[y][x] = False

    def set_wall(self, x, y):
        self.cells[y][x] = True

    # a function to return if the current cell is a wall,
    #  and if the cell is within the maze bounds
    def is_wall(self, x, y):
        # checks if the coordinates are within the maze grid
        if 0 <= x < self.width and 0 <= y < self.height:
            # if they are, then we can check if the cell is a wall
            return self.cells[y][x]
        # if the coordinates are not within the maze bounds, we don't want to go there
        else:
            return False

    def create_maze(self, x, y):
        # set the current cell to a path, so that we don't return here later
        self.set_path(x, y)
        # we create a list of directions (in a random order) we can try
        all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        random.shuffle(all_directions)

        # we keep trying the next direction in the list, until we have no directions left
        while len(all_directions) > 0:

            # we remove and return the last item in our directions list
            direction_to_try = all_directions.pop()

            # calculate the new node's coordinates using our random direction.
            # we *2 as we are moving two cells in each direction to the next node
            node_x = x + (direction_to_try[0] * 2)
            node_y = y + (direction_to_try[1] * 2)

            # check if the test node is a wall (eg it hasn't been visited)
            if self.is_wall(node_x, node_y):
                # success code: we have found a path

                # set our linking cell (between the two nodes we're moving from/to) to a path
                link_cell_x = x + direction_to_try[0]
                link_cell_y = y + direction_to_try[1]
                self.set_path(link_cell_x, link_cell_y)

                # "move" to our new node. remember we are calling the function every
                #  time we move, so we call it again but with the updated x and y coordinates
                self.create_maze(node_x, node_y)
        return

    And there we go! A recursive algorithm to generate a maze. Sorry that I didn't use more of your code, but since I wasn't quite sure where you were going with it I thought I could at least help by showing you some working code.

    One last thing we can quickly add is a print function, so that we can print out our maze to the screen. By using the "double underscore method" (dundermethod) __repr__ (update: use the method name __str__ instead, see comments) we can overwrite the print functionality. The following code generates a string representing our newly generated maze:

    def __repr__(self):
    string = ""
    conv = {
        True: "██",
        False: "  "
    }
    for y in range(self.height):
        for x in range(self.width):
            string += conv[self.cells[y][x]]
        string += "\n"
    return string

    By placing this inside the maze class, we can now perform the following, and it even works starting with even cells!

    >>> maze.create_maze(1, 1)
>>> print(maze)
██████████████████
██      ██      ██
██████  ██  ██  ██
██  ██  ██  ██  ██
██  ██  ██████  ██
██  ██          ██
██  ██████████  ██
██              ██
██████████████████
>>> maze.create_maze(4, 4)
          ██      
  ██████  ██████  
  ██              
  ██████████████  
  ██      ██      
  ██  ██████████  
  ██          ██  
  ██████████  ██  
              ██

    Hope it helped!