Mazes
The Wikipedia page on mazes tells you about some algorithms for solving them. The most useful ones for your robot are
- right hand rule: whenever you get to an intersection, turn right
- random: whenever you get to an intersection, choose a random direction
- depth first search: when you first get to an intersection turn right, the next time take the straight branch, the next the left branch and if you get there again, backtrack
The right hand rule is easy to implement. but will not explore all of some mazes.
Random searching will eventually search all of a maze, but can take a long time.
Depth first search will search all of a maze and do it efficiently, but presents hardware and software challenges:
- you have to know when you get back to an intersection, so you have to recognize the difference between each intersection using the short and long black strips. (Using a rotation sensor might help determine the length.)
- DFS uses recursion, but nqc doesn't have recursion.
DFS using recursion: depthfirst.c
DFS using a stack instead of recursion: depthfirst2.c
This page has many more maze algorithms that you might want to consider.