Examples that I enjoyed working on most

Flood Fill Pathfinding Algorithm

A powerful method of maze solving used for our Micromouse robot.

How it works

The maze is divided into cells, and the shortest distance from each cell to the goal is calculated. Initially, it is assumed there are no walls in the maze.

Then, as the mouse tries to reach the goal by moving to the neighboring cell with the lowest distance, the distances are updated every time a wall is discovered.

This is repeated, and so the mouse is able to map out the maze and the respective distances to the goal of each cell.

Upon returning to the start, it is simply a matter of connecting the shortest distances to derive a path that leads straight to the goal.

Images from Green Ye's micromouse lecture slides.


create two dimensional array 'distance'
create two dimensional array 'walls'

position = bottom left coordinate of maze

for all elements in walls
    element = empty

for all elements in distance
    element = shortest distance to goal

while position != goal
    if a new wall is discovered
        push current coordinate to stack
        for all accessible neighboring cells
            push neighboring cell coordinates to stack

        while !stack.isEmpty
            coordinate = pop from stack

            if distance != lowest distance of neighbors + 1
                distance = lowest distance of neighbors + 1

                for all accessible neighboring cells
                    push neighboring cell coordinates to stack
    move to neighbor with lowest distance

A stack approach like this is essential, since using recursion will fill up memory much faster on our microcontroller. With a solid understanding of the algorithm and the functions that were going to be needed, it was time to move on to the implementation.

C++ Implementation

Since the architecture we are using for our mouse is mostly supported by C++ compilers, this was the obvious language to use.

The full code can be viewed on our project's Github page and is free for use.

In order to easily test the algorithm and mouse functions, the code includes a DebugTools class. The printMaze function, for example, prints an ASCII maze including distance values and walls.

Besides the outer edge walls, each wall is displayed twice. This is intended, since walls are also stored in memory twice (one from each neighboring cell).

This function was extremely useful for debugging, and will also be used during live testing of the mouse, as it has capabilities for bluetooth serial communication.

3DoT Bootloader

A dedicated bootloader for the 3DoT board: a few hundred bytes smaller and with the added capability of entering the bootloader manually, in case of uploading troubles.

The bootloader conveniently integrated into the Arduino IDE.

See also: This guide I wrote on burning fuses and uploading bootloaders to ATMega32u4-based boards.