Maze router

Required preparation:

• Read this chapter and try to understand the Lee algorithm

Introduction¶

During the IP-2 project ”Smart Robot Challenge” you need to develop a robot that can find its way through a maze. During this assignment you will develop a maze router that can be used for this. For this assignment, the maze router is created as a separate program with a simple user interface. Later, you will incorporate the program into a larger program that will control the robot.

We will describe an algorithm that can be used to compute the route through the maze, as well as a data structure to implement the algorithm. The assignment may be done in a group of 2 students.

Assignment¶

The maze field of the IP-2 project “Smart Robot Challenge” is given is Figure 2. here are 12 stations, numbered from 1 till 12, that act as starting or end point of a route through the maze. There are horizontal and vertical roads between the stations, and the crossings of these roads are labeled with names like c00, c01, c02, etc. A road, or edge, between two crossings $c~i,j$ and $c~i,j+1$ is denoted by “$i~j$ e”, where $i$ and $j$ and indices, and the letter ‘e’ indicates “east”. Between two crossings $c~i,j$ and $c~i+1,j$ the edge is denoted by “$i~j$ s”, where ‘s’ stands for “south”.

The program should take as input a list of blocked edges, followed by a pair of stations between which a route should be computed. The list of blocked edges is preceeded by the number of blocked edges. An example input is given below.

2 2 0 s 2 3 e
10 12

This example specifies that there are 2 blocked edges, between respectively c20 and c30, and between c23 and c24, and that a route has to be computed from station 10 to station 12. The output of the program should be a free route between the 2 stations, given as a list of the crossings that are passed on the route. For the example input, the output should be one of the following lines:

c10 c20 c21 c31 c30
c10 c11 c21 c31 c30

Algorithm¶

There are several algorithms known for shortest path computation, see e.g. Wikipedia (n.d.). In our case we are dealing with a rather simple map, which is rectangular and does not have a lot of nodes (points) and edges (roads). Therefore we propose to use also a rather simple algorithm that is straightforward to implement. This is the Lee or wavefront algorithm, see Lee (1961) and Zhou (n.d.), that was originally developed to solve routing problems for the design of integrated circuits. Note that it is not compulsory to use this algorithm to solve this assignment, and that you are free to choose another algorithm, as long as it provides a valid solution for all possible input combinations.

To describe the Lee algorithm, we model the “Smart Robot Challenge” map from Figure 2 by an array of 13 × 13 cells as shown in Figure 3. Each station, crossing and edge in the original map is thereby represented by a cell, such that when items are adjacent in the original map, their corresponding cells in the array are also adjacent. The remaining cells in the array model the empty space in the original map. Cells corresponding to stations, crossings or unblocked edges are initialized with a value 0. Cells corresponding to empty space or blocked edges are initialized with a value -1.

Next, the Lee algorithm is applied for the array as described by the algorithm in Figure 4. In the algorithm, a neighbor cell is defined as a cell that is directly to the right, to the left, above or below the cell that is considered (so the cells that diagonally touch each other are not considered neighbor cells).

The contents of the array after expansion steps 1, 5 and 13 of the algorithm, are shown in respectively Figure 5, 6 and 7. The path that is followed during the trace back step of the algorithm is also shown in Figure 7. Note that an alternative path is via c01 instead of via c13.

Datastructure¶

The datastructure that is used to implement the above algorithm can be quite simple. We need to maintain a 2-dimensional array of integers of size 13 × 13.

int maze[13][13];

The program then typically will start by initializing the array according to the topology of the maze. After that the blocked edges should be read and represented in the array, followed by reading the start and target station, and finally the application of the Lee algorithm.

Input and Output¶

If you use the above data structure, you can use the functions defined in the C file leelib.c to read the indices of an edge or terminal, and to print the name of a crossing, according to the required input and output format. It also contains a function to print the elements of the 13 × 13 matrix, which may be used for debugging. The header file leelib.h provides prototypes for the functions available in leelib.c.

void readEdge (int *i, int *j)
/* Scans input to read a blocked edge.
   Returns the indices i and j in m[13][13] of an edge.
   Call this function with pointers to the variables
   that should receive the values, e.g.
   readEdge (&x, &y);
 */

void readStation (int *i, int *j)
/* Scans input to read a station.
   Returns the indices i and j in m[13][13] of a station.
 */

void printCrossingName (int i, int j)
/* Print the name of the crossing with indices i and j in m[13][13]/ */

void printMatrix (int m[][13])
/* Print the elements of the matrix m[13][13]. */

Development¶

As a development strategy it is suggested to first implement the Lee algorithm itself, and not yet read the specified user input. Test the code by directly initializing the data structure (matrix) in the C code. To debug the code, the function printMatrix may be used that prints the contents of the data structure (matrix).

When implementing the algorithm, be careful that matrix indices do not get out of range.

When everything is working correctly, extend the program so that it meets the input/output requirements as mentioned above.