Why I made it
I watched this video by veritasium about Micro-Mouse maze-solving competitions, and found the logic to get to the center fascinating. Hence, despite not having a maze or a mouse, I spent a few hours coding my own interpretation of the logic used to get to the center.
Context
According to Wikipedia;
Micromouse is an event where small robotic mice compete to solve a 16×16 maze.
The rules are simple: A small robot mouse has to get to the center as fast as possible, while not knowing more than what it sees from an inside view along with where the maze's center is (relative to itself). My code respects these rules.
How it works
To decide in which direction it should go in, the mouse follows these steps:
Get possibilities from where you are at (ex: UDLR)
Ignore where you came from (ex: ULR)
If no options are left, go where you came from (dead end)
If one option left, go in that direction (continue)
If you are at an intersection you already crossed (see step 9), ignore the directions associated to it.
If one option left, go there and append that direction to the list (last branch to explore)
If no options left, you already tried all directions from where you are, so go back in the direction you initially came from the first time you went to that intersection.
Apply the priorities to decide where to go (ex: R)
Associate where you came from and where you will go with the current intersection's position to do the right choice if ever you are to reach that same intersection again
Change MouseX and MouseY accordingly
The priorities are as follow:
- If you can go towards the middle (X), do so
- Else if you can go towards the middle (Y), do so
- Or else chose any path (other than the one you took to come)
Code
Here is the python code:
"""
Maze solver based off some of the best Micro-Mouse competition techniques.
A maze is randomly generated, a mouse starts in the top left corner, and it finds its way
to reach the center basing itself only on where the center is relative to himself and in
which directions can it go in from where it currently is.
The techniques this script is inspired by are the ones that follow:
1. Djikstra best path (direction in this case) to center
2. Flood-fill (for going through each branch before returning to the trunk)
3. Ultimately, Theseus (for some trial and error)
"""
import time
import random
size = 17
# This is experimental, current logic struggles with open spaces, keep low
freewalls = 0
def clear_screen():
"""Clear screen and return to first line using an ASCII escape sequence"""
print("\x1b[1;1H", end="")
def generate_maze():
"""Randomly generates a solvable maze"""
maze = [["\u25fc" for _ in range(size)] for _ in range(size)]
def carve(x, y):
maze[x][y] = " "
dirs = [(2, 0), (-2, 0), (0, 2), (0, -2)]
random.shuffle(dirs)
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < size and 0 <= ny < size and maze[nx][ny] == "\u25fc":
maze[x + dx // 2][y + dy // 2] = " "
carve(nx, ny)
carve(0, 0) # ensure where the mouse starts at is open
# Creating some freestanding walls
for _ in range(freewalls):
freewallX = 0
freewallY = 0
while maze[freewallX][freewallY] == " ":
freewallX = random.randrange(size)
freewallY = random.randrange(size)
maze[freewallX][freewallY] = " "
maze[int((size - 1) / 2)][int((size - 1) / 2)] = " " # ensure center is open
return maze
displaygrid = generate_maze()
logicgrid = [row[:] for row in displaygrid]
MouseX = 0
MouseY = 0
width = len(displaygrid[0])
intersections = {}
camefrom = ""
def possible_movements(x, y):
"""Get possibilities for in which direction the mouse can go in"""
return logicgrid[y][x]
def displayed_character(x, y):
"""Get displayed character on a given position"""
if x < width and x >= 0 and y < width and y >= 0:
return displaygrid[y][x]
else:
return None
def set_logic(x, y, setto):
"""Set the possible directions the mouse can move in from a given position"""
logicgrid[y][x] = setto
def remove_logic(x, y, removethis):
"""Remove a direction from the possible directions the mouse can go in from a given position"""
logicgrid[y][x] = logicgrid[y][x].replace(removethis, "")
def display_check(x, y):
"""Check if the given position has the mouse or the goal before final printed result"""
if [x, y] == [MouseX, MouseY]:
return "M"
elif x == y == (width - 1) / 2:
return "X"
else:
return displayed_character(x, y)
def add_intersection(x, y, camefrom):
"""Add a direction to the list of directions to which the mouse has gone in from a certain position"""
intersections.setdefault((x, y), []).append(camefrom)
def recall_intersection(x, y):
"""Return all directions the mouse already went in from the intersection it is at"""
if intersections.get((x, y)):
return [_ for _ in intersections.get((x, y)) if _ is not None]
else:
return None
def next_move(directions, camefrom, middle):
"""Choose in which direction to go in next"""
possibilities = directions.replace(camefrom, "")
if len(possibilities) == 0: # It reached a dead end
return camefrom
if len(possibilities) > 1 and recall_intersection(
MouseX, MouseY
): # It has been there before, ignore all branches it has already explored
for branch in recall_intersection(MouseX, MouseY):
possibilities = possibilities.replace(branch, "")
if (
len(possibilities) == 0
): # If all branches from where it is have been explored, go back to where you initially came from
return recall_intersection(MouseX, MouseY)[0]
if len(possibilities) == 1: # If there is only one branch to explore left
return possibilities
add_intersection(MouseX, MouseY, camefrom)
movechoice = None
if MouseX < middle and "R" in possibilities:
movechoice = "R"
elif MouseX > middle and "L" in possibilities:
movechoice = "L"
elif MouseY < middle and "D" in possibilities:
movechoice = "D"
elif MouseY > middle and "U" in possibilities:
movechoice = "U"
else: # Take any path if they all dont go closer to the center. Occurs more often as width increases.
movechoice = possibilities[0]
add_intersection(MouseX, MouseY, movechoice)
return movechoice
def update_logic():
"""Set all the directions in which the mouse can go in per the displayed maze"""
for y, row in enumerate(logicgrid):
for x, cell in enumerate(logicgrid):
if displayed_character(x, y) == " ":
set_logic(x, y, "UDLR")
# Top and bottom
if y == 0:
remove_logic(x, y, "U")
if y == width - 1:
remove_logic(x, y, "D")
# Sides
if x == 0:
remove_logic(x, y, "L")
if x == width - 1:
remove_logic(x, y, "R")
# Corners
if x == 0 and y == 0:
set_logic(0, 0, "RD")
if x == 0 and y == width - 1:
set_logic(x, y, "UR")
if x == width - 1 and y == 0:
set_logic(x, y, "LD")
if x == width - 1 and y == width - 1:
set_logic(x, y, "UL")
# Non-walls
if displayed_character(x + 1, y) != " ":
remove_logic(x, y, "R")
if displayed_character(x - 1, y) != " ":
remove_logic(x, y, "L")
if displayed_character(x, y + 1) != " ":
remove_logic(x, y, "D")
if displayed_character(x, y - 1) != " ":
remove_logic(x, y, "U")
else:
set_logic(x, y, "WALL")
def update_display():
"""Print the maze"""
# Frame top
print("\u2588" * (2 * width + 1))
# Frame sides and content
for y, row in enumerate(displaygrid):
line = ["\u2588"]
for x, cell in enumerate(row):
line.append(f"{display_check(x, y)} ")
line[-1] = line[-1][:-1] # remove the last space
line.append("\u2588")
print("".join(line))
# Frame bottom
print("\u2588" * (2 * width + 1))
if __name__ == "__main__":
update_logic()
update_display()
print("\033[2J\033[H", end="")
middle = (width - 1) / 2
movenumber = 0
while MouseX != middle or MouseY != middle:
choices = possible_movements(MouseX, MouseY)
goto = next_move(choices, camefrom, middle)
if goto == "U":
MouseY -= 1
camefrom = "D"
if goto == "D":
MouseY += 1
camefrom = "U"
if goto == "L":
MouseX -= 1
camefrom = "R"
if goto == "R":
MouseX += 1
camefrom = "L"
time.sleep(0.1)
clear_screen()
update_display()
movenumber += 1
print(f"Done in {movenumber} steps")
Preview
Please tell me everything that comes to mind.
