• Explore
• My scripts
• Calculator

Génère un labyrinthe parfait de 16x11 puis trouve le chemin optimal vers la sortie à l’aide de l’algorithme A*. Mémorise le labyrinthe ayant le plus chemin

from kandinsky import *
from random import randrange,random
import time
from ion import *

largeur, hauteur = 320, 222
width, height = 32, 22
taille_x = largeur // width
taille_y = hauteur // height

def trace_case(laby, x, y, couleur_fond=(128,128,128), couleur_murs=(200,200,200)):
    # tracé du fond de case
    fill_rect(x*taille_x, y*taille_y, taille_x, taille_y, couleur_fond)
    fill_rect(int((x+0.9)*taille_x), y*taille_y,int(0.1*taille_x),int(0.1*taille_y),couleur_murs)
    fill_rect(int((x+0.9)*taille_x), int((y+0.9)*taille_y),int(0.1*taille_x),int(0.1*taille_y),couleur_murs)
    fill_rect(x*taille_x, int((y+0.9)*taille_y),int(0.1*taille_x),int(0.1*taille_y),couleur_murs)
    fill_rect(x*taille_x, (y)*taille_y,int(0.1*taille_x),int(0.1*taille_y),couleur_murs)
    
    
    # présence ou non de murs sur les côtés
    gauche, haut, droite, bas = get_directions(laby, x, y)
    # tracé des murs
    if not gauche:
        fill_rect(x * taille_x, int((y + .1) * taille_y), int(0.1 * taille_x), int(0.8 * taille_y), couleur_murs)
    if not haut:
        fill_rect(int((x + 0.1) * taille_x), y * taille_y, int(0.8 * taille_x), int(0.1 * taille_y), couleur_murs)
    if not droite:
        fill_rect(int((0.9 + x) * taille_x), int((y + 0.1) * taille_y), int(0.1 * taille_x), int(0.8 * taille_y), couleur_murs)
    if not bas:
        fill_rect(int((x + 0.1) * taille_x), int((y + 0.9) * taille_y), int(0.8 * taille_x), int(0.1 * taille_y), couleur_murs)

def dessine(laby):
    for h in range(height):
        for w in range(width):
            trace_case(laby, w, h, (128,128,128) ,(200,200,200))

def get_directions(laby, x, y):
    if x > 0 :
        gauche = (laby & 2 ** (2 * (width * y + x - 1))) >> (2 * (width * y + x - 1))
    else :
        gauche = 0
    if y>0 :
        haut = (laby & 2 ** (2 * (width * (y - 1) + x) + 1)) >> (2 * (width * (y - 1) + x) + 1)
    else :
        haut = 0
    droite = (laby & 2 ** (2 * (width * y + x))) >> (2 * (width * y + x))
    bas = (laby & 2 ** (2 * (width * y + x) + 1)) >> (2 * (width * y + x) + 1)
    return gauche, haut, droite, bas

def inverse_mur(laby,x,y,direction):
    mask = laby & 0
    if direction == 0:
        mask += 2 ** (2 * (width * y + x - 1))
    elif direction == 1:
        mask += 2 ** (2 * (width * (y - 1) + x) + 1)
    elif direction == 2 :
        mask += 2 ** (2 * (width * y + x))
    else :
        mask += 2 ** (2 * (width * y + x) + 1)
    return laby ^ mask 

def perfect(laby):
  groupes=[[(i%width,i//width)] for i in range(width*height)]
  
  while len(groupes) > 1:
    groupe = randrange(0,len(groupes))
    mur_casse = False
    ordre_cases = sorted(groupes[groupe], key=lambda x: random())
    k = 0
    while not mur_casse:
      case = ordre_cases[k]
      directions = sorted([0, 1, 2, 3], key=lambda x: random())
      for i in directions:
        if (i == 0
          and ordre_cases[k][0] > 0
          and not (ordre_cases[k][0] - 1, ordre_cases[k][1]) in groupes[groupe]
        ):
          to_move = get_group(groupes,(ordre_cases[k][0] - 1, ordre_cases[k][1]))
          mur_casse = True
        elif (
          i == 1
          and ordre_cases[k][1] > 0
          and not (ordre_cases[k][0], ordre_cases[k][1] - 1) in groupes[groupe]
        ):
          to_move = get_group(groupes,(ordre_cases[k][0], ordre_cases[k][1] - 1))
          mur_casse = True
        elif (
          i == 2
          and ordre_cases[k][0] < width - 1
          and not (ordre_cases[k][0] + 1, ordre_cases[k][1]) in groupes[groupe]
        ):
          to_move = get_group(groupes,(ordre_cases[k][0] + 1, ordre_cases[k][1]))
          mur_casse = True
        elif (
          i == 3
          and ordre_cases[k][1] < height - 1
          and not (ordre_cases[k][0], ordre_cases[k][1] + 1) in groupes[groupe]
        ):
          to_move = get_group(groupes,(ordre_cases[k][0], ordre_cases[k][1] + 1))
          mur_casse = True
        if mur_casse and groupe != to_move:
          laby = inverse_mur(laby, ordre_cases[k][0], ordre_cases[k][1], i)
          groupes = merge_groupes(groupes, groupe, to_move)
          
          break
      k += 1
  return laby

def get_group(groupes, XY):
  for i in range(len(groupes)):
    if XY in groupes[i]:
      return i
  else :
    raise ValueError("{} n'est pas dans le groupe".format(XY))

def merge_groupes(groupes,A,B):
  groupes[A] += groupes[B]
  del(groupes[B])
  return groupes

def recherche_trajet(laby, depart = (0, 0), arrivee = (0, 0), dessine = False, temps = 0):
  distances = [[((w-arrivee[0])**2+(h-arrivee[1])**2)**.5 for w in range(width)] for h in range(height)]
  visitees = [[-1 for w in range(width)] for h in range(height)]
  a_traiter = [depart]
  visitees[depart[1]][depart[0]] = 0
  itineraire_trouve=False
  while len(a_traiter) > 0:
    x,y=a_traiter[0]
    case = get_directions(laby,x,y)
    if dessine :
        trace_case(laby,x,y,(200,128,128),(200,200,200))
    
    if temps!=0:
        time.sleep(temps)
    
    if a_traiter[0] == arrivee:
      return visitees
    
    del(a_traiter[0])
    
    if x > 0 and case[0]:
        if visitees[y][x-1] == -1:
          visitees[y][x-1] = visitees[y][x] + 1
          a_traiter.append((x - 1, y))
      
    if y > 0 and case[1]:
        if visitees[y-1][x] == -1:
          visitees[y-1][x] = visitees[y][x] + 1
          a_traiter.append((x, y - 1))
    
    if x < (width - 1) and case[2]:
        if visitees[y][x + 1] == -1:
          visitees[y][x + 1] = visitees[y][x] + 1
          a_traiter.append((x + 1, y))
      
    if y < (height - 1) and case[3]:
        if visitees[y + 1][x] == -1:
          visitees[y + 1][x] = visitees[y][x] + 1
          a_traiter.append((x, y + 1))
    
       
    a_traiter.sort(key=lambda d:distances[d[1]][d[0]])
    

  raise ValueError("Chemin non trouvé")

def chemin(laby,visitees,depart,arrivee,dessine=False,temps=0):
    itineraire=[arrivee]
    while itineraire[-1]!=depart:
        case=itineraire[-1]
        x,y=case
        direction=get_directions(laby,x,y)
        possibles=[]
        if x>0:
            if visitees[y][x -1] == visitees[y][x]-  1 and direction[0]:
                possibles.append((x - 1, y))
        if y>0:
            if visitees[y - 1][x] == visitees[y][x] - 1 and direction[1]:
                possibles.append((x, y - 1))
        if x<width - 1:
            if visitees[y][x + 1]==visitees[y][x] - 1 and direction[2]:
                possibles.append((x + 1,y))
        if y<height - 1:
            if visitees[y + 1][x]==visitees[y][x] - 1 and direction[3]:
                possibles.append((x,y + 1))
        
        itineraire.append(possibles[0])
        
    for i in itineraire:
        if dessine :
            trace_case(laby,i[0],i[1],(250,250,128),(200,200,200))
        if temps!=0:
            time.sleep(temps)
        
    return itineraire[::-1]

def dessine_perso(x,y,taille_perso):
    fill_rect(x, y, taille_perso, taille_perso, (255,255,0))


    
def move_perso(laby,x,y,taille_perso):
    
    new_x=x-keydown(KEY_LEFT)+keydown(KEY_RIGHT)
    new_y=y-keydown(KEY_UP)+keydown(KEY_DOWN)
    directions=get_directions(laby,new_x//taille_x,new_y//taille_y)
    # tests position
    a = new_x % taille_x < 0.1 * taille_x
    b = new_x % taille_x + taille_perso > 0.9 * taille_x
    c = new_y % taille_y < 0.1 * taille_y
    d = new_y % taille_y + taille_perso > 0.9 * taille_y
    if (not(((not c) and (not d))) and (not ((not a) and (not b)))):
        return x,y
    if ((not directions[0]) and a) or ((not directions[1]) and c) or ((not directions[2]) and b) or ((not directions[3]) and d):
        return x,y
    return new_x,new_y
        


def jeu(laby,position):
    x,y=position
    taille_perso=int(0.5*taille_x)
    while True:
        trace_case(laby,x//taille_x,y//taille_y)
        if x//taille_x > 0 :
            trace_case(laby,x//taille_x - 1,y//taille_y)
        if y//taille_y > 0:
            trace_case(laby,x//taille_x,y//taille_y - 1)
        if x//taille_x - 1 < width :
            trace_case(laby,x//taille_x + 1,y//taille_y)
        if y//taille_y - 1 < height :
            trace_case(laby,x//taille_x,y//taille_y + 1)
        
        dessine_perso(x,y,taille_perso)
        if keydown(KEY_ZERO):
            visitees = recherche_trajet(a, (x//taille_x,y//taille_y), (width-1,height-1),False,0)
            itineraire = chemin(a,visitees,(x//taille_x,y//taille_y), (width-1,height-1),True,0)
        x,y=move_perso(a,x,y,taille_perso)
        time.sleep(0.01)
        if x//taille_x==width-1 and y//taille_y==height-1:
            return True

while True :
    a = 0
    fill_rect(0,0,320,222,(128,128,128))
    draw_string("Génération du labyrinthe",10,100)
    draw_string("Patientez !",10,150)
    a = perfect(a)
    dessine(a)
    trace_case(a,width - 1,height - 1,(128,255,128))

    jeu(a,(int(taille_x*0.2),int(taille_x*0.2)))