Generateur/resolveur de labyrinthe

Télécharger le projet
Commenter

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

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 ^^
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 (cs_Bl0tCh)