Algorithme A* (Recherche de chemin)

[Cortes48]

Algorithme A* (Recherche de chemin)

Ce tuto est est traduction de ce tutoriel.

L'algorithme A*(prononcé A star) peux être compliqué pour les débutant. Ce tuto est fais pour les débutant.

Introduction: La zone de recherche

Supposons que nous avons quelqu'un qui veut aller du point A au point B. Supposons qu'un mur sépare les deux points. Sur la figure 1 le carré rouge est le point B ,le carré vert est le point A et le bleu est le mur.


figure 1

En premier nous divisons notre zone en plusieurs case afin de simplifier l'algorithme,vous pourrez le diviser en Tile dans votre jeu.

Les cases sont appelées noeud (Nodes en anglais).

Commencer la recherche

Maintenant que nous avons divisé notre zone, nous devons commencer à recherché le plus court chemin entre le point A et le point B.

Nous commençons la recherche grâce à ses étapes:

1. On commence au point A et on ajoute à une "open list" les carré qui vont nous intéresser. L' "open list" ressemble à une liste de course. En ce moment il y a juste un élément sur la liste, mais nous aurons plus tard. Elle contient les carré qui vont être autour du chemin que vous voudrez prendre.
   
2. On regarde les carré qui sont adjacent à notre point de départ et on ignore les carré non-praticable(le mure)On ajoute les carré praticable à l'open list. Pour chacun de ces carré, on les sauvegarde avec comme parent , le point de départ. Le parent est très important,on en reparlera plus tard.
   
3. On enlève le carré A de l'openlist pour le mettre dans la closelist qui va contenir tous les carré qui ont déjà été regardé.

Je vais reformuler un peux tous ça:

L'openlist contient tous les carrés à analyser.
Pour analyser un carré on regarde ces carrés adjacents,si ces carrés adjacents sont praticables,on les ajoutes à l'open list sinon on ne fait rien.
Un carré dans l'openlist à toujours un parent,c'est à dire le carré adjacent qui nous à permis de le découvrir.
Une fois que nous avons analysé un carré,on le supprime de l'openlist pour le mettre dans la closelist qui contient tous les carrés analysés.

Sur la figure ci-dessous ,Le carré vert est le point de départ. Il est entouré de bleu pour montrer qu'il à été ajouté à la closelist. Tous les autres carrés adjacents sont entourés de vert car ils ont été ajoutés à l'openlist pour être analysé. Ils ont tous un petit pointeur gris pour montrer qui est leur parent, ici le carré vert est leur parent.


figure 2

Attribut du score

La clé pour déterminer les carré utilisés pour trouver le chemin le plus court est donné par cette équation :

F = G + H

G est la coût du déplacement du point de départ jusqu'au carré analysé.
H est le coût de la distance (sans diagonal) du point d'arrivé jusqu'au carré analysé.

Nous allons instaurer les coût.
Un déplacement î v -> vaut 10 et en diagonal ça vaut 14.

Un petit schema pour comprendre :


On voit bien sur la case a droite du carré vert où il y a marqué les lettres, que les valeurs corresponde, ce carré est à un déplacement à droite du point de départ, donc G=10 et il est a 3 carré du point d'arrivé,donc H=30.

Ensuite on continu la recherche sur le carré qui a la valeur F la moins élevé.




Et après on arrive sur notre carré rouge.
Pour retrouver le chemin c'est très simple,on regarde le carré qui à decouvert le carré rouge puis le carré qui à découvert le carré qui carré qui découvert le carré rouge etc etc de parent à parent jusqu'au carré vert.


Voilà ce tuto est terminé, maintenant à vous de l' implémenté dans votre jeux

[thoduv]

Merci, c'est sympa.
Par contre... la différence participe passé/verbe à l'infinitif... à revoir... ! oO

[Cortes48]

Merci , j'essaye de corrigé les fotes

[dolarcles]

Tuto sympa oui, merci.

Envoyé par thoduv

Merci, c'est sympa.
Par contre... la différence participe passé/verbe à l'infinitif... à revoir... ! oO

+1, c'est un véritable massacre, surtout qu'il y a un tutorial à ce propos. À corriger rapidement ou je te transforme en cochon !

Sinon tu pourrais citer la base théorique de ton algorithme.

[Cortes48]

Je suis dejà en cochon , je suis protéger de dolarcles

[Lord Raptor]

Envoyé par Cortes48

Je suis dejà en cochon , je suis protégé de dolarcles