Lost

When your snake wanders in a maze...

Sébastien Boisgérault
Associate Professor, ITN Mines Paris – PSL

Introduction

The aim of this project is to develop an “automatic navigation system” for our snake, to allow it to reach the fruit despite a complex environment with rocks that should be avoided.

Getting Started

For the sake of simplicity, we will consider here only mazes defined within a 30x30 grid. We will represent them in Python as sets of pairs of integers between 0 and 29, where each pair represents the coordinates of an empty cell of the maze. The pair (0, 0) corresponds to the top left corner of the grid.

A maze generated (pseudo-)randomly with a mix of 75% empty cells (in white) and 25% walls (in black).

Maze Visualizer

We store the description of such mazes in files, using a simple (but undocumented) file format. For example the maze displayed above is stored as random-maze.py.

Download this example maze file.
Inspect it contents and make an educated guess about the file format specification.
Construct the maze object random_maze associated to this file.

Solution

The random-maze.py file is an (ASCII) text file that contains:

{
    (15, 21),
    (26, 21),
    (7, 17),
    ...
    (18, 8),
}

So to begin with, we can load this content as a string random_maze_repr:

file = open("random-maze.py", mode="rt", encoding="ascii")
random_maze_repr = file.read()
file.close()

This string contains a sequence of integer pairs which seem to represent the integer coordinates of the empty maze cells. So, we could probably analyze the contents line by line, extract the coordinates, etc. For example, the following code makes the job:

random_maze = set()
for line in random_maze_repr.splitlines():
    line = line.strip()
    if line not in ("{", "}", ""):
        core = line[1:-2]
        x, y = core.split(",")
        x, y = int(x.strip()), int(y.strip())
        random_maze.add((x, y))

But we can also notice that the string format is exactly the representation that Python uses for sets of pairs of integers. In this case, that means that we can simply eval the string instead:

random_maze = eval(maze_repr)

Additionally, this solution would work even if the file format had a more compact representation where there are several coordinates on the same line.

Finally, after a bit of clean-up, our integrated solution would be:

def load_maze(filename):
    file = open(filename, mode="rt", encoding="ascii")
    maze_repr = file.read()
    file.close()
    maze = eval(maze_repr)
    return maze

random_maze = load_maze("random-maze.py")

Visualization

Develop a function draw_maze to display a maze. This function should work in the following context:

import pyxel

WIDTH = 30
HEIGHT = 30

random_maze = ...

pyxel.init(WIDTH, HEIGHT)
draw_maze(random_maze)
pyxel.show()

Solution

BLACK = 0
WHITE = 7  # ℹ️ light grey tbh

def display(color, pixels=None):
    if pixels is None:
        pyxel.cls(color)
    elif len(pixels) >= 1 and type(pixels[0]) == int:
        display(color, [pixels])
    else:
        for x, y in pixels:
            pyxel.pset(x, y, color)

def draw_maze(maze):
    display(BLACK)
    display(WHITE, maze)

Create your own maze

Design your own 30x30 maze, for example the empty maze, a spiral, etc.

Graphs and Paths

Mazes and Graphs

For each maze we define a graph

whose vertices are the empty cells of the maze,
whose edges represent the admissible movements from one cell to a neighboring cell (the two cells are empty and share a side),
for which the weight of each edge is 1; it represents the number of elementary actions (or “cost”) needed to move from one cell to a neighboring cell.

Given this definition

What Python data structure would we naturally use to represent these graphs?
Implement a function maze_to_graph which builds the graph associated to a maze.

Solution

It seems natural to represent the vertices as a set of pairs of integers, the edges as a set of pairs of vertices and the weights as a dictionary having as keys the edges and as unique value the integer 1.

UP, RIGHT, DOWN, LEFT = (0, -1), (1, 0), (0, 1), (-1, 0) 

def maze_to_graph(maze):
    vertices = set(maze)
    edges = set()
    weights = {}
    for vertex in vertices:
        x, y = vertex
        for (dx, dy) in [UP, RIGHT, DOWN, LEFT]:
            neighbor = (x + dx, y + dy)
            if neighbor in vertices:
                edge = (vertex, neighbor)
                edges.add(edge)
                weights[edge] = 1
    return (vertices, edges, weights)

Reachable Cells

Implement a function reachable_cells which returns the set of cells of a maze which are reachable from the cell source.

Computation of the cells reachable from the top-left corner. The green cells are reachable cells whose neighbors have between inspected; orange cells are reachable, but their neighbors have not yet been inspected; Two groups of empty cells stay white until the end, and hence are unreachable.

Solution

def reachable_cells(maze, source):
    vertices, edges, _ = maze_to_graph(maze)
    todo = {source}
    done = set()
    while todo:
        current = todo.pop()
        neighbors = {
            v for v in vertices 
            if (current, v) in edges
        }
        for n in neighbors:
            if n not in done:
                todo.add(n)
        done.add(current)
    return done

Extend the function draw_maze to graphically differentiate a set of cells using a given color. Then use it to represent the set of cells reachable from the top left corner of the maze random_maze.

Solution

LIGHT_GREEN = 11

def draw_maze(maze, cells=None):
    display(BLACK)
    display(maze, WHITE, maze)
    if cells is not None:
        display(cells, LIGHT_GREEN)

TOP_LEFT = (0, 0)

cells = reachable_cells(random_maze, source=TOP_LEFT)

pyxel.init(WIDTH, HEIGHT)
draw_maze(maze=random_maze, cells=cells)
pyxel.show()

Mazes and Paths

Computation of the cells reachable from the top-left corner, together with the path effectively used to joing them (in pink).

Solution

A possible solution is:

def path_from(maze, source):
    vertices, edges, _ = maze_to_graph(maze)
    todo = set()
    done = set()
    path = {}
    if source in maze:
       todo.add(source)
       path[source] = [source]
    while todo:
        current = todo.pop()
        neighbors = {
            v for v in vertices 
            if (current, v) in edges
        }
        for n in neighbors:
            if n not in done and n not in todo:
                path[n] = path[current] + [n]
                todo.add(n)
        done.add(current)
    return path

Use this function to find a path joining the top left and bottom right corners of the maze random_maze and graphically represent the result by updating your function draw_maze.

A path that joins the top left corner and the bottom right one (in pink).

Solution

We can extend our function draw_maze as follows:

PINK = 14

def draw_maze(maze, cells=None, path=None):
    display(BLACK)
    display(maze, WHITE, maze)
    if cells is not None:
        display(cells, LIGHT_GREEN)
    if path is not None:
        display(path, PINK)

and use it like that:

target_to_path = path_from(random_maze, TOP_LEFT)
BOTTOM_RIGHT = (WIDTH - 1, HEIGHT - 1)
path = target_to_path[BOTTOM_RIGHT]
draw_maze(random_maze, path=path)

Snake Game: Autopilot

Go back to the snake game of the previous session, discard the user inputs and instead use your brand new path finding algorithm to select the snake next move.

🎮

Solution

constants.py:

import pyxel

# Geometry
WIDTH = 30
HEIGHT = 30

# Frame rate
FPS = 10

# Colors
BLACK = 0
WHITE = 7
PINK = 8
DARK_GREEN = 3
LIGHT_GREEN = 11

# Directions
UP = [0, -1]
RIGHT = [1, 0]
DOWN = [0, 1]
LEFT = [-1, 0]
ARROW_KEYS = [
    pyxel.KEY_UP, 
    pyxel.KEY_DOWN, 
    pyxel.KEY_LEFT, 
    pyxel.KEY_RIGHT
]

maze.py:

from constants import UP, RIGHT, DOWN, LEFT

def maze_to_graph(maze):
    vertices = set(maze)
    edges = set()
    weights = {}
    for vertex in vertices:
        x, y = vertex
        for (dx, dy) in [UP, RIGHT, DOWN, LEFT]:
            neighbor = (x + dx, y + dy)
            if neighbor in vertices:
                edge = (vertex, neighbor)
                edges.add(edge)
                weights[edge] = 1
    return (vertices, edges, weights)

def path_from(maze, source):
    vertices, edges, _ = maze_to_graph(maze)
    todo = set()
    done = set()
    path = {}
    if source in maze:
       todo.add(source)
       path[source] = [source]
    while todo:
        current = todo.pop()
        neighbors = {
            v for v in vertices 
            if (current, v) in edges
        }
        for n in neighbors:
            if n not in done and n not in todo:
                path[n] = path[current] + [n]
                todo.add(n)
        done.add(current)
    return path

snake.py:

import pyxel
from constants import *
from maze import path_from

def spawn_new_rocks():
    global rocks
    rocks = []
    for i in range(WIDTH):
        for j in range(HEIGHT):
            if (i+j) % 5 == 0 and (i-j) % 11 == 0:
                rocks.append((i, j))

def spawn_new_snake():
    global snake_geometry, snake_direction
    snake_geometry = [
        (10, 15),
        (11, 15),
        (12, 15),
    ]
    snake_direction = RIGHT

def spawn_new_fruit():
    global fruit
    while True:
        fruit = (pyxel.rndi(0, WIDTH-1), pyxel.rndi(0, HEIGHT-1))
        if fruit not in snake_geometry and fruit not in rocks:
            break

def spawn_everything():
    spawn_new_rocks()
    spawn_new_snake()
    spawn_new_fruit()

path_to_fruit = None

def compute_path_to_fruit():
    head, body = snake_geometry[-1], snake_geometry[:-1]
    maze = {(i, j) for j in range(HEIGHT) for i in range(WIDTH)}
    maze = maze - set(rocks)
    maze = maze - set(body)
    path_map = path_from(maze, head)
    if fruit in path_map:
        return path_map[fruit]
    else:
        return None

def select_move():
    global snake_direction, path_to_fruit
    if path_to_fruit is None or len(path_to_fruit) == 1:
        path_to_fruit = compute_path_to_fruit()
    if path_to_fruit is not None:
        current, next = path_to_fruit[0], path_to_fruit[1]
        snake_direction = (next[0] - current[0], next[1] - current[1])
        del path_to_fruit[0]

def crash(head):
    """
    Returns True if the snake crashes: 
      - into itself, 
      - into a rock, 
      - or into the arena wall.
    """
    return (
        head in snake_geometry
        or head in rocks
        or (
        head[0] < 0
        or head[0] > WIDTH-1
        or head[1] < 0
        or head[1] > HEIGHT-1
        )
    )

def snake_move():
    global snake_geometry, fruit
    snake_head = snake_geometry[-1]
    new_snake_head = (
        snake_head[0] + snake_direction[0],
        snake_head[1] + snake_direction[1],
    )
    if crash(new_snake_head): # 💀
        # 🐍 keep the old head and shrink the tail
        snake_geometry = snake_geometry[1:-1] + [snake_head]
    elif new_snake_head == fruit: # 🍓
        # 🐍 move the head and grow the tail
        snake_geometry = snake_geometry + [new_snake_head]
        spawn_new_fruit()
    else:
        # 🐍 move the head; the tail follows
        snake_geometry = snake_geometry[1:] + [new_snake_head]

def update():
    select_move()
    snake_move()

def display(color, pixels=None):
    if pixels is None:
        pyxel.cls(color)
    elif len(pixels) >= 1 and isinstance(list(pixels)[0], int):
        display(color, [pixels])
    else:
        for x, y in pixels:
            pyxel.pset(x, y, color)

def draw():
    display(WHITE)
    snake_body = snake_geometry[:-1]
    snake_head = snake_geometry[-1]
    display(DARK_GREEN, snake_body)
    display(LIGHT_GREEN, snake_head)
    display(BLACK, rocks)
    display(PINK, fruit)

pyxel.init(WIDTH, HEIGHT, fps=FPS)
spawn_everything()
pyxel.run(update, draw)