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
• 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):

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

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`:

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.

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:

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` 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`:

## 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