[Résolu] Pathfinding Algorithme A* - exemple exe gmk

Salut,

à chaque fois que j'ai essayé de m'intéresser aux RTS sous game maker, j'ai été confronté au problème du choix des chemins, c'est à dire l'algorithme qui permet à un personnage situé à la case A de savoir s'il existe un trajet (optimal ou presque) vers la case B en évitant tous les obstacles, puis de s'y rendre éventuellement. (Les données sont sous la forme d'une liste de cases reliées entre elles si elles se touchent physiquement)

Au début je me suis dit pourquoi ne pas utiliser Dijkstra (qui trouve le meilleur chemin), puis j'ai lu que l'algo A* ( ou A star ) était plus rapide, donc plus adapté aux jeux (et en contrepartie, il ne trouve pas le meilleur, juste un bon chemin).

Est-ce que quelqu'un est capable de m'éclairer sur son fonctionnement ?

Evidemment ce genre de "tuto" pourrait être très utile à de nombreuses autres personnes voulant créer du RTS.

Wikipédia :
http://fr.wikipedia.org/wiki/Algorithme_A*

Un exemple sur GM, mais je le trouve un peu trop évolué :
http://gmc.yoyogames.com/index.php?showtopic=286571


edit : j'ai réussi, voiçi mon gmk

l'algo a* est connu, après pas testé personnellement sur gml.

salut

concernant le A*, il me semble que Gm a une implantation plutôt pas mal de cet algo. Même si c'est pas complètement nickel, ça marche déjà pas mal.

Il faut utiliser le mp_grid. Tu recherches du pathfinding pour un jeu en isométrique ou en vue de dessus ?

Quelques exemples que j'avais trouvé, assez simples, je crois. Je ne sais plus de qui ils sont, mais je pense que c'est préciser dans le fichier :

http://blendman.free.fr/dev/gm/pathfinding/

Tu y trouveras 3 exemples, en espérant que cela t'aide .

Sinon, je vais te donner mon interprétation de ce que j'en avais lu, mais je ne dis pas que c'est exactement ça le pathfinding, hein .
C'est juste l'idée que je m'en fais .
Pour schématiser, il semble qu'il faille prendre la recherche du chemin comme une addition au restaurant dont le but est de payer le moins cher possible .

Tout d'abord, tu as des cases, situées dans un tableau, donc tu connais ces cases. Chaque case à un "cout" en fonction des cases à coté, et des cases départ et arrivée.
Tu as une case de départ (x,y,) (cout =0) et une case d'arrivée (xx,yy) (cout =1 ou 2, ça dépend de la case d'avant), que tu connais précisément.
Donc, tu calcules la somme la moins cher (ou l'une des sommes) pour y arriver (lignes, ou diagonale ou les deux) par exemple, imaginons que tu démarres sur la case (3,4) et tu vas en (6,2)
Avec ça, tu connais normalement la direction. Tu sais que tu dois aller au nord/est (en haut , à droite). Tu dois donc calculer par rapport à cette direction-là.
une des sommes serait : (6-3)*2 + (4-2)*2 = 10 euros pour y aller. C'est une des chemins possible.

Tu peux aussi faire le calcul avec les diagonales :
if x<xx and y<yy {cout = 1} // on va au nord-est .
if x<xx and y=yy {cout = 2}
etc...
tu vas sur la case obtenue, tu l'ajoutes dans ta liste et tu continues avec la case suivante.

Tu pourras donc sans doute faire moins de 10 euros s'il n' y pas d'obstacle entre le départ et l'arrivée. Mais s'il y a des obstacles, ça risque d'être plus cher .

les cases en haut/bas/droite/gauche valent 2 euros , alors que les diagonales coutent 1 euro (ou inversement, cela dépend de ce que tu veux faire).
Tu vérifies à chaque case si tu peux aller à gauche, droite, bas, haut ou en diagonal.
Si tu peux aller dans une des directions, tu ajoutes cette/ces cases à une liste dite "ouverte", ainsi que la somme que cela fait.
Et ainsi de suite, jusqu'à atteindre ton but.
Lorsque tu atteins ton but, tu calcules les sommes obtenues par tes divers chemins, et tu choisis le moins cher .

voilà, c'est comme cela que j'ai cru comprendre la méthode. Après, il doit y avoir des détails qui m'échappent, car je ne l'ai pas encore mis en pratique réellement . Mais disons que c'est un début de réponse, sans le prendre pour la vérité absolue concernant le A* ,c ar ce n'est pas du tout le cas ).

Je me suis déjà intéressé à l'algorithme du pathfinding A* mais j'avais des bugs.
Je vais me relancer dedans.

Sinon tu peut aller voir ici un tutoriel qui explique le fonctionnement du pathfinding A star : tuto ici

Bijour, et merci pour vos réponses

Je cherche à le faire tourner sur un jeu vu de dessus (style pokémon), mais dans ce que j'ai commencé à coder, chaque case est un objet qui contient une liste d'adjacence, donc ça marcherait autant pour les deux vues

et j'ai décidé que les couts de déplacement étaient tous à 1 pour faire simple.

Je vais regarder ce tutoriel parce que j'ai pas bien compris blendman ^^ surtout au niveau déroulement de l'algo et liste ouverte ou fermée.

http://gmc.yoyogames.com/index.php?showtopic=286571
C'est un moteur utilisant A*.
Tu peux le comprendre ou l'utiliser.

Ca y est, j'ai réussi, voiçi mon gmk
J'ai suivi le tuto du site du zero. Les déplacements en diagonale sont interdits et tous les déplacements coûtent 1€
Le personnage ne se déplace pas, mais le chemin est stocké dans une liste inversée de cases (lol). arrivée->départ

hmmm c'est moi ou passer en dessous du tas de pierre est plus court?

C'est vrai, (je n'avais même pas calculé) mais son but n'est pas de trouver le plus court chemin, mais un bon chemin en peu de temps. Il y a des situations où il n'est pas très efficace. Et si il existe un chemin, il le trouvera dans tous les cas.

Dijkstra est une bonne solution également, mais un peu plus long à implémenter pour une grille que A*.

Le pathfinding A* n'a pas pour but de trouver le chemin le plus court, il doit trouver un chemin c'est tout.

Si tu veut un pathfinding qui calcule le chemin le plus court, tu peut utiliser l'algorithme de Dijkstra.
Mais ce dernier s'avère plus lourd que le A*.

Si tu veut en savoir plus sur cet algorithme, tu peut voir se tutoriel du siteduzero par ici.

merci pour ton gmk chulien ça aide a comprendre

Faudrait taper ça dans les scripts. ça peut être utile, et je pense pas que quelqu'un qui cherche un système de pathfinding viendra voir ici.

salut

C'est intéressant.

Je vais essayer de voir s'il y a moyen de le transposer en purebasic car je vais avoir besoin d'un pathfinding .

Merci pour ton exemple

tout a fait d'accord avec jo,
c'est du beau travail en tout cas.

lien mort ressuscité

http://www.mediafire.com/?uf9tm388pa6kc8y

Moi ça m’intéresse mais pour des case hexagonal
Vous savez faire ?

"Lien invalide" ou mort... bref, il faudrait le ré-uploader, siouplait ^^
(je devrais en avoir l'usage sur un projet).