A-Star - Algo de pathfinding - Page 2

Je dis juste : essaie de faire tourner A* sur une carte de 1024 par 768 carrés, et tu vas comprendre si A* est + rapide que Dijkstra !

En fait, tout dépend de la taille de la grille et du type de carte.

Pour info, A* c'est utilisé presque que pour les jeux et Dijkstra est en passe de devenir la méthode n°1 de recherche de trajectoire dans les réseaux et sur le net, devant RIP (Routing Internet Protocol).

Vas parler du A* à l'école polytechnique de Montréal, à l'université de Princeton ou à la section robotique du MIT!
[edit]Edité par pyroangel le 27-03-2002 à 18:01:21[/edit]

Attends... v te chercher qq chose moi aussi...

Grr... Bon en fait je vais rien chercher du tout... J'avais trouvé une page avec les tests de différents algos de pathfinding, dont Dijkstra et A*, or A* est le plus rapide de tous les algos testés, et de loin.

Voilà. Maintenant, tu peux faire un prog ti pour ton algo comme ça on pourra vraiment tester.

No problemo !


Alors : une carte en 65536 x 65536 avec 25 polygones de 16 sommets en moyenne chacun, ça te va ?

P-ê pas, c tellement rapide A*...

Une carte en 65536 x 65536 avec 25 polygones de 16 sommets en moyenne chacun, ça te va ?

Ah c malin ça... Tu veux vraiment faire ça ? Vas-y je sens que ça va être assez drole
Mais j'ai dit SUR TI !!! Et puis en plus qu'est-ce que tu veux que j'en fasse de tes 25 polygones ? Le A* ça travaille en case par case

nan, CT pour te donner une idée des calculs que devra faire Dijkstra (Découper 25 polygones non convexes d'environ 16 sommets chacun, c palpitant non?)

pour toi, ça fait au max dans les 4 294 967 296 cases à tester !!!

T fou toi ???

Tu crois que tu va donner un nombre completement arbitraire de polygones comme ça ? Soit tu fais un truc précis, à ce moment là ça donne un nombre énorme de cases pour A*, mais aussi un nombre énormes de polygones.
Soit tu fais 25 polygones, à ce moment là tu as un truc absolument pas précis, et du coup je fais un truc en A* avec des grosses cases comme ça y'en a pas bcp à tester.

Essaie pas de faire des trucs qui t'avantagent... Quand on teste des algos on le fait serieusement.

combien de polygones alors (100 ? 200? )

allez : tant que tu veux : il faut juste que le nombre de sommets dans la carte soit inférieur à 1 000...

Tu fais ce que tu veux... la seule contrainte c'est : sur Ti.

Alors programme un générateur de carte aléatoire, on va faire calculer chaque algo sur 200 maps différentes et chaque fois A* et Dijkstra tourneront sur la même

Tu fais ce que tu veux du moment qu'on peut comparer.

t'as l'air d'y croire à ton A*

y a du contest dans l'air la on dirait...
bob je te soutiens ( par la pensé parce que le C je viens de m'y mettre et je vais arreter des 2 jours je crois )


Bais POWAAAAAAAAAAAAAAAAAAAAAAAA

quel con il est entrain de tout flooder !

Le C c'est difficile au début, mais quand t'apprends sur PC avec un Environnement de Développement Intégré genre C++ Builder et un bon débogueur, c'est que du bonheur...

Le C c'est super facile les gars, vous semblez pas comprendre !

Tout ce qu'il y a de + difficile qu'en basic c'est la gestion de la mémoire et les pointeurs !

Vous allez pas attendre toute votre vie pour qu'on vous fasse les fonctions et l'interpréteur qui va avec pour faire les progs qui vous plaisent !

Avec la C tout est possible!!!!!!!!!!!!


Et moi G vu des tests qui montrent que Dijkstra est + rapide qu'A*.........

Et moi j'ai vu le contraire...

Eh bin le gars il savait pas implémenter Dijkstra ou alors il a fait ça sur des maps trop petites.

De toute façon, c un faux débat puisque les efficacités dépendent des cartes.

C l'approche qui diffère :

                             - t'en es encore aux RTS en 2D
                             - je suis déjà prêt pour les FPS et RTS en 3D

Le gars... LES gars !

Arf tes "FPS" en 3D ils sont fait avec du raycasting...
Si tu veux faire un combat de limaces en 3D avec de l'IA, en effet tu pourras utiliser ton algo...

lol

C tjrs + marrant qu'un combat d'escargots en 2D

...
J'avais pas remarqué que Starcraft était lent, Age of empire non plus

Enfin j'ai peut-être mal regardé...

n'oublie pas : les sprites, c'est en binaire dans ta carte vidéo, pas en ti-basic dans de la flash !!!!!!!

Tu suis pas le rythme pour les posts

Sans déconner ? Connaisseur en plus... hum...

C'est quoi le rapport ?

Arrêtez avec votre mauvais esprit, on dirait PpHd vs TIMad !
Essayez plutôt de trouver une solution pour l'algo.
Faudrait que Neurone nous explique la fin de son algo...

C pas du mauvais esprit, il est persuadé que son algo qui ralenti sur pc marche mieux que le A*, instantané sur Ti

A* instantané sur ti lol avec une carte en 2x2 !!!!!!!!!!!!!

Non, A* c bien pour l'approche par carte représentée paar matrice, mais ça a aussi ces inconvénients.

J'ai aussi regardé comment ç marché et j'ai testé une version sur PC


Mais la caractéristique la + intéressante de A* et qui ne t'a même pas effleuré c'est que A* gère les niveaux de difficultés de passage:

alors ton approche Noir : passe pas Blanc : passe, c'est à réviser par + c'est foncé, +c difficile à traverser comme case : exemple, courir sur la plage c + rapide que nager dans la mer. Toi t'irais tout droit alors qu'il faut courir le + possible puis nager le moins possible.......
Moi aussi , j'aimerais bien voir l'algo de Neurone, que je le porte sur CASIO GRAPH 20!!!!!!!

Ton truc "qui ne m'a pas effleuré", je ne l'ai pas fait car, au cas où tu ne l'as pas remarqué, j'ai fait une démo et pas un jeu...

La carte fait 160x100 pixels, soit l'écran de la Ti. La tienne fait 640x480 si je ne me trompe pas... Donc réduit la à 160x100 et on va voir si c'est instané. Et encore, faut tester ça sur Ti...

On compare des algos, pas des implémentations :

Un algo est meilleur qu'un autre <=> quand les conditions d'entrées tendent vers l'infini, le tps de calcul de cet algo est < à celui de l'autre algo..

Tu connais la définition d'un algo ou tu prends tons méthodes heuristiques pour des algos?

Il dort !
[edit]Edité par pyroangel le 27-03-2002 à 20:08:32[/edit]

Non, son modem chauffe...

Dans 11 minutes j'ai un ISO de Jedi Knight 2 à graver

T'as pas répondu à ma question, j'ai comme l'impression que tu la contournes soigneusement...