mimo-10 / maze-solver

A maze solver written in C based on a custom queue based flood fill algorithm

Queue-based Flood fill maze solver

Maze solver written entirely in C from scratch

Testing

Run using bash run.sh 1 200 to run the first maze, 2 for the second and 3 for the 3rd. Own mazes can be tested by renaming the file to maze.txt and then calling the run script with corresponding n as argument. The second argument is maxSteps, how many steps the solver is allowed to take.

Tested on Fedora 37 and MacOS Ventura. Probably works on Windows...

The program

The program will execute the following steps to solve a maze:

1. Read a maze txt file
2. Perform a modified queue based flood fill on the maze for every exit
3. Move the agent to the adjacent cell with the lowest value until the value is 0 (optimal exit reached)

Modified queue based flood fill

Modified here refers to the fact that the algorithm needs to not only flood, but to flood the best way (to find the optimal exit path). This means that after the first flood fill, the subsequent flood fills need to be mindful to not overwrite and create worse paths. This is achieved by simply checking if the new value is greater than the current value. If it is, continue flooding and if not, terminate. We can terminate because if at any point the new value is greater (in value) then the subsequent path can not be a better path than the existing path.

Queue is used to ensure that every cell gets the correct manhattan distance from the flood origin.

Further development

This can probably be improved in more ways that I could ever imagine, but I want to note that I'm aware of at least 2 improvements. These are not of great concern which is why I'm not going to fix them immediately.