Maze Generation with Elixir

Continuing with selected sections of Classic Computer Science Problems in Python (CCSPiP) by David Kopec, we build mazes and attempt to solve them. This post corresponds to Chapter 2 Section 2.

The generic search concept established in Chapter 2 is reused and expanded elsewhere in the book. This goes to show how powerful, and general, search algorithms can be. To make this more manageable for the reader, the material is to be split into separate posts and build off of each other. The approximate plan is:

• Maze Generation
• Depth First Search
• Breadth First Search
• A* Search

Of course, the search algorithms covered end up sharing a bit of code, so the latter posts will be smaller compared to this one.

There is a lot of code produced in this section. Please check the GitHub repository if you are interested in seeing it in full. To keep the post's size reasonable, we are only going to focus on a subset of the overall code. There is room for improvement, but it will suffice. We might not have written the most idiomatic Elixir, but the static code analysis tool credo doesn't complain.

In order to stay somewhat aligned with the Python approach, structs were introduce for the first time in this series. At a high level, you can think of them as maps with only specific fields. Overall, structs proved invaluable here... they let the code better mirror the CCSPiP approach, while allowing for clearer typespecs.

Maze Generation with a List of Lists

A maze location consists of a row, column, and arbitrary value (such as "X" for a wall or " " for an open space):

defmodule CCSP.Chapter2.MazeLocation do
  alias __MODULE__, as: T

  @type t :: __MODULE__.t()

  defstruct value: nil, row: nil, column: nil

  @spec new(String.t(), non_neg_integer, non_neg_integer) :: t
  def new(value, row, column) do
    %T{value: value, row: row, column: column}
  end
end

We use maze locations extensively in the Maze module. To create a Maze struct, we have the new function as a bit of sugar.

@type location :: {non_neg_integer, non_neg_integer}
@type maze_state :: list(list(MazeLocation.t()))
@opaque t :: __MODULE__.t()

defstruct state: [], total_rows: 0, total_columns: 0

@spec new(maze_state, non_neg_integer, non_neg_integer) :: t
def new(state, total_rows, total_columns) do
  %T{state: state, total_rows: total_rows, total_columns: total_columns}
end

Our maze_state typespec is defined as a list of lists of MazeLocation. During an earlier attempt, this was a nested list of tuples, but it got somewhat painful to read, so the structs were introduced.

To create a maze and populate it with various types of cells, we have init/5:

@spec init(integer, integer, float, location, location) :: t
def init(rows \\ 9, columns \\ 9, sparseness \\ 0.2, start \\ {0, 0}, goal \\ {9, 9}) do
  randomly_fill_maze(rows, columns, sparseness)
  |> List.update_at(
    elem(start, 0),
    &List.update_at(&1, elem(start, 1), fn location -> %{location | value: cell("START")} end)
  )
  |> List.update_at(
    elem(goal, 0),
    &List.update_at(&1, elem(goal, 1), fn location -> %{location | value: cell("GOAL")} end)
  )
  |> new(rows + 1, columns + 1)
end

@spec randomly_fill_maze(integer, integer, float) :: maze_state
defp randomly_fill_maze(rows, columns, sparseness) do
  Enum.map(0..rows, fn row ->
    Enum.map(0..columns, fn column ->
      random_cell(row, column, sparseness)
    end)
  end)
end

The init/5 function has several default values to let us call init/0 for convenience. Running through the body of the function, we start by creating a list of lists of MazeLocation in randomly_fill_maze/3. Then we place a number of walls based on the sparseness provided via random_cell/3. After, we replace the start and goal location values in the event they were turned into walls. After all this, we feed the nested list into new/3, which finally creates the Maze struct.

The way to access or update a specific element by position in a nested list is not particularly pleasing. There are some blog posts and StackOverflow questions about this topic but they all focus on lists of keywords, which isn't quite the same thing. It feels like if deeply nested lists are involved, maps should be considered as a viable option instead.

Find Your-Cell and Neighbors

Moving on, another well-used function is get_cell/3, which relies on Enum.at/3 to retrieve the list at row and the specific MazeLocation at column. In the event row or column are out of bounds of the list, we have default values to fall back on.

@spec get_cell(t, integer, integer) :: MazeLocation.t()
def get_cell(maze, row, column) do
  maze.state
  |> Enum.at(row, [])
  |> Enum.at(column, nil)
end

Quite simply, get_cell/3 extracts a specific MazeLocation from the maze. It is used heavily in the successors/2 function, which for a given cell, returns non blocked orthogonal neighbors. The function is rather lengthy and somewhat uninteresting as it is repetitive logic, but the gist of it is checking adjacent cells to the given cell and seeing if it is blocked with an "X" value.

Searching for a Pretty View

Our cutting edge data visualization tool to better understand our mazes is the console. To view the maze, we have pretty_print/1, which takes in the maze's state rather than the maze itself:

@spec pretty_print(list(list(maze_state)))) :: :ok
def pretty_print(maze_state) do
  Enum.each(maze_state, fn row ->
    Enum.each(row, &IO.write(" #{&1.value} "))
    IO.puts("")
  end)
end

The extra white space wrapping the value is to make the maze, well, pretty. If you omit the white space then the maze appears more vertical than horizontal, which looks a bit weird. An example with the whitespace:

 S  *  *  *                   
 X     X  *  X                
       X  *  X           X    
    X     *              X  X 
          *  *  *             
                *  *     X  X 
    X              *  *       
                      *  *    
             X           *  * 
 X              X        X  G 

• S is for the starting position of the maze
• G is for the goal of the maze
• X is for a wall or other impassable barrier
• * is the actual final path the maze solver takes

Note it is possible for the maze to seal the starting or goal positions with X - the maze becomes impossible to solve in this case. We could avoid this situation by checking if a cell is surrounded by walls during the randomly_fill_maze/3 function... but then it wouldn't quite be random, would it?

To wrap all this together, we call init/5 and feed the returned Maze struct's state into pretty_print/0:

maze = Maze.init(9, 9, 0.2, {0, 0}, {9, 9})
Maze.pretty_print(maze.state)

We Must Go Deeper

Naturally, one of the first things you do once you create a maze generator is kick the wheels and go from a nice small maze like a 5 by 5 to a massive 500 by 500. This can test how effective your data structures and algorithms actually are.

The maze generation completes fast enough, but we hit a snag when solving the maze with any search algorithm. Luckily, the profiling tool ExProf came to the rescue. It was very simple to wrap the code in the profile macro and get some basic, albeit, useful information about what was going on.

After some digging, it was discovered that the successors/2 function was wildly inefficient... as much as 75% of the time running was spent in this function. Even more digging revealed that the numerous calls to get_cell/3 are the real culprit. If you recall, lists in Elixir are linked lists - to reach the end element, you must first traverse the entire list. In the original implementation of successors/2, we would call get_cell/3 between four and eight times. This is fine for a small maze, but the application got bogged down doing this for large mazes as it has to traverse so much so deep.

To remedy this in the long run, the most likely implementation of the maze state would be something along the lines of a map with a key consisting of a the row and column for a specific MazeLocation (or another map-based solution). This approach was not adopted here as it deviates quite a bit from CCSPiP.

Our interim solution, the code seen in this post, reduces the number of get_cell/3 calls down to four, which is fast enough for a 100 by 100 maze to be generated and solved.

The Path has been Found

This post has been full of twists, turns, and doubling back to earlier points, but we've reached our goal. Now we can rest and reflect on this sojourn.

This was the first foray into any significant data modeling with Elixir and manipulating nested lists. Lots of experimentation and refactoring took place as it became apparent certain approaches would not pan out nicely. Even then, we are probably a few more iterations away from a solution we would be content with. On the bright side, the way the functions compose together makes extending this maze generation straightfoward. For instance, if we wanted consistent corridors and turns in the maze, a function to replace randomly_fill_maze/3 is easy to introduce.

If you like what you have read, please consider sharing this post via your preferred social network. When a post is popular it provides a certain sense of achievement and motivates me to write more potentially-useful-to-someone-someday blog posts. It is quite the win-win situation for everyone. As always, if you see an error, please feel free to reach out.

Photo by Rafif Prawira on Unsplash