Can I compute the trajectory in a maze if I know the walls?

Question

Let's assume that I have a mouse in a maze and the mouse need to find the exit.

I know where the exit is and where my position is. I also know the position of the walls.

How can I compute the trajectory for the path in the maze? What method should I use?

Answer 1

At each position in the labyrinth, the mouse has at most four directions it can move toward (North, West, South, East). You can use a brute-force approach and compute the following tree recursively. Each node of the tree is labeled by a word, say $w$, on the alphabet $\{N, W, S, E\}$ that corresponds to a path from the starting position. Using this path, you can recover the corresponding position of the mouse : say mouse started at coordinates $(x, y)$, then it has now coordinates $(x + n_E - n_W, y + n_N - n_S)$ where $n_E$ is the number of $E$s in $w$, etc.

• The root of the tree is the empty word $\epsilon$.
• If a node corresponds to the exit, no child is added to it (the mouse found an exit).
• If a node labeled by $w$ doesn't correspond to the exit, add a child for each legal step that the mouse can make in this position and that doesn't lead to a position that has already been visited along the path $w$.

In the end, all possible path to exit are leaves of this tree (but beware, some leaves correspond to dead ends).