pathfinding.py

import random
import tkinter as tk
import customtkinter as ctk

'''GRILLE'''
class Grid:
    def __init__(self):
        self.rows = 20
        self.cols = self.rows
        self.height = canvas.winfo_reqheight()
        self.width = canvas.winfo_reqwidth()
        self.box_height = self.height / self.rows
        self.box_width = self.width / self.cols
        self.lines = []
        self.rectangles = []
        self.closed_list = []
        self.current_group = []
        self.groups = []

    def draw_grid(self):
        # Dessine les bordures de la grille
        for line_id in self.lines:
            canvas.delete(line_id)
        self.lines.clear()
        for x in range(self.cols + 1):
            line_id = canvas.create_line(x * self.box_width, 0, x * self.box_width, self.height, fill='black')
            self.lines.append(line_id)
        for y in range(self.rows + 1):
            line_id = canvas.create_line(0, y * self.box_height, self.width, y * self.box_height, fill='black')
            self.lines.append(line_id)

    def randomize_grid(self, probability):
        # Randomise la couleur des cases d'après la probabilité choisie par l'utilisateur
        self.grid = []
        for i in range(self.rows):
            self.grid.append([])
            for _ in range(self.cols):
                self.grid[i].append(random.choices([0, 1], [(100 - int(probability.get())) / 100, int(probability.get()) / 100])[0])
        if self.is_grid_black(self.grid):
            i1 = random.randint(0, self.rows - 1)
            j1 = random.randint(0, self.cols - 1)
            i2 = random.choice([x for x in range(self.rows) if x != i1])
            j2 = random.choice([x for x in range(self.cols) if x != j1])
            self.grid[i1][j1] = 0
            self.grid[i2][j2] = 0
        self.draw_obstacles()
    
    def correct_grid(self):
        # Recolore des cases en blanc pour les rendre connexes
        self.groups = []
        self.closed_list = []
        # Parcours de la grille et recense les groupes de cases blanches
        for i in range(len(self.grid)):
            for j in range(len(self.grid[i])):
                if self.grid[i][j] == 0 and (i, j) not in self.closed_list:
                    self.flood_fill(i, j)
                    self.groups.append(self.current_group)
                    self.current_group = []
        # Correction de la grille jusqu'à ce qu'il ne reste qu'un groupe de cases blanches
        while len(self.groups) > 1:
            # Parcours de chaque groupe
            for group in self.groups:
                corrected = False
                # Parcours de chaque case du groupe actuel
                for box in group:
                    # Parcours des cases noires adjacentes
                    for one in self.adjacent_boxes(box[0], box[1], 'black'):
                        # Parcours des cases blanches adjacentes à la case noire actuelle
                        for zero in self.adjacent_boxes(one[0], one[1], 'white'):
                            # Si la case blanche n'appartient pas au même groupe, on recolore la case noire qui les relie
                            if zero not in group:
                                self.grid[one[0]][one[1]] = 0
                                corrected = True
                                # Fusion des deux groupes
                                for group2 in self.groups:
                                    if group2 == group:
                                        continue
                                    for box2 in group2:
                                        if box2 == zero:
                                            for i in group2:
                                                group.append(i)
                                            # Ajout de la case noire recolorée dans le groupe, si pas déjà fait
                                            if (one[0], one[1]) not in group:
                                                group.append((one[0], one[1]))
                                            self.groups.remove(group2)
                                            break
                                    else:
                                        continue
                                    break
                # Si aucune correction n'a pu être apportée au groupe, une case noire quelconque est supprimée
                if not corrected:
                    for any in group:
                       for one in self.adjacent_boxes(any[0], any[1], 'black'):
                           self.grid[one[0]][one[1]] = 0
                           break
                       else:
                           continue
                       break
            self.groups = []
            self.closed_list = []
            self.correct_grid()
        return
    
    def flood_fill(self, i, j):
        # Crée des groupes de cases blanches connexes
        # Ajoute la case dans des listes
        self.closed_list.append((i, j))
        self.current_group.append((i, j))
        # Vérification des cases adjacentes
        if j <= self.cols - 2 and self.grid[i][j+1] == 0 and (i, j+1) not in self.closed_list:
            self.flood_fill(i, j+1)
        if i <= self.rows - 2 and self.grid[i+1][j] == 0 and (i+1, j) not in self.closed_list:
            self.flood_fill(i+1, j)
        if j >= 1 and self.grid[i][j-1] == 0 and (i, j-1) not in self.closed_list:
            self.flood_fill(i, j-1)
        if i >= 1 and self.grid[i-1][j] == 0 and (i-1, j) not in self.closed_list:
            self.flood_fill(i-1, j)

    def set_start_finish(self):
        # Dessine un point de départ et d'arrivée
        self.draw_obstacles()
        # Choix aléatoire des points
        self.start = random.choice(self.groups[0])
        self.groups[0].remove(self.start)
        self.finish = random.choice(self.groups[0])
        self.groups[0].append(self.start)
        # Modifie la couleur des points
        rect_id = canvas.create_rectangle(self.start[1] * self.box_width, self.start[0] * self.box_height,
                                          (self.start[1] + 1) * self.box_width, (self.start[0] + 1) * self.box_height, fill='SpringGreen2')
        self.rectangles.append(rect_id)
        rect_id = canvas.create_rectangle(self.finish[1] * self.box_width, self.finish[0] * self.box_height,
                                          (self.finish[1] + 1) * self.box_width, (self.finish[0] + 1) * self.box_height, fill='OrangeRed2')
        self.rectangles.append(rect_id)

    def astar(self):
        # Algorithme de pathfinding A*
        # Initialisations
        g0 = 0
        # Fonction heuristique
        h0 = abs(self.start[0] - self.finish[0]) + abs(self.start[1] - self.finish[1])
        f0 = g0 + h0
        # Listes ouverte et fermée : éléments sous la forme (f, h, g, case courante, parent)
        astar_open = [(f0, h0, g0, self.start, None)]
        astar_closed = []
        # Parcours de la liste ouverte
        while len(astar_open) > 0:
            for neighbor in self.adjacent_boxes(astar_open[0][3][0], astar_open[0][3][1], 'white'):
                self.colorize(neighbor[1] * self.box_width, neighbor[0] * self.box_height,
                              (neighbor[1] + 1) * self.box_width, (neighbor[0] + 1) * self.box_height, 'light blue')
                g = astar_open[0][2] + 1
                h = abs(neighbor[0] - self.finish[0]) + abs(neighbor[1] - self.finish[1])
                f = g + h 
                # Cas 1 : voisin déjà dans la liste ouverte
                if any(e[3] == neighbor for e in astar_open):
                    # Si les valeurs sont plus faibles, on modifie le parent de la case voisine
                    if f < astar_open[0][0] or f == astar_open[0][0] and h < astar_open[0][1]:
                        for e in astar_open:
                            if e[3] == neighbor:
                                astar_open[astar_open.index(e)] = (f, h, g, neighbor, astar_open[0][3])
                # Cas 2 : voisin dans la liste fermée (on passe directement au voisin suivant)
                elif any(e[3] == neighbor for e in astar_closed):
                    continue
                # Cas 3 : voisin dans aucune liste
                else:
                    # La case est ajoutée dans la liste ouverte
                    astar_open.append((f, h, g, neighbor, astar_open[0][3]))
                    # Si le voisin est la case d'arrivée, on arrête l'algorithme
                    if neighbor == self.finish:
                        parent = astar_open[0][3]
                        break
            else:
                # Actualisation des listes à la fin du parcours des voisins
                astar_closed.append(astar_open[0])
                astar_open.remove(astar_open[0])
                astar_open.sort()
                continue
            astar_closed.append(astar_open[0])
            astar_open.remove(astar_open[0])
            break
            
        # Dessin du chemin trouvé (de l'arrivée au départ)
        while parent != None:
            for e in astar_closed:
                if e[3] == parent:
                    if e[3] != self.start:
                        # Colorie les cases du chemin en bleu
                        self.colorize(e[3][1] * self.box_width, e[3][0] * self.box_height,
                                      (e[3][1] + 1) * self.box_width, (e[3][0] + 1) * self.box_height, 'RoyalBlue4')
                    parent = e[4]
                    break
        self.colorize(self.start[1] * self.box_width, self.start[0] * self.box_height,
                      (self.start[1] + 1) * self.box_width, (self.start[0] + 1) * self.box_height, 'SpringGreen4')
        self.colorize(self.finish[1] * self.box_width, self.finish[0] * self.box_height,
                      (self.finish[1] + 1) * self.box_width, (self.finish[0] + 1) * self.box_height, 'OrangeRed4')

    def adjacent_boxes(self, i, j, color):
        # Crée une liste pour les cases adjacentes de couleur voulue
        neighbors = []
        if color == 'white':
            if j <= self.cols - 2 and self.grid[i][j+1] == 0:
                neighbors.append((i, j+1))
            if i <= self.rows - 2 and self.grid[i+1][j] == 0:
                neighbors.append((i+1, j))
            if j >= 1 and self.grid[i][j-1] == 0:
                neighbors.append((i, j-1))
            if i >= 1 and self.grid[i-1][j] == 0:
                neighbors.append((i-1, j))
        elif color == 'black':
            if j >= 1 and self.grid[i][j-1] == 1:
                neighbors.append((i, j-1))
            if i >= 1 and self.grid[i-1][j] == 1:
                neighbors.append((i-1, j))
            if j <= self.cols - 2 and self.grid[i][j+1] == 1:
                neighbors.append((i, j+1))
            if i <= self.rows - 2 and self.grid[i+1][j] == 1:
                neighbors.append((i+1, j))
        return neighbors

    def draw_obstacles(self):
        # Dessine les rectangles noirs
        # Supprime tous les rectangles actuels
        for rect_id in self.rectangles:
            canvas.delete(rect_id)
        self.rectangles.clear()
        # Redessine les nouveaux rectangles
        for i in range(len(self.grid)):
            for j in range(len(self.grid[i])):
                if self.grid[i][j] == 1:
                    self.colorize(j * self.box_width, i * self.box_height,
                                  (j + 1) * self.box_width, (i + 1) * self.box_height, 'gray12')
    
    def colorize(self, x0, y0, x1, y1, color):
        # Colorie une case d'une couleur donnée en paramètres
        rect_id = canvas.create_rectangle(x0, y0, x1, y1, fill=color)
        self.rectangles.append(rect_id)

    def is_grid_black(self, grid):
        # Vérifie que la grille ait au minimum 2 cases blanches
        # Si ce n'est pas le cas, elle recolore 2 cases noires
        white_nb = 0
        for i in grid:
            for value in i:
                if value == 0:
                    white_nb += 1
                if white_nb >= 2:
                    return False
        return True

'''FONCTIONS DES WIDGETS'''
def randomize():
    if entry_value.get() != '':
        grid.randomize_grid(entry_value)
        # Widgets bloqués
        button_set.configure(state='disabled', fg_color=DISABLED_COLOR)
        button_astar.configure(state='disabled', fg_color=DISABLED_COLOR)
        slider_grid_size.configure(state='disabled', progress_color='gray60', button_color='gray80')
        # Boutons débloqués
        button_correct.configure(state='normal', fg_color=ENABLED_COLOR, command=correct)
        button_clear.configure(state='normal', fg_color=ENABLED_COLOR, command=clear)

def correct():
    grid.correct_grid()
    grid.draw_obstacles()
    # Boutons bloqués
    button_correct.configure(state='disabled', fg_color=DISABLED_COLOR)
    # Boutons débloqués
    button_set.configure(state='normal', fg_color=ENABLED_COLOR, command=set)

def set():
    grid.set_start_finish()
    # Boutons débloqués
    button_astar.configure(state='normal', fg_color=ENABLED_COLOR, command=astar)

def astar():
    grid.astar()
    # Boutons bloqués
    button_astar.configure(state='disabled', fg_color=DISABLED_COLOR)

def clear():
    grid.grid = []
    grid.draw_obstacles()
    # Boutons bloqués
    button_correct.configure(state='disabled', fg_color=DISABLED_COLOR)
    button_set.configure(state='disabled', fg_color=DISABLED_COLOR)
    button_astar.configure(state='disabled', fg_color=DISABLED_COLOR)
    button_clear.configure(state='disabled', fg_color=DISABLED_COLOR)
    # Widgets débloqués
    slider_grid_size.configure(state='normal', progress_color=PROGRESS_COLOR, button_color=ENABLED_COLOR)

def set_grid_size(event):
    grid.rows = int(slider_grid_size.get())
    grid.cols = grid.rows
    grid.box_height = grid.height / grid.rows
    grid.box_width = grid.width / grid.cols
    grid.draw_grid()
    value = slider_grid_size.get()
    text_grid_size.configure(text='Grid Size : ' + str(int(value)) + ' x ' + str(int(value)))

def restrict_input(*args):
    # Restreint l'input aux nombres entiers compris entre 1 et 99
    try:
        value = int(entry_value.get())
        if value < 1:
            entry_value.set('1')
        elif value > 99:
            entry_value.set('99')
    except ValueError:
        entry_value.set('')

if __name__ == '__main__':
    '''CONSTANTES'''
    FRAME_W = 1000
    FRAME_H = 750
    CANVAS_W, CANVAS_H = FRAME_H, FRAME_H
    BUTTON_W = 160
    BUTTON_H = 36
    FONT = 'Bahnschrift'
    FONT_S = 16
    TEXT_COLOR = 'gray12'
    ENABLED_COLOR = 'PaleGreen3'
    DISABLED_COLOR = 'PaleGreen4'
    HOVER_COLOR = 'PaleGreen2'
    PROGRESS_COLOR = 'DarkSeaGreen2'
    TEXT_COLOR_DIS = 'gray20'

    '''FENETRE'''
    root = ctk.CTk()
    root.title('Pathfinding : A* Algorithm')
    root.resizable(False, False)
    root.geometry('1050x800')

    '''WIDGETS'''
    # FRAME
    frame = ctk.CTkFrame(root, width=FRAME_W, height=FRAME_H, fg_color='gray22')
    frame.place(relx=0.5, rely=0.5, anchor='c')

    # CANVAS
    canvas = tk.Canvas(frame, bd=-2, width=CANVAS_W, height=CANVAS_H, bg='floral white')
    canvas.place(relx=1, rely=0.5, anchor='e')

    # GRILLE
    grid = Grid()
    grid.draw_grid()

    # ENTREE
    entry_value = tk.StringVar(value='35')
    entry_value.trace('w', restrict_input)
    entry_probability = ctk.CTkEntry(frame, width=50, height=30, font=(FONT, FONT_S), justify='c',
                                    textvariable=entry_value)
    entry_probability.place(x=125, y=185, anchor='c')

    # TEXTE
    # Taille de la grille
    text_grid_size = ctk.CTkLabel(frame, text='Grid Size : ' + str(int(grid.rows)) + ' x ' + str(int(grid.cols)), font=(FONT, 14))
    text_grid_size.place(x=125, y=80, anchor='c')

    # Probabilité de génération d'obstacle
    text_probability = ctk.CTkLabel(frame, width=100, text= 'Obstacle Generation\nProbability', font=(FONT, 14))
    text_probability.place(x=(FRAME_W - CANVAS_W) / 2, y=145, anchor='c')

    # Symbole '%'
    text_percent = ctk.CTkLabel(frame, text='%', font =(FONT, FONT_S))
    text_percent.place(x=170, y=185, anchor='e')

    # SLIDER
    slider_grid_size = ctk.CTkSlider(frame, width=BUTTON_W, from_=5, to=30, fg_color='gray40', progress_color=PROGRESS_COLOR,
                                number_of_steps=25, button_color=ENABLED_COLOR, button_hover_color=HOVER_COLOR)
    slider_grid_size.set(grid.rows)
    slider_grid_size.bind('<ButtonRelease-1>', set_grid_size)
    slider_grid_size.place(x=125, y=50, anchor='c')

    # BOUTONS
    # Génération d'une nouvelle grille
    button_randomize = ctk.CTkButton(frame, width=BUTTON_W, height=BUTTON_H, text='Randomize Grid', font=(FONT, FONT_S),
                                    text_color=TEXT_COLOR, fg_color=ENABLED_COLOR, hover_color=HOVER_COLOR,
                                    command=randomize)
    button_randomize.place(x=(FRAME_W - CANVAS_W) / 2, y=250, anchor='n')

    # Correction de la grille
    button_correct = ctk.CTkButton(frame, width=BUTTON_W, height=BUTTON_H, text='Correct Grid', font=(FONT, FONT_S),
                                text_color=TEXT_COLOR, fg_color=DISABLED_COLOR, hover_color=HOVER_COLOR, state='disabled',
                                text_color_disabled=TEXT_COLOR_DIS)
    button_correct.place(x=(FRAME_W - CANVAS_W) / 2, y=300, anchor='n')

    # Placement des points de départ et d'arrivée
    button_set = ctk.CTkButton(frame, width=BUTTON_W, height=BUTTON_H, text='Set Start / Finish', font=(FONT, FONT_S),
                            text_color=TEXT_COLOR, fg_color=DISABLED_COLOR, hover_color=HOVER_COLOR, state='disabled',
                                text_color_disabled=TEXT_COLOR_DIS)
    button_set.place(x=(FRAME_W - CANVAS_W) / 2, y=350, anchor='n')

    # Lancement de A*
    button_astar = ctk.CTkButton(frame, width=BUTTON_W, height=BUTTON_H, text='Run Algorithm (A*)', font=(FONT, FONT_S),
                                text_color=TEXT_COLOR, fg_color=DISABLED_COLOR, hover_color=HOVER_COLOR, state='disabled',
                                text_color_disabled=TEXT_COLOR_DIS)
    button_astar.place(x=(FRAME_W - CANVAS_W) / 2, y=400, anchor='n')

    # Clear de la grille
    button_clear = ctk.CTkButton(frame, width=BUTTON_W, height=BUTTON_H, text='Clear Grid', font=(FONT, FONT_S),
                                text_color=TEXT_COLOR, fg_color=DISABLED_COLOR, hover_color=HOVER_COLOR, state='disabled',
                                text_color_disabled=TEXT_COLOR_DIS)
    button_clear.place(x=(FRAME_W - CANVAS_W) / 2, y=650, anchor='n')

    '''AFFICHAGE'''
    root.mainloop()