Discussion :

[Eric Sigoillot]

Bonjour à tous !

Je cherche de la documentation sur un algorithme de poursuite, un peu à la PacMan.
Si vous avez des noms à me proposer... Je suis preneur. Je précise que l'algo n'a rien à voir avec le problème du voyageur de commerce (enfin je crois...).

J'explique le problème. Etant donné deux objets dans un environnement remplit de blocs, on veut que l'un des deux objets se rapproche du deuxième. A noter que l'environnement peut être modifié (les blocs), et que le deuxième objet peut fuir à volonter.

Après mes prmières recherches, il semblerait qu'il faille que je m'oriente sur l'algo A*, mais je manque d'infos.

Merci d'avance.

[Eric Sigoillot]

Bon, j'ai bien trouvé une page s'approchant du A*, mais c'est pas encore ça... (http://gameprog.free.fr/articles/ia/pathfinder1.htm, pour ceux que ça intéresse).

Quelqu'un sait comment rechercher le symbole "*" dans un moteur de recherche sans qu'il soit pris pour un caractère générique... C'est assez bête de ne pas pouvoir rechercher la chaîne "A*" !

Y'a vraiment personne ??

A+

[mio]

Je vais essayer de repondre du mieux que je peux.
Tu as parfaitement raison ce probleme n'a rien a voir avec celui du voyageur de commerce ou il faut trouver le plus court chemin pour visiter un ensemble de n villes et retourner au point de depart. Ce probleme la peut etre resolu par un recuit simule, si ma memoire ne me trompe concernant le nom de la methode, lorsque le nombre de villes est raisonnablement petit (ordre de grandeur de la dizaine).
Concernant l'algorythme A*, je crois me rappeller que cette page est assez interessante et il doitt y avoir du code source a lire en plus si tu es un adepte du source. Moi je prefere les explications en francais. (ou en anglais)
http://theory.stanford.edu/~amitp/GameProgramming/
avec le jeu developpe par le gars
http://www-cs-students.stanford.edu/~amitp/games.html
Sinon il y a
http://www.gameai.com/ai.html
Desole tout est en anglais mais ca se comprend bien. Par contre je ne suis pas sur que l'algo que tu as choisi soit le meilleur. En effet dans le pathfinding tu donnes une destination a une ou plusieurs unites et tu calcules le meilleur chemin pour s'y rendre tout en essayent de rester realiste. C'est a dire que le joueur ne doit pas en theorie connaitre la topologie du terrain en fonction du mouvement de l'unite...Je ne vais pas m'etendre sur cela mais ici ton probleme est different car l'unite qui est poursuivi bouge en permanence ou du moins peut potentielement bouger a chaque instant (avec une vitesse nulle ou non).
Malheureusement, je n'ai pas en tete de maniere de coder de maniere efficace un algorithme de poursuite de maniere generique. Apres pour un probleme biewn specifique il faut voir. Sinon pour tes recherches sur google, comme le A* algorithme est l'algo qui fait du cafe pour le pathfinding il faut chercher "pathfinding" voir pourquoi pas "intelligence artificielle".
Voila je ne peux pas dire beaucoup plus pour le moment.

[Qwazerty]

Salut
a tous
Je sais pas sur quoi vous programmer, moi sur VB, mais si c sur c y'as un site genial mais je me suis fait remonter les brettelles par un moderateur pour l'avoir ecri alors je mail ca a Hdd34 si d'autre sont interseer ... je sais que le mail perso et anti forum mais la sensure l'ai parfois aussi ...
A+

[Eric Sigoillot]

Merci de m'avoir répondu !

Entre temps, j'ai réussi à tomber sur la page dont tu parles, Mio. Je suis en train de l'éplucher !

Pour le lien que tu m'as passé Qwazerty, il m'a l'air correct mais... Je n'ai pas encore trouvé la fonction "Rechercher". Ca pourrait aider...

En attendant, je vous remercie.

A+

[mio]

Je veux pas etre pointilleux et faire le caracteriel mais SVP c'est mio sans majuscule. Merci...

[Qwazerty]

[Eric Sigoillot]

D'accord MiO
Sans vouloir t'emmerder...

A+

[funkeejeffou]

Tu peux aussi t'interesser à l'algo Alpha Beta qui est une amelioration de l'algo MINIMAX en intelligence artificielle, et qui a largement fait ses preuves (encore utilisé de nos jours dans style Diablo2 et d'autres...).
Pas très dur a coder, son efficacité depends de la fonction d'heuristiques que tu vas lui donner (fonction d'evaluation du plus court chemin par exemple).
Tu trouveras sans problemes de la doc sur le net et je te le recommande
Bonne chance