Génération de labyrtinthes et recherche de solution

Le but est de trouver le plus court chemin dans un labyrinthe en utilisant l'algorithme de Dijkstra

On va tout d'abord chercher à générer nos propres labyrinthes pour tester l'algorithme

Ce seront des labyrinthes carrés ou du moins rectangulaires dans un premier temps, pour des raisons pratiques et esthétiques.

On testera dans un second temps sur des labyrinthes plus exotiques afin de vérifier l'exactitude et l'universalité de notre implémentation de l'algorithme de Dijkstra

import random
from enum import Enum
import numpy as np
import sys
from PIL import Image
from IPython import display
import matplotlib.pyplot as plt
inf8 = float('inf')

sys.setrecursionlimit(8000)
class Directions(Enum):
    UP = 1
    DOWN = 2
    LEFT = 3
    RIGHT = 4

def createMaze(width,height):
    
    #On élargit le labyrinthe pour pouvoir entourer de murs
    if width % 2 == 0:
        width += 1
    if height % 2 == 0:
        height += 1
        
    maze = np.ones((height, width),dtype=float)

    for i in range(height):
        for j in range(width):
            if i % 2 == 1 or j % 2 == 1:
                maze[i, j] = 0
                if i == 0 or j == 0 or i == height - 1 or j == width - 1:
                    maze[i, j] = 0.5
                    
    sx = random.choice(range(2, width - 2, 2))
    sy = random.choice(range(2, height - 2, 2))
    
    generator(sx, sy, maze, width, height)
    
    for i in range(height):
        for j in range(width):
            if maze[i, j] == 0.5:
                maze[i, j] = 1
                
    maze[1, 2] = 1
    maze[height - 2, width - 3] = 1
                
    maze = maze * 255.0
    im = Image.fromarray(maze)
    im=im.convert("L")
    im.save("maze.png")
    plt.imshow(im)

    return maze

def generator(cx, cy, grid, width, height):
    grid[cy, cx] = 0.5
    #on se restreint bien a la zone de travail pour eviter les erreurs d'indice
    if not (cx in range(2, width - 2) and cy in range(2, height - 2)): 
        pass
    elif grid[cy - 2, cx] == 0.5 and grid[cy + 2, cx] == 0.5 and grid[cy, cx - 2] == 0.5 and grid[cy, cx + 2] == 0.5:
        pass
    else:
        li = [1, 2, 3, 4]
        while len(li) > 0:
            dir = random.choice(li)
            li.remove(dir)
            
            if dir == Directions.UP.value:
                ny = cy - 2
                my = cy - 1
            elif dir == Directions.DOWN.value:
                ny = cy + 2
                my = cy + 1
            else:
                ny = cy
                my = cy
                
            if dir == Directions.LEFT.value:
                nx = cx - 2
                mx = cx - 1
            elif dir == Directions.RIGHT.value:
                nx = cx + 2
                mx = cx + 1
            else:
                nx = cx
                mx = cx

            if grid[ny, nx] != 0.5:
                grid[my, mx] = 0.5
                generator(nx, ny, grid, width, height)

createMaze(50,50)

array([[255., 255., 255., ..., 255., 255., 255.],
       [255.,   0., 255., ..., 255.,   0., 255.],
       [255., 255., 255., ..., 255., 255., 255.],
       ...,
       [255., 255., 255., ..., 255., 255., 255.],
       [255.,   0., 255., ..., 255.,   0., 255.],
       [255., 255., 255., ..., 255., 255., 255.]])

On peut voir qu'il y a des soucis sur les bords, nos labyrinthes sont résolubles de façon triviale : en passant par les bords ! On va donc modifier le code pour nettoyer le rendu

sys.setrecursionlimit(8000)
class Directions(Enum):
    UP = 1
    DOWN = 2
    LEFT = 3
    RIGHT = 4

def createMaze(width,height,name):
    
    #On élargit le labyrinthe pour pouvoir entourer de murs
    if width % 2 == 0:
        width += 1
    if height % 2 == 0:
        height += 1
        
    #Ici on elargit la zone de travail, On terminera par elaguer afin d'obtenir un joli labyrinthe
    width+=2
    height+=2
        
    maze = np.ones((height, width),dtype=float)

    for i in range(height):
        for j in range(width):
            if i % 2 == 1 or j % 2 == 1:
                maze[i, j] = 0
                if i == 0 or j == 0 or i == height - 1 or j == width - 1:
                    maze[i, j] = 0.5
                    
    sx = random.choice(range(2, width - 2, 2))
    sy = random.choice(range(2, height - 2, 2))
    
    generator(sx, sy, maze, width, height)
    
    for i in range(height):
        for j in range(width):
            if maze[i, j] == 0.5:
                maze[i, j] = 1
                
    maze[1, 2] = 1
    maze[height - 2, width - 3] = 1
                
    maze = maze * 255.0
    #On crop afin d'eliminer les traces de l'algorithme sur les bords
    final=maze[2:-2,2:-2]
    im = Image.fromarray(final)
    im=im.convert("L")
    im.save(name + '.png')
    plt.imshow(im)

    return final

def generator(cx, cy, grid, width, height):
    grid[cy, cx] = 0.5
    #on se restreint bien a la zone de travail pour eviter les erreurs d'indice
    if not (cx in range(2, width - 2) and cy in range(2, height - 2)): 
        pass
    elif grid[cy - 2, cx] == 0.5 and grid[cy + 2, cx] == 0.5 and grid[cy, cx - 2] == 0.5 and grid[cy, cx + 2] == 0.5:
        pass
    else:
        li = [1, 2, 3, 4]
        while len(li) > 0:
            dir = random.choice(li)
            li.remove(dir)
            
            if dir == Directions.UP.value:
                ny = cy - 2
                my = cy - 1
            elif dir == Directions.DOWN.value:
                ny = cy + 2
                my = cy + 1
            else:
                ny = cy
                my = cy
                
            if dir == Directions.LEFT.value:
                nx = cx - 2
                mx = cx - 1
            elif dir == Directions.RIGHT.value:
                nx = cx + 2
                mx = cx + 1
            else:
                nx = cx
                mx = cx

            if grid[ny, nx] != 0.5:
                grid[my, mx] = 0.5
                generator(nx, ny, grid, width, height)

createMaze(100,100,'maze2')

array([[255.,   0., 255., ..., 255.,   0., 255.],
       [255.,   0., 255., ..., 255.,   0., 255.],
       [255.,   0., 255., ..., 255.,   0., 255.],
       ...,
       [255.,   0., 255., ..., 255.,   0., 255.],
       [255.,   0.,   0., ...,   0.,   0., 255.],
       [255., 255., 255., ..., 255., 255., 255.]])

On va maintenant passer à la résolution des labyrinthes générés, en utilisant l'algorithme de Dijkstra https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

On commence par créer quelques fonctions auxiliaires

def dijkstra_init(graph, source = (0,0)):
    d=np.zeros(graph.shape)
    prev=np.empty(graph.shape,tuple)
    Q=[]
    for i in range(graph.shape[0]):
        for j in range(graph.shape[1]):
            d[i,j]=inf8
            Q.append((i,j))
    d[source]=0    
    return d,prev,Q

#Ici on s'intéresse aux changements de couleur
#La distance entre un point noir et un point blanc doit être prohibitive

def dist(m,a,b=(0,0)):
    return abs(m[b]-m[a])/255

def dijkstra_get_min(Q, d):
    m=inf8
    u=(-1,-1)
    for s in Q:
        if d[s] < m:
            m = d[s]
            u = s
    return u

def neighbours(node):
    x, y = node
    return [
        (x + x_offset, y + y_offset)
        for x_offset in (-1, 0, 1)
        for y_offset in (-1, 0, 1)
        if  not(x_offset == y_offset == 0) and (x_offset ==0 or y_offset == 0) # on bloque la case en elle meme
        
    ]

def dijkstra(graph, source=(0,0)):
    d,prev,Q=dijkstra_init(graph, source)
    while Q:
        u= dijkstra_get_min(Q,d)
        Q.remove(u)
        for v in neighbours(u):
            if 0<=v[0]<graph.shape[0] and 0<=v[1]<graph.shape[1]:
                if d[v] > (d[u]+dist(graph,v,u)):
                    d[v] = (d[u]+dist(graph,v,u))
                    prev[v] = u
    return d, prev

dijkstra(createMaze(50,50,'maze2'),(0,0))

(array([[0., 1., 0., ..., 0., 0., 0.],
        [0., 1., 0., ..., 1., 1., 1.],
        [0., 1., 0., ..., 0., 0., 0.],
        ...,
        [0., 0., 0., ..., 0., 0., 0.],
        [1., 1., 1., ..., 0., 1., 0.],
        [0., 0., 0., ..., 0., 1., 0.]]),
 array([[None, (0, 0), (1, 2), ..., (0, 45), (0, 46), (0, 47)],
        [(0, 0), (1, 0), (2, 2), ..., (2, 46), (2, 47), (2, 48)],
        [(1, 0), (2, 0), (2, 3), ..., (2, 47), (2, 48), (3, 48)],
        ...,
        [(45, 0), (46, 0), (46, 1), ..., (47, 46), (46, 46), (46, 47)],
        [(46, 0), (46, 1), (46, 2), ..., (48, 46), (47, 46), (46, 48)],
        [(48, 1), (48, 2), (48, 3), ..., (48, 45), (48, 46), (47, 48)]],
       dtype=object))

On peut alors créer une fonction qui va nous dessiner le chemin trouvé sur le labyrinthe

def dijkstra_path(graph,name='solution',source=(0,0),destination=(-1,-1)):
    path=[]
    prev=dijkstra(graph,source)[1]
    s=destination
    while s!=source:
        path.append(s)
        s=prev[s]
    path.append(source)
    graphint=graph.astype(int)
    for x in path:
        graphint[x]=75
    im= Image.fromarray(graphint)
    im=im.convert("L")
    im.save(name + '.png')
    plt.imshow(im)

dijkstra_path(createMaze(30,30,'maze2'))

dijkstra_path(createMaze(100,50,'maze3'),'solution2')

Bien, tout semble fonctionner Essayons maintenant avec un labyrinthe rond, par exemple:

Ici l'arrivée est au milieu, on garde le départ en haut à gauche

Il nous faut donc convertir l'image en ndarray pour pouvoir le traiter avec notre programme

import imageio
img = imageio.imread('https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Circularmazeexample.jpg/241px-Circularmazeexample.jpg')
circ1=np.array(img)
print(circ1.shape)
plt.imshow(img)

(240, 241)

<matplotlib.image.AxesImage at 0x2732be12c40>

On va traiter l'image pour s'assurer de n'avoir que des pixels blancs ou noirs

circ1[circ1<128]=0
circ1[circ1>=128]=255

Je suspecte notre implémentation de Dijkstra d'être sous-optimale, je vais donc minuter la résolution

from timeit import default_timer as timer
start=timer()
dijkstra_path(circ1,'test',(0,0),(120,120))
end=timer()
t1=end-start
print(t1)

C:\Users\Gauthier\AppData\Local\Temp/ipykernel_15280/1705546453.py:17: RuntimeWarning: overflow encountered in ubyte_scalars
  return abs(m[b]-m[a])/255

174.63121050000063

On va procéder à quelques modifications, à savoir:

- Modification de la fonction distance car la précédente n'est sensible qu'aux différences de couleur

- Autoriser les diagonales

- Utiliser une liste à priorité pour éviter d'avoir à rechercher le minimum dans Q à chaque itération, optimisation générale du code

import math

#Nouvelle distance pseudo euclidienne, sensible aux murs

def dist(m,a,b=(0,0)):
    if(m[a]==m[b]==255):
        d=math.sqrt(abs(b[0]-a[0])**2 + abs(b[1]-a[1])**2)
    else:
        d=inf8
    return d    

def neighbours_full(node):
    x, y = node
    return [
        (x + x_offset, y + y_offset)
        for x_offset in (-1, 0, 1)
        for y_offset in (-1, 0, 1)
        if  not(x_offset == y_offset == 0) # on bloque la case en elle meme et sinon on retourne les 8 voisins directs
        
    ]

from heapq import heappush, heappop

def dijkstra_init_full(graph, source = (0,0)):    
    d=np.zeros(graph.shape)
    prev=np.empty(graph.shape,tuple)
    vis=np.empty(graph.shape) #On va utiliser un tableau de booléen pour voir si on a visité la case, pour avoir une
                                #liste de travail réduite
    Q=[]
    
    for i in range(graph.shape[0]):
        for j in range(graph.shape[1]):
            d[i,j]=inf8
            vis[i,j]=False
            
    d[source],vis[source]=0,True
    #Contrairement à précédemment, on commence avec une liste contenant seulement la source,
    #au lieu de l'ensemble des sommets
    heappush(Q,(0,source))    
    return d,prev,Q,vis

def dijkstra_full(graph, source=(0,0)):
    d,prev,Q,vis=dijkstra_init_full(graph, source)
    
    while Q:
        (di, u) = heappop(Q)
        vis[u] = True
        for v in neighbours_full(u):
            if (0<=v[0]<graph.shape[0]) and (0<=v[1]<graph.shape[1]) and (not vis[v]) :
                if d[v]> di+dist(graph,v,u):
                    d[v] = di + dist(graph,v,u)
                    heappush(Q, (d[v], v))
                    prev[v] = u
    return d, prev

def dijkstra_path_full(graph,name='solution',source=(0,0),destination=(-1,-1)):
    path=[]
    prev=dijkstra_full(graph,source)[1]
    s=destination
    
    while s != source:
        path.append(s)
        s=prev[s]
        
    path.append(source)
    graphint=np.zeros((graph.shape[0],graph.shape[1],3))
    graphint[:,:,0]=graph.astype(int)
    graphint[:,:,1]=graph.astype(int)
    graphint[:,:,2]=graph.astype(int)
    for x in path:
        graphint[x[0],x[1],1]=75 #On s'arrange pour faire ressortir le chemin
        
    im= Image.fromarray(graphint.astype('uint8'),"RGB")
    #im=im.convert("L")
    im.save(name + '.png')
    plt.imshow(im)
    

dijkstra_path_full(createMaze(200,50,'maze2'))

Comparons les performances avec l'exécution précédente sur le labyrinthe rond

start=timer()
dijkstra_path_full(circ1,'test',(0,0),(120,120))
end=timer()
t2=end-start
print(t1/t2)

194.57293192061658

Le résultat est convaincant

Voulant tester sur de gros labyrinthes générés par notre programme, celui-ci crash dès que la taille des tableaux dépasse 2^15.

Nous allons donc ré-écrire notre fonction génératrice en utilisant un arbre binaire

import numpy as np
def carve_maze_bin(grid:np.ndarray, size:int) -> np.ndarray:
    output_grid = np.empty([size*3, size*3],dtype=int)
    output_grid[:] = 0
    
    i = 0
    j = 0
    while i < size:
        w = i*3 + 1
        while j < size:
            k = j*3 + 1
            toss = grid[i,j]
            output_grid[w,k] = 255
            if toss == 0 and k+2 < size*3:
                output_grid[w,k+1] = 255
                output_grid[w,k+2] = 255
            if toss == 1 and w-2 >=0:
                output_grid[w-1,k] = 255
                output_grid[w-2,k] = 255
            
            j = j + 1
            
        i = i + 1
        j = 0
        
    return output_grid

def preprocess_grid_bin(grid:np.ndarray, size:int) -> np.ndarray:
    
    # fix first row and last column to avoid digging outside the maze external borders
    first_row = grid[0]
    first_row[first_row == 1] = 0
    grid[0] = first_row
    for i in range(1,size):
        grid[i,size-1] = 1
    return grid

def gen_bin(n=1, p=0.5, size=5,name='mazebin'):
    
    grid = np.random.binomial(n,p, size=(size,size))
    processed_grid = preprocess_grid_bin(grid, size)

    maze = carve_maze_bin(processed_grid, size)
    im = Image.fromarray(maze)
    im=im.convert("L")
    im.save(name +'.png')
    plt.imshow(im)
    return maze
    

gen_bin(1,0.5,200)

array([[  0,   0,   0, ...,   0,   0,   0],
       [  0, 255, 255, ..., 255, 255,   0],
       [  0, 255,   0, ...,   0, 255,   0],
       ...,
       [  0, 255,   0, ...,   0, 255,   0],
       [  0, 255,   0, ..., 255, 255,   0],
       [  0,   0,   0, ...,   0,   0,   0]])

La génération est rapide mais ces labyrinthes ne sont pas très esthétiques, essayons avec l'algorithme "recursive backtracker"

https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker

from queue import LifoQueue
from PIL import Image
import numpy as np
from random import choice

def gen_back(w, h):
    width=w//2
    height=h//2
    maze = np.zeros((2*width+1, 2*height+1))

    # Create a path on the very top and bottom so that it has an entrance/exit
    maze[:2,:2] = 255
    maze[-2:, -2:] = 255
    
    cells = np.zeros((width, height))
    stack = LifoQueue()
    cells[0, 0] = 1
    stack.put((0, 0))

    while not stack.empty():
        x, y = stack.get()

        adjacents = []
        if x > 0 and cells[x - 1, y] == 0:
            adjacents.append((x - 1, y))
        if x < width - 1 and cells[x + 1, y] == 0:
            adjacents.append((x + 1, y))
        if y > 0 and cells[x, y - 1] == 0:
            adjacents.append((x, y - 1))
        if y < height - 1 and cells[x, y + 1] == 0:
            adjacents.append((x, y + 1))

        if adjacents:
            stack.put((x, y))

            neighbour = choice(adjacents)
            neighbour_on_img = (neighbour[0]*2 + 1, neighbour[1]*2 + 1)
            current_on_img = (x*2 + 1, y*2 + 1)
            wall_to_remove = (neighbour[0] + x + 1, neighbour[1] + y + 1)

            maze[neighbour_on_img] = 255
            maze[current_on_img] = 255
            maze[wall_to_remove] = 255

            cells[neighbour] = 1            
            stack.put(neighbour)
            
    im = Image.fromarray(maze)
    im=im.convert("L")
    plt.imshow(im)
    return maze

gen_back(50,50)

array([[255., 255.,   0., ...,   0.,   0.,   0.],
       [255., 255.,   0., ...,   0., 255.,   0.],
       [  0., 255.,   0., ...,   0., 255.,   0.],
       ...,
       [  0.,   0.,   0., ...,   0.,   0.,   0.],
       [  0., 255., 255., ..., 255., 255., 255.],
       [  0.,   0.,   0., ...,   0., 255., 255.]])

Essayons maintenant sur un labyrinthe de grande taille :

dijkstra_path_full(gen_back(500,500),'big')

On termine avec la recherche d'une solution dans un labyrinthe inhabituel :

https://www.amazingmazes.co.uk/images/bubblebabybl.jpg

import urllib.request
urllib.request.urlretrieve('https://www.amazingmazes.co.uk/images/bubblebabybl.jpg',"hives.jpg")
img = Image.open("hives.jpg").convert("L")
hives=np.array(img)
hives[hives<100]=0
hives[hives>200]=255
print(hives.shape)
plt.imshow(img)

(700, 860)

<matplotlib.image.AxesImage at 0x2732fe28b50>

path=dijkstra_path_full(hives,'hives_sol',(170,145),(550,620))

References :

Génération de labyrinthes :

https://github.com/AryanAb/MazeGenerator

https://github.com/antigones/pymazes/blob/main/binary.py

https://github.com/ravenkls/Maze-Generator-and-Solver/blob/master/maze_generator.py

Algorithme de Dijkstra :

https://towardsdatascience.com/solving-mazes-with-python-f7a412f2493f

https://codereview.stackexchange.com/questions/249011/implementation-of-dijkstras-algorithm-in-python

https://gist.github.com/m00nlight/245d917cb030c515c513

https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Labyrinthe dessiné :

https://www.amazingmazes.co.uk/

Gauthier HARENG, étudiant de L3-Mathématiques à UGA - 2021