Génération d'un labyrinthe avec recherche du chemin le plus court avec astar

Télécharger le projet
Commenter

Description

ce programme permet de:

- générer un labyrinthe aléatoire
- utilisation de l'algorithme astar pour trouver le chemin le plus court (même si dans le cas du labyrinthe parfait il y a un seul chemin possible l'algorithme utilisé trouve le meilleur chemin possible)
La sélection de la destination est faite avec le souris

Dépendances : pygame

Source / Exemple : 


# -*- coding: utf8 -*-
"""
Laby , par Mehdi Cherti 2010 (mehdidc): 
	- generation d'un labyrinthe
	- utilisation de l'algorithme astar pour trouver le chemin le plus court (selection de la destination avec la souris)
"""
from  random import randint , choice
import pygame
from pygame.locals import *
import def_const
from math import sqrt

const = def_const.def_const ()
""" definitions des constantes """

# Couleurs
const.white  = (255 , 255 , 255)
const.pink   = (255 , 0 , 255)
const.black  = (0 , 0 , 0)
const.yellow = (255 , 255 , 0)

#directions 
const.right = 0
const.left = 1
const.up = 2
const.down = 3

# autres

const.wc = 20 # width d'un seul carreau du laby
const.hc = 20# height d'un seul carreau du laby

const.perso_radius = const.wc/2 # rayon du personnage (qui est un cercle)
const.time_perso = 50 # temps en ms avant chaque test du clavier pour les touches qui concernent le perso
const.time_perso_poll = 50 # temps en ms avant chaque mise a jour de la position du perso
""" fin definitions des constantes"""

class Point:
	def __init__ (self,xy):
		self.x = xy[0]
		self.y = xy[1]

""" Definition de la classe cellule de labyrinthe"""
class cellule:
	def __init__(self):
		self.state = False
		self.portes = [True , True , True , True] # Droite , Gauche , Haut , Bas
		
""" distance : retourne la distance euclidienne entre deux points """
def distance (p1 , p2):
	return sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

""" classe Personnage """
class Perso:
	def __init__ (self,lab):
		self.x = 1
		self.y = 1
		self.chemin =None
		self.laby = lab
		self.color = const.yellow
	""" affichage """	
	def show(self,buffer):
		a,b = const.perso_radius , const.perso_radius
		pygame.draw.circle (buffer, self.color , (a+self.laby.sx+self.x*self.laby.wc,b+self.laby.sy+self.y*self.laby.hc) , 
		const.perso_radius)
		
	""" mouvement selon la direction"""
	def move (self,dir):
			
		if not self.laby.get_cell (self.x , self.y).portes[dir]:
			if dir == const.right and self.x+1 < self.laby.w :
				self.x += 1
			if dir == const.left and self.x-1 >=0:
				self.x -= 1
			if dir == const.up and self.y-1 >=0:
				self.y -= 1
			if dir == const.down and self.y+1 < self.laby.h:
				self.y += 1
				
	""" fonction utilisée par astar pour traiter une des cases adjacentes"""
	def traitement (self ,  liste_fermee , liste_ouverte , x ,  y , dir ,parent ,dest):
		if parent.portes[dir] : return
		c = self.laby.get_cell (x,y)
		if c in liste_fermee : return
		
		if c in liste_ouverte:
			G = distance ( (x,y) , (parent.x , parent.y))
			c.dir = self.laby.notdir (dir)
			if G < c.G:
				c.G = G
				c.F = c.H + c.G
				c.parent = parent
		else:
			c.parent = parent
			c.dir = self.laby.notdir (dir)
			c.G = distance ( (x,y) , (parent.x , parent.y))
			c.H = distance ( (x,y) , (dest.x ,dest.y))
			c.F = c.G + c.H
			liste_ouverte.append (c)
	""" retourne , après avoir trouvé le chemin avec astar , un tableau contenant le chemin"""
	def  get_astar (self, csource , cdest):
		
		source = self.laby.get_cell (csource[0] , csource[1])
		dest = self.laby.get_cell (cdest[0] , cdest[1])
		cur=dest
		chemin = []
		while cur and (cur.x != source.x or cur.y != source.y):
			if cur.x == cur.parent.x-1 :
				chemin.append (const.right)
			if cur.x == cur.parent.x+1:
				chemin.append (const.left)
			if cur.y == cur.parent.y+1:
				chemin.append (const.up)
			if cur.y == cur.parent.y-1:
				chemin.append (const.down)
			cur = cur.parent
		
		ret = []
		id = len(chemin) - 1
		while id>=0:
			ret.append (self.laby.notdir(chemin[id]))
			id-=1
		return ret
		
	""" mise a jour de la position du personnage """
	def poll(self):
		if self.chemin:
			self.move (self.chemin.pop (0))
			
	""" permet de se deplacer selon le chemin """
	def aller(self,chemin):
		self.chemin = chemin
			
	"""
	algorithme de pathfinding Astar , desti represente le tuple de la destination
	"""
	def astar (self , desti):
		dest = Point(desti)
		liste_ouverte = []
		liste_fermee = []

		debut = self.laby.get_cell (self.x , self.y)
		liste_ouverte.append (debut)
		debut.F = distance ((self.x,self.y) , (dest.x,dest.y))
		debut.G = 0
		debut.H = debut.F
		debut.parent = None
		
		
		while 1:
			if len(liste_ouverte) <= 0 : 
				break
			min , min_id= liste_ouverte[0].F,0
					
			for id,v in enumerate(liste_ouverte[1:]):
				if v < min :
					min = v
					min_id = id +1
			liste_fermee.append (liste_ouverte[min_id])
			
			if liste_ouverte[min_id].x == dest.x and liste_ouverte[min_id].y == dest.y : break
			
			self.traitement (liste_fermee,liste_ouverte,liste_ouverte[min_id].x +  1 , liste_ouverte[min_id].y , const.right , liste_ouverte[min_id] , dest)
			self.traitement (liste_fermee,liste_ouverte,liste_ouverte[min_id].x -  1 , liste_ouverte[min_id].y , const.left , liste_ouverte[min_id] , dest)
			self.traitement (liste_fermee,liste_ouverte,liste_ouverte[min_id].x  , liste_ouverte[min_id].y-1 , const.up , liste_ouverte[min_id] , dest)
			self.traitement (liste_fermee,liste_ouverte,liste_ouverte[min_id].x  , liste_ouverte[min_id].y+1 , const.down , liste_ouverte[min_id] , dest)
			liste_ouverte.remove (liste_ouverte[min_id])

""" classe du labyrinthe """
class laby:
	def __init__ (self,w,h,sx=0,sy=0):
		self.w = w
		self.h = h
		self.cellules = []
		self.wc = const.wc
		self.hc = const.hc
		self.sx = sx
		self.sy = sy
		""" initialisation des cellules , pour chaque cellule , il initialise sa position dans le labyrinthe """
		for v in range(self.w*self.h):
			a = cellule()
			a.x = v % self.w
			a.y = v / self.w
			self.cellules.append (a)
	""" retourne la cellule correspondante à la position (x,y) """
	def get_cell (self,x,y):
		return self.cellules[x +  y * self.w]
	""" retourne direction de sens contraire d'une direction """
	def notdir(self,dir):
		if dir == const.right : return const.left
		if dir == const.left : return const.right
		if dir == const.up : return const.down
		if dir == const.down : return const.up
		
	""" generation du labyrinthe """
	def generate_laby (self,x=-1,y=-1):
		if x==-1:
			x = randint(0,self.w-1)
			y = randint(0,self.h-1)
		cell_act = self.get_cell (x,y)
		
		if not cell_act.state :
			cell_act.state = True
			tab = []
			if x+1<self.w and not self.get_cell(x+1,y).state : tab.append((x+1,y,const.right))
			if x-1>=0  and not self.get_cell(x-1,y).state    : tab.append((x-1,y,const.left))
			if y-1>=0  and not self.get_cell(x,y-1).state   : tab.append((x  ,y-1,const.up))
			if y+1<self.h and not self.get_cell(x,y+1).state : tab.append((x  ,y+1,const.down))
			if tab:
				
				while tab:
					C = choice (tab)
					if not self.get_cell(C[0] , C[1]).state:
						
						cell = self.get_cell (C[0] , C[1])
						cell_act.portes[C[2]] = False
						cell.portes[self.notdir(C[2])] = False
						self.generate_laby (C[0] , C[1])
					tab.remove (C)
				return True
			else : 
				return False
		
	""" affiche le labyrinthe """
	def show(self,buffer):
		W,H = self.wc , self.hc
		sx,sy = self.sx , self.sy
		for y in range(self.h-1):
			for x in range(self.w-1):
				c = self.get_cell (x,y)
				if c.portes[const.right] :
					pygame.draw.line (buffer , const.white , (sx+(x+1)*W,sy+y*H),(sx+(x+1)*W,sy+(y+1)*H))
				if c.portes[const.down] :
					pygame.draw.line (buffer , const.white , (sx+(x)*W,sy+(y+1)*H),(sx+(x+1)*W,sy+(y+1)*H))

		x = self.w - 1

		for y in range(self.h-1):
			c = self.get_cell (x , y)
			if c.portes[const.down]:
				pygame.draw.line (buffer , const.white , (sx+x*W,sy+(y+1)*H),(sx+(x+1)*W,sy+(y+1)*H) )

		y = self.h - 1
		for x in range(self.w-1):
			c = self.get_cell (x , y)
			if c.portes[const.right]:
				pygame.draw.line (buffer , const.white , (sx+(x+1)*W,sy+(y)*H),(sx+(x+1)*W,sy+(y+1)*H) )
		pygame.draw.rect (buffer , const.pink , (sx , sy , W * self.w , H * self.h),2)
		

if __name__ == "__main__":
	
	mylaby = laby(20,20) # création d'un labyrinthe de 20x20 cellules
	pygame.init ()
	pygame.display.set_mode ( (640,480))
	screen = pygame.display.get_surface ()
	
	mylaby.generate_laby() # géneration aléatoire du labyrinthe

	perso = Perso (mylaby)
	keys = None
	move_time = 0
	perso_time = 0

	while True:
		screen.fill (const.black)
		events = pygame.event.get ()
		
		for event in events:
		
			""" click de la souris """
			if event.type == MOUSEBUTTONDOWN:
				mx , my = pygame.mouse.get_pos ()
				x = (mx - mylaby.sx) / mylaby.wc
				y = (my - mylaby.sy) / mylaby.hc
				if x>=0 and y>=0 and x < mylaby.w and y < mylaby.h:
					perso.astar ((x,y)) # trouve le chemin avec astar
					chemin = perso.get_astar ((perso.x,perso.y) , (x,y)) # reçoit le chemin en tableau qui donne les directions à prendre sequentiellement
					perso.aller (chemin) # ordonne au personnage d'aller au chemin sans arrêter la boucle principale
					
		keys = pygame.key.get_pressed ()
		
		""" Mouvement du personnage """
		if pygame.time.get_ticks () - move_time >= const.time_perso:
			move_time = pygame.time.get_ticks ()	
			if keys[pygame.K_RIGHT]:
				perso.move (const.right)
			if keys[pygame.K_LEFT]:
				perso.move (const.left)
			if keys[pygame.K_UP]:
				perso.move (const.up)
			if keys[pygame.K_DOWN]:
				perso.move (const.down)
			
		if keys[pygame.K_ESCAPE] :
			break
			
		""" mise a jour de la position du personnage """
		if pygame.time.get_ticks () - perso_time >= const.time_perso_poll:
			perso_time = pygame.time.get_ticks ()
			perso.poll ()
			
		""" affichage """
		mylaby.show (screen)
		perso.show (screen)
		pygame.display.flip ()
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (mehdicherti)