dmonde/lib/AEtoile.py

#from __future__ import unicode_literals
# -*- coding: utf-8 -*-
"""algorithme de recherche du plus court chemin entre deux cases"""
from math import *
import time
from threading import Thread

#pour des performances correctes, ne pas utiliser pour de deplacements de plus de 100 cases

        
def distance(coord1, coord2):
    return sqrt((coord1[0] - coord2[0])**2 + (coord1[1] - coord2[1])**2)

def distanceCarree(coord1, coord2):
    """bcp plus rapide a calculer que la distance reelle"""
    return (coord1[0] - coord2[0])**2 + (coord1[1] - coord2[1])**2
       
class N():
    """noeud du chemin"""
    def __init__(self, coord):
        self.parent = None    #coord du noeud qui a amene a ce noeud-ci
        self.coord = coord
        self.kDep = 1
        self.coutG = 0
        self.coutH = 0
        self.cout = 0

    def creer(self, parent, cible, kDep):
        self.parent = parent
        self.kDep = kDep
        self.coutH = distanceCarree(self.coord, cible)
        self.coutG = self.parent.coutG + self.kDep
        self.cout =  (self.coutG)**2 + self.coutH

class Chemin(Thread):
    def __init__(self, plateau, origine, cible):
        self.plateau = plateau
        self.origine = origine
        self.cible = cible
        self.echec = False
        self.stop = False

    def arreter(self):
        self.stop = True

    def liste(self):
        """retourne la liste des coord a traverser pour atteindre l'objectif
           se base sur la fonction estFranchissable() des cases"""
        Thread.__init__(self)
        t0 = time.time()
        nO = N(self.origine)
        nO.parent = None
        nO.coutG = 0
        nO.cout = 0

        filOuvert = []   #"liste ouverte": noeuds etudies et a etudier
        filFerme = [nO]    #"liste fermee":  noeuds retenus
        chemin = []
        position = nO
        echec = False
        
        #on continue jusqu'a tomber sur la case cible, ou jusqu'a un echec
        while position.coord != self.cible and not self.echec:
            
            #on etudie tous les voisins de la case en cours
            for coord in self.plateau.cases[position.coord].voisins:
                if self.stop: return []
                #on elimine les cases deja retenues (celles qui sont dans le fil ferme)
                trouve = False
                for nTest in filFerme:
                    if self.stop: return []
                    if nTest.coord == coord:
                        trouve = True
                if not trouve:
                    
                    #on elimine les cases infranchissables
                    if self.plateau.cases[coord].estFranchissable():
                        noeud = N(coord)
                        
                        #on calcule le cout de la case
                        if self.stop: return []
                        noeud.creer(position, self.cible, self.plateau.cases[coord].coutDep())

                        #si le noeud est trouve dans la liste ouverte, on le compare a celui-ci
                        # si ce nouveau noeud a un cout moindre, on remplace
                        # sinon on ajoute ce noeud a la liste ouverte
                        trouve = False
                        for nTest in filOuvert:
                            if self.stop: return []
                            if nTest.coord == noeud.coord:
                                if noeud.cout < nTest.cout:
                                    nTest.parent = noeud.parent
                                    nTest.cout = noeud.cout
                                    trouve = True
                                    
                        if not trouve:
                            filOuvert.append(noeud)

            #on parcourt les noeuds de la liste ouverte
            #et on cherche le meilleur noeud (le cout le plus faible)
            #si trouve: on l'ajoute a la liste fermee, on le retire de la liste ouverte et on continue
            #sinon, le chemin n'existe pas
            meilleur = None                
                            
            for noeud in filOuvert:
                if self.stop: return []
                if meilleur == None:
                    meilleur = noeud
                else:
                    if noeud.cout < meilleur.cout:
                        meilleur = noeud
                    
            if meilleur:
                filFerme.append(meilleur)
                filOuvert.remove(meilleur)
                position = meilleur
            else:
                echec = True

        #on revient de parent en parent jusqu'a l'arrivee
        if not self.echec:
            while position.coord != self.origine:
                if self.stop: return []
                chemin.insert(0, position.coord)
                position = position.parent
        else:
            chemin = []
        print len(chemin), time.time() - t0
        return chemin   
    
### pour les tests

##class Plateau():
##    def __init__(self):
##        self.cases = {}
##
##class Case():
##    def __init__(self, coord):
##        self.coord = coord
##        self.voisins = []
##        self.majVoisins()
##        
##    def majVoisins(self):
##        voisins = []
##        lst = [(x, y-1), (x+1, y-1), (x+1, y), (x+1, y+1), (x,   y+1), (x-1, y+1), (x-1, y), (x-1, y-1)]
##        for coord in lst: 
##            if (coord[0] > 0 and coord[1] > 0 and coord[0] <= 5 and coord[1] <= 5):
##                self.voisins.append(coord)
##                
##    def estFranchissable(self):
##        return not (self.coord[0]==2 and self.coord[1] in [3, 4])
##
##    def coutDep(self):
##        cout = 1
##        if self.coord in [(3,2), (3,3), (3, 4), (4,3), (4,4)]:
##            cout = 2
##        return cout
##
##    
##plateau = Plateau()
##
##for x in range(1, 6):
##    for y in range(1, 6):
##        plateau.cases[(x, y)] = Case((x, y))
##depart = (1, 2)
##arrivee = (5, 5)
##    
##for essai in range(1,2):
##    t0 = time.time()
##    c = chemin(plateau, depart, arrivee)
##    print (time.time() - t0)
##    print c