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):
We use maze locations extensively in the
Maze module. To create a
Maze struct, we have the
new function as a bit of sugar.
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 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
randomly_fill_maze/3. Then we place a number of walls based on the
sparseness provided via
random_cell/3. After, we replace the
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
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
column. In the event
column are out of bounds of the list, we have default values to fall back on.
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:
Sis for the starting position of the maze
Gis for the goal of the maze
Xis 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
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.