begin process at 2010 09 04 11:35:55
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Divers

 > GENERATEUR/RESOLVEUR DE LABYRINTHE

GENERATEUR/RESOLVEUR DE LABYRINTHE


 Information sur la source

Note :
9,6 / 10 - par 5 personnes
9,60 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Divers Classé sous :solution, générateur, labyrinthe, solveur, resolveur Niveau :Débutant Date de création :17/09/2005 Date de mise à jour :05/11/2005 13:29:37 Vu / téléchargé :5 709 / 284

Auteur : Bl0tCh

Ecrire un message privé
Commentaire sur cette source (1)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
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

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

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

05 novembre 2005 13:29:37 :
Implementation de lalgo de dijkstra grace à l'article de wikipedia

 Sources du même auteur

Source avec Zip Source avec une capture STEGANOGRAPHIE SUR BITMAP 24 BITS
Source avec Zip COMPRESSION PAR LA METHODE DE HUFFMAN
Source avec Zip PARSEUR/LECTEUR DE FICHIER BITMAP
BINDSHELL BASIQUE
Source avec Zip Source avec une capture BATAILLE NAVALE EN LOCAL OU EN RESEAU :D

 Sources de la même categorie

Source avec Zip SCRIPT PERMETTANT DE DÉCODER LA STRUCTURE SECONDAIRE D'UNE P... par Basilio
SUPPRESSION par Rano Its
Source avec Zip RECONNAISSANCE VOCALE par brennal
CONVERTISSEUR DE TEMPÉRATURE par skizo00o
Source avec Zip Source avec une capture I.A. (DÉBUTANT) par Rano Its

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture GÉNÉRATEUR DE PASSWORD par PlugnPlay666
Source avec Zip FIBONACCI ITÉRATIF ET RÉCURSIF par djackows
Source avec Zip Source avec une capture GÉNÉRATEUR DE MOTS ALÉATOIRES par lomar et lomar
Source avec Zip Source avec une capture ALBUMEUR PHOTO: SCRIPT DE CRÉATION D'ALBUM PHOTO EN HTML À P... par vychnou
GÉNÉRATEUR DE MOT DE PASSE par neoboy_84

Commentaires et avis

Commentaire de HCD le 11/11/2005 00:20:48

Plutôt impressionnant pour un débutant !
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 !

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Solveur Sudoku ? [ par Rehodi ] Boujour, j'ai un projet a rendre Mercredi etle sujet est de créer un solveur de sudoku en python avec un grille donné et non aléatoire, cette grille d L'échelle verticale de Tkinter est positive de haut en bas ! Ça s'inverse ? [ par reveurduciel ] Bonjour Je suis en train de faire de petits module avec python pour illustrer une foule de problèmes physique et j'ai un problème. En effet, tkinter u


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Septembre 2010
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
27282930   

Consulter la suite du CalendriCode

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,014 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales