The maze adventures

I write about this because I tend to forget about code I write, so in order to keep it fresh on memory
I’ve decided to keep a record of it and maybe someone else can make use of it. Even though it is still
mostly theoretical, at least in part, because the actual robot has not been completely built, the new
version, as the last version was a total disaster due to a problematic deadline and some not so
co-operating human subjects. Basically testing proved impossible and I had to carry on with school.
I also do not pretend to be innovating in any aspect, there are several known methods to solve mazes
and most have been written about elsewhere, (hint: use Google). I’ve just used the information I have
gathered from various sources to work out a solution that in theory and in software, works.

There is one usual method used to solve mazes, which consists of turning either left or right at
every intersection, eventually you will reach the exit, however this does not work in a maze with
loops, or cycles.

The maze is the SRS Line Maze for the Robothon information for it can be located at: Clicky

Hardware

OMNIFlash
A Linux ARM embedded platform with 16 GPIOs, 5 DC Power

Algorithms

Breadth First Search – Maze discovery, first pass

We know before hand that the end of the maze will be the spot where all our sensors detect black. That spot
will be marked as the goal and it will be used to detect the end of the first pass. The way it works is to
walk around the line to find the junctions, and when you do you use the algorithm to keep track of where the
robot is facing and where it took a turn in order to backtrack when you find a dead-end and at the same time
to avoid looping.

Depth First Search – Shortest path, second and third passes.

Once the information about the junctions has been gathered in the previous pass, the second pass is trivial.
There is enough data to know which way to turn on the next junction to reach the end on the shortest path.

The rest of the work consists on calibrating the robot to be able to keep itself inside the line and to make
sure to be able to detect the junctions, other than that it is pretty straightforward.

A little code:

typedef struct _CMapperStruct
{
vec * rooms;

} CMapperStruct;

Originally the software was written in C++ , but because of the lack of some of the STL libraries inside the
OMNIFlash I had to remove those enhanced object oriented elements, however, the structure of the program went
intact. Rooms is a vector, it will keep the rooms. Each room is an element of the structure Graph.


typedef struct _Graph
{
int x, y, id, directions[4];
enum color visit;
struct _Graph * pred;

} Graph;

This is the structure that will be used throughout the program and will be worked upon.

The element directions keeps a record of the junctions, as it transverses the maze it will be able to
etect which way to turn. Color is used as an aid for the algorithms to mark rooms visited, and rooms
finished discovering their vertices. Pred is the pointer which helps backtrack during the first pass
with the aid of a queue and in resolving the shortest route with a stack.