Exploring and traversing a maze…

A while ago, I mentioned that I was taking a deep interest into the “Advent of Code” (AoC) project by Eric Wastl. Since then, I’ve filled my dedicated Github repository quite a lot: I’ve worked on this year’s challenges both in Python and Javascript (Node JS), and I’ve also started to take a look at some challenges from 2018. Recently, one of the challenge was about maze exploration and traversal and it re-acquainted me with interesting algorithmic concepts.

To me, the AoC programming puzzles are really great for several reasons: they aren’t too long to solve, they train you in many algorithms, they show you how important optimization is… and the overall story is quite funny! Anyway, I’ve been doing plenty and learning a lot lately thanks to AoC. What I find very nice is that each problem helps me (re)discover both language-specific tricks and programming concepts or common algorithms (test-driven development, time complexity, recursive functions, regular expressions, path finding strategies…).

Day 15’s challenge was focused on discovering and walking through a maze. The story is as follows: we are in a spaceship and we need to fix the oxygen system that seems to be having some difficulties; to do so, we can control a little robot stuck in the same room as the oxygen system – we want it to reach this system as quickly as possible. The catch? We don’t know where the oxygen system is exactly and we can only get information on the room’s shape by moving the robot and getting feedback from it: whenever it is asked to make a move, the robot sends us a message to say whether it successfully completed the action – that means the target position was empty -, whether it got blocked – that means the target position is a wall -, or whether it found the oxygen system. So, the idea is to ask the robot to move around (and sort of run into walls blindly, which is cruel, but heh…) to be able to map out the room and find the oxygen system.

Something worth noting is that the board can be seen as a graph where each tile is a node and the fact that a neighbor tile is accessible is an edge. This means that the problems we will study can be regarded as graph problems and solved with usual graph-related algorithms.

Ultimately, we want to reach the oxygen system by walking the shortest path and turning the system on to fill the room with oxygen. Since we don’t have the room map to begin with, we’ll need to have a 3-steps process:

  1. explore the room with the robot to identify the corridors, the walls and the target position (i.e. the position of the oxygen system)
  2. find the shortest path from the initial position of the robot to the aforementioned target position
  3. compute how the oxygen flows from the oxygen system to the rest of the board once turned on

For now, I’ve solved the problem in Python – and I’ve also had some fun with visualizations to show how the algorithms process the maze (using the NumPy and PIL Python libraries). I’ll include the videos that can be created with my program in the article because I think they give an intuition of how the algorithms work.

Now, let’s study each step a bit more in detail.

Note: having the robot move and run the program that was passed to it relies on a piece of code that was developed previously during the month. Still, we can easily decouple the robot’s program execution part from the maze-related problems. In this article, I won’t dive into the details of how the program is run; I might actually do another article specifically on this topic because it requires you to reimplement a mini-compiler and it’s really interesting to see how it was gradually improved through the challenges…

Exploring the maze

First thing first, we need to understand what our environment is. The technique is to “flow” through the maze board and bump into all the walls until we’ve completely mapped out the room. In other words, we will move the robot through the entire maze systematically and keep track of the type of each tile in the board: either 0 for a wall, 1 for an empty space or 2 for the target point. In the end, this will provide us with a board that matches each tile coordinate to its type.

The maze exploration is done recursively by finding out the type of all the tiles in the neighborhood of the robot’s current position, then moving it to one of the neighbor and reiterating the process with this new position, and move again, and so on… we do this until we are done exploring the maze, or we are stuck somewhere. Whenever this happens, we can simply backtrack to the last unexplored tile and recurse from the next neighbor.

Here is a little video of the exploration process (I have fixed the image size beforehand although the robot first knows about only a few tiles and slowly discovers the rest):

 

In this visualization, we show the various types of tiles with different colors:

  • in green, the start position of the robot
  • in red, the target position (position of the oxygen system)
  • in grey, the walls
  • in white, the empty (and walkable) corridors

Walking the maze

Alright, we have now explored the entire maze and therefore found the position of the oxygen system. It’s time to find the shortest path to it and hopefully reach it in time to restore the oxygen in the room!

There are several algorithms to do this but a very common way of finding the shortest path in a graph is to use Dijkstra’s algorithm. It was conceived by Edsger Dijkstra in the late 1950s and can be applied to weighted or unweighted graphs to determine the best path between two nodes (in our case, the tile where the robot initially sits and the tile where the oxygen system sits).

Note: Dijkstra’s algorithm can be seen as a special case of breadth-first search, and it can be further improved with the A* search algorithm – if you have additional information on your graph, it can reduce the size of the subgraphs to check and thus give a better execution time.

The idea of this algorithm is to prepare a table linking each tile to its “best” neighbor, meaning the tile next to it that will allow us to get to the target with the minimal number of moves. By maintaining a record of all the nodes that have already been visited, we make sure that we don’t examine the same tile twice and that the algorithm eventually finishes. When this pairing is done, we simply need to walk back from the target position to the source position by taking the best neighbor each time. Basically, Dijkstra’s algorithm gives you the path from target to source and can be reversed at the end to get the required path. The distances computations is done in the following way:

  • start from an initial position that has a null distance to the start, and consider all other nodes have an infinitely great distance to the start
  • while you still have nodes to visit or while you haven’t reached the target position, keep computing:
    • when you’re on a node, its distance to the start is whatever “parent” you’ve traversed to get there’s own distance to the start, plus the distance between the “parent” and current tile (here: all distances are 1 because we don’t weight the edges of our graph)
    • you mark this tile as visited
    • you compute the distance of each neighbor of the current tile to the start
    • you move to the one that has the smallest distance

Note: A*’s improvements mainly rely on another distance table that “predicts” what the distance of each node should be from the end position and then considers the best neighbor to be the one that gives a minimal distance both to the start and the end of the path. This prediction is done using some heuristics that are more or less complex.

Below is another short video that shows the path that is found by the algorithm before it is reversed (it goes from the target point, in red, to the source point, in green). The tiles in the path are colored in yellow on the previously computed grid:

“Filling” the maze

Part II of the problem asks you to determine how long it will take to fill the entire room with oxygen once the system is turned back on. This can be studied as a graph flow problem: you want to see how fast the various nodes in your graph are reached if you “propagate something” from an initial position and let if “flow” down the graph.

You may know that there are two common ways of exploring a graph: either with a depth-first search (DFS) or a breadth-first search (BFS). The main technical difference is that DFS relies on stacks (that are LIFO structures) whereas BFS relies on queues (that are FIFO structures). What this actually means is that a DFS follows a path until it reached the end while a BFS works “level per level”; a DFS will look at a neighbor in the graph and then recursively process this neighbor and its neighbors until it can’t, while a BFS will instead look at all the neighbors and only then move on to the first one to process it the same way.

Note: for more details on the differences between DFS and BFS, you can check out this article on Tech Differences.

Here, from a computation point of view, both types of search would work (the graph is not big enough for the time/memory differences between DFS and BFS to really kick on). Actually, I had first implemented a DFS but decided to change to a BFS so that I could do the visualization. Indeed, when we think of this problem, we clearly “feel” that we would rather see the oxygen flow to all neighbors and only then to their own neighbors, instead of having some “branch” of the maze being suddenly filled with oxygen as we exit the deep recursion.

Take a look at the filling process starting from the oxygen system’s position – the tiles that are currently filled with oxygen are shown in blue:

 

What happened? The algorithm works as follows:

  • start from a given position (here, the oxygen system, in red)
  • fill each of its neighbors with oxygen and store all of those neighbors in the queue of nodes to check at the next iteration (also, remember that they belong to “generation #1”)
  • while you have nodes to check in the queue:
    • pop the node out of the queue and get two relevant pieces of information about it: its position (let it be (x,y)) and its generation (let it be n)
    • get all the neighbors that are accessible (i.e. that are neither “walls” nor already filled with oxygen) – their positions can be (x+1,y)(x-1,y)(x,y+1) or (x,y-1)
    • for each neighbor, fill it with oxygen and add it to the queue of nodes to check as a member of the “generation #n+1″

This way, we do a breadth-first search through our graph and we can easily plot the board at each iteration to have our oxygen flow propagate through the maze as shown in the video. If you want to know how many iterations it required, you have to be careful not to just increment a counter each time you pop a node out of the queue, because all nodes of the same generation should count only for 1 iteration.

To conclude

Graph theory is used in many specialties because graphs can model plenty of situations be it in pure maths, computer science, biology, chemistry, physics, linguistics, sociology, economy, logistics… Since Leonhard Euler’s first paper on the topic in 1736, the field has developed immensely and is now present almost everywhere around us.

Graphs are a very powerful modeling tool that allow us to extract relevant data from a given state and to even predict some additional information about it (like the optimal paths in it, the interesting subsets it comprises, the evolution of flows, etc.). While there are still lots of unsolved problems in this domain, we also have an amazing gallery of nice algorithms to look at and just looking at Wikipedia’s list of graph theory topics gives you an idea of how complex the field can be!

What I like most about graphs is how they can represent things in a surprising way: on the one hand, it can be quite logical to take a network of cities and roads and map it as a set of vertices and edges; but on the other hand, optimizing waiters schedule by assigning them colors and using graph coloring algorithms to solve the problem is less obvious. Modeling a problem with graphs can often imply looking at it in a different way and I do believe it’s a great way of making sure you’re fully familiar with your question. If you’re not able to rephrase the problem, you’re probably not comfortable with it yet to solve it. Just like any modeling tool, graphs are a double-edge sword: if you use them right, then you get a synthetic representation of your situation but if you glue one too hastily on your problem, you might just deform or hide away some information.

In my opinion, AoC and other programming puzzles of this kind are a nice way of approaching fields like this one, of scratching the surface through a narrow problem and perhaps getting you curious about the rest. Today, I talked about graph theory but I will surely post other articles as I continue working on Advent of Code about other domains that these challenges offer you to study!

References
  1. Advent of Code’s about: https://adventofcode.com/2019/about
  2. My Github’s repository for AoC: https://github.com/MinaPecheux/Advent-Of-Code
  3. Tech Differences, “Difference Between BFS and DFS” (https://techdifferences.com/difference-between-bfs-and-dfs.html), October 2017. [Online; last access 16-December-2019].
  4. I. Wikimedia Foundation, “Test-driven development” (https://en.wikipedia.org/wiki/Test-driven_development), November 2019. [Online; last access 16-December-2019].
  5. I. Wikimedia Foundation, “Time complexity” (https://en.wikipedia.org/wiki/Time_complexity), December 2019. [Online; last access 16-December-2019].
  6. I. Wikimedia Foundation, “Recursion (computer science)” (https://en.wikipedia.org/wiki/Recursion_(computer_science)), December 2019. [Online; last access 16-December-2019].
  7. I. Wikimedia Foundation, “Regular expression” (https://en.wikipedia.org/wiki/Regular_expression), December 2019. [Online; last access 16-December-2019].
  8. I. Wikimedia Foundation, “Pathfinding” (https://en.wikipedia.org/wiki/Pathfinding), September 2019. [Online; last access 16-December-2019].
  9. I. Wikimedia Foundation, “Dijkstra’s algorithm” (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), December 2019. [Online; last access 16-December-2019].
  10. I. Wikimedia Foundation, “A* search algorithm” (https://en.wikipedia.org/wiki/A*_search_algorithm), November 2019. [Online; last access 16-December-2019].
  11. I. Wikimedia Foundation, “Graph theory” (https://en.wikipedia.org/wiki/Graph_theory), December 2019. [Online; last access 16-December-2019].

Leave a Reply

Your email address will not be published. Required fields are marked *