Forums Développement Multimédia

Aller au contenu

- - - - -

Tuto algorithme A star

algorithme A star tuto aide PAO CODE

7 réponses à ce sujet

#1 laverdure

  • Guests

Posté 09 January 2016 - 21:29 PM

Bonjour,

Voila , le lien vers le topic du tuto en question : http://forums.mediab...lgorithme_astar
est mort : http://flash.mediabo...howtopic=121874 je me permet donc de relancer le topic !

Voila, je comprend la logique et le code du tuto seulement une ligne de code me laisse perplexe
private static function getCurrentNode():Node
{
var tmpList:Array = new Array();
var maximum:int = m_openList.length;
var minF:int = 1000000;
var curNode:Node = null;

for( var i:int = 0; i < maximum; ++i )
{
var node:Node = m_openList[i] as Node;

if( node.f < minF )
{
minF = node.f;
curNode = node;
}
}

return curNode;




je ne comprend pas pourquoi la variable minF prend une valeur aussi grosse, 10000 me semble énorme
J'attend vos réponses pour m’éclairer la lanterne ;)

#2 laverdure

  • Guests

Posté 09 January 2016 - 21:35 PM

Je rajoute une petite chose, je ne comprend pas non plus ce que la ligne de code "var node:Node = m_openList[i] as Node;" veux dire, c'est le "as" qui me pose problème...

#3 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 6997 messages

Posté 09 January 2016 - 22:49 PM

Hello,

Tu as aussi une autre approche utilisée ici : http://forums.mediab...cman#pathfinder

Pour ta première question :

if( node.f < minF )
{
minF = node.f;
curNode = node;
}

Ici on vérifie si l'ID du noeud est inférieure à l'ancienne ID la plus petite déjà trouvée.
On part à 1000000 car on estime que notre programme n'aura pas besoin d'atteindre cette valeur, ça n'a aucune incidence puisque dès le premier pas de la boucle on modifie cette valeur par la plus petite valeur trouvée. L'objectif étant sans doute (je n'ai pas tout lu et le tuto n'est pas de moi) de trouver le plus petit chemin entre deux positions.

Pour ta deuxième question :

var node:Node = m_openList[i] as Node;

Il s'agit d'un transtypage, on demande à un objet de se comporter comme un autre objet.
Si tu fais un peu de POO c'est un des effets du polymorphisme, un objet peut avoir plusieurs types, le sien et celui de sa class mère par exemple, ou d'une des classes héritées. Ici on a besoin d'un objet de type NODE, mais on ne doit pas savoir si dans le tableau interrogé (encore une fois je n'ai pas lu le tuto) on a bien des objets de ce type, par contre on sait que ces objets ont une dépendance sur ce type, en gros ils héritent du type Node. On peut donc demander au programme de récupérer l'objet et de le transtyper en un objet Node qu'on peut ensuite utiliser comme un objet de type Node.

Pour être plus clair :

J'ai un objet de type Node.
Je crée un objet de type Tuile qui hérite de Node.
Tuile récupère toutes les propriétés et méthodes de Node y compris son type.
Tuile est donc de deux types, Node et Tuile.
Une tuile est bien un type de noeud, l'inverse n'est pas vrai.

Si a un moment dans mon programme j'ai besoin de travailler avec des objets Node mais que j'ai des objets Tuiles, je peux effectuer un transtypage pour que mon objet Tuile se comporte comme un objet Node.

L'instruction "as" permet ce transtypage :

m_openList[i] as Node;

Tout comme cette autre écriture :

Node(m_openList[i]);


#4 laverdure

  • Guests

Posté 10 January 2016 - 14:48 PM

Bonjour,

merci pour les réponse , en gros on caste le type de l'objet pour être sure qu'il est bien de type Node ! Mais ce que je ne comprend pas trop c est que ma liste ne contient que des objets de type node (je travail en c# et mon tableau est en faite une liste de type node ) donc finalement ça sert a rien non ?

#5 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 6997 messages

Posté 10 January 2016 - 16:44 PM

Ca dépend de l'objet stocké dans le tableau, et surtout de la structure du programme.
Si il peut arriver que tu aie un objet de type évolué (Tuile) qui doit se comporter comme un objets moins évolué (Node) alors ce transtypage à tout son intérêt puisqu'il permet de cibler un nombre d'objets bien plus important pour une même méthode (peut importe le nombre d'héritage et donc d'évolutions de ton objet). Comme pour beaucoup de choses dans la POO, l'objectif est avant tout de sécuriser ton programme et les données qu'il utilise. C'est pour ça qu'on type les données, ici tu as donc une sécurité pour le cas où ton objet serait de type évolué par rapport à un objet de type Node, ça ne mange pas de pain et ça permet de t'assurer de travailler avec le bon type de donnée. Sur ce même principe tu as en POO l'héritage, le polymorphisme, l'encapsulation, les accesseurs et les getters/setters, tout ceci ne sert qu'à une chose en définitive, verrouiller ta brique de programmation afin d'en minimiser l'impact sur le programme principal. On encapsule pour éviter les accès directs à des références internes à l'objet, on crée un objet avec le moins de dépendances possibles pour qu'il ait son fonctionnement propre (indépendant du reste de l'application), on utilise des getters/setter pour modifier les attributs de l'objet, l'override pour modifier le comportement d'une classe héritée, super pour envoyer des informations aux méthodes de la superclasse (classe mère), etc.... L'objectif premier de la POO, en dehors du fait de simplifier la structure, c'est de créer des biques logicielles indépendantes capables d'être sorties de leur contexte pour être utilisées à volonté dans un autre programme. Chaque partie est indépendante, on y accède via des "interfaces" de programmation afin de "discuter" avec lui, mais son fonctionnement interne reste opaque pour le reste de l'application.

Pour résumer tout ça on peut dire que le programme connaît les méthodes pour discuter avec un objets (interfaces) mais que le comportement interne de l'objet lui même est tout à fait inconnu au reste du programme (encapsulation). L'objet apprend donc à se gérer tout seul selon les instructions qu'on lui donne (getters/setters, puis/ou super, override). Si besoin pour faire vraiment très simple, maman dit à son enfant "vas te laver les dents" et l'enfant le fait sans qu'on ait besoin de lui apprendre à chaque fois comment faire. L'enfant sait se gérer selon les instructions qu'on lui donne (ici sa mère mais ça peut être n'importe qui d'autre, par exemple le programme principal).

Donc ici effectuer un transtypage pour s'assurer que le type de donnée à traiter soit correct quel que soit la liste envoyée me semble être une bonne approche, inutile quand on est sûr du type de donnée qu'on passe à l'instruction, mais utile dans tous les autres cas, et es-tu sûr d'avoir réfléchis à tous les autres cas de figure ?

Prenons un exemple simple en pseudo code/logique.
Tu as besoin de faire un calcul de distance entre deux objets.
Mais ces objets peuvent être de n'importe quel type (ennemis, tirs, balle, joueur, .... ).
Créer une méthode générique qui permet de calculer la distance entre deux objets n'est pas un problème.
Par contre tu dois passer à ta méthode deux objets du type le plus basique possible (x,y,hauteur, largeur) pour pouvoir au moins faire ton calcul de distance quel que soit l'objet.
C'est là que le transtypage est intéressant car on peut dire que tout objet hérite de la classe "Object" de base qui intègre par défaut les paramètres dont j'ai besoin (x,y,hauteur, largeur).
Donc ma méthode va fonctionner pour tout objet de type Object.
A ce moment là il me suffit de transtyper mon objet en "Object" (polymorphisme) pour que ma méthode puisse s'appliquer de manière générique à tout objet dans mon programme qui hérite de "Object" (et en AS3 tout hérite forcément de la classe Object puisque tout est "objet").

Si je raisonne dans ce sens je me débrouille pour que les méthodes communes puissent avoir un référentiel de paramètres commun, ici c'est le type le plus basique me permettant de faire mon calcul, donc "Object" puisque tous mes objets héritent de cette classe et qu'elle intègre tous les paramètres dont j'ai besoin pour mes calculs.

Dans le cas que tu propose, "Node" est l'objet le plus basique qui intègre les attributs et méthodes dont j'ai besoin pour faire mes calculs. Comme qui peut le plus peut le moins, tout type d'objet évolué hérité de "Node" pourra fonctionner avec cette méthode dans mon programme sans lever une erreur, même si je n'ait pas pensé avant à tous les cas de figure possible.

Donc pour te répondre, ça ne sert à rien... si tu as bien pensé à tout et que tu ne souhaite pas réutiliser les méthodes que tu écris dans d'autres programmes ou de manière plus étendue. Moi perso le calcul de distance je le colle dans une classe "Utils" que je réutilise à chaque fois et je me débrouille pour que cette méthode utilise les objets les plus génériques possible, du coup j'en suis débarrassé une bonne fois pour toute.

#6 Invité

  • Guests

Posté 10 January 2016 - 17:03 PM

Ba dans le cas de mon tuto et dans ce que je veux faire (pour l'instant ) il n'y a pas besoin de le faire mais j'ai compris le pourquoi du comment c est ce que je voulais :) merci !

#7 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 6997 messages

Posté 10 January 2016 - 17:41 PM

De rien, bon courage.

#8 Scorbutics

  • Guests

Posté 10 April 2018 - 22:23 PM

Bonjour,
Je passe par là simplement pour vous dire qu'en 2018 il y a toujours des gens qui regardent ce tuto et je remercie grandement les auteurs qui m'ont permis à l'époque d'implémenter un A * en C++ en se basant sur votre tutorial.
Bonne continuation à vous,
Scorbutics




Répondre à ce sujet



  

1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)

authorised training centre

Centre de Formation Mediabox - Adobe et Apple Authorised Training Center.

Déclaré auprès de la Direction du Travail et de la Formation Professionnelle

Mediabox : SARL au capital de 62.000€ - Numéro d'activité : 11 75 44555 75 - SIRET : 49371646800035

MEDIABOX, 23, rue de Bruxelles, 75009 PARIS

FFP