Maze solving algorithm in C
basically, I'm trying to implement an algorithm in C that can solve a maze using the right-hand or left-hand rule. I get a triangular maze like this in a file:
I have already implemented functions to parse the file and load the maze into a dynamic 2D array. From the values in the array, I can tell whether each field has or doesn't have a right border, left border, and vertical border (top or bottom, depending on the position of the field). I'm also told the coordinates of the starting point (i.e. 6,1 in this particular example) and the initial border to follow (i.e. bottom) and, of course, whether to use the right hand or the left hand rule to find the exit.
I'm supposed to list the coordinates of the fields that lead to the exit. I've basically implemented all the necessary functions to parse and check the maze validity, but I don't exactly understand how to put a right hand and left hand rule in an algorithm. I hope this is enough information to understand what I'm trying to do. I don't necessarily need specific code, I only need to understand how to actually go about this.
Thanks.
Answer
Let's formulate the right-hand rule in terms of the triangular maze cells. Suppose we have entered a cell by crossing its bottom edge, as indicated by a gray arrow in the diagram below.
The right-hand rule tells us to keep our right hand on a wall. When we enter a cell, where is the wall?
In the first case above, there is no wall to the immediate right. There must be a wall somewhere to the right of us, so we want to keep turning right until we hit it. Turning right in the triangular maze means turning 60 degrees clockwise and stepping over the triangle's edge into the adjacent cell.
In the second case, there is a wall on the immediate right when we enter the cell. We want to keep this wall to our right, so we turn left and step to the adjacent cell in that direction.
In the third case, there are walls on both sides. We must turn around and leave the cell. We're returning to the previous cell by moving in the opposite direction, so the wall to the right will be a different edge of the triangle this time.
To follow the left-hand rule, we use similar reasoning on a mirror image of the illustration above.
Next, we need a numerical representation of the grid cells. There are various ways to number the cells and edges. One possibility is shown in the diagram below. The edges of every triangle are numbered 0, 1, 2. At left are the two orientations of a triangle, showing the edge numbering for each. In the center are the eight possible wall configurations for each triangle orientation. At right are the decimal and binary representations of each wall configuration, using the edge number to index binary digits from right to left, i.e., from least significant digit to most significant digit.
With this numbering scheme, the maze shown in the question can be represented with the following text. The first line contains the number of rows and columns in the grid. The second line describes our starting point: row number, column number, crossed edge. The remaining lines contain the cell descriptions.
6 7
6 1 2
4 2 1 1 5 0 3
4 1 2 0 2 0 1
4 0 1 0 1 3 4
4 2 7 4 0 1 1
6 4 1 1 6 4 2
2 2 6 0 2 2 6
The final piece of the implementation is a transition matrix that lets us look up the next state in a maze traversal given the current state and the edge we're crossing.
Before describing the transition matrix, let me be quite clear about how we're numbering the grid. Externally, we'll number rows and columns starting from one, as shown in the diagram. That's how we'll read the starting location and it's how we'll display the solution to the user. Within the program, however, it is convenient to number the rows and columns starting from zero, because that's how the C language indexes arrays. For instance, we'll say the top left cell is in row 0 and column 0. This means that if we have a two-dimensional integer array called maze, we refer to the upper left cell as maze[0][0].
Given the row index r and column index c of a triangular grid cell, using zero-based numbering, let's figure out the triangle orientation from the parity of r and c. If they have the same parity, meaning they are both odd or both even, the triangle points downward. Otherwise, it points upward. An easy way to implement this is by calculating (r+c)%2, which is 0 if the parities are the same and 1 if the parities differ.
Next, we have to take into account the edge that we're crossing. If we know the orientation of the triangle we're leaving and the number of the edge that we're crossing, we can work out:
The row number of the triangle that we're entering.
The column number of the triangle that we're entering.
The number of the edge that we crossed, in the context of the newly entered triangle.
All of this information is represented in the following three-dimensional array.
moves[2][3][3] = {
{ {-1, 0, 1}, {0, 1, 2}, {0, -1, 0} },
{ {0, 1, 2}, {1, 0, 0}, {0, -1, 1} } };
The first index is for the triangle orientation, with 0 for a downward triangle and 1 for an upward triangle. The second index is the number of the edge that we're crossing, using the edge numbering of the triangle that we're leaving. The third index is used to look up the three pieces of information listed above.
0: The change in the row number.
1: The change in the column number.
2: The edge number we just crossed, using the edge numbering of the new triangle.
For instance, let's look at the first move in the sample maze. We start in row 5, column 0. The sum parity is 1, meaning an upward triangle. We're crossing edge 0. Thus, we look at maze[1][0]. The resulting information is {0, 1, 2}, telling us that in the new cell:
The row index changes by
0.The column index changes by
1.We just crossed edge
2.
Now we can apply the algorithm in a loop that ends once we have left the bounds of the maze.
Below is an ANSI C implementation of the concepts I've discussed. You will have to adapt it to whatever file format you're using to represent the maze. Please remember that in the description of the starting location, my format specifies the edge that was crossed to enter the maze.
#include <stdlib.h>
#include <stdio.h>
int **maze, row_num, col_num,
moves[2][3][3] = { /* moves[orientation][edge] == {dr, dc, crossed} */
{ {-1, 0, 1}, {0, 1, 2}, {0, -1, 0} },
{ {0, 1, 2}, {1, 0, 0}, {0, -1, 1} } };
void go(int r, int c, int crossed, int turn) {
int edge, *move;
while (1) {
if (r < 0 || r >= row_num || c < 0 || c >= col_num) {
printf("out\n\n"); /* We've left the maze. */
return;
} /* Increment the indices for external display. */
printf("%d %d\n", r+1, c+1);
edge = crossed; /* We'll consider the crossed edge last. */
while (1) { /* Turn and look for an open edge. */
edge = (edge+turn+3)%3;
if ((maze[r][c] & (1 << edge)) == 0) {
break;
}
}
move = moves[(r+c)%2][edge];
r += move[0]; /* After looking up the move, update the */
c += move[1]; /* cell position and the edge number. */
crossed = move[2];
}
}
int main() {
int r_start, c_start, crossed_start, r, c;
scanf("%d %d", &row_num, &col_num);
scanf("%d %d %d", &r_start, &c_start, &crossed_start);
--r_start; /* We decrement the cell indices because */
--c_start; /* they are zero-based internally. */
maze = (int **) malloc(row_num*sizeof(int *));
for (r = 0; r < row_num; ++r) {
maze[r] = (int *) malloc(col_num*sizeof(int));
for (c = 0; c < col_num; ++c) {
scanf("%d", &maze[r][c]);
}
}
printf("\nRight-hand rule:\n");
go(r_start, c_start, crossed_start, -1);
printf("Left-hand rule:\n");
go(r_start, c_start, crossed_start, 1);
return 0;
}