[UNITY3D] Sauvegarde/Chargement des personnages + recherche de chemin plus intelligente

Hé salut ça faisait longtemps!
Et non le projet n'est PAS oublié, simplement, soyons honnête, j'ai passé plus d'un mois en vacances sans y toucher, donc le défi de 50 jours sans s'arrêter il est LEGEREMENT raté. Du coup je me fais plus chier à bosser dessus tous les jours, surtout que j'ai pas spécialement le temps pour en plus. Par contre, je bosse dessus dès que je peux, et je m'y mets au moins une heure à chaque fois, ça je le garde pasque bon ça je peux le faire. Et puis aussi, je vais écrire un article quand ce sera vraiment utile et qu'il y aura quelque chose à dire, pas juste: "hé j'ai passé deux heures a faire des mises à jour du coup j'ai rien fait en vrai lol tu l'aimes la carotte ou pas?"

La carotte

Enfin maintenant cette introduction passée, voici venu le temps de vous faire part des dernières avancées. Et bon, ben autant vous dire que je suis plutôt content de ce que j'ai pu ajouter récemment.
Comme vous l'avez vu dans le titre, les personnages sont maintenant sauvegardés et chargés proprement. Et ça, c'est top. Mais c'était pas si facile que ça, et c'etait un peu le truc qui me rebutait et que j'ai repoussé peut être un peu trop longtemps avant de finalement m'y pencher. Pourquoi c'était difficile, allez vous me dire? Et je suis content que cette question soit posée, car c'est exactement ce à quoi je comptais répondre. Le hasard du monologue de blog fait bien les choses quand même.

Comme expliqué précédemment, nous avons trois listes: la liste des humains, celle des humains sans maison, et celle des humains qui ont une maison. Quand une maison est posée, 5 humains y sont assignés et se dirigent vers cette maison. Ils sont ajoutés alors a la liste des humains et a celle des humains sans maison. Une fois arrivés a leur destination, ils sont enlevés de la liste des humains sans maison et sont rajoutés a celle des humains avec maison.

Jusque là rien de bien difficile. Mais pour plus tard, j'ai pour intention de faire en sorte que, en cliquant sur une maison, on puisse voir tous les humains qui y sont assignés. Donc pour cela, chaque maison possède elle aussi une liste d'humains. Pour simplifier, regardez le schéma suivant:

Schéma simplifié

Un humain possède une maison comme cible, et une maison possède une list d'humains comme habitants. Et là, pour sauvegarder, ça coince. Pourquoi? Hé bien simplement parce que le mecanisme de sérialization se contente de parcourir chaque objet et de le stocker tel quel. Ce qui veut dire que si on stocke un humain, il va donc stocker le champ "target" complet, donc une maison entière. Or la maison, elle, possède une liste d'humains. Donc en stockant la maison il va stocker tous les humains que la maison contient. Et donc pour chaque humain, il va restocker la maison (puisque pour chaque humain habitant, Target sera toujours cette maison). Et donc il va restocker la liste d'habitants. Et ainsi de suite. On est ici rentré dans une boucle infinie d'appel, où tout va etre stocké un nombre infini de fois. Et ça, ben on veut pas.

Alors heureusement, Unity est assez intelligent pour repérer ce genre de cas et s'arreter de stocker a partir d'un certain palier. On evite ainsi de faire planter le programme et aussi d'avoir un fichier de sauvegarde de 1200223454 To pour seulement trois cubes. Mais ça ne résout en rien le problème en fait. Heureusement, pour ça il existe une méthode assez simple, qui est de générer un identifiant unique a chaque humain et maison, et de stocker ces identifiants plutôt que les objets complets. Ainsi on évite les boucles infinies, on ne stocke chaque objet qu'une fois et une seule. Le schéma ressemble a ceci à la fin:

Schéma simplifié corrigé

Pour information, cette méthode d'identifiant unique est utilisée assez fréquemment dans le monde de l'informatique, notamment dans les systèmes de base de données. En effet ce système permet de récupérer rapidement un élément dans un grand ensemble, plutôt que d'avoir a parcourir manuellement tous les éléments un à un pour trouver le bon.
Et le chargement se fait ensuite tout seul, il n'y a plus qu'a récupérer les positions des objets, et dire a chaque humain où se diriger.


La seconde chose sur laquelle j'ai travaillé est le déplacement des humains. Avant, ils se contentaient de foncer en ligne droite vers la maison, en ignorant tout sur leur passage. Maintenant, ils éviterons arbres et autres maisons, et privilégieront la route s'ils en trouvent une dans leur direction. Pour ce faire j'ai simplement réadapté l'algorithme de recherche de chemin qu'on avait mis en place pour créer la route. J'ai juste eu a faire en sorte d'ignorer les arbres et les maisons, et de donner un cout moins élevé aux routes qu'aux morceaux d'herbes. Ainsi, voici ce que ça donne:

Du coup voilà, nos humains commencent à être un poile moins bêtes, et ça c'est cool. Prochaine étape, leur donner un endroit où travailler. Je pense. Je suis pas sûr.

En tout cas, c'en est fini pour cet update, j'espere que ça vous aura plus. N'hésitez pas à me dire ce que vous en pensez, si c'est pas trop technique aussi pasque je me pose toujours la question. Ou au contraire si ça ne l'est pas assez dites le aussi. Et en tout cas merci pour votre attention, et a très vite pour d'autres aventures chocolatéss.

[Unity3D][Jour 17] Des gens

Salut les blogouzes ça roule?

Aujourd'hui j'ai pas chomé, j'ai bien avancé sur le jeu malgré une envie proche de zéro et un mal de crâne des enfers. Enfin c'est pas ce qui vous intéresse, vous ce que vous voulez c'est en savoir plus sur le jeu, parce que hein voilà bon bref ok j'arrête.

La nouveauté du jour, c'est la gestion des ressources. Enfin d'une ressource en particulier: les gens. En gros, j'ai créé un nouveau préfab que j'ai appelé "human", qui est juste un cylindre bleu (z'avez jamais vu des humains comme ça?). Lorsqu'il est créé a l'écran, on va lui assigner deux choses: une vitesse de déplacement, et une cible. Et son rôle, et bien ce sera simplement d'avancer vers la cible à sa vitesse jusqu'a l'atteindre.

Un humain

Alors oui, ça prend deux secondes à expliquer, mais en vrai, ça a pris plus d'une heure à mettre en place, entre le fait que je savais pas comment ça marchait sous Unity, et le fait de trouver une architecture de code pas trop dégueulasse et réutilisable, ça prend du temps.

Mais bon, maintenant que j'ai ça, on peut commencer à faire spawner des humains ! Et comment on fait ça? Ici j'ai fait quelque chose de très simple pour commencer, j'ai arbitrairement décidé qu'une maison pouvait contenir 5 habitants, et du coup, chaque fois qu'une nouvelle maison est créée, on crée aussi 5 humains, à qui on va donner pour cible cette maison. Et puis voilà quoi. Pour mieux comprendre l'idée, regardez le gif qui suit:

Et voilà le travail! Bon alors, ils foncent tout droit meme au travers des arbres, ils viennent tous du meme coin, mais l'important c'est que ça marche, il ne faut pas oublier que c'est juste un prototype pour le moment! En tout cas on commence à avoir un prototype qui à l'air un peu vivant, et ça, c'est ultra classe :D Vous remarquerez aussi qu'une fois arrivés sur place, le compteur "people" s'incrémente, histoire qu'on sache combien la ville a d'habitants.

Du coup, c'est tout pour aujourd'hui, la prochaine étape sera de faire un déplacement un poil plus intelligent, par exemple suivre une route, ou éviter les arbres.

Sur ce des bisous les blogouzes, a la prochaine!

[Jour 16] C'est à cette heure ci que tu rentres?

Oui, je suis de retour, douze ans plus tard. Ok j'ai dit que j'allais faire 50 jours d'affilée, mais j'ai jamais dit que y'aurais pas de pauses

Bref, cet article sera assez court parce que ben, j'ai passé douze ans a faire des mises a jour en fait, mais j'ai repris. J'ai changé la maniere dont les arbres sont gérés. Avant, un arbre, c'était un bloc de terre avec un arbre dessus. Maintenant un arbre, ben c'est un arbre.

J'ai du refactoriser beaucoup de code, mais du coup, maintenant, on a des arbres qui sont posés sur les blocs de terre, et donc que l'on pourra retirer par la suite. Je me suis dit que ça pourrait être utile un jour.

Voilà article terminé, le prochain objectif, c'est de faire en sorte de faire rentrer de l'argent :) A bientard

[Unity3D][Défi50Jours] Jour 15 - ARJEN

Bonjour, aujourd'hui on va parler d'un truc important: l'ARJEN

Alors, oui j'ai pas donné de nouvelles pendant plus d'une semaine, mais j'étais pas là et après j'étais malade, du coup j'ai pas bossé. Mais je suis revenu, et c'est pas important, l'important comme je vous l'ai dit, c'est l'ARJEN, avec un grand J.

Car oui, ça y est, après une grande session d'environ 4h, j'ai ajouté le système de POGNON, de FLOOZ, le système capitaliste comme tu l'aimes. Tu veux poser une maison? OK, mais maintenant va falloir PAYER mon gars et ouais. Une route? Crache tes biftons. T'as plus d'ARJEN? Ben tant pis, tu verras tout rouge, et tu posera plus rien. Faudra attendre la prochaine maj avant de pouvoir regagner du POGNON, déso pas déso.

Du coup, la partie commence avec 1000 d'ARJEN, et une portion de route coute 5 ARJEN tandis qu'une maison en compte 100. Voyez-ci après des exemples d'utilisation de l'ARJEN.

PLINDARJEN.jpg

PUDARJEN.jpg

Et bien sûr tout est sauvegardé, comme ça si tu es pauvre, tu seras toujours pauvre en revenant. MALINX LE LINX

Pour expliquer vite fait comment ça marche, j'ai créé une classe ressource, qui a comme paramètre un nom et une quantité. J'y ai ajouté une fonction d'ajout qui ajoute simplement un nombre à cette quantité.

Dans la classe Game, j'instancie un objet Resource, avec les paramètres de départ "ARJEN" et 1000. Vous pouvez aussi voir qu'il y a un objet instancié avec les paramètres "people" et 0, mais pour l'instant on s'en sert pas.

Ensuite, sur la classe bâtiment, j'ai ajouté une variable "cout" avec une valeur par défaut a 5. J'ai ensuite créé une fonction "Create" que l'on va appeler lorsqu'on pose l'objet sur le sol, qui s'occupe simplement d'enlever la valeur cout au total de l'ARJEN. Ensuite, pour les Maisons, qui sont une extension de la classe Bâtiment, j'ai simplement changé le cout à 100.

Ensuite, la partie un peu plus dure, c'est de rester au dessus de zéro. Dans la partie qui sert à poser les objets, il faut faire plusieurs choses:

- détecter le type de l'objet en sélectionné

- le peindre en rouge si son coût est supérieur à l'ARJEN restant

- ne pas poser si l'objet est en rouge, poser et appeler la fonction Create de l'objet sinon

Bon, pour les maisons c'était simple, par contre pour les routes, hummm. Le principe est le même, sauf que, comme il y a un cliqué glissé, il faut effectuer ces opérations a chaque mouvement de la souris, et sur le nombre total de routes affichées. Et enfin, lorsque l'utilisateur relâche le bouton, si on était en rouge, il faut supprimer les routes. Je vous épargne le code en lui même, mais autant vous dire que tout ça a demandé beaucoup de temps et d'essais, mais maintenant tout marche.

Dernière chose importante, montrer l'ARJEN à l'écran. Bon là c'est tout moche, parce que y'a toujours pas d'UI, mais l'ARJEN c'est l'ARJEN, UI ou pas.

Du coup voilà qui conclut notre article du jour. On a de plus en plus quelque chose qui ressemble à un jeu ! La prochain étape du coup, c'est de pouvoir faire rentrer de l'ARJEN, avec notamment l'ajout de micro-transactions centres des impôts par exemple.

Sur ce des bisous, et à la prochaine! 

[Unity3D][Défi50Jours] Jour 14 - Le jeu des devinettes

Salut lecteur.

Aujourd'hui j'ai la flemme de faire un grand article, alors on va jouer à un jeu ok? Ok, de toute façon soit tu joues le jeu soit tu t'en vas j'ai dit que j'allais pas écrire hein.

Donc voilà le jeu: je mets un gif, et tu devines ce qui a été ajouté durant la dernière session. Prêt?

Superjeu.gif

Ca devrait être assez facile. Et niveau code rien qui n'a pas déjà été vu, c'est aussi pour ça que je vous épargne le blabla. Alors, vous avez deviné?

Dites le moi dans les commentaires

Des bisous, la prochaine session on fait vraiment l'UI c'est promis.

PS: il n'y aura pas de sessions de vendredi à lundi inclus, je serais en déplacement et je n'aurais pas de pc

[Unity3D][Défi50Jours] Jour 12 et 13 - Améliorations et maisons

Coucou.

Alors oui déso j'ai pas touché au truc ce weekend, et je n'ai pas non plus posté d'updates depuis quelques jours. J'avais la flemme, je fais des journées longues tu sais? C'est compliqué la vie, surtout qu'après le boulot je dois rentrer, me faire à manger, et jouer aux jeux vidéos, du coup c'est dur de trouver du temps !

Mais soit rassuré, toi, lecteur avisé, je suis de retour ! J'ai bel et bien bossé lundi et hier, et oui, j'ai avancé! J'ai même sûrement rattrapé mon retard vu que j'ai fait deux sessions de 3h environs. Et quoi de nouveau vas-tu me demander? Hé bien nous l'allons voir tout de suite.

[Unity3D][Défi50Jours] Jour 11 - Sauvegarde/chargement des routes

Yo.
Hier, c'était encore une session assez courte malheureusement, il y a eu une soirée imprévue avec le boulot et qui a duré des plombes, du coup je n'ai pas eu le temps que je voulais pour coder.
Mais j'ai quand même une bonne nouvelle, la pose des routes est maintenant finalisée :)

Hier, pendant le peu de temps que j'ai eu pour coder, j'ai tout de même pu mettre en place le système de sauvegarde et chargement des routes.

Pour faire simple, jusque là nous avions l'objet TileObject, qui représentait un point de notre map, avec sa position et son type (Grass, Dirt...). Ici, j'ai créé un nouvel objet nommé BuildingObject, qui pourra être utilisé pour tous les types d'objets posable sur la map. Il contient le type de building ainsi que son orientation. Et il suffit ensuite de dire que chaque TileObject peut maintenant contenir un BuildingObject.

Lors de la construction de chaque morceau de route, on va créer le BuildingObject correspondant et on l'ajoute au TileObject qui se situe sous cette route. Pour supprimer une route, il faudra d'abord supprimer à l'écran le GameObject route, puis supprimer le BuildingObject contenu dans le TileObject correspondant. Et une fois fais, tout se sauvegarde.
(A noter que la manière de sauvegarder les objets est pour l'instant adéquat car un morceau de route fait la taille d'une case, mais si on se met en tête de faire des bâtiments qui peuvent faire plusieurs cases de long ou de large, il faudra peut être changer ce système pour autre chose.)

Pour ne pas conserver les routes à l'écran lorsqu'on change de map, il suffit de supprimer tous les BuildingObject contenus sur la map.

Ensuite, pour le chargement, lorsqu'on instancie chaque case de notre Map, on vérifie si un BuildingObject existe, et ci c'est le cas on instancie le préfab correspondant et on lui applique une rotation en fonction de la direction qui lui est assignée.

Sauvegarde/chargement exemple

Et c'est tout! C'est assez simple au final, ça marche comme il faut, et du coup maintenant on a tout ce qu'il nous fallait pour les routes. Du coup la prochaine étape, ça va être la gestion des ressources, et la pose d'autres type de buildings, avec l'interface et tout et tout. A très vite pour l'update du jour 12!

[Unity3D][Défi50Jours] Jour 10 - Pose de routes à la souris

Bon, je vais être honnête, aujourd'hui j'étais trop défoncé pour faire une heure complète. Cependant, j'ai quand même pu avancer sur les routes et ajouter la fonctionnalité pour créer des sections de routes à la main.
Du coup l'article d'aujourd'hui va être très court, mais c'est pas plus mal pour une fois :)


Pour expliquer comment marche ce système, lorsqu'un clic est détecté, on créée un  Nœud de départ à la position de la souris. On créée par la même occasion un noeud de fin. Puis tant que le bouton est enfoncé, si la position de la souris change, on change aussi la position du noeud final, et on créée la route en appelant A* et la fonction de traçage de route.

Lorsqu'on change la souris de place d'une case, le chemin calculé ne passe plus forcément par le même endroit que celui calculé pour la case précédente. Et du coup si on se contente d'afficher la route à chaque fois sans rien faire d'autre, on se retrouve vite avec tous les "essais" de chemins sur la carte, et c'est très moche.

C'est bien mais pas top

Il faut donc supprimer à chaque fois ces chemins. La solution la plus simple est de garder dans une liste tous les blocs instanciés, et à chaque fois que la souris bouge, on supprime tous les blocs et on vide la liste, avant d'afficher la nouvelle route et d'y ajouter les nouveaux blocs.

Là on est pas mal

Enfin, comme vous pouvez le constater, le dernier problème à résoudre est qu'avec ce système de liste, on efface la route actuelle si on essaie d'en poser une nouvelle. Pour résoudre ce problème, il suffit de créer une nouvelle liste à chaque fois qu'un clic est détecté, et d'effectuer les mêmes étapes que précédemment sur cette nouvelle liste.

Et voilà le travail :) Ce n'est pas encore tout à fait parfait, mais ça marche déjà très bien et fait ce qu'on veut. Et c'est très visuel donc j'ai pu faire péter les gifs. Du coup je suis plutôt très satisfait!

Le résultat final qui pète des culs

Voilà, comme convenu, un billet très court, mais avec un résultat bien visible. J'espère que ces progrès vous hypent autant que moi. N'hésitez pas à laisser vos remarques, impressions, conseils, questions, et à partager ça fait toujours plaisir, des bisous poilus

[Unity3D][Défi50Jours] Jour 9 - amélioration des routes

Salut les petits protozoaires euclidiens c'est l'heure de l'update numéro 2 après 7 !

Hier, on avait fait des routes, en utilisant A*. A la fin ça marchait, sauf qu'on n'avait que des diagonales, et ce n'est pas très optimal pour un jeu de gestion de ville. Dans ma dernière session, je me suis donc attaqué à les rendre moins diagonales et plus réaliste.

Pour ça, il a fallu faire quelques modifications sur notre classe Noeud. Souvenez vous, jusqu'ici il comportait sa position, son coût et une référence vers le noeud qui le précède. Ce que nous allons faire ici, c'est altérer la fonction de calcul de coût, notre Heuristique, pour que ce coût soit plus élevé lors d'un changement de direction. Pour ce faire il a simplement fallu ajouter un champ direction à notre objet Noeud. Puis, dans le calcul du coût, si la direction du noeud actuel est différente de celle de son noeud parent, alors on augmente la valeur du coût. Ici j'ai arbitrairement ajouté une valeur de 10.
Ce qui a pour effet que le noeud choisi sera toujours dans la même direction que le noeud précédent, sauf en cas de rencontre d'obstacle, ou si le chemin devient vraiment plus rapide en tournant.


L'étape d'après a été de faire en sorte de ne pas prendre en compte les obstacles. Pour ça, rien de plus simple, lorsque l'on récupère les voisins d'un noeud, si l'un des voisins est un obstacle, on l'ignore.
Maintenant, on a des belles routes qui serpentent à travers la forêt.

Ensuite, j'ai créé une sublime texture de route via Gimp, et l'ai appliquée au préfab de route. Le résultat est plutôt pas mal, même si j'ignore pourquoi la bande blanche se répète sur les six faces du
pavé.

La super texture de route

La super route

Une fois fais, j'ai fais en sorte qu'à la création de la map, deux points soient sélectionnés aléatoirement, en faisant attention à ce que ce ne soient pas des obstacles, puis j'ai tracé une route entre ces deux points. Et voilà un exemple de résultat:

Random route

Sympa non? Pour les plus observateurs, il reste encore un léger souci: les routes sont toutes orientées dans le même sens, et du coup discontinues... Mince, comment faire? Oh zut je me demande...

Hé bien vous vous souvenez de cette variable direction ajoutée au noeud? Il suffit d'orienter la route en fonction de cette direction et le tour est joué :) Par défaut, la route est posée de telle sorte que sa longueur soit à l'horizontale. Pour les directions gauche et droite, il n'y a rien à faire en plaçant la route, et pour les directions haute et basse, une simple rotation de 90 degrés suffit. Ensuite on lance, et TADAAAA.

Random route mais mieux

Voilà, une vraie route (bon mis à part les angles mais on verra ça plus tard). Ca fait bien plaisir, et en seulement 9 jours de dev, on a un résultat visible, assez propre, et plutôt bien satisfaisant. La prochaine étape sera de mettre en place la sauvegarde de ces routes, puis de faire en sorte de pouvoir placer les routes avec un clic long de la souris. Et on aura fini avec les routes ! :)

Je suis assez excité pour ce qu'il y a à venir, et j'espère que vous aussi. Comme d'habitude, n'hésitez pas à me faire part de vos remarques ou questions si vous en avez, et si vous aussi voulez vous lancer un défi de ce genre, foncez, car ça fait vraiment du bien de voir un projet se construire ainsi.

Sur ce des bisous carabistouillés.

[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!