EXEMPLE DE PATHFINDING EN UTILISANT L'ALGORITHME A* (OPENGL) (DEV-C++)

Signaler
Messages postés
688
Date d'inscription
jeudi 26 décembre 2002
Statut
Membre
Dernière intervention
19 mai 2005
-
Maaaaat
Messages postés
1
Date d'inscription
jeudi 22 décembre 2005
Statut
Membre
Dernière intervention
5 janvier 2008
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/24257-exemple-de-pathfinding-en-utilisant-l-algorithme-a-opengl-dev-c

Maaaaat
Messages postés
1
Date d'inscription
jeudi 22 décembre 2005
Statut
Membre
Dernière intervention
5 janvier 2008

Super exactement ce qu'il me fallait
kangoo75
Messages postés
47
Date d'inscription
mercredi 20 juillet 2005
Statut
Membre
Dernière intervention
28 mai 2008

bravo ! ça compile .
Merci

PS : pour ceux que ça interresse, 4 articles trés bien sur le pathfinding sur : http://www.vieartificielle.com/article/index.php?action=article&id=161
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

hmm, lgdi32 alors?
kangoo75
Messages postés
47
Date d'inscription
mercredi 20 juillet 2005
Statut
Membre
Dernière intervention
28 mai 2008

Erreur : cannot find -lgdi :(
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

tu dois aussi mettre -lgdi il me semble.
kangoo75
Messages postés
47
Date d'inscription
mercredi 20 juillet 2005
Statut
Membre
Dernière intervention
28 mai 2008

Bonjour,
j'ai installé la librairie openGL ,j'ai mis dans l'éditeur de lien de dev c++ :

-lopengl32
-lglu32
-lglut32

Et j'ai l'erreur à la compilation :


undefined reference to `CreateFontA@56'
undefined reference to `SelectObject@8'
undefined reference to `SelectObject@8'
undefined reference to `DeleteObject@4'
undefined reference to `GetStockObject@4'
undefined reference to `SwapBuffers@4'
undefined reference to `ChoosePixelFormat@8'
undefined reference to `SetPixelFormat@12'
collect2: ld returned 1 exit status
make.exe: *** [Projet2.exe] Error 1

Ai je oublié quelque chose ?

Merci
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Pour l'optimisation, tout se joue au niveau de la structure de données qu'on utilise pour récupérer le prochain "noeud" (la prochaine case en fait) à traiter dans l'algorithme.

La première idée c'est de chercher la case dans toute la map à chaque itération: lent!
La seconde, c'est de mettre dans une liste chaînée toutes les cases qui sont susceptibles d'être la suivante (les modifiées en fait): bcp mieux!
La dernière (pour moi en tout cas ^^), c'est de mettre ces cases non pas dans une liste mais dans une priority queue (file à priorité): extraordinairement plus rapide! ^^

Si on imagine une map de n cases, le premier algo est en n², le second également mais dans la pratique c'est bcp bcp bcp mieux, et le troisième est en n log n, avec le n dans le log très petit, donc c'est quasiment linéaire avec le nombre de cases, c'est NOËL, noêl je vous dis ^^
cs_MATHIS49
Messages postés
370
Date d'inscription
vendredi 10 octobre 2003
Statut
Membre
Dernière intervention
14 mai 2010

Utilité : 11/10
Commentaires : 9/10
Ergonomie : 10/10

Que dire de plus ? A quand l'optimisation? :)
cs_gomoz
Messages postés
135
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

super, ca va mettre très utile pour piger le truc !
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

ce serait pas mal de ponderer les cases: traverser du sable est plus dur que traverser du bitume, un truc de ce genre (du style coût en points de mouvement, comme dans heroes of might and magic 4 e.a.)
RaphAstronome
Messages postés
105
Date d'inscription
samedi 7 décembre 2002
Statut
Membre
Dernière intervention
17 août 2009

Super !!!

Sous dev-c++ ne pas oublier : -lopengl32 -lGdi32
(dans Options du Projet > Paramètres > Editeur de liens).
fser
Messages postés
74
Date d'inscription
vendredi 26 septembre 2003
Statut
Membre
Dernière intervention
23 avril 2005

Je met 8/10 car je trouve dommage que le chemin puisse se faire en "diagonale" : si on fait un chemin de ce genre :
__
|_|__
|_]

le "truc" peut se faufiller entre les cubes
Saros
Messages postés
921
Date d'inscription
vendredi 20 décembre 2002
Statut
Membre
Dernière intervention
23 septembre 2010

Il faut installer les librairies OpenGL pour compiler... On peut trouver ça sur le net...
fser
Messages postés
74
Date d'inscription
vendredi 26 septembre 2003
Statut
Membre
Dernière intervention
23 avril 2005

Mes compilateur ( Dev C++, Borland C++ builder ) retourne des erreurs du type :
[Linker error] undefined reference to `glColor4f@16'
ou encore
[C++ Erreur] Unit1.cpp(2): E2129 Constante caractère trop longue (ou vide)
ou [C++ Erreur] Unit1.cpp(2): E2206 Caractère '@' (0x|40) incorrect
a quoi est ce du ?
voici les erreurs retournées par visual studio :
Compiling...
main.cpp
c:\téléchargements\sources\pathfinding\main.cpp(53) : error C2059: syntax error : '}'
c:\téléchargements\sources\pathfinding\main.cpp(53) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(53) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(56) : error C2059: syntax error : '}'
c:\téléchargements\sources\pathfinding\main.cpp(56) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(56) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(59) : error C2059: syntax error : '}'
c:\téléchargements\sources\pathfinding\main.cpp(59) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(59) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(62) : error C2059: syntax error : '}'
c:\téléchargements\sources\pathfinding\main.cpp(62) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(62) : error C2143: syntax error : missing ';' before '}'
c:\téléchargements\sources\pathfinding\main.cpp(391) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(391) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(391) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(396) : error C2374: 'a' : redefinition; multiple initialization
c:\téléchargements\sources\pathfinding\main.cpp(392) : see declaration of 'a'
c:\téléchargements\sources\pathfinding\main.cpp(446) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(459) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(461) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(463) : warning C4305: 'argument' : truncation from 'const double' to 'float'
c:\téléchargements\sources\pathfinding\main.cpp(465) : warning C4305: 'argument' : truncation from 'const double' to 'float'
Error executing cl.exe.

main.exe - 13 error(s), 8 warning(s)
Saros
Messages postés
921
Date d'inscription
vendredi 20 décembre 2002
Statut
Membre
Dernière intervention
23 septembre 2010

J'ai trouvé génial, le fait que l'on puis construire soi-même un chemin...
Et puis pareil, en 3D ce serait bien :)
10/10
Saros
lolquivole
Messages postés
11
Date d'inscription
dimanche 13 juillet 2003
Statut
Membre
Dernière intervention
20 juillet 2005

le pathfinding en 3D est beaucoup plus complexe (plus de chemins à chercher)
Mais bon si tu reste dans le plan, ce n'est pas si dur à faire : tu transforme la carte 3d en 2d, ensuite tu exécute la fonction pour avoir le chemin, il te suffit avec une caméra qui bouge de suivre le chemin que tu as obtenu. D'ailleurs tu peux mettre des poids aux chemins:tu peux faire en sorte que monter un escalier par exemple, prenne plus de temps que d'y aller par un chemin normal.
Modéliser le monde est quand même la phase la plus difficile...
xarier
Messages postés
688
Date d'inscription
jeudi 26 décembre 2002
Statut
Membre
Dernière intervention
19 mai 2005

tout simplement geanial code bien claire programme tres utile mais il ya un trucs que jaurait prefairé c d'avoir ajouter une animation ca serait super :)
et aussi de faire un path finding pour 3D (avec les mur et tout) et la camera bouge pour qu'il trouve le chemin de sortie le plus court elle meme :)

MAIS fronchement BRAVO !!!!