Generateur/resolveur de labyrinthe
Soyez le premier à donner votre avis sur cette source.
Vue 20 928 fois - Téléchargée 1 531 fois
Description
Un simple generateur aleatoire de labyrinthe qui sait aussi trouver la sortie ^^.
Ce code est utile pour plusieurs choses :
-il est orienté objet
-Introduction à la recursivité
-Utilisation de la serialisation
Pis voila koi
Ameliorations à faires:
-En 3 dimensions (plusieurs etages)
-Utilisation de lalgo de drijska pour trouver le chemin le plus cour paske là il cherche un chemin mais il essaie pas qu'il soit le plus cour possible ^^ --> Fait aujourd'hui
-Possibilité de naviguer dedans (surement avec OpenGL)
Enjoy
Hop, normalement aucun bug meme si ça doit etre possible qu'il y en ai ^^
Ce code est utile pour plusieurs choses :
-il est orienté objet
-Introduction à la recursivité
-Utilisation de la serialisation
Pis voila koi
Ameliorations à faires:
-En 3 dimensions (plusieurs etages)
-Utilisation de lalgo de drijska pour trouver le chemin le plus cour paske là il cherche un chemin mais il essaie pas qu'il soit le plus cour possible ^^ --> Fait aujourd'hui
-Possibilité de naviguer dedans (surement avec OpenGL)
Enjoy
Source / Exemple :
####MakeLaby.py####
from random import *
import marshal, sys, wx, afficheur, Arbre
class LabyMakerError(Exception):
pass
class LabyMaker:
"""Classe generant et resolvant des labyrinthe simple
Ameliorations possibles :
3 Dimensions (plusieurs etages)
"""
def __init__(self, new=0, h=None, w=None, ilots=None):
"""instancie la classe et cree un labyrinthe
"""
self.load=0
if(new!=0): self.new(h, w, ilots)
def __isConstructible(self, i, j):
"""Intern
Di si une case est constructible ou non
"""
if(self.laby[i][j]=='MUR') : return -1
try:
if (( self.laby[i][j+1] =='MUR' and self.laby[i-1][j] !='MUR' and self.laby[i-1][j-1] !='MUR' and self.laby[i][j-1] !='MUR' and self.laby[i+1][j-1] !='MUR' and self.laby[i+1][j] !='MUR') or
( self.laby[i-1][j] =='MUR' and self.laby[i][j-1] !='MUR' and self.laby[i+1][j-1] !='MUR' and self.laby[i+1][j] !='MUR' and self.laby[i+1][j+1] !='MUR' and self.laby[i][j+1] !='MUR') or
( self.laby[i][j-1] =='MUR' and self.laby[i+1][j] !='MUR' and self.laby[i+1][j+1] !='MUR' and self.laby[i][j+1] !='MUR' and self.laby[i-1][j+1] !='MUR' and self.laby[i-1][j] !='MUR') or
( self.laby[i+1][j] =='MUR' and self.laby[i][j+1] !='MUR' and self.laby[i-1][j+1] !='MUR' and self.laby[i-1][j] !='MUR' and self.laby[i-1][j-1] !='MUR' and self.laby[i][j-1] !='MUR')):
return 1
else:
return -1
except:
return -1
def __makeConstrTab(self):
"""Intern
fabrique un tableau de cas constructible
"""
constrTab=[]
for x in range(self.size[0]):
for y in range(self.size[1]):
if(self.__isConstructible(x,y)==1) : constrTab.append((x,y))
return constrTab
def _ecart(self, p1, p2):
if(p2>p1) : return p2-p1
if(p1>p2) : return p1-p2
return 0
def new(self, h, w, ilots=None):
"""fabrique le labyrinthe
"""
if(h<=2 or w<=2) : raise LabyMakerError, 'taille invalide'
self.laby=[]
self.size=(h,w)
Entree=randint(1,self.size[1]-2)
Sortie=randint(1,self.size[1]-2)
for x in range(self.size[0]):
a=[]
for y in range(self.size[1]):
mur=0
entree=0
sortie=0
if(x==0 or x==self.size[0]-1) : mur=1
elif(y==0 or y==self.size[1]-1) : mur=1
if(x==0 and y==Entree) : mur=0; entree=1
elif (x==self.size[0]-1 and y==Sortie) : mur=0; sortie=1
if(mur==1) : a.append('MUR')
elif(entree==1) : a.append('ENTR')
elif(sortie==1) :
a.append('SORT')
else :
a.append('VIDE')
self.laby.append(a)
n=ilots
if(n==None) : n=randint(1, int((self.size[0]+self.size[1])/2))
dejax=[]
dejay=[]
for i in range(n):
while 1:
x=randint(0,self.size[0]-1)
if x not in dejax : break
while 1:
y=randint(0,self.size[1]-1)
if y not in dejay : break
self.laby[x][y]='MUR'
constrTab=self.__makeConstrTab()
while len(constrTab)>0:
coord=choice(constrTab)
constrTab.remove(coord)
x,y=coord[0], coord[1]
self.laby[x][y]='MUR'
for i in range(x-1, x+2):
for j in range(y-1, y+2):
if(i==x and j==y) : continue
if(self.__isConstructible(i,j)==1 and (i,j) not in constrTab) : constrTab.append((i,j))
elif((i,j) in constrTab and self.__isConstructible(i,j)==-1) : constrTab.remove((i,j))
#CONSTRUCTION de l'arbre
self.arbre=Arbre.ArbreGraphe(-1, -1, -1)
self.nodeListe=[self.arbre]
for x in range(self.size[0]):
for y in range(self.size[1]):
if(self.laby[x][y]=='ENTR') : self.arbre.setInfos(0, -1, (x, y))
elif(self.laby[x][y]!='MUR') :
Node=Arbre.Noeud(-1, -1, (x, y))
if(self.laby[x][y]=='SORT') : self.fin=Node
self.nodeListe.append(Node)
for node in self.nodeListe:
coord=node.getCoord()
i, j=coord[0], coord[1]
if(i!=x and j!=y) : continue
if(i==x and self._ecart(j, y)!=1) : continue
if(j==y and self._ecart(i, x)!=1) : continue
node.addNode(Node)
self.load=1
def Output(self, res=None, wximg=0):
"""Simple affichage en mode texte
"""
if(self.load==0) : raise LabyMakerError, 'aucun labyrinthe en cours'
output=''
if(wximg!=0): image=wx.EmptyImage(self.size[0]*8, self.size[1]*8, True)
for x in range(self.size[0]):
for y in range(self.size[1]):
type=self.laby[x][y]
if(type=='MUR'):
if(wximg!=0) :
for i in range(x*8, x*8+8):
for j in range(y*8, y*8+8):
image.SetRGB(i,j,0,0,0)
output+='#'
elif(type=='VIDE' or type=='ENTR' or type=='SORT'):
if(res!=None):
if((x,y) in res or x==0) :
if(wximg!=0) :
for i in range(x*8, x*8+8):
for j in range(y*8, y*8+8):
no=0
## try:
## if(i>=x*8+7):
## if(self.laby[x+1][y]=='MUR'):
## no=1
## image.SetRGB(i,j,255,255,255)
## elif(i<=x*8+1):
## if(self.laby[x-1][y]=='MUR'):
## no=1
## image.SetRGB(i,j,255,255,255)
## elif(j<=j*8+1):
## if(self.laby[x][y-1]=='MUR'):
## no=1
## image.SetRGB(i,j,255,255,255)
## elif(j<=j*8+7):
## if(self.laby[x][y+1]=='MUR'):
## no=1
## image.SetRGB(i,j,255,255,255)
## except:
## pass
if(no==0) : image.SetRGB(i,j,255,0,0)
output+='+'
else:
if(wximg!=0) :
for i in range(x*8, x*8+8):
for j in range(y*8, y*8+8):
image.SetRGB(i,j,255,255,255)
output+=' '
else:
if(wximg!=0) :
for i in range(x*8, x*8+8):
for j in range(y, y*8+8):
image.SetRGB(i,j,255,255,255)
output+=' '
else :
if(wximg!=0) :
for i in range(x*8, x*8+8):
for j in range(y*8, y*8+8):
print i,j
image.SetRGB(i,j,255,255,255)
output+=' '
output+='\n'
if(wximg==0): print output
else : return image
def save(self, path='laby.lm'):
"""sauvegarde le fichier pour un chargement futur
"""
if(self.load==0) : raise LabyMakerError, 'aucun labyrinthe en cours'
try:
marshal.dump([self.laby, self.size], open(path, 'wb'))
except:
raise LabyMakerError, sys.exc_info()[1]
def open(self, path):
"""charge un fichier labyrinthe
"""
try:
dec=marshal.load(open(path, 'rb'))
self.laby=dec[0]
self.size=dec[1]
self.load=1
except:
raise LabyMakerError, sys.exc_info()[1]
def ResolveLaby(self):
"""resoud le labyrinthe
ameliorations :
faire en sorte de trouver le chemin le moins long --> drijska
"""
return self.go2() #version dijkstra
def go(self, case, option=[], notgo=[], chemin=[], res=None):
"""algo recursif pour trouver la sortie
ya des trucs qui servent a rien style option ^^
"""
x,y=case[0], case[1]
for i in range(x-1, x+2):
for j in range(y-1, y+2):
if(i!=x and j!=y) : continue
if((i==x and j==y) or
(j<0 or x<0 or x>self.size[0]-1 or j>self.size[1]-1)
) : continue
if(type(i)!=type(0)) : i=i[0]
try:
if(self.laby[i][j]=='VIDE' and (i,j) not in notgo) :
notgo.append((i,j))
option.append([(i,j), []])
chemin.append((i,j))
res=self.go((i,j), option[-1][1], notgo, [i for i in chemin])
if(res!=None) : return res
del(chemin[-1])
elif(self.laby[i][j]=='SORT'):
chemin.append((i,j))
return chemin
except:
print i, j
time.sleep(10)
return res
def _mini_(self):
mini=-1
out=None
for noeud in self.nodeListe:
if((noeud.getValeur()<mini and noeud.getValeur()!=-1) or mini==-1) : mini=noeud.getValeur(); out=noeud
return out
def go2(self):
#algo de dijkstra
vu=[]
while len(self.nodeListe)!=0:
n1=self._mini_()
vu.append(n1)
self.nodeListe.remove(n1)
for n2 in n1.getFils():
if(n2.getValeur()>n1.getValeur()+1 or n2.getValeur()==-1):
n2.setInfos(n1.getValeur()+1, n1, n2.getCoord())
debut=self.arbre
n=self.fin
chemin=[]
while n!=debut:
chemin.insert(0, (n.getCoord()[0], n.getCoord()[1]))
n=n.getPrecedent()
return chemin
lab=LabyMaker(1, 40, 40, 20)
app = wx.PySimpleApp(0)
wx.InitAllImageHandlers()
frame_1 = afficheur.Afficheur(None, -1, "")
app.SetTopWindow(frame_1)
frame_1.SetBitmap(wx.BitmapFromImage(lab.Output(lab.ResolveLaby(), 1))) #affichage sous forme d'image
#print lab.Output(lab.ResolveLaby())
frame_1.Show()
app.MainLoop()
##Arbre.py##
class Noeud:
def __init__(self, valeur, precedent, coord):
self.valeur=valeur
self.precedent=precedent
self.fils=[]
self.coord=coord
def getFils(self):
return self.fils
def addNode(self, node):
if node not in self.fils :
self.fils.append(node)
node.addNode(self)
def delNode(self, node):
try:
self.fils.remove(node)
except:
pass
def delNodeByCoord(self, coord):
i=0
while i<len(self.fils):
node=self.fils[i]
if(node.getCoord()==coord) : del(self.fils[i]); break
i+=1
def getCoord(self):
return self.coord
def getValeur(self):
return self.valeur
def getPrecedent(self):
return self.precedent
def setInfos(self, valeur, precedent, coord):
self.valeur=valeur
self.precedent=precedent
self.coord=coord
class ArbreGraphe(Noeud):
def __init__(self, valeur, precedent, coord):
"""initialisation. Racine est un noeud qui sert de point d'entree
ds l'arbre """
Noeud.__init__(self, valeur, precedent, coord)
###afficheur.py###
#!/usr/bin/env python
# -*- coding: ISO-8859-1 -*-
# generated by wxGlade 0.3.5.1 on Sat Sep 17 16:58:07 2005
import wx
class Afficheur(wx.Frame):
def __init__(self, *args, **kwds):
# begin wxGlade: MyFrame.__init__
kwds["style"] = wx.DEFAULT_FRAME_STYLE
wx.Frame.__init__(self, *args, **kwds)
#self.bitmap_1 = wx.StaticBitmap(self, -1, wx.Bitmap("C:\\Documents and Settings\\Home\\Mes documents\\Mes images\\rotationnage.bmp", wx.BITMAP_TYPE_ANY))
self.__set_properties()
# end wxGlade
def SetBitmap(self, bmp):
self.bitmap_1=wx.StaticBitmap(self, -1, bmp)
self.__do_layout()
def __set_properties(self):
# begin wxGlade: MyFrame.__set_properties
self.SetTitle("Genrateur/resolveur de bitmap")
# end wxGlade
def __do_layout(self):
# begin wxGlade: MyFrame.__do_layout
sizer_1 = wx.BoxSizer(wx.VERTICAL)
sizer_1.Add(self.bitmap_1, 0, wx.FIXED_MINSIZE, 0)
self.SetAutoLayout(True)
self.SetSizer(sizer_1)
sizer_1.Fit(self)
sizer_1.SetSizeHints(self)
self.Layout()
# end wxGlade
# end of class MyFrame
if __name__ == "__main__":
app = wx.PySimpleApp(0)
wx.InitAllImageHandlers()
frame_1 = MyFrame(None, -1, "")
app.SetTopWindow(frame_1)
frame_1.Show()
app.MainLoop()
Conclusion :
Hop, normalement aucun bug meme si ça doit etre possible qu'il y en ai ^^
Codes Sources
A voir également
- Generateur/resolveur de labyrinthe
- Générateur de labyrinthe - Forum C
- Générateur de nombre ✓ - Forum PHP
- Générateur de pseudo - Forum C
- Generateur de facture ✓ - Forum PHP
- Générateur de lettre ✓ - Forum VB.NET
22 mai 2019 à 22:02
Merci pour le code. Je me suis surtout servi de la partie création de labyrinthe, justement pour des exercices avec des étudiants sur la recherche de chemin dans un labyrinthe.
Le code fonctionne avec de toutes petites modifications en python3. Quelques remarques:
o j'ai amélioré la rapidité de création du labyrinthe de manière drastique en transformant constrTab en set plutôt qu'en liste.
o Le code gagne également en performance en utilisant plutôt des entiers plutôt que des chaînes de caractères pour caractériser les cases:
VIDE=0
MUR=1
ENTR=2
SORT=3
Puis après, on peut dire: self.laby[i][j]==MUR.
Bien cordialement,
11 nov. 2005 à 00:20
Dans le genre "labyrinthe", j'ai trouvé chez EYROLLES un livre de Sean Riley :"Game Programming with Python".
Moyennant l'installation de:
Pygame,PyOpenGL,PyUI,Twisted,Hoop Library
(c'est un peu compliqué, mais ça marche...),
le CD-ROM joint avec le livre donne accès au domaine de l'intelligence artificielle, avec pour exemple le tracé du plus court chemin dans un labyrinthe que l'on peut construire en entrée de jeu.
Pour info.
Bonne continuation !
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.