Discussion :

[Aspic]

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Médinoc]

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.

[Aspic]

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

[Médinoc]

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.

[sopsag]

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

[khayyam90]

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).

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