Labyrinthes

Pour obtenir le labyrinthe du fichier "random-maze.py":

filename = "mazes/random-maze.py"
file = open(filename, mode="rt", encoding="utf-8")
random_maze_repr = file.read()
file.close()
random_maze = eval(random_maze_repr)

# Pygame
import pygame as pg


# Constants
WIDTH, HEIGHT = 30, 30
CELL_SIZE = 20
FPS = 10
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)

def draw_background(screen):
    screen.fill(BLACK)

def draw_walls(screen, maze):
    h = CELL_SIZE
    for x, y in maze:
        pg.draw.rect(screen, WHITE, (x * h, y * h, h, h))

def display_maze(maze):
    pg.init()
    pg.display.set_caption("Labyrinthes")
    width_height = (WIDTH * CELL_SIZE, HEIGHT * CELL_SIZE)
    screen = pg.display.set_mode(width_height)
    clock = pg.time.Clock()
    while True:
        events = pg.event.get()
        if any(event.type == pg.QUIT for event in events):
            break
        draw_background(screen)
        draw_walls(screen, maze)
        pg.display.update()
        clock.tick(FPS)
    pg.quit()

Par exemple pour créer un labyrinthe sans mur :

empty_maze = set()
for y in range(0, HEIGHT):
    for x in range(0, WIDTH):
        empty_maze.add((x, y))

Puis pour le sauvegarder

empty_maze_repr = repr(empty_maze)
file = open("mazes/empty_maze.py", mode="wt", encoding="utf-8")
file.write(empty_maze_repr)
file.close()

Il semble naturel de représenter les sommets comme un ensemble de paires d’entiers, les arêtes comme un ensemble de paires de sommets et les poids comme un dictionnaire ayant comme clés les arêtes et comme valeur unique l’entier 1.

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

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

LIGHT_GREEN = (128, 255, 128)

def draw_cells(screen):
    h = CELL_SIZE
    for x, y in cells:
        pg.draw.rect(screen, LIGHT_GREEN, (x * h, y * h, h, h))

def display_maze(maze, cells=None):
    pg.init()
    pg.display.set_caption("Labyrinthes")
    width_height = (WIDTH * CELL_SIZE, HEIGHT * CELL_SIZE)
    screen = pg.display.set_mode(width_height)
    clock = pg.time.Clock()
    while True:
        events = pg.event.get()
        if any(event.type == pg.QUIT for event in events):
            break
        draw_background(screen)
        draw_walls(screen, maze)
        if cells is not None:
            draw_cells(screen)
        pg.display.update()
        clock.tick(FPS)
    pg.quit()

TOP_LEFT = (0, 0)
cells = reachable_cells(random_maze, source=TOP_LEFT)
display_maze(random_maze, cells=cells)

Une solution possible consiste à définir :

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

puis à étendre notre fonction display_maze de la façon suivante :

PINK = (255, 128, 128)

def draw_path(screen, path):
    h = CELL_SIZE
    for x, y in path:
        pg.draw.rect(screen, PINK, (x * h, y * h, h, h))

def display_maze(maze, cells=None, path=None):
    pg.init()
    pg.display.set_caption("Labyrinthes")
    width_height = (WIDTH * CELL_SIZE, HEIGHT * CELL_SIZE)
    screen = pg.display.set_mode(width_height)
    clock = pg.time.Clock()
    while True:
        events = pg.event.get()
        if any(event.type == pg.QUIT for event in events):
            break
        draw_background(screen)
        draw_walls(screen, maze)
        if cells is not None:
            draw_cells(screen)
        if path is not None:
            draw_path(screen, path)
        pg.display.update()
        clock.tick(FPS)
    pg.quit()

On exploite ensuite ces fonctions de la façon suivante:

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

def draw_map(screen, map):
    h = CELL_SIZE
    v_max = max(v for v in map.values())
    for (x, y), v in map.items():
        pg.draw.rect(
            screen,
            colormap(float(v / v_max)),
            (x * h, y * h, h, h),
        )

def display_maze(maze, cells=None, path=None, map=None):
    pg.init()
    pg.display.set_caption("Labyrinthes")
    width_height = (WIDTH * CELL_SIZE, HEIGHT * CELL_SIZE)
    screen = pg.display.set_mode(width_height)
    clock = pg.time.Clock()
    while True:
        events = pg.event.get()
        if any(event.type == pg.QUIT for event in events):
            break
        draw_background(screen)
        draw_walls(screen, maze)
        if cells is not None:
            draw_cells(screen, cells)
        if map is not None:
            draw_map(screen, map)
        if path is not None:
            draw_path(screen, path)
        pg.display.update()
        clock.tick(FPS)
    pg.quit()

map = {
    target: len(path) - 1 
    for target, path in target_to_path.items()
}
display_maze(random_maze, map=map)

Par construction, si à chaque cellule cible le chemin associé est le plus court possible, les longueurs des chemins entre deux cellules vides voisines ne peuvent différer que de -1, 0 ou 1. Par conséquent, il suffit de constater des écarts de couleurs importants entre cellules voisines de la carte (correspondant à un écart de longueur égal au moins à deux) pour en conclure qu’on a trouvé un chemin non optimal. Et c’est bien le cas à quelques endroits sur la carte des longueurs associée à l’algorithme path_from.

On va donc développer un algorithme nous assurant que la longueur est effectivement minimale.

import math

def shortest_path_from(maze, source): 
    vertices, edges, weight = maze_to_graph(maze)
    distance, path = {}, {}
    todo = {source}
    distance[source] = 0
    path[source] = [source]
    while todo:
        current = todo.pop()
        neighbors = {
            v for v in vertices 
            if (current, v) in edges
        }
        for n in neighbors:
            d = distance[current] + weight[(current, n)]
            if d < distance.get(n, math.inf):
                distance[n] = d
                path[n] = path[current] + [n]
                todo.add(n)
    return path

On peut tracer la carte de couleurs correspondantes avec :

target_to_path = shortest_path_from(random_maze, TOP_LEFT)
map = {
    target: len(path) - 1 
    for target, path in target_to_path.items()
}
display_maze(random_maze, map=map)