Description 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!

The breadth-first search algorithm

Set up the environment

Let’s create a new PyRat program. To do so, please copy template.py into a new file bfs.py.

Now, let’s setup the maze configuration a bit. Here, we are going to work with a single character, in a 15×11 maze, with no mud and only a single piece of cheese. As before, we will show the trace so that we can check afterward if the character indeed took the shortest path.

The final bode block in the file should therefore look like this:

#################################################################################################################
###################################################### GO ! #####################################################
#################################################################################################################

if __name__ == "__main__":

    # Map the functions to the character
    players = [{"name": "BFS", "preprocessing_function": preprocessing, "turn_function": turn}]

    # Customize the game elements
    config = {"maze_width": 15,
              "maze_height": 11,
              "mud_percentage": 0.0,
              "nb_cheese": 1,
              "trace_length": 1000}

    # Start the game
    game = PyRat(players, **config)
    stats = game.start()

    # Show statistics
    print(stats)

#################################################################################################################
#################################################################################################################

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 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. A good idea is therefore to pass the functions that manipulate the structure as arguments of the traversal.

Here is the skeleton of the function you should write (in the « Functions » section of the file to keep things organized):

def traversal ( source:             int,
                graph:              Union[numpy.ndarray, Dict[int, Dict[int, int]]],
                create_structure:   Callable[[], Any],
                push_to_structure:  Callable[[Any, Tuple[int, int, int]], None],
                pop_from_structure: Callable[[Any], Tuple[int, int, int]]
              ) ->                  Tuple[Dict[int, int], Dict[int, Union[None, int]]]:

    """
        Traversal function that explores a graph from a given vertex.
        This function is generic and can be used for most graph traversal.
        To adapt it to a specific traversal, you need to provide the adapted functions to create, push and pop elements from the structure.
        In:
            * source:             Vertex from which to start the traversal.
            * graph:              Graph on which to perform the traversal.
            * create_structure:   Function that creates an empty structure to use in the traversal.
            * push_to_structure:  Function that adds an element of type B to the structure of type A.
            * pop_from_structure: Function that returns and removes an element of type B from the structure of type A.
        Out:
            * distances_to_explored_vertices: Dictionary where keys are explored vertices and associated values are the lengths of the paths to reach them.
            * routing_table:                  Routing table to allow reconstructing the paths obtained by the traversal.
    """
    
    # TODO: Fill here according to the specifications in the documentation above

In Python, it is possible to definie nested functions, i.e., functions within functions. It makes them impossible to call from outside the embedding function, which is practical to avoid a user calling a function that just does some auxiliary work.

Let’s use this functionality to define a function bfs that exploits the function traversal we just defined.

def bfs ( source: int,
          graph:  Union[numpy.ndarray, Dict[int, Dict[int, int]]]
        ) ->      Tuple[Dict[int, int], Dict[int, Union[None, int]]]:

    """
        A BFS is a particular traversal where vertices are explored in the order where they are added to the structure.
        In:
            * source: Vertex from which to start the traversal.
            * graph:  Graph on which to perform the traversal.
        Out:
            * distances_to_explored_vertices: Dictionary where keys are explored vertices and associated values are the lengths of the paths to reach them.
            * routing_table:                  Routing table to allow reconstructing the paths obtained by the traversal.
    """
    
    # Function to create an empty FIFO, encoded as a list
    def _create_structure ():
        # TODO: Fill here

    # Function to add an element to the FIFO (elements enter by the end)
    def _push_to_structure (structure, element):
        # TODO: Fill here

    # Function to extract an element from the FIFO (elements exit by the beginning)
    def _pop_from_structure (structure):
        # TODO: Fill here
    
    # Perform the traversal
    distances_to_explored_vertices, routing_table = traversal(source, graph, _create_structure, _push_to_structure, _pop_from_structure)
    return distances_to_explored_vertices, routing_table

First thing to do in this Lab is to fill the holes in the functions above. Then, please write a small unit test file to check if everything goes well. That test should check on (one or more) controlled mazes that distances_to_explored_vertices and routing_table contain the expected results.

Routing

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.

Here is the code you should fill:

def find_route ( routing_table: Dict[int, Union[None, int]],
                 source:        int,
                 target:        int
               ) ->             List[int]:

    """
        Function to return a sequence of locations using a provided routing table.
        In:
            * routing_table: Routing table as obtained by the traversal.
            * source:        Vertex from which we start the route (should be the one matching the routing table).
            * target:        Target to reach using the routing table.
        Out:
            * route: Sequence of locations to reach the target from the source, as perfomed in the traversal.
    """
    
    # TODO: Fill here according to the specifications in the documentation above

Again, update your unit test file so that you guarantee that this function works as expected.

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 make your character move! Here is a function that you can use to help you:

def locations_to_actions ( locations:  List[int],
                           maze_width: int
                         ) ->          List[str]: 

    """
        Function to transform a list of locations into a list of actions to reach vertex i+1 from vertex i.
        In:
            * locations:  List of locations to visit in order.
            * maze_width: Width of the maze in number of cells.
        Out:
            * actions: Sequence of actions to visit the list of locations.
    """
    
    # We iteratively transforms pairs of locations in the corresponding action
    actions = []
    for i in range(len(locations) - 1):
        action = locations_to_action(locations[i], locations[i + 1], maze_width)
        actions.append(action)
    return actions

Now, fill the preprocessing function to compute the series of actions to perform. Store them in the persistent variablememory, and use the result in theturn function.

The depth-first search algorithm

When you are done with the BFS, you can try to code a DFS. Duplicate your file template.py into dfs.py, setup the environment as for the BFS, and import all the needed functions from dfs.py. Then, fill the following function, as well as the preprocessing and turn ones:

def dfs ( source: int,
          graph:  Union[numpy.ndarray, Dict[int, Dict[int, int]]]
        ) ->      Tuple[Dict[int, int], Dict[int, Union[None, int]]]:

    """
        A DFS is a particular traversal where vertices are explored in the inverse order where they are added to the structure.
        In:
            * source: Vertex from which to start the traversal.
            * graph:  Graph on which to perform the traversal.
        Out:
            * distances_to_explored_vertices: Dictionary where keys are explored vertices and associated values are the lengths of the paths to reach them.
            * routing_table:                  Routing table to allow reconstructing the paths obtained by the traversal.
    """
    
    # Function to create an empty LIFO, encoded as a list
    def _create_structure ():
        # TODO: Fill here

    # Function to add an element to the LIFO (elements enter by the end)
    def _push_to_structure (structure, element):
        # TODO: Fill here

    # Function to extract an element from the LIFO (elements exit by the end)
    def _pop_from_structure (structure):
        # TODO: Fill here
    
    # Perform the traversal
    distances_to_explored_vertices, routing_table = traversal(source, graph, _create_structure, _push_to_structure, _pop_from_structure)
    return distances_to_explored_vertices, routing_table

If your traversal function was coded properly, it should work quickly!

Once you are done, make the usual tests.

Then, you can try to adapt the scripts provided with PyRat to compare the moves needed by the DFS and BFS algorithms to catch a single piece of cheese!