[Path Finding] Algorithme A star

Bonjour à tous,

Je dois créer un algorithme de recherche du plus court chemin pour mon jeux vidéo 2D. J'ai bien compris le principe de l'algo en allant sur le net mais pour son implémentation en C, je bloque.

J'ai déjà créé une structure pour chaque noeud (case) :

Code:

---

1 2 3 4 5 6

typedef struct noeud { int x, y; int cout_f, cout_g, cout_h; struct noeud * parent; }

---

Mais est ce que je dois utiliser des listes chainées obligatoirement pour coder cet algorithme en C ? Je ne vois pas comment créer les listes ouvertes et fermés :(

Merci beaucoup :)

Bonjour,
Je ne vois pas ce que tu appelles listes ouvertes ou fermées. Peux-tu élaborer?

Au niveau de la structure que tu as créée: Si c'est pour un arbre, alors c'est le format le moins efficace qui existe: L'arbre à chaînage inversé. Ce format peut être sympa pour stocker des données sérialisées (je crois qu'il est assez populaire dans une table de base de données), mais PITA pour manipuler des données en mémoire.

Salut,

Les listes ouvertes et fermés sont celles utilisées dans l'algorithme :
http://khayyam.developpez.com/articl...o/astar/#LII-1

Et je n'utilise pas d'arbre, j'utilise une matrice pour découper mon terrain de jeu, exactement comme dans le lien que je viens de te donner.

Le seul hic, c'est que c'est codé en C++ et non en C et en C++, c'est un langage orienté objet donc plus facile de coder l'algorithme ;)

Mon problème réside dans la création d'une liste pour stocker des "objets" de type noeud (cf mon typedef) avec les opérations de base (ajout, suppression, insertion).

Merci

J'avais fait un code réutilisable sympa pour des listes simplement chaînées en C, mais je ne l'ai pas sous la main. Il faudrait que tu me contactes ce soir pour me le demander. Sinon, tu peux essayer de contacter Cyrine, je le lui avais envoyé...

Sinon, tu peux peut-être essayer les conteneurs de la GLib, je ne m'y suis jamais attaqué, mais j'ai "entendu" dire qu'elle était sympa.

Juste pour info, il y a aussi l'algorithme de Dijkstra pour trouver le plus court chemin. L'inconvénient c'est qu'il ne tient pas compte des info topologiques, mais l'avantage c'est qu'il te garantit le plus court.

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Hadrien

Tu n'es pas obligé de prendre des listes, tu peux partir sur des tableaux si ça te chante. C'est juste que l'algorithme nécessite de passer des éléments d'un tableau à un autre (donc avec suppression en milieu de tableau).

La liste chainée est en effet une bien meilleure structure de données que le tableau pour le A* (la liste chainée triée peut même être plus performante encore).

:arrow: http://nicolasj.developpez.com/articles/listesimple/ ?

J'ai du mal à voir la performance d'une liste chaînée triée par rapport à une liste chaînée normale.

Pour moi, ça réduit seulement le temps de recherche d'un facteur deux (puisqu'une recherche dichotomique est impossible, une liste chaînée n'étant pas un arbre) au prix d'une insertion qui passe du temps constant au temps linéaire...

Citation:

---

Envoyé par Médinoc

J'ai du mal à voir la performance d'une liste chaînée triée par rapport à une liste chaînée normale.

---

c'est juste que l'algo A* a souvent besoin de prendre le "meilleur" élément d'une liste. Si cette liste est triée, la récupération de cet élément se fait en O(1) : c'est le premier de la liste.

Joli.
Il est temps que je lise l'article sur le A*...

Bonsoir à tous :)
Merci pour vos réponses.

Effectivement, la liste chainée triée permet d'aller plus vite mais pour l'instant, peut importe la vitesse, je veux juste que ca marche et après à la rigeur on optimisera si nécessaire :)

Médinoc m'a proposé un code pour les listes chainées, donc si tu pouvais me l'envoyer ou alors l'uploader sur ce thread ca sera super sympa ;)

Ensuite, avant que je me lance pour rien, pensez vous que la structure de liste chainée soit correcte pour coder la "ListeOuverte" et la "ListeFermée" de l'algo A* ?

Salut,

Aujourd'hui, je n'ai pas le temps donner un exemple propre et clair d'utilisation du code, donc j'envoie directement le projet.
Ce projet utilise trois fois le même code de listes chaînées pour trois types différents. Notez qu'il s'agit de listes chaînées intrusives.

Salut,
Je ne vois pas le code pour les listes chainées avec les fonctions d'ajout, d'insertion, de suppression, de recherche dans la liste...

PS : C'est quoi des chaines intrusives :oops: ?

Une liste chaînée est dite intrusive quand le pointeur suivant est un champ de la structure utilisée.

Le code des fonctions de liste est dans liste.cinc, qui est inclus par plusieurs fichiers source différents.
Ces fonctions permettent de parcourir la liste (y compris avec un parcours indirect), d'insérer un élément dans la liste (avec un pointeur de pointeur), et de détacher un élément de la liste pour le détruire séparément.

Ton code est un peu compliqué pour moi mais merci de me l'avoir envoyé :)

J'ai trouvé un code assez simple sur les listes chainées :
http://chgi.developpez.com/sortlist/

Par contre, je voulais créer une fonction qui supprime un élément précis de la chaine :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int deleteNoeud(slist **sl, t_noeud n) { slist *tmp; if (!*sl) return -1;   while (*sl) { tmp = (*sl)->suiv;   if (comparerStructure((*sl)->data, n) == 1) // si on a trouvé le bon noeud { free(*sl); // on le delete *sl = tmp; return 0; }   *sl = tmp; }   return -1; // on a pas trouvé }

---

Le problème c'est que une fois le noeud supprimé (ca marche), ma liste chainée est vide !!!

J'ai exactement piqué le même code sauf que j'ai remplacé "Val" par une structure t_noeud

Merci ;)