Fabien-B · July 28, 2017 11:54
diff --git a/algo.py b/algo.py
 MAX_RECURSION_DEPTH = 10

 #le principe :
 #on a des polygones sur la table (pas encore de ronds, on verra ça plus tard).
 # on cherche le chemin qui "tourne le moins" : en visant l'objectif, on contourne les obstacles au plus près.
 # donc en gros on entre dans une recursion sur un arbre binaire : à chaque point, on a deux chemins possibles
 # à moins que l'on puisse atteindre l'objectif. Dans ce cas, on arrête la recherche sur cette branche de l'arbre.
 # Il y a un risque de stack overflow, donc il vaut mieux mettre une limite de récursion, c'est plus prudent.

 # on trace la ligne droite du point de départ à celui d'arrivé.
 #   Si on ne touche aucun polygone, c'est bon ! on a un chemin !
 #   Sinon, on prend les points touchant le polygon qui sont sur la tangente à gauche et droite de celui-ci.
 #   Pour chacun de ces points, on l'ajoute à la trajectoire, et on recommence en essayant de trouver un chemin de ce point jusqu'à l'objectif.



 def find_path(dep, obj):
    found_paths = []
    def g(p, path):
        if len(path) > MAX_RECURSION_DEPTH:     #si on veut stopper l'algo si on va trop profond en récursion
            return
        if atteignable(p, obj):         #si l'objetif est atteignable en ligne droite, c'est ok, on a un chemin !
            #path += obj                #suivant si on veut avoir l'objectif dans le chemin ou pas.
            found_path.append(path)     #une variante serait de sortir au prmier chemin trouvé, mais ce ne sera pas le chemin optimal.
        else:
            poly = getFirstPolygon(p1, obj)     # on trouve le premier polygon qui est intersecté par le vecteur p1 -> objectif
            t1, t2 = poly.get_tangente(p1)      # on récupère les points du polygone qui sont sur la tangente à gauche et à droite.
            g(t1, obj, path+t1)                 # on cherche le chemin de ces points vers l'objectif, en mémorisant le chemin parcouru.
            g(t2, obj, path+t2)
    
    g(dep, [dep])       # On lance la recherche du chemin depuis le point de départ, et on initialise le chemin au point de départ!
    
    return min(found_paths, key=lambda x : compute_lenght(x))  # on retourne le chemin le plus court parmi ceux trouvés
	MAX_RECURSION_DEPTH = 10

	#le principe :
	#on a des polygones sur la table (pas encore de ronds, on verra ça plus tard).
	# on cherche le chemin qui "tourne le moins" : en visant l'objectif, on contourne les obstacles au plus près.
	# donc en gros on entre dans une recursion sur un arbre binaire : à chaque point, on a deux chemins possibles
	# à moins que l'on puisse atteindre l'objectif. Dans ce cas, on arrête la recherche sur cette branche de l'arbre.
	# Il y a un risque de stack overflow, donc il vaut mieux mettre une limite de récursion, c'est plus prudent.

	# on trace la ligne droite du point de départ à celui d'arrivé.
	# Si on ne touche aucun polygone, c'est bon ! on a un chemin !
	# Sinon, on prend les points touchant le polygon qui sont sur la tangente à gauche et droite de celui-ci.
	# Pour chacun de ces points, on l'ajoute à la trajectoire, et on recommence en essayant de trouver un chemin de ce point jusqu'à l'objectif.



	def find_path(dep, obj):
	found_paths = []
	def g(p, path):
	if len(path) > MAX_RECURSION_DEPTH: #si on veut stopper l'algo si on va trop profond en récursion
	return
	if atteignable(p, obj): #si l'objetif est atteignable en ligne droite, c'est ok, on a un chemin !
	#path += obj #suivant si on veut avoir l'objectif dans le chemin ou pas.
	found_path.append(path) #une variante serait de sortir au prmier chemin trouvé, mais ce ne sera pas le chemin optimal.
	else:
	poly = getFirstPolygon(p1, obj) # on trouve le premier polygon qui est intersecté par le vecteur p1 -> objectif
	t1, t2 = poly.get_tangente(p1) # on récupère les points du polygone qui sont sur la tangente à gauche et à droite.
	g(t1, obj, path+t1) # on cherche le chemin de ces points vers l'objectif, en mémorisant le chemin parcouru.
	g(t2, obj, path+t2)

	g(dep, [dep]) # On lance la recherche du chemin depuis le point de départ, et on initialise le chemin au point de départ!

	return min(found_paths, key=lambda x : compute_lenght(x)) # on retourne le chemin le plus court parmi ceux trouvés
No results found