 |
| Un homme énervé - Giphy |
Sans rentrer dans les détails, Unity n'a plus marché, puis Visual Studio, et après Visual Studio n'arrivait plus à reconnaitre le code créé par Unity. Du coup, j'ai passé mes sessions du weekend à réparer ces bouses. Dans le même temps j'ai tout de même pu faire un peu de recherche sur comment faire le placement de routes.
Hier, j'ai pu mettre en pratique ce que j'ai appris. Dans un premier temps j'ai créé un nouveau prefab tout moche de route. Puis j'ai vérifié que j'étais bien capable dans poser un lors du clic de la souris. Ici rien de compliqué. L'étape suivante était la création de section de route. Pour faire apparaître une route allant d'un point A à un point B de manière intelligent, sur un monde en deux dimension, il est très simple et plutôt conseillé d'utiliser l'algorithme de recherche de chemin nommé A star, ou A*.
 |
| A* animé - Wikipédia |
A*, explications
Pour ceux qui ont vu le live d'hier, le A* est un algorithme à la fois très simple à mettre en place, très bien pensé, et archi dur à expliquer à l'oral, en tout cas pour ma part. Son principe est assez simple, en lui fournissant un tableau de points, un point de départ, et un point d'arrivée, il va assigner un nombre à certains voire à tous les points du tableau, appelé cout. Et pour aller du point A au point B, il suffit de se "déplacer" vers le point adjacent ayant le coût le plus faible. Le coût du point de départ n'a pas d'incidence sur la suite, et sera souvent mis à 0 pour plus de facilité
 |
| Chemin final A* - Alazob TM |
Le calcul du coût
Comment est calculé le coût de chaque point? Et donc comment va-t-on déterminer quel point est le plus propice à visiter? Hé bien, le coût est en général une estimation appelée une "heuristique". Pour définir le mot plus clairement, une heuristique est simplement une fonction qui permet de calculer rapidement une solution réalisable mais pas forcément optimale à un problème. Dans le cas de l'algorithme. Dans notre cas cette heuristique est le plus souvent calculée par l'addition de deux nombres: la distance parcourue entre le point de départ et le point actuel, et la distance estimée entre le point actuel et le point d'arrivée. Durant le live, j'ai utilisé la distance carrée, mais en 2D on peut aussi utiliser la distance de Manhattan. La distance carrée la distance usuelle que l'on apprend en cours, mais sans la racine carrée, histoire d'avoir des chiffres ronds. Pour la distance de Manhattan, vous comptez de combien de cases vous avez à vous déplacer latéralement, puis en hauteur pour arriver au second point, et vous additionnez les deux.
Les noeuds
Pour pouvoir dérouler sereinement l'algorithme, on va créer un nouveau type d'objet que l'on va appeler "noeud". Un noeud représente en fait un point donné de la carte, et contient donc ses coordonnées x et y, mais aussi son poids. Afin de pouvoir retracer le chemin, on va aussi y stocker une référence vers un autre noeud, que l'algorithme s'occupera d'ajouter.
File prioritaire
Pour ne pas visiter plusieurs fois les mêmes noeuds, mais aussi pour récupérer à chaque fois le bon noeud a évaluer, nous allons avoir besoin d'une structure de données appelée File Prioritaire, ou Priority Queue en anglais. Une file est une structure qui permet de stocker un ensemble de données du même type, comme une liste ou un tableau. Sa particularité est que l'on ne peut ajouter des objets qu'à la fin de la file, et lorsque l'on veut récupérer un élément on ne pourra à chaque fois récupérer le premier de la file. On dit que c'est une structure de type "FIFO", pour "First In, First Out". Et oui, c'est exactement comme une file d'attente à la poste ou autre.
Une file prioritaire, c'est le même principe, sauf qu'on a instauré un passe coupe file comme a Disney. Dans le cas informatique, quand un élément arrive, s'il remplit une certaine condition, il va remonter dans la file et sera placé en début de file, ou juste derrière un élément qui remplira mieux cette condition.
Dans l'algorithme A*, la condition sera d'avoir le coût le plus petit possible. Ainsi on récupèrera toujours le meilleur élément possible en premier.
Liste des voisins d'un noeud
Il nous faudra aussi être capables de récupérer tous les voisins d'un noeud. C'est à dire tous les noeuds sur lesquels on peut arriver en se déplaçant d'une case depuis le noeud actuel. Dans notre cas, les routes ne seront pas diagonales, donc les voisins sont uniquement les noeuds directement situés à gauche, droite, en haut et en bas.
Il faut de plus veiller à deux choses: que ces points existent bien (i.e qu'il ne soient pas en dehors de la map), et qu'ils ne soient pas un obstacle. S'ils vérifient ces conditions on peut les évaluer.
En créant chaque noeud voisin, on lui assigne le noeud actuel comme parent. De plus, comme on s'est déplacé d'une case, sa distance au point de départ est assignée à (distance au départ du noeud actuel + 1). Sa distance au point d'arrivée est calculée avec la méthode de calcul choisie, ici la distance carrée.
Le déroulement de l'algorithme
Une fois qu'on a tout en place, l'algorithme est le suivant:
- On créé une file prioritaire dans laquelle on stockera les noeuds qui sont à évaluer, on la nommera par convention openList
- On créé une seconde file qui contiendra les noeuds déjà visités, afin d'éviter de tourner en rond. Celle ci s'appelle en général closedList
- On ajoute le point de départ à la liste des points à évaluer
- Puis, tant qu'il y a des points à évaluer (ie tant que openList n'est pas vide):
- On récupère le premier noeud de openList
- S'il a les meme coordonnées que le noeud final, on renvoie ce noeud et on finit l'algo
- Sinon, on récupère la liste des voisins de ce noeud, et pour chaque voisin:
- S'il existe déjà dans une des deux liste et avec un cout inférieur au cout actuel, on l'ignore
- Sinon on ajoute ce voisin à la liste des noeuds a évaluer
- Enfin on enlève le noeud actuel de la liste des points à évaluer
Ici on s'est assuré de toujours évaluer en premier le noeud dont le coût est le plus faible, donc celui qui nous mènera le plus rapidement à l'arrivée. Si tout va bien, l'algorithme va au bout d'un moment évaluer un noeud qui sera notre point d'arrivée, et s'arrêtera là en revoyant ce noeud. En revanche, s'il n'arrive jamais à ce stade, cela signifie que le point d'arrivée est hors d'atteinte, et il faudra renvoyer une erreur.
Pour mieux comprendre, j'ai repris l'exemple précédent en notant en bleu la distance parcourue, et en jaune la distance a parcourir. Et vous pourrez aussi noter une une magnifique erreur de calcul sur la case finale mais flemme de tout refaire.
 |
| Le meme avec les distance - Alazob TM ft Michel Bonenmaths |
Dans mon cas, j'ai exécuté ce code en omettant simplement d'enlever les obstacles. J'ai fait en sorte qu'a la création de la map il s'applique entre deux points arbitraires, et voici le résultat:
 |
| Route générée par Astar - Numérobis |
Comme vous le voyez, c'est très diagonal, et c'est assez normal si vous avez compris le déroulement de l'algo, puisqu'il cherche a arriver le plus rapidement possible.
La prochaine étape va donc d'améliorer cela et faire en sorte d'avoir des routes un peu plus agréables à voir. Ensuite, on pourra les texturer et faire en sorte de les placer à la souris plutôt qu'au démarrage.
Enfin, on fera en sorte de les sauvegarder/charger avec le reste.
Voilà pour le compte rendu du jour, j'espère que ça vous aura plus et que vous aurez compris comment marche l'algo. Si vous avez des questions/suggestions n'hésitez pas :)
Et a votre avis, comment allons nous régler le problème des routes trop diagonales ? :p
Je vous laisse méditer là dessus, bisous baveux.
Aucun commentaire:
Enregistrer un commentaire