(Jan-25-2026, 07:10 AM)WhackoJacko99 Wrote: Hello everyone, I'm still fairly new to using Python so please go easy on me. Im trying to make a flood-fill algorithm for a micromouse maze and I dont really know where to start. I have an algorithm for left-hand following movement but I'm trying to convert it over to being flood-fill. Any help would be greatly appreciated. I will also attach the API that it is using
The code:
#!/usr/bin/env python3
import API
# Directions
N, E, S, W = 0, 1, 2, 3
DIRS = [(-1,0),(0,1),(1,0),(0,-1)] # (dx, dy)
DIR_BITS = [1, 2, 4, 8]
OPPOSITE = [2, 3, 0, 1]
WIDTH = API.mazeWidth() # Should be 5
HEIGHT = API.mazeHeight() # Should be 5
# Center tile for 5x5 maze
CENTER_TILE = (2, -2)
# Maze state
walls = [[0]*HEIGHT for _ in range(WIDTH)]
visited = [[False]*HEIGHT for _ in range(WIDTH)]
steps_map = [[-1]*HEIGHT for _ in range(WIDTH)]
# Mouse state
x, y = 0, 0 # Starting at top-left corner
dir = N
step_count = 0
# ---------------- Helper functions ----------------
def in_bounds(nx, ny):
return 0 <= nx < WIDTH and 0 <= ny < HEIGHT
def sense_walls():
"""Update walls at current position"""
global walls
for offset, check in [(0, API.wallFront), (-1, API.wallLeft), (1, API.wallRight)]:
d = (dir + offset) % 4
if check():
walls[x][y] |= DIR_BITS[d]
nx, ny = x + DIRS[d][0], y + DIRS[d][1]
if in_bounds(nx, ny):
walls[nx][ny] |= DIR_BITS[OPPOSITE[d]]
def rotate_left():
global dir
API.turnLeft()
dir = (dir - 1) % 4
def rotate_right():
global dir
API.turnRight()
dir = (dir + 1) % 4
def move_forward():
"""Move one tile forward and stop if at center"""
global x, y, step_count
API.moveForward()
x += DIRS[dir][0]
y += DIRS[dir][1]
step_count += 1
visited[x][y] = True
steps_map[x][y] = step_count
# Stop immediately if center reached
if x == CENTER_TILE[1] and y == CENTER_TILE[0]:
exit()
else:
print(y)
print(CENTER_TILE[0])
# ---------------- Main Left-Hand Wall Loop ----------------
visited[x][y] = True
steps_map[x][y] = step_count
sense_walls()
while True:
if not API.wallLeft():
rotate_left()
move_forward()
elif not API.wallFront():
move_forward()
elif not API.wallRight():
rotate_right()
move_forward()
else:
rotate_right()
rotate_right()
move_forward()
sense_walls()
Just got up and being lazy, I submitted your Query to XGrok, here is the response:
From Grok:
The code you shared is a classic **left-hand wall follower** (with a tiny bug in the center check — more on that below). Switching to **flood-fill** (also called floodfill or distance-map / shortest-path flood) is a great next step for micromouse, as it finds the actual shortest path once enough of the maze is known, rather than just hugging walls.
### Quick fix in your current code (unrelated to floodfill)
In
move_forward() you have:
if x == CENTER_TILE[1] and y == CENTER_TILE[0]:
But
CENTER_TILE = (2, -2) — that negative y looks wrong.
For a 5×5 maze indexed [0…4][0…4] with start at (0,0) top-left and center at (2,2), you probably want:
CENTER_X, CENTER_Y = 2, 2
# then later:
if x == CENTER_X and y == CENTER_Y:
API.log("Reached center!")
exit()(Also the
print(y); print(CENTER_TILE[0]) looks like debug code that can be removed.)
### Flood-fill for micromouse – how it works (the simple version)
The core idea is:
1. Maintain a **distance map** (costs / steps from each cell to the goal)
2. **Goal** = usually the four center cells in larger mazes, but for 5×5 often just (2,2)
3. Every time you discover new walls (or after major exploration), **re-flood** from the goal(s) outward:
- Set goal distance = 0
- Neighbor cells get distance = neighbor's distance + 1 (if better)
- Use a queue (BFS) → guaranteed shortest path in steps
4. From your **current position**, look at the four possible neighbors
5. Choose to move to the accessible neighbor that has the **lowest distance**
This is usually done in two phases:
- **Search phase** — explore unknown areas (often still using wall-following or simple heuristic), updating the wall map and re-flooding occasionally
- **Speed-run phase** — once center is found, flood from center → start, then follow the decreasing distance path
For a beginner moving from left-hand rule, the easiest transition is:
Keep exploring with something simple (even keep left-hand for now), but **after every move** (or every few moves):
- Update walls from sensors
- Re-run flood-fill from center
- Then instead of left-hand logic, move toward the neighbor with smallest distance
### Suggested structure for flood-fill version
Here’s how you can adapt your code step by step.
Keep most of your globals / helpers, but add/replace:
# Add near the top
from collections import deque
# Goal for 5×5 (adjust if your API uses different indexing)
GOAL_X, GOAL_Y = 2, 2
# Distance map: lower = better (closer to goal)
dist = [[999] * HEIGHT for _ in range(WIDTH)] # big number = unknown/far
def reset_and_flood_from_goal():
"""Recompute shortest distances from current known walls"""
for i in range(WIDTH):
for j in range(HEIGHT):
dist[i][j] = 999
q = deque()
q.append((GOAL_X, GOAL_Y))
dist[GOAL_X][GOAL_Y] = 0
while q:
cx, cy = q.popleft()
cd = dist[cx][cy]
for d in range(4): # N E S W
if (walls[cx][cy] & DIR_BITS[d]) != 0:
continue # wall in that direction
nx = cx + DIRS[d][0]
ny = cy + DIRS[d][1]
if not in_bounds(nx, ny):
continue
if dist[nx][ny] > cd + 1:
dist[nx][ny] = cd + 1
q.append((nx, ny))Then change your main loop to something like this:
# Initial setup
x, y = 0, 0
dir = N
step_count = 0
visited[x][y] = True
sense_walls()
# Optional: flood once at beginning (will be almost all 999)
reset_and_flood_from_goal()
while True:
sense_walls() # always sense first
# Re-flood after sensing (you can do this less often for speed later)
reset_and_flood_from_goal()
if x == GOAL_X and y == GOAL_Y:
API.log("Center reached in " + str(step_count) + " steps!")
break # or exit() depending on simulator
# Find best move: lowest dist among accessible neighbors
best_dist = 9999
best_dir = -1
for offset in [-1, 0, 1]: # prefer forward > left > right (or customize)
cand_dir = (dir + offset) % 4
if (walls[x][y] & DIR_BITS[cand_dir]) != 0:
continue # wall
nx = x + DIRS[cand_dir][0]
ny = y + DIRS[cand_dir][1]
if not in_bounds(nx, ny):
continue
if dist[nx][ny] < best_dist:
best_dist = dist[nx][ny]
best_dir = cand_dir
if best_dir == -1:
# Dead end / error — turn around
rotate_right()
rotate_right()
continue
# Face the best direction
while dir != best_dir:
if (best_dir - dir) % 4 == 1:
rotate_right()
else:
rotate_left()
# Move
move_forward()
# Optional: log distance map occasionally for debugging
# if step_count % 5 == 0:
# API.log("Current dist at mouse: " + str(dist[x][y]))### Key points & tips
- In very early exploration, many cells have dist=999 → mouse will mostly do exploration (you can keep left-hand as fallback when multiple equal choices)
- Re-flooding every step is fine for 5×5 or 9×9 (very fast), but in 16×16 real mazes people flood only when new cells are discovered
- For speed runs (second run): flood once from center → start, then follow decreasing dist without re-flooding
- Your wall representation (bitmask per cell) is good — keep it
-
visited can still be useful to avoid re-visiting known dead-ends
If you want to post this on python-forum.io, feel free to use/adapt any part — just credit back to our chat if you like (no obligation).
Let me know how it goes, or if you want to add:
- diagonal moves (more advanced)
- better exploration strategy
- printing the distance map for debug
- handling multiple goal cells (center 2×2 block)
Happy coding, and good luck with the little mouse! 🐭🏁
