Bonjour,

J'essaye d'améliorer le jeu de labyrinthe proposé sur le cours de Pygame d'OC. Je trouvais dommage d'avoir à créer moi-même les maps alors que des algorithmes existent pour en générer automatiquement !

J'ai donc parcouru certains threads du forum + d'autres sources, et je me suis arrêté sur l'algorithme du Recursive Backtracking.

Je fais appel à vous pour savoir si mon implémentation en python est bonne. J'ai découpé mon code en deux entités (pour le moment, je me concentre uniquement sur la génération du labyrinthe : la gestion des personnages / ennemis / bonus viendra après), le "niveau", et les "cellules". En voici les codes :

Niveau :

# -*- coding: utf-8 -*-
import os
import pygame
from entities.banana import *
from entities.wall import *
from entities.empty import *
from entities.perso import *
from entities.start import *
from entities.ennemy import *
from entities.cell import *
from pygame.locals import *
from random import *
from constantes import background, wall, banana, start

class Level_new():
	"""Classe définissant un Labyrinthe généré automatiquement
	grâce à l'algorithme du recursive backtracking. 
	"""
	step = 32
	def __init__(self, size): #constructeur d'exercice : numéro de niveau
		self.tuple_level = []
		self.size = size
		y = 0
		while (y < self.size):
			x=0
			while (x < self.size):
				self.tuple_level.append(Cell(x,y))
				x = x + 1
			y = y + 1

	def go_in_cell_arround(self, current_cell, cells_around):
		if not cells_around: #Si pas de cells autour
			return current_cell #On reste sur la cell courante
		for cell in cells_around:
			next_cell = choice(cells_around)
		if (next_cell.x_pos == current_cell.x_pos + 1):
			current_cell.remove_wall('left', next_cell) #on pète les murs de gauche de la cellule + celui de droite de la prochaine
		elif (next_cell.x_pos == current_cell.x_pos -1):
			current_cell.remove_wall('right', next_cell) # idem
		elif (next_cell.y_pos == current_cell.y_pos +1):
			current_cell.remove_wall('down', next_cell) # idem bas et haut
		else:
			current_cell.remove_wall('up', next_cell) # idem haut et bas

		next_cell.visited = True # on s'assure que la prochaine cellule soit marquée visitée
		return next_cell

	def visit_cells(self):
		
		starting_cell = self.tuple_level[3]#choice(self.tuple_level) # on choisit une cell pour commencer le laby
		starting_cell.visited = True # on la rend visitée
		path_visited = [starting_cell]
		current_cell = starting_cell
		current_index = self.tuple_level.index(current_cell)
		print (path_visited)
		while path_visited: # tant qu'on n'est pas revenu au point de départ
			cells_around = []
			if (current_cell.x_pos == 0 and current_cell.y_pos == 0): # pour en haut à gauche,  cases à côté = en à droite et en dessous
				print ('cellule en haut à gauche')
				cells_around = [self.tuple_level[current_index +1], self.tuple_level[current_index + self.size]]
			elif (current_cell.x_pos == self.size -1 and current_cell.y_pos == self.size -1): # pour en bas à droite, à gauche et en haut
				cells_around = [self.tuple_level[current_index - 1], self.tuple_level[current_index -self.size]]
			elif (current_cell.x_pos == 0 and current_cell.y_pos == self.size -1): # pour en bas à gauche
				cells_around == [self.tuple_level[current_index + 1], self.tuple_level[current_index -self.size]]
			elif (current_cell.y_pos == 0 and current_cell.x_pos == self.size -1): # pour en haut à droite
				print ('cellule en haut à droite')
				cells_around = [self.tuple_level[current_index -1], self.tuple_level[current_index +self.size]]
			elif (current_cell.x_pos == 0): # pour les murs de gauche
				cells_around = [self.tuple_level[current_index +1], self.tuple_level[current_index + self.size], self.tuple_level[current_index - self.size]]
			elif (current_cell.x_pos == self.size -1): # pour les murs de droite
				cells_around = [self.tuple_level[current_index -1], self.tuple_level[current_index + self.size], self.tuple_level[current_index - self.size]]
			elif (current_cell.y_pos == 0): # pour les murs d'en haut
				cells_around = [self.tuple_level[current_index -1], self.tuple_level[current_index + 1], self.tuple_level[current_index + self.size]]
			elif (current_cell.y_pos == self.size -1): # pour les murs d'en bas
				cells_around = [self.tuple_level[current_index -1], self.tuple_level[current_index + 1], self.tuple_level[current_index - self.size]]
			else:
				print ('au milieu')
				cells_around = [self.tuple_level[current_index -1], self.tuple_level[current_index +1], self.tuple_level[current_index + self.size], self.tuple_level[current_index - self.size]]
			print ('current cell : X {}, Y {}'.format(current_cell.x_pos, current_cell.y_pos))
				
			for i, cell in enumerate(cells_around):
				print ('position des cells à côté : X {}, y {} (num {} dans la liste). Visitée : {}'.format(cell.x_pos, cell.y_pos, i, cell.visited))
				if (cell.visited == True): # si les cells autour ont déjà été visitées
					cells_around.remove(cell) # on les supprime de la liste
			next_cell = self.go_in_cell_arround(current_cell, cells_around) # on se déplace jusqu'à la prochaine cell qui devient la cell courante
			next_index = self.tuple_level.index(next_cell)  #on modifie l'index de la cell courante
			if path_visited[-1] == next_cell: # Si on est resté sur la même cell (pas de cells autour)
				path_visited.pop() # On supprime cette cell du chemin
				current_cell = path_visited[-1] # on prend la précédente cell en tant que cell courante
				current_index = self.tuple_level.index(current_cell) #on modifie l'index
			else: #si on a bien changé de cell
				current_cell = next_cell #on prend la prochaine cell en tant que cell courante
				current_index = next_index #et on modifie l'index
				print ('nous sommes maintenant en X {}, Y {}'.format(current_cell.x_pos, current_cell.y_pos))
		return self.tuple_level

La cellule :

# -*- coding: utf-8 -*-
import os
import pygame
from entities.entity import *
from pygame.locals import *
from constantes import *

class Cell(Entity):
	"""Classe définissant une banane
	"""

	step = 32

	def __init__(self, x_pos, y_pos): #constructeur de wall
		Entity.__init__(self)
		self.solid = False
		self.wall_up = True
		self.wall_down = True
		self.wall_left = True
		self.wall_right = True
		self.visited = False


	def remove_wall(direction, opposite_cell)
		if direction == 'up':
			self.wall_up = False
			opposite_cell.wall_down = False
		elif direction == 'down':
			self.wall_down = False
			opposite_cell.wall_up = False
		elif direction == 'left':
			self.wall_left = False
			opposite_cell.wall_right = False
		elif direction == 'right':
			self.wall_right = False
			opposite_cell.wall_left = False
		return self

J'ai donc un level qui contient un tableau de cells. Chaque cell a 7 attributs : la présence d'un mur en haut, bas, gauche ou droite, un statut (visitée ou non) et une position X et Y.

Pour la création du labyrinthe (méthode visit_cells()) :

• Je pars du principe que tous les murs sont fermés.
• Je choisis une cellule au hasard
• Je change son statut à "visité"
• j'ajoute cette cellule au "chemin parcouru"
• Tant que le "chemin parcouru" n'est pas vide :
• je détermine quelles sont les cellules autour d'elle (en faisant attention aux bordures du niveau)
• Je supprime de la liste des cellules alentour celles qui ont déjà été visitées
• J'essaye de visiter une des cellules restantes
• Si il n'y en a pas, je reste sur la cellule en cours ; je la supprime du chemin parcouru, et je recule d'une case
• Si on a bien changé de cellule, la nouvelle cellule devient la cellule courante.

Que pensez-vous de l'algorithme ? Y-a-t-il des choses à modifier dans celui-ci ?

Il y a très probablement des erreurs de syntaxe liées au fonctionnement des classes (avec self) que j'essayerai de corriger par moi-même.

Merci

EDIT : une des choses qui me gêne personnellement, c'est qu'une cellule puisse détruire le mur d'une cellule adjacente : comment faire autrement ?

EDIT 2 : correction de certaines erreur de syntaxe dans la méthode  visit_cells. J'ai un problème, ma méthode s'exécute bien, mais je finis par faire une boucle infinie et je navigue entre deux cellules en permanence ... Une idée ?

EDIT 3 : après débug, j'ai réussi à obtenir un script qui me génère effectivement des labyrinthes "parfaits". Je reste ouvert à d'éventuelles remarques concernant la syntaxe ! (cf. fichiers modifiés par le dernier commit sur mon repo github).

-
Edité par ftassy 4 janvier 2017 à 16:25:24