Victor Gusev
← Projects

Micromouse Simulator

Java maze-solving simulator with Flood Fill pathfinding and a visualization engine.

GitHub (opens in a new tab)

Micromouse Simulator — figure

Year
2023
Category
robotics

Stack

JavaJava Graphicsalgorithmssimulationvisualization
Problem
Micromouse is a popular competition where you build a small robot to traverse a maze quickly and return back to the start.
Approach
Maze-solving simulator featuring Flood Fill pathfinding algorithm and a graphical visualization engine.
Result
The solver runs one wavefront pass per distance layer over the 16x16 grid — O(n·d) for n cells and d the longest path, bounded by the grid rather than by the maze, so a full solve is instant.

How it works

Flood fill wavefront on the maze gridEach cell of the maze grid holds its distance from the goal at the centre. The solver expands one wavefront layer per pass rather than recursing, so a full solve costs one pass per distance layer over the sixteen by sixteen grid, and the mouse then walks downhill from any starting cell.One wavefront pass per distance layer7654345665432345543212344321012354321234654323457654345687654567Reading itEach cell holds its distancefrom the goal. The mouse walksdownhill from wherever it is.Why it is fastOne pass per layer — O(n·d),bounded by the grid, not the maze.The first version copied thevisited-set per recursive call,making every step O(n) on its own.A 16×16 competition grid; eight columns shown. Walls make the flood route around them.
Flood fill, as the mouse sees it
01

The problem

Micromouse is a popular competition where you build a small robot to traverse a maze quickly and return back to the start. While maze-solving algorithms are available to research and find online, if someone wants to test a certain algorithm against a maze prior to testing on Hardware, is is important that a clean visualizer is used.

02

Architecture

Maze-solving simulator featuring Flood Fill pathfinding algorithm and a graphical visualization engine. Uses a file parsing pipeline to load competition mazes. Run on Java

03

What did not work

When originally testing this project, it ran very slowly due to attempting to re-generate the entire maze/re-run maze solving algorithms every frame. This was fixed using concepts/algorithms learned to reduce time complexity, and now the program runs much faster.

04

Measured results

The solver runs one wavefront pass per distance layer over the 16x16 grid — O(n·d) for n cells and d the longest path, bounded by the grid rather than by the maze, so a full solve is instant. The first implementation was not: it copied the visited-set at every recursive call, making each step O(n) on its own and the whole solve visibly slow to watch.

Post-mortem

Learned various algorithms to solve mazes, and learned how to iterate and understand big O. I also got more familiar with the Java programming language.