Description of the Lab
Overview of the Lab
In this Lab, we program a breadth-first search algorithm for catching a single piece of cheese in a maze, in a minimum number of moves.
As you will see in the articles above, it is very easy to switch between a breadth-first search and a depth-first search if you structure your code well using functions (as we saw in the good programming practices). Try to keep that in mind while you program!
Set up the environment
As always, you should start by duplicating the PyRat template file on Google Colab. For recall, you should go on the Google Colab template program, click on « File », then « Save copy in drive ». Rename it as
bfs.ipynb, and make it accessible by link. We will refer to this link as
In this Lab, we will use the following command:
python pyrat.py --rat <shared_link_to_bfs.ipynb> -md 0.0 -p 1 -x 5 -y 5 --random_seed 1
In that command line, we put no mud in a 5×5 maze, and put only one piece of cheese inside. Additionally, we force the maze to be the same every time you execute your program (option
random_seed), so that you can check easily by hand if your traversal performs as it should. To check that, don’t hesitate to use calls to
The breadth-first search algorithm
The BFS algorithm
To program the BFS function, you should adapt the pseudo-code that you have seen in the articles or the videos. Note that your BFS function needs as arguments the graph (
maze_map) and a starting position.
In order to make your code easily transformable into a depth-first search (or later, into Dijkstra’s algorithm), you should separate as much the traversal algorithm from the functions that manipulate the data structure. Typically, your code should look like something like this:
def create_structure () : # Create an empty FIFO
def push_to_structure (structure, element) : # Add an element to the FIFO
def pop_from_structure (structure) : # Extract an element from the FIFO
def traversal (start_vertex, graph) : # BFS traversal
First thing to do in this Lab is to fill the holes in the functions above, and to call the
traversal function from the
preprocessing function to check if you have implementation errors.
At this point, we have designed a traversal algorithm that crawls the maze in increasing distance to the starting location.
In order to find the shortest path to reach a piece of cheese from the output of the BFS algorithm, it is now necessary to implement a routing algorithm. Therefore, in the traversal function, you should remember which vertex added which other vertex along the shortest path by creating a routing table.
Once you have updated your traversal function to compute the routing table, implement a function that finds the shortest path from a routing table, a starting vertex and a destination vertex.
def find_route (routing_table, source_location, target_location) : # Use the routing table to find the sequence of locations from source to target
Move, little rat!
Now that you have a list of locations to reach the only cheese in the maze from your initial location, you can adapt the code you developed in Lab 2, to transform it into a list of moves to apply.
def moves_from_locations (locations) : # Transform a series of locations into corresponding moves to realize it
When you have computed this list in function
preprocessing, you should store it into a global variable so that it can be accessed from function
turn, which will return the next move to perform at each turn.