MMSim

Out of the blue, I decided to write a simulator in Python for the Micromouse DeCal I helped teach this semester. Past semesters of Micromouse never got around to doing the actual maze solving and I felt that part of the reason was not having a good explanation or reference implementation of the algorithm. Flood fill is the de facto standard when it comes to this thing so I decided to learn it and implement it. Due to all the power outages and midterms, we ended up not getting to maze solving yet again but we’ll definitely do it next semester.

Here’s a link to my repo.

Maze Representation

First, I came up with a simple and efficient way of storing mazes. Since mazes are constructed as a bunch of square cells with walls placed between them, I looked into a Cartesian coordinate system. For each cell, we can have north, south, east, and/or west walls. We represent having a wall in that direction as having the corresponding bit be a 1. This will make it easier to convert to Arduino later. I then setup a bunch of code to help read maze files and display them.

Flood Fill

The flood fill algorithm is conceptually pretty simple. It can be modeled as water flowing along the fastest path from highest to lowest elevation. As the robot moves through the maze, it reconstructs it in memory, which necessitates updating the “heights” of each cell. There’s lots of room for improvement in the future, but my algorithm currently only considers the Manhattan distance between cells and constantly recalculates all heights using BFS.

Robot Representation

As for the robot, I used an object oriented approach, naming it Karel after the way I was taught Java in high school. I modeled Karel with the knowledge that the algorithm would eventually be moved over to C++ on the Arduino. As such, I made sure to write code as non-Pythonic as possible and to reduce memory usage. To start, Karel has a couple of sensors which can tell us if there’s certain walls around us. It can also turn left, turn right, and move forward. With each movement, we gain new information about the maze and so update our reconstruction accordingly. Just having a couple of sensors and move methods is all that flood fill needs to find the shortest path to the target.