Encore un autre pathfinding - Page 1

J'ai mis un peu de temps mais ça marche!

Il y a quelques temps de ça j'ai fait un pathfinding qui lisait les données d'un tableau 2D ou 3D.
J'ai ajouté un nouveau mode de recherche utilisant des noeuds dont les coordonnées sont plus flexibles (on est plus limité à des nombres entiers, ils peuvent êtres décimaux) mais surtout chaque noeud peut avoir de 1 à une infinité de voisins (tandis qu'avec l'ancienne méthode c'était soit 8, soit 26 selon si on travail en 2D ou 3D)

Les sources

Voilà un exemple de représentation :


NOTA : Je vais créer une classe pour gérer permettre la création de fichiers de map et gérer les liaisons plus facilement, la doc arrivera plus tard (enfin j'espère!)
NOTA² : Le code est normalement portable sur tous les OS

Tu pourrais expliquer un peu plus ce que fait ton code ? (pa trop envie de lire le code)

Un fichier contient une série de noeuds, chaque noeud a des coordonnées X,Y,Z et une liste de voisins (de 1 à l'infini)

La classe est initialisée en lui donnant un fichier, les IDs du noeud de départ et d'arrivée.
La recherche est basée sur la méthode A*

on ajoute le noeud de départ à la liste ouverte
tant qu'il existe un noeud dans la liste ouverte et que le noeud d'arrivée n'y est pas
{
---on choisit le meilleur noeud de la liste ouverte
---on le met dans la liste fermée
------on ajoute ses voisins
------si le voisin n'existe pas, le noeud choisit devient son parent
------s'il existe alors
---------soit le noeud choisit est un meilleur parent et on lui assigne
---------soit le parent précédent est meilleur et on ne change rien
}

Les noeuds en question peuvent représenter ce que tu veux :
-le croisement de plusieurs routes
-un local dans un bâtiment (<= je m'en sert pour créer une map des locaux d'une industrie et permettre de trouver comment aller rapidement d'un local à un autre)
-... il peut y avoir d'autres utilisation en élec ou avec les fluides en général

Il me reste encore à ajouter des coeff aux noeuds ce qui permettra de différencier le chemin le plus court du plus avantageux.
Je cherche aussi un moyen d'ajouter des critères de sélection d'un noeud (ne pas utiliser si péage dans le cas de route ou local bruyant pour le cas des locaux par exemple)

C'estd koi la difference avec Dijkstra ? (a moins que mes souvenirs de RO soient mauvais )

A* explore d'abord les noeuds qui "sont dans la bonne direction", comme ça il peut trouver un premier chemin potable (mais pas forcément optimal) et quand il examine les autres chemins, il n'a pas besoin d'explorer les chemins plus longs que ce premier chemin, parce qu'il sait qu'ils ne seront pas optimaux

Grosso modo c'est une optimisation heuristique dans le cas où on a juste besoin de trouver un chemin optimal entre deux points particuliers (et pas le cas plus général de Dijkstra où on cherche tous les chemins optimaux à partir d'un point de départ ^^)

Je ne sais pas comment fonctionne l'algo Dijkstra
Pour ce qui est d'A*, il utilise un heuristic : F = G + H où G est la distance entre deux noeuds et H la distance "à vole d'oiseau" du noeud qu'on examine jusqu'à l'arrivée. Le "meilleur noeud de la liste ouverte" dont je parle est celui qui a un F le plus faible c'est à dire le chemin qui fait le moins de détours possible et qui va droit à l'arrivée.
On peut nuancer cet heuristic avec un coefficient qui majore la distance entre deux noeud (nature du terrain, vitesse limite autorisée pour un trajet routier, ...)
Pour qu'un alog soit A* il doit respecter les notions de listes ouverte et fermée et le calcul de l'heuristic F=G+H

spomky
: On peut nuancer cet heuristic avec un coefficient qui majore la distance entre deux noeud (nature du terrain, vitesse limite autorisée pour un trajet routier, ...)

Ouais, mais ca, c'est pas lie a l'algo lui meme normalement, c'est jsute ta fonction objectif qui change (donc la definition de "meilleur")

Oui ça n'est pas lié à l'algo, l'algo de base trouve le chemin le plus court quoi qu'il arrive. Un coeff ou d'autres critères permettent juste d'obtenir un chemin différent

Je up le sujet pour éviter d'en ouvrir un autre.J'ai pas mal bossé sur mon pathfinding depuis la dernière fois :
Ce qu'il fait aujourd'hui :
*Pour la map :
-import/export d'un fichier contenant tous les objets et leurs liaisons
-export au format XML
-les objets peuvent avoir des coordonnées X,Y,Z ou latitude,longitude,altitude (degré décimal - Dd, degré minute décimal - DMd, degré minute seconde décimal - DMSd et degré minute seconde - DMS) ... pour utiliser les coordonnées retournées par un système GPS
-toutes les conversions de Dd, DMd, DMSd et DMS : 47.54098° (Dd) <=> 47°32.4588' (DMd) <=> 47°32'27.528" (DMSd) <=> 47°32'27" (DMS)
-calcul de distances entre deux points
-gestion d'un coefficient pour chaque liaison (entre un point A et B il peut être de 1 et entre B et A de 2 par exemple)
-mode lecture seule ou lecture/écriture (ajout/supp d'objets ou de liaisons)
-détection des noeuds orphelins (sans aucune liaison)
-possibilité de calculer les distances des coordonnées GPS au mm, cm, dm, m ou km (basé sur une valeur approximative du rayon de la Terre)

*Pour la recherche :
-recherche d'un chemin le plus court ou le meilleur (utilise les coeff)
-possibilité d'effacer et de relancer autant de recherche que l'on veut
-naviguer de nœud en nœud dans le résultat de la recherche
-donne la distance à parcourir du point de départ jusqu'au point d'arrivée avec ou sans coeff


Ce qu'il me reste à faire (entre autres) :
-permettre l'import/export de points aux formats GPX (un format libre) et KML (utilisé par GoggleEarth)
-import de map à partir d'un fichier XML
-enregistrer une map différents fichiers (images et données diverses)
-mettre un checksum
-trouver un système pour mettre plus de contraintes sur une liaison (pas seulement un coeff)
-prendre en compte l'altitude dans le calcul de la distance entre 2 points (pour les coordonnées GPS seulement)
-changer le rayon de la Terre selon la position pour avoir un calcul de distances plus précis
-...