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.
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.
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.
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.