[Unity3D][Défi50jours] Jour 6, 7 et 8 - Pose de routes

Comme vous aurez pu le remarquer, ce week end il n'y a pas eu de billets de blog ni de changements sur le git ou le trello. La raison est simple: j'ai eu la fausse bonne idée de mettre à jour Unity vers sa dernière version. J'étais jusque là sur la version 2017, et ait remarqué que la 2018 était sortie, avec apparemment plein de nouvelles fonctionnalités. Du coup comme j'avais du temps je me suis dit "tiens je vais voir ce que ça donne". Pire idée du monde.

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.

[Unity3D][Défi50jours] Jour 5 - Déplacement sur une grille et suivi de la caméra

Journal de bord de Macmist, défi 50 jours Unity, jour 5

Aujourd'hui, ou plutôt hier soir, je me suis attaqué au déplacement d'objet sur le terrain. Il fallait que l'objet puisse suivre la souris lorsqu'elle se déplace à l'écran, mais aussi qu'il reste à des positions fixes sur une grille. Ca a été plutôt laborieux et j'ai du faire appel à toutes les ressources de l'internet, mais j'y suis finalement parvenu.

Au début, j'ai créé un script qui faisait apparaitre un cube, et j'ai essayé de lui donner comme position la position de la souris. Le problème que cela a posé est que la souris n'a pas de position en 3D, mais seulement sur le plan (x, y), dans Unity cela revient à la largeur et la hauteur. La profondeur est omise.

L'espace dans Unity

L'objet suivait donc la souris, mais se déplaçait du coup latéralement et en hauteur uniquement. Or il fallait qu'il puisse se déplacer sur les axes x et z. Il me fallut donc chercher une autre solution.

Je me suis souvenu alors d'une notion apprise durant ma formation et qui aurait pu être utile. Quelques recherches plus tard, j'ai découvert que Unity permettait de la mettre en place de manière très simple. Cette méthode est celle du Raycasting, ou lancé de rayons en français. C'est une technique qui est énormément utilisée dans le jeu vidéo pour résoudre une grande variété de problématiques, et c'est pourquoi il est naturel que Unity fournisse des fonctions déjà toute faites pour la mettre en place.

Si vous lisez ceci et ne savez pas ce qu'est le Raycasting, laissez moi vous l'expliquer brièvement. Il s'agit d'une technique de géométrie visant a déterminer le point ou l'objet le plus proche dans une direction donnée. Son principe est très simple, on "lance" un rayon (en fait une droite), à partir d'un point donné et dans une direction précise. On peut donner à se rayon une longueur maximale ou le considérer comme infini. Puis, si le rayon est arrêté par quelque chose (une surface, un objet...), on arrête le lancé et récupère la position de ce point d'intersection. Les cas d'application sont nombreux, par exemple détecter le point d'impact d'une balle de revolver lancée à toute vitesse, ou encore définir le champ de vision d'un personnage. En effet, comme on s'arrête à la première intersection, si intersection il y a, l'objet est forcément visible depuis le point d'origine du lancé.
Si l'on décidait de ne pas s'arrêter à la première intersection, mais plutôt de faire "rebondir" le rayon et le suivre ainsi dans toute ses intersections, on parlerait alors de RayTracing. C'est une autre technique, plus gourmande, mais aussi très utilisée, notamment pour calculer les ombres et les reflets de lumière avec un haut degré de réalisme.

Schéma explicatif

Ray casting en action

Image rendue par RayTracing

Après toutes ces explications comprenez sans doute comment le Raycasting pouvait être intéressant ici. Pour arriver à faire suivre la souris par l'objet, j'ai mis en place la technique suivante: lancer un rayon depuis la caméra en direction de la souris. Si il y a un point d'impact sur le terrain, déplacer l'objet à cet endroit. Et ça a marché comme sur des roulettes.
A ce moment là, l'objet suivait la souris comme je le voulais, mais je n'étais pas au bout de mes peines, car deux problèmes restaient à être résolu. Premièrement, l'objet était à moitié rentré dans le terrain, et secondement, l'objet ne devait pas pouvoir se déplacer n'importe comment, mais plutôt suivre la grille (c'est à dire avoir des positions à chiffres ronds, (1.4, 12.4, 0.789) n'est pas une position acceptable, il nous faudrait (1, 12, 1)).
Ces deux problèmes ont finalement été plutôt simples à résoudre. Pour le premier il suffit de placer l'objet de manière à ce que son point le plus bas soit pile au niveau du point le plus haut du sol. On sait où se trouve le sol, il est au point d'impact. Celui ci étant à une hauteur y, et notre objet faisant une hauteur y2, il suffit de placer l'objet à une hauteur y + y2 / 2, puisque généralement dans Unity le centre de gravité d'un objet est situé en son point central.
Pour le second problème, il suffisait d'arrondir les coordonnées x et z au nombre entier le plus proche pour pouvoir coller à la grille.

Exemple de l'objet bien positionné

Après tout ça, il me restait une ultime chose à faire afin de pouvoir clore la session et m'endormir sereinement: faire bouger la caméra en fonction de la souris.
Au moins, cette partie était très peu technique, et j'ai pu la mettre en place en très peu de temps. Pour faire simple, il suffisait d'établir une marge autour des bords de l'écran, en nombre de pixels, à partir de laquelle faire bouger la caméra si la souris entrait à l'intérieur

Voilà, ma tâche était accomplie. Et quelle satisfaction de voir tout prendre forme. Je vais maintenant pouvoir me retirer dans mes quartiers afin de prendre un repos bien mérité. A demain très cher journal.

[Unity3D][Défi50jours] Jour 4 - Génération d'un terrain - suite et fin

Bonsoir cher ami lecteur.
Tout d'abord, pour ceux qui l'attendaient, je suis désolé de n'avoir pas pu faire la session d'hier en live, mais je manquais d'énergie pour le faire suite à une journée bien trop chargée.
Et l'update du jour est venue tardivement parce que ben, journée chargée aussi quoi.

Sur ce trêve d'escusage, place compte rendage.

Le but de la session d'hier était donc de finir ce qui avait été commencé la veille, à savoir passer la map en 3d, et essayer de sauvegarder/charger cette même map.

[Unity3D][Défi50jours] Jour 3 - Génération d'un terrain

Bloup bloup blip, c'est l'heure de l'update du jour 3 !

Maintenant qu'on sait comment sauvegarder/charger, il est temps de rentrer un peu plus directement dans la mère... Dans le lard du sujet !

[Unity3D][Défi50jours] Jour 2 - Travail de recherche et experimentations

Yoyoyo yo yoyoyo, je suis le ratz qui fait du rap...
Bonjour, update jour 2, ça va? Moi ça va, je fais les updates les lendemains, c'est malin, du coup on croit que je suis décalé et que je n'ai pas fait mes devoirs. Mais NON, QUE NENNI mon ami, je suis bel et bien dans les temps et ait bien effectué mon heure quotidienne de développement hier soir, en ce mardi 19 juin. Et aujourd'hui, c'est l'heure de l'article update, même s'il va être très court*. Alors accroche toi à ton slip, on est parti.

[Unity3D] 50 jours de devs, pour un builder game - Annonce et résumé du jour 1

Yo, ça faisait un moment non?

Bon, on va faire simple. Hier, j'ai annoncé sur twitter que je me lançais un "défi" avec Unity: commencer un projet de jeu et travailler tous les jours au moins une heure pendant 50 jours. Et pour faire d'une pierre deux coups, j'ai choisi de m'orienter sur la création d'un jeu de construction/gestion de ville, dans le style des Zeus, Banished ou encore SimCity.

Alors bien sûr, je ne m'attends pas a avoir un jeu complet en 50 jours, loins de là, mais mon but est d'arriver à m'investir dans un projet perso, et de progresser le plus loin possible dans tous les aspects qu'il touche. J'espère pouvoir arriver à quelque chose de fonctionnel et de testable, mais on verra bien où cela mènera.

Dans un premier temps je compte utiliser des assets gratuits du Unity Store, mais à terme, j'aimerais modéliser mes propres batiments sous Blender, et pourquoi pas faire aussi la musique. Tout cela me permettrai d'en apprendre plus sur comment créer un jeu vidéo, et au final c'est quelque chose que j'ai toujours eu envie de faire.

Donc voilà, j'ai réfléchi au concept, mûri l'idée, et j'ai décidé hier soir de me lancer les trois pieds dedans. Je posterai ici les avancées de chaque jours, pour ceux que ça intéresserai de suivre. Je ferais aussi régulièrement certaines sessions en live, au moins deux fois par semaine je l'espère. Enfin, le code sera disponible en open-source a cette adresse: https://github.com/macmist/unity-builder. Pour les développeurs parmi vous, vous aurez l'occasion de tester, et pourquoi pas forker le projet et travailler sur vos propres variations si le coeur vous en dit.

Voilà donc pour la partie annonce, maintenant, place au résumé d'hier soir.

La première session d'hier soir, faite en live, avait pour but de poser les bases du projet. Réfléchir a quoi mettre dans le jeu, quelles fonctionnalités, quelles interfaces, quels objets etc. Ici je me suis limité à quelque chose de basique. Je ne cherche pas a faire le prochain jeu futuriste aux douze mille fonctionnalités inédites que tout le monde va s'arracher, mais juste à apprendre et progresser.

Le jeu sera donc un jeu de construction de ville très inspiré de Zeus. Il y aura un terrain avec une grille, sur laquelle on pourra placer des routes et des bâtiments. Construire un bâtiment coutera de l'argent, et certains d'entre eux permettront d'en gagner sur le temps. L'autre ressource du jeu sera les habitants, qui permettront de faire marcher les bâtiments. 

Il y aura trois voire quatre types de bâtiments: habitation, usine, centre d'impôts et peut être poste de commerce.

Il sera possible d'avoir des informations sur les batiments et habitants en cliquant dessus.

Les habitants disposeront d'une jauge de contentement, pour le moment simplement liée au montant des impots, qui fera monter ou baisser la productivité.

Enfin, des évènements pourront survenir comme des séismes ou des incendies.

Bien sûr si le temps le permet, d'autre fonctionnalités seront ajoutées.

La seconde partie du live a consisté a regrouper ces fonctionnalités par type et de réfléchir a l'ordre dans lequel leur développement se fera.

Pour plus d'informations à ce sujet je vous invite a regarder directement le lien github de tout à l'heure.

Voilà pour ce premier jour. J'espère que l'aventure vous tente, n'hésitez pas à me donner vos avis ou a suggérer des choses a ajouter si vous pensez à quelque chose qui n'est pas dans la liste.

Sur ce je vous dit a tout a l'heure ou demain pour le résumé de mon travail du jour, des bisous!

[Unity3D][Donjon] Génération procédurale d'un donjon

Certains l'ont peut être déjà vu sur ma chaîne youtube, je me suis lancé dans l'aventure de créer pas à pas un générateur de donjon sous Unity3D. Je le fais en live sur ma chaine twitch avec des rediffusions sur youtube.
C'est un sujet vraiment intéressant, qui soulève pas mal de problématiques, et j'essaie tant bien que mal de les résoudre. J'apprends beaucoup en le faisant, et j'apprends encore plus en essayant de le retranscrire, d'expliquer ce que je fais en live.
D'abord, comment créer une pièce, puis comment répartir toutes les pièces dans l'espace, comment représenter un donjon, comment ajouter des couloirs, comment faire en sorte qu'il n'y ait pas d'impasse, comment éviter la redondance, comment passer de la 2D à la 3D.
Toutes ces choses sont vraiment intéressante et essayer d'y répondre apprend beaucoup! Je vous invite dors et déjà à suivre cette aventure, sur ma chaine twitch en live, ou sur les replays disponibles dans cette playlist:

Et le projet est disponible ici: https://github.com/macmist/Unity-Roguelike/
Mais toutes ces problématiques ne sont que le début, la partie émergée de l'iceberg, par la suite de nombreuses autres pourront survenir:
Comment remplir les salles, comment éclairer, où placer les monstres, quels comportements leur donner, qu'est ce que le joueur pourra faire, tout autant de choses intéressantes auxquelles nous pourront être confrontés. Alors si vous êtes intéressés, suivez l'aventure, participer, proposez vos problématiques, vos solutions, vivons ensemble cette aventure !

Merci d'avance à tous !