Contents of the page


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

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:

# Function to create a LIFO
def create_structure () :
    # ...



# Function to add an element to the FIFO
def push_to_structure (structure, element) :
    # ...



# Function to extract an element from the FIFO
def pop_from_structure (structure) :
    # ...



# Traversal
def traversal (start_vertex, graph) :
    # ...

First thing to do in this Lab is to fill the holes above. Assuming your program is named AIs/bfs.py, use the following command:

python pyrat.py --rat AIs/bfs.py -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 everytime 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 print in your code, for instance to visualize which location is extracted from your data structure.

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. Therefore, in the traversal function, you should remember which vertex added which other vertex towards the shortest path to create 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.

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 use the code you developed in Lab 1, to transform it into a list of moves to apply.

When you have computed this list in function preprocessing, you should store it into a global variable so that it can be acessed from function turn.

Then, you can apply the moves one after the other by using the following code:

def turn (maze_map, maze_width, maze_height, player_location, opponent_location, player_score, opponent_score, pieces_of_cheese, time_allowed) :
    
    # moves_to_perform is the global list of moves, filled during preprocessing
    global moves_to_perform

    # We perform one move along the identified path
    move = moves_to_perform.pop(0)
    return move
##############################################################
# New code
##############################################################

# Transforms locations into moves
def moves_from_locations (locations) : 
    moves = []
    for i in range(len(locations) - 1) :
        difference = (locations[i+1][0] - locations[i][0], locations[i+1][1] - locations[i][1])
        if difference == (0, -1) :
            moves.append(MOVE_DOWN)
        elif difference == (0, 1) :
            moves.append(MOVE_UP)
        elif difference == (1, 0) :
            moves.append(MOVE_RIGHT)
        elif difference == (-1, 0) :
            moves.append(MOVE_LEFT)
        else :
            raise Exception("Impossible move")
    return moves



##############################################################
# Updated code
##############################################################

def preprocessing (maze_map, maze_width, maze_height, player_location, opponent_location, pieces_of_cheese, time_allowed) :
    
    # Traversal + routing
    explored_vertices, routing_table = traversal(player_location, maze_map)
    route = find_route(routing_table, player_location, pieces_of_cheese[0])

    # Store into global variable
    global moves_to_perform
    moves_to_perform = moves_from_locations(route)



def turn (maze_map, maze_width, maze_height, player_location, opponent_location, player_score, opponent_score, pieces_of_cheese, time_allowed) :
    
    # moves_to_perform is the global list of moves, filled during preprocessing
    global moves_to_perform

    # We perform one move along the identified path
    move = moves_to_perform.pop(0)
    return move