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 sqrt
# import time
# from PyQt4.QtGui import QApplication
#pour des performances correctes, ne pas utiliser pour des 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 + self.coutH

class Chemin():
    def __init__(self, plateau, origine, cible, z1 = 0, z2 = 0):
        self.plateau = plateau
        self.origine = origine
        self.cible = cible
        self.echec = False
        self.stop = False
        self._z1 = z1
        self._z2 = z2

        ###active l'evolution sur le plateau
        self.debug = 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"""
#         if self.debug:
#             for coord in self.plateau.cases:
#                 self.plateau.cases[coord].majEstCibleCurseur(False)
#                 self.plateau.cases[coord].majEstCibleAttaque(False)
#                 QApplication.processEvents()

        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
        self.echec = False
        
        #on continue jusqu'a tomber sur la case cible, ou jusqu'a un echec
        it = 0
        while position.coord != self.cible and not self.echec:
            it += 1
##            print "iteration: ", i
            
            #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
                    cout = self.plateau.coutDep(position.coord, coord)

                    if cout >= 0:
                        noeud = N(coord)
                        
                        #on calcule le cout de la case
                        if self.stop: return []

                        noeud.creer(position, self.cible, cout)
#                         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)
                            
#                             if self.debug:
#                                 self.plateau.cases[noeud.coord].majEstCibleCurseur(True, True)
#                                 time.sleep(0.05)
#                                 QApplication.processEvents()

            #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)
#                 if self.debug:
#                     self.plateau.cases[meilleur.coord].majEstCibleCurseur(True, False)
#                     QApplication.processEvents()
#                     time.sleep(0.05)
                filOuvert.remove(meilleur)
                position = meilleur
            else:
                self.echec = True

        #on revient de parent en parent jusqu'au depart
        if not self.echec:
            while position.coord != self.origine:
                if self.stop: return []
                chemin.insert(0, (position.coord, position.kDep))
#                 if self.debug:
#                     self.plateau.cases[position.coord].majEstCibleCurseur(False)
#                     self.plateau.cases[position.coord].majEstCibleAttaque(True)
#                     QApplication.processEvents() 
                position = position.parent
        else:
            chemin = []          
        
        return chemin