[Pathfinding] A* (A Star)

Bonjour les développeurs!!!

Voilà, j'ai commencer à implémenter A* (A Star) pour la recherche de plus court chemin dans un jeu vidéo en 2D.
Mon code ne fonctionne pas, je ne sais plus quoi faire pour l'améliorer ou pour le corriger ...
J'ai bien évidemment fait des recherches sur A Star, mais le problème ne se situe pas totalement dans la compréhension de cet algorithme mais dans mon implémentation partielle.

Pour cet implémentation, je me suis basé sur l'article suivant : A* Pathfinding for Beginners par Patrick Lester sur GameDev .

Mon code faisant plus de 600 lignes, celui-ci se trouve à l'adresse suivante : A* (A Star)

Le problème que je rencontre est qu'une fois la fonction lancée, on rentre dans une boucle infinie ...

Merci de l'aide apportée d'avance.

*EDIT* :
- [08/05/2008] à 17h54: Quelques bug fixes, plus de boucle infinie mais je ne sais pas encore si le code fonctionne correctement.

Kurapix

aurais-tu un main pour le compiler directement ?
Tu as un tableau 2D ou un graphe ? (en entrée dans ton jeu video)

Le main.c se résume ainsi pour mes tests :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <stdio.h> #include <stdlib.h>   #include "pathfinding.h" #include "structures.h"   int main(int argc, char *argv[]) { t_point Depart = {0, 0}, Arrivee = {10, 10}; path_find_astar(Depart, Arrivee);   return 0; }

---

Je n'ai aucune idée pour l'intégration de mon implémentation d'A Star dans le jeu pour l'instant.
La map sera composée de TILES, il faudra donc mettre des poids pour chacuns des TILES.
Une autre personne de mon équipe est chargé de coder le système de map ... ^^" je n'ai donc hélas pas de map sous la main pour pouvoir tester A Star.

Pour l'instant, avec A Star, j'en suis uniquement au coding de l'algorithme sans prise en compte d'obstacles (ce qui n'a pas de sens dans un jeu ... mais pour l'élaboration du code ... ;) ).
Je suis conscient que A Star peu retourner plusieurs "plus court chemin", mais le but ici est d'en retourner au moins un ^^.
J'essaierais de l'adapter ensuite.

Donc pour te répondre, je pense plutôt que ce sera un tableau 2D plutôt qu'un graphe.

Kurapix

Je l'ai entièrement recoder avec les arbres binaires, de ce fait mon code est plus rapide, propre et moins sujet à bug.
Je fais encore quelques modifications et tests, ensuite, je posterais mon code pour avoir votre avis ;) .

Kurapix