GENERATEUR/RESOLVEUR DE LABYRINTHE

####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()

Télécharger le zip

05 novembre 2005 13:29:37 :

Implementation de lalgo de dijkstra grace à l'article de wikipedia