:: PlayerAdvance.org ::  

Précédent   :: PlayerAdvance.org :: > :: Développement Amateur :: > Autres > Tutoriels

Tutoriels Tutoriels dédiés au développement sur d'autres supports

Publicité

Réponse
 
Outils de la discussion Modes d'affichage
Vieux 07/09/2008, 11h20   #1
Cortes48
Modérateur
 
Date d'inscription: 28/02/2007
Localisation: Grenoble
Messages: 576
Par défaut Algorithme A* (Recherche de chemin)

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

Dernière modification par Cortes48 ; 07/09/2008 à 15h23.
Cortes48 est déconnecté   Réponse avec citation

Publicité

Vieux 07/09/2008, 11h43   #2
thoduv
Membre confirmé
 
Date d'inscription: 10/11/2005
Localisation: ...
Messages: 1 464
Par défaut

Merci, c'est sympa.
Par contre... la différence participe passé/verbe à l'infinitif... à revoir... ! oO
__________________
"S'il n'y a pas de solutions c'est qu'il n'y a pas de problème ..."
< mon devblog > ... < Lapinou Jumps ! - un jeu de plate-forme "vertical" avec un mignon petit lapin. >
thoduv est déconnecté   Réponse avec citation
Vieux 07/09/2008, 11h54   #3
Cortes48
Modérateur
 
Date d'inscription: 28/02/2007
Localisation: Grenoble
Messages: 576
Par défaut

Merci , j'essaye de corrigé les fotes
Cortes48 est déconnecté   Réponse avec citation
Vieux 07/09/2008, 11h57   #4
dolarcles
Revenant
 
Date d'inscription: 07/07/2006
Localisation: dining in Hell
Messages: 3 406
Par défaut

Tuto sympa oui, merci.

Citation:
Envoyé par thoduv Voir le message
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.
__________________
Signature absente
dolarcles est déconnecté   Réponse avec citation
Vieux 07/09/2008, 11h59   #5
Cortes48
Modérateur
 
Date d'inscription: 28/02/2007
Localisation: Grenoble
Messages: 576
Par défaut

Je suis dejà en cochon , je suis protéger de dolarcles
Cortes48 est déconnecté   Réponse avec citation
Vieux 07/09/2008, 21h20   #6
Lord Raptor
Membre confirmé
 
Date d'inscription: 08/10/2006
Localisation: Sophia-Antipolis
Messages: 1 247
Par défaut

Citation:
Envoyé par Cortes48 Voir le message
Je suis dejà en cochon , je suis protégé de dolarcles
__________________
Lord Raptor est déconnecté   Réponse avec citation
Réponse

Liens sociaux

Publicité



Utilisateurs regardant la discussion actuelle : 1 (0 membre(s) et 1 invité(s))
 
Outils de la discussion
Modes d'affichage

Règles de messages
Vous ne pouvez pas créer de nouvelles discussions
Vous ne pouvez pas envoyer des réponses
Vous ne pouvez pas envoyer des pièces jointes
Vous ne pouvez pas modifier vos messages

Les balises BB sont activées : oui
Les smileys sont activés : oui
La balise [IMG] est activée : oui
Le code HTML peut être employé : non
Navigation rapide

Discussions similaires
Discussion Auteur Forum Réponses Dernier message
[Offre d'emploi] Recherche pixel artist / CDI zeGouky [DEV] Divers 37 20/07/2007 22h52
Moteur de recherche Web pour PA Dr.Vince Le Site & Le Forum 37 04/04/2007 16h19
NDS Recherche graphiste pour shoot'em up Getget94 Aide au développement 30 07/10/2006 12h50
Recherche Save Jeux DS pour SC ktastroff [NDS] Divers 3 13/12/2005 21h17
[projet] Recherche codeur pour projet RPG thoduv [DEV] Divers 2 03/12/2005 18h46


Fuseau horaire GMT +2. Il est actuellement 11h01.


Édité par : vBulletin® version 3.7.2
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Tous droits réservés.
Version française #16 par l'association vBulletin francophone
Design par Ass-Itch, DJP et Dr.Vince