Je crée mon jeu vidéo E11 : génération procédurale de carte (partie 2)

Posté par . Édité par Benoît Sibaud, palm123 et Xavier Claude. Modéré par patrick_g. Licence CC by-sa
Tags :
53
28
avr.
2014
Jeu

«Je crée mon jeu vidéo» est une série d'articles sur la création d'un jeu vidéo, depuis la feuille blanche jusqu'au résultat final. On y parlera de tout : de la technique, du contenu, de la joie de voir bouger des sprites, de la lassitude du développement solitaire, etc. Vous pourrez suivre cette série grâce au tag gamedev.

Dans l'épisode 10, on a fabriqué des cartes d'altitude avec diverses méthodes et divers opérateurs qui permettent de rendre la carte plus réaliste. Dans cette deuxième partie de ce double épisode consacré à la génération de carte pour un RPG, on va décorer notre carte.

Sommaire

En retard

Avant toute chose, cet épisode a pris beaucoup plus de temps que prévu. La fatigue de la vie quotidienne est un élément qu'il ne faut jamais sous-estimer, surtout quand elle s'accumule. Elle réduit considérablement la capacité à avancer, malgré une motivation intacte. C'est ce qui m'est arrivé ces dernières semaines, ce qui a provoqué un énorme retard. Pourtant, les tâches étaient simples et claires, il y avait un peu de travail algorithmique, comme nous allons le voir, mais rien de vraiment insurmontable. Juste qu'une fois devant le clavier, je n'arrivais plus à taper les choses efficacement, tout mettait des heures alors que ça aurait dû mettre quelques minutes.

Les vacances actuelles seront sans doute profitables pour me remettre sur les rails. En tout cas, elles m'ont déjà permis de finir cet épisode, même s'il est assez loin de ce que j'avais imaginé au départ. Parce qu'il reste du travail sur ce sujet.

Rappel de l'objectif

L'idée de ce double épisode est d'être capable de générer des cartes pour un RPG. Plus précisément, on utilisera notre carte comme un fond, étant donné que le jeu utilise la vue de dessus. Ça veut donc dire que cette carte sera très présente sur l'écran et qu'il faut la préparer au mieux. Pourquoi la générer ? Il ne s'agit pas ici de générer toute la carte dans ses moindres détails, mais simplement de produire un canevas assez précis qui puisse être manipulé par la suite. Toute la question est dans cette précision.

Le premier épisode permettait de générer une carte d'altitude, ce qui est une première étape essentielle. Cette carte d'altitude avait de bonnes caractéristiques, par exemple en terme de déplacement possible des unités, ce qu'on avait matérialisé par le score de jouabilité. On avait donc à notre disposition une carte d'unité dont on va se resservir ici.

La carte de base

Pour cet épisode, on va voir trois aspects essentiels : la génération des rivières, la génération des biomes, la génération des formes de collision. Puis on discutera de ce qu'on peut apporter de plus.

Les étapes de construction

Génération des rivières

La génération des rivières est sans doute la partie la plus facile. Il s'agit d'ajouter à notre carte des rivières pour la rendre un peu plus réaliste. Et puis le franchissement de rivière peut devenir une activité importante quand on joue à un RPG.

L'algorithme utilisé ici est extrêmement simple, tout en donnant des résultats pas trop mauvais. L'idée est de partir d'un point en altitude (on peut fixer l'altitude minimale) puis de suivre la pente la plus forte jusqu'à arriver à la mer. Ça a l'air simple comme ça mais ça ne l'est pas. Parce qu'il se peut que l'eau se retrouve piégée dans un minimum local, et il faut donc savoir comment sortir de ce minimum local sans effondrer les performances de la génération.

La solution la plus efficace est d'utiliser une file de priorité. Pour chaque case ajoutée à la rivière, on ajoute toutes les cases adjacentes à la file avec comme priorité l'altitude la plus faible. Ainsi, on a toujours en tête de file la case qui permet de descendre le plus. Ainsi, quand on se retrouve dans un minimum local, cet algorithme va permettre de faire monter l'eau petit à petit jusqu'à trouver un endroit par où descendre un peu plus. On crée ainsi des lacs naturels.

Ensuite, on itère un certain nombre de fois pour avoir plusieurs rivières. Si on repart à chaque fois de la carte initiale, certaines rivières vont parcourir les mêmes cases, créant ainsi des affluents.

La carte avec des rivières

Voilà ce que ça peut donner avec vingt rivières. On voit en particulier le lac qui s'est créé au nord-est et comment la rivière longe la colline. Et on observe aussi qu'avec six rivières, on arrive à former un fleuve avec ses affluents à l'ouest.

Génération des biomes

Un biome est, d'après Wikipédia, «un ensemble d'écosystèmes caractéristique d'une aire biogéographique et nommé à partir de la végétation et des espèces animales qui y prédominent et y sont adaptées». Un biome est caractérisé par un climat, lui-même étant associé à des températures et des précipitations. Pour savoir quel biome correspond à quelle fourchette de températures et de précipitations, on utilise généralement le diagramme Whittaker.

Sur notre carte, nous n'avons ni températures, ni précipitations. Mais nous avons des altitudes et des rivières ! On va considérer que plus on monte en altitude, plus il fait froid. En vrai, la température baisse entre 0.6 et 1.0°C tous les 100m, donc l'approximation n'est pas si insensée. Il reste donc à calculer l'humidité, et là, on va considérer que plus on est loin d'un point d'eau (rivière ou mer), moins on est humide. Pour cela, on fait un parcours en largeur de toutes les cases, en commençant aux points d'eau et on décrémente l'humidité petit à petit.

La carte d'humidité

On obtient une carte d'humidité : plus c'est clair, plus c'est humide. Et inversement, les zones sombres indiquent des zones très sèches.

Ensuite, en fonction de l'altitude et de l'humidité, on doit déterminer un biome. On s'inspire pour cela du diagramme de Whittaker qu'on adapte. J'ai utilisé la même adaptation que celle du tutoriel d'Amit Patel. On peut le visualiser de la manière suivante.

Les biomes

En abscisse, on a l'humidité (plus on va à droite, plus c'est humide), et en ordonnée, on a l'altitude (plus on va en haut et… plus on monte logique). Chaque couleur représente un biome différent. Depuis les forêts tropicales jusqu'au sommets enneigés, en passant par les steppes, tout y est à peu près.

Reste ensuite à appliquer les biomes en fonction de la carte d'altitude et de la carte d'humidité qu'on vient de calculer. Et tadam !

La carte des biomes

Ou, si on veut une version avec du relief :

La carte des biomes en relief

On se rend compte que la zone quasi-désertique au sud-est correspond à une dépression où il n'y a pas de rivière. On voit également les montagnes qui se dégagent avec les zones neigeuses.

Générations des formes de collisions

Un des objectifs de cette génération de carte est de pouvoir générer automatiquement les formes de collisions. Parce que les faire à la main peut être assez long et fastidieux. Dans l'épisode précédent, on avait vu comment on générait une carte d'unité, c'est-à-dire un ensemble de cases accessibles à une unité dont on précise à la fois la taille (en nombre de cases) et la capacité à franchir les pentes.

La carte d'unité

La carte d'unité est donc une carte binaire. Il reste à déterminer les polygônes qui forment les contours infranchissables, c'est-à-dire la limite des zones blanches et noires. Je dois avouer que c'est un des algorithmes qui m'a demandé le plus de réflexion et dont je suis assez fier. Voici comment j'ai procédé.

Pour chacune des cases accessibles (les cases blanches), j'ai ajouté quatre arcs orientés qui représentent le contour de cette case à un premier ensemble E1. Toutes les cases sont orientés dans le même sens, ici le sens des aiguilles d'une montre. Ensuite, il faut enlever des arcs pour ne garder que ceux des contours des zones blanches. L'idée est ici d'enlever les arcs (A,B) tels que l'arc (B,A) fait également partie de l'ensemble E1. En effet, si on trouve ces deux arcs, c'est qu'ils ont été ajoutés par deux cases adjacentes et donc, ils font partie de l'intérieur de la zone. Nous obtenons alors un ensemble E2 qui contient tous les contours mais en petits morceaux. Dernière étape, il faut donc reconstituer les contours ! Pour ça, tant que E2 n'est pas vide, on prend un arc, puis on cherche le ou les arcs qui ont comme origine l'extrêmité de cet arc.

Un contour

Je dis «le ou les» parce qu'il se peut qu'il y en ait deux, dans le cas où deux cases sont reliées uniquement par un sommet, comme on peut le voir sur la figure ci-dessus. Il faut alors faire un choix non-aléatoire : un choix aléatoire pourrait nous faire tourner en rond assez longtemps. Pour maximiser la taille du contour, on choisit de toujours tourner à gauche. Comme on parcourt le contour dans le sens des aiguilles d'une montre, on inclut dans chaque zone les cases qui sont reliées uniquement par un sommet et donc on minimise le nombre de contours. On itère tout ça et on obtient nos contours.

Cet algorithme est assez efficace si on prend garde à utiliser les bonnes structures de données et les bons algorithmes. S'il y a n1 cases accessibles, c'est-à-dire 4*n1 arcs dans l'ensemble E1, la construction de E2 peut se faire en O(n1 log n1), grâce à un tri préalable des arcs, puis à une recherche dichotomique pour essayer de trouver l'arc inverse pour chaque arc. Ensuite, s'il y a n2 éléments dans E2, on peut reconstruire les contours en O(n2 log n2) de la même manière, c'est-à-dire en triant les arcs et en faisant une recherche dichotomique pour trouver le ou les prochains arcs. Au final, on n'est jamais quadratique, ce qui est une performance tout à fait honorable à mon sens.

Cette fois, on a tout ce qu'il nous faut en terme de données.

La carte prête à l'emploi

Il faut désormais générer la carte prête à l'emploi, c'est-à-dire au format TMX de Tiled, et plus précisément avec les conventions retenues pour le jeu lui-même.

Le problème fondamental

Tiled est un très bon logiciel et il permet de faire plein de choses. Il a notamment une brosse qui permet de créer des «terrains» de manière très facile, une fois qu'on a indiqué sur le tileset quel morceau de tuile était associé à quel terrain. La brosse est capable de générer des gros morceaux de carte de manière à ce que les cases adjacentes de la carte aient des terrains identiques. Tout ceci est bien expliqué dans un tutoriel pour créer les terrains et utiliser la brosse.

Pour pouvoir bénéficier de cette fonctionnalité le jour où on passera à l'édition manuelle de la carte, il nous faut deux choses. Premièrement, déterminer les terrains. Ça, c'est la partie facile, parce qu'on peut identifier les biomes aux terrains et donc, on a autant de terrains que de biomes. Deuxièmement, il faut avoir un tileset adapté à cette brosse. Et ça, c'est la partie difficile. Parce qu'on voit bien dans le tutoriel que ce qui marche bien, c'est quand la limite entre deux terrains est sur la tuile, puisque c'est ça qui va permettre à l'outil de pouvoir générer des zones complètes.

Or, notre carte, pour l'instant, ce sont uniquement des cases monochromes. Au départ, j'avais pensé à modifier la carte pour étendre certaines zones d'une demi-case. Ça permettait notamment d'élargir les rivières facilement. Le problème, c'est qu'on arrive très vite à des cas particuliers impossibles à démêler. On doit prendre en compte au moins les huit cases adjacentes (directement ou par un coin) et donc, si on prend en compte qu'on peut avoir autant de biomes que de cases, ça fait un nombre de cas beaucoup trop importants. La solution est toute bête, il suffit de décaler notre grille d'une demi-case suivant les deux axes ! Et pour faire simple, on sacrifie une rangée sur le bord. Ainsi, toutes les limites de biomes sont maintenant au milieu des cases.

Notre nouvelle carte est alors composée de tuiles, elles-mêmes découpés en quatre parties qui ont les couleurs de quatre cases de la carte originale. Évidemment, on va trouver toute sorte de tuiles et il va bien falloir déterminer le tileset.

Détermination du tileset

Comme notre carte est générée, il faut également générer le tileset qui sera utilisée pour la carte. Pour ça, il faut déterminer l'ensemble de tuiles qui a été utilisé. Au départ, on place déjà dans le tileset les tuiles pleines qui seront les référents pour chacun des terrains et qui les identifie dans Tiled.

Ensuite, on parcourt toute notre carte et pour chaque tuile nouvelle, on l'ajoute à notre ensemble de tuiles. Puis, une fois qu'on a fini, il ne reste plus qu'à générer l'image avec toutes les tuiles, comme les attends le format TMX. Ici, en l'occurrence, les tuiles font 32x32 à l'affichage mais à cause d'un pseudo-bug, les tuiles font en fait 34x34. Le bug provoquait des petits défauts d'affichage, on voyait notamment la couleur de la tuile voisine à la limite des tuiles, ce qui était assez désagréable. Je crois avoir lu que ce bug vient d'une erreur d'arrondi dans les nombres flottants, voilà pourquoi je parle de pseudo-bug. La solution que j'avais trouvée à l'époque, c'était d'agrandir mes tuiles d'un pixels, ce qui permet de masquer ces petits défauts.

Touche finale, plutôt que d'avoir des limites de biomes uniquement horizontales et verticales, on peut modifier un peu les tuiles de manière à avoir des biseaux. Et ce n'est pas si simple. Il y a notamment le cas merdique où la tuile a deux couleurs mais disposées en diagonales. Dans ce cas, il faut donner la priorité à une des deux couleurs pour les joindre. C'est essentiel quand une de ces deux couleurs représente une rivière, on veut que la rivière soit continue. Je passe les détails qui tiennent parfois de la magie sur comment déterminer si on dessine un biseau ou pas, et je passe aussi sur la taille de ce biseau pour que les diagonales joignent parfaitement sans qu'on ne puisse voir les limites des tuiles.

Au final, on obtient ça :

Le tileset final

Évidemment, une fois ce tileset généré, rien n'empêche un artiste de l'améliorer comme bon lui semble. Mais cette version de base peut tout à fait convenir, dans un premier temps, pour le développement du jeu.

La carte finale dans Tiled

Ce moment où on ouvre la carte générée dans Tiled la toute première fois est un moment assez intense. On se demande si on a tout fait correctement, si ça va marcher, si ça ne va pas être trop gros pour Tiled. Et puis tadam, ça s'affiche et c'est merveilleux. Voici quelques captures d'écran pour montrer le résultat dans Tiled.

Tiled

Sur cette première capture, on voit les contours qu'on a calculés précédemment. On retrouve les formes qu'on avait dans la carte d'unité (ce qui est plutôt une bonne nouvelle). On peut également voir le tileset en bas à droite, avec les limites des tuiles, qui a été ajouté par Tiled, ce qui permet de mieux les distinguer.

Tiled

Sur cette seconde capture, on voit exactement le même endroit mais avec les biomes, c'est-à-dire ici l'ensemble des tuiles. En bas à droite, j'ai mis la vue où on peut voir tous les terrains.

Tiled

Sur cette troisième capture, j'ai zoomé sur une des rivières au nord pour observer les limites biscornues entre les biomes qu'on obtient avec les biseaux. Ce n'est pas si mal que ça, non ?.

La carte finale dans le jeu

Évidemment, la carte marche également dans le jeu. Pour vous convaincre, voici une petite capture d'écran avec Kalista à la plage. L'endroit correspond à la troisième capture dans Tiled, au nord de l'île.

Akagoria

Pour les contours, vous devez me faire confiance, ça marche aussi. Presque trop bien d'ailleurs, et nous allons en parler maintenant.

La suite !

Les zones inaccessibles

Dans le jeu, les zones inaccessibles sont bien inaccessibles, aucun problème pour ça. Malheureusement, ces zones ne sont pas distinguées visuellement des autres zones. Ce qui fait qu'on a l'impression de heurter des murs invisibles en permanence. C'est très désagréable. Je suis à la recherche d'un artefact visuel permettant de distinguer ces zones.

J'ai fait quelques essais qui sont pour l'instant non-convaincants. Le premier essai consistait à mettre par dessus chaque tuile inaccessible une autre tuile, partiellement transparente qui assombrissait la tuile du dessous. Outre le fait que ça ne rendait pas très bien visuellement, on n'avait pas l'impression d'une zone infranchissable mais plutôt d'un biome différent. Bref, solution abandonnée. Au second essai, j'ai essayer de placer des objets qui montrerait que la zone est infranchissable, en l'occurrence des cailloux. J'ai donc fabriqué une tuile avec trois cailloux. L'impression visuelle était nettement meilleure, et on distinguait bien la zone infranchissable. Mais avec une tuile unique, on avait des zones très géométriques avec un même motif répété beaucoup trop de fois.

J'ai encore trois idées. La première, c'est de générer plusieurs tuiles de cailloux de manière à éviter cet aspect géométrique. Seulement, à force de voir des cailloux partout, ça risque d'être un peu rébarbatif à la longue. La seconde idée, c'est d'utiliser non pas des tuiles, mais des sprites complets, un peu comme mes arbres de l'épisode 06. On pourrait par exemple avoir des rochers. La difficulté ici consiste à recouvrir exactement la zone infranchissable avec ces sprites mais pas plus, ni moins. Une troisième idée est de se servir des informations de pentes (puisque ces zones correspondent à des endroits trop pentus pour notre unité) et de trouver des tuiles qui puissent rendre compte de la pente. Avec un rebord, par exemple.

Peut-être que la solution viendra d'un mélange de plusieurs idées.

Les décorations

Une autre manière de rendre la carte moins monotone est d'ajouter des décorations. Et là, je pense immédiatement à mes arbres. Pourquoi ne pas tout simplement créer des forêts complètes ? Générer des forêts aléatoirement n'est pas si difficile. Avec les biomes, je sais où elles sont situées, j'ai déjà des sprites d'arbres, yapluka. Ça permettrait d'avoir une première version de la carte pas trop pauvre.

Dans la même idée, on pourrait aussi ajouter des rochers, et pas seulement sur les zones infranchissables. Dans les zones montagneuses par exemple, ça ferait assez couleur locale. Reste à pouvoir générer des rochers aléatoirement. J'ai un peu avancé sur ce point, ça rend assez bien, dans le même style que les arbres en fait, donc ça pourrait marcher.

En termes d'éléments naturels, ça me paraît déjà une bonne base. Mais je suis sûr que les idées vont venir au fur et à mesure. N'hésitez pas à donner vos idées !

D'autres pistes à explorer

Parmi les autres pistes à explorer, il y également la génération de routes. Et là, il faut vraiment que je vous fasse découvrir quelque chose. J'ai eu l'occasion de discuter sur le canal IRC #akagoria avec un doctorant d'une équipe de recherche française qui étudie, entre autre, la génération procédurale de paysage, l'équipe GeoMod du LIRIS à Lyon. Ils ont notamment une plateforme de développement de mondes virtuels, malheureusement propriétaire. Mais on peut voir des vidéos de démonstration assez époustouflantes. Vraiment, je vous les conseille toutes, ça ne dure pas très longtemps et c'est bluffant.

Parmi tous les travaux de cette équipe, il y a notamment des travaux sur la génération de routes, ainsi que sur la génération de réseaux routiers hiérarchiques. On peut retrouver une partie de ces travaux dans la thèse d'Adrien Peytavie sur la génération procédurale de monde (en français). Ça donne une bonne base pour générer des routes, même si les algorithmes sont décrits très succinctement.

Surtout, les discussions que j'ai eues avec ce doctorant m'ont ouvert des pistes de réflexion intéressantes. Il regrettait (et je ne peux pas l'en blâmer) que la plupart du temps, la génération procédurale de paysage suit le même schéma : celui que j'ai présenté au cours de ces deux épisodes. Je partage son analyse. J'ai choisi cette voie par facilité, parce que je savais qu'elle donnerait des résultats suffisamment convaincants. Mais je pense comme lui qu'on peut faire mieux que le bruit de Perlin et le diagramme de Whittaker. Notons bien que ce couple est utilisé dans de nombreux jeux, dont le célèbre Minecraft.

Il défendait l'idée que c'était une erreur de faire de la génération de paysage à grain fin directement, comme je l'ai fait. Les algorithmes utilisés ne conviennent pas pour traiter à la fois les paysages globaux (des montagnes, des plaines) et les détails (un arbre, un cailloux). Il proposait plutôt de procéder en plusieurs étapes, tout d'abord déterminer un paysage global avec du bruit de Perlin ou autre, ce qui permet de déterminer des zones globales. Puis, dans chaque zone, d'utiliser à nouveau du bruit pour générer les détails. Pour donner un exemple concret, si on considère que chaque case de ma carte initiale représente non pas une tuile au final mais un grand carré de tuiles, on aurait alors la possibilité, pour chaque carré de tuiles d'ajuster les limites de biomes avec du bruit de manière à avoir des formes un peu moins rectilignes (même avec les biseaux). J'ai trouvé cette idée très intéressante même si le temps me manque pour l'expérimenter dans l'immédiat. Et dans son esprit, on pouvait même avoir plusieurs niveaux dans ce genre.

Le deuxième point qui mériterait sans doute un peu de travail, c'est d'oublier le diagramme de Whittaker. En effet, ce diagramme est très pratique mais il donne des paysages hautement irréalistes ! Qui a déjà vu un désert, une taïga, une forêt tropicale et des steppes sur une île aussi petite ? Bon, on est dans un jeu donc on peut faire un peu comme on veut, mais quand même. On pourrait aussi rester dans un climat tempéré, et donc limiter le nombre de biomes, et ça ne serait pas moins intéressant. On pourrait partir sur l'étagement et avoir toute une série de climat et de végétation très intéressante. Je crois que je vais approfondir ce point quand j'aurai un peu de temps parce qu'il me semble qu'il peut donner des résultats plus «réaliste» que le diagramme de Whittaker, si on peut parler de «réalisme» dans un jeu de cette nature.

Conclusion

Voilà donc où nous en sommes rendus : nous avons une carte de base qui demande encore quelques ajustements avant de pouvoir entrer dans la phase d'édition manuelle. Je n'ai pas encore tout pushé sur les dépôts git mais ça sera sans doute fait entre le moment où j'écris ces lignes et le moment où elles seront publiées. En particulier, j'ai mis tout ce que j'ai décrit ici dans un binaire à part dans le projet mapmaker de manière à séparer ce qui relève des algorithmes génériques (ceux de la partie 1) et des algorithmes spécifiques au jeu (ceux de la partie 2).

Pour la suite immédiate, je vais laisser cet aspect en plan et je vais m'intéresser aux inputs. Parce que ma réflexion sur les dialogues (prochain point dans ma feuille de route), ainsi que la bibliothèque jnuit de devnewton, m'ont amené à y réfléchir et de manière plus générale à réfléchir aux interactions entre mon personnage et mon univers. Sur les dialogues, les questions arrivent très vite : qui initie le dialogue ? Est-ce qu'il faut appuyer sur un bouton ? Comment détecter qu'on est bien à côté de quelqu'un qui veut dialoguer ? Comment gérer les dialogues interactifs ? L'exemple, donné dans un commentaire sur un épisode précédent, des dialogues du jeu Andor's Trail donne une piste.

Bref, encore de nombreux épisodes en perspective !

  • # Site web

    Posté par . Évalué à 3.

    J'ai également fait une petite mise à jour du site web pour le rendre moins austère. Vous me direz ce que vous en pensez ;)

    • [^] # Re: Site web

      Posté par . Évalué à 3.

      Je m'aperçois que je n'ai pas incrémenté le numéro d'épisode. Est-ce qu'un gentil modo pourrait corriger cette erreur ? Merci !

      • [^] # Re: Site web

        Posté par (page perso) . Évalué à 5.

        Voilà, c'est fait. Merci de l'avoir signalé.

        « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

        • [^] # Re: Site web

          Posté par . Évalué à 2.

          Et du coup, il y a moyen de mettre à jour le lien permanent pour qu'il y ait un 11 à la place du 10 ?

          • [^] # Re: Site web

            Posté par (page perso) . Évalué à 3.

            Là, il va falloir demander à quelqu'un qui a plus de pouvoir que moi. Je crois qu'une entrée dans le suivi serait le plus simple.

            « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

            • [^] # Re: Site web

              Posté par (page perso) . Évalué à 3.

              Numéro mis à jour dans l'URL.

              • [^] # Re: Site web

                Posté par . Évalué à 2.

                Merci ! Je ne savais pas si c'était possible, j'ai demandé au cas où. Mais ça me perturbait de voir un 10 à la place du 11. Du coup, c'est mieux comme ça, je suis soulagé ;)

    • [^] # Re: Site web

      Posté par (page perso) . Évalué à 2.

      Je suis le seul à ne pas avoir trouvé le site en question ?

      La réalité, c'est ce qui continue d'exister quand on cesse d'y croire - Philip K. Dick

      • [^] # Re: Site web

        Posté par (page perso) . Évalué à 4.

        Vu que le lien a été cliqué 147 fois jusqu'à maintenant, je dirais oui.

        « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

      • [^] # Re: Site web

        Posté par . Évalué à 2.

  • # Raaah

    Posté par . Évalué à 4.

    Enfin, je commençai a être en manque :p et j'avais raison, c'est toujours aussi intéressant.

  • # Rivière en diagonale, et taille des rivière?

    Posté par . Évalué à 6.

    Encore merci pour cette dépèche encore une fois fortement intéressante.

    J'ai une question sur tes rivières, a l’œil on a impression qu'elle vont principalement en diagonale est-ce un biais au niveau de l'algo de rivière ou de celui le l'altitude ou un pur hasard ?

    Autre question j'ai pas vue de notion de débit ou de largeur de rivière qui augmente au fur et a mesure de la distance, de l'arrivée d'un affluant ou même lorsque le terrain s’aplanit?
    Dans la réalité les débits des cours d'eau augmente tout au long de leur parcourt et la surface occupée par le court d'eau dépend du relief et aussi d'une variable proche de la notion de débit.
    Il ne semble pas y avoir cette notion dans ton algo et donc les rivière ne grandissent pas en largeur (sauf pour les lac au causse du relief).
    Ca pourrai être intéressant et avec des fleuve plus large il pourrait même se former des iles au milieu des fleuves (comme dans la nature).

    j'ai hâte de voir le prochaine épisode.

    • [^] # Re: Rivière en diagonale, et taille des rivière?

      Posté par . Évalué à 3.

      Bonnes questions. J'ai quelques réponses.

      J'ai une question sur tes rivières, a l’œil on a impression qu'elle vont principalement en diagonale est-ce un biais au niveau de l'algo de rivière ou de celui le l'altitude ou un pur hasard ?

      C'est un biais assumé au niveau de l'algorithme. J'ai fait divers essais et c'est ce qui donnait les meilleurs résultats. Il faudra que je regarde ça à nouveau parce qu'avec une file de priorité, ça ne devrait pas changer quelque chose (en fait, je me dis que ce biais datait de l'époque où j'utilisais une simple file). C'est sans doute aussi un biais au niveau des données, parce qu'en allant en diagonale, tu as plus de chance d'avoir une différence d'altitude plus élevée qu'avec la case à côté.

      Autre question j'ai pas vue de notion de débit ou de largeur de rivière qui augmente au fur et a mesure de la distance, de l'arrivée d'un affluant ou même lorsque le terrain s’aplanit?

      Dans les versions préliminaires, j'élargissais la rivière au fur et à mesure. En fait, elle était générée de la même manière mais au moment de l'afficher, j'affichais soit le point tout seul, soit le point et les quatre points adjacents (horizontaux et verticaux) à partir de la moitié, soit le point et les huit points adjacents (horizontaux, verticaux diagonaux) à partir des 3/4. Je pense que je vais le réintroduire parce que ça marchait plutôt pas mal. Et maintenant, avec les améliorations des biseaux, ça peut rendre vraiment bien. Surtout que les rivières sont assez peu larges comparées au personnage.

      • [^] # Re: Rivière en diagonale, et taille des rivière?

        Posté par . Évalué à 4.

        C'est sans doute aussi un biais au niveau des données, parce qu'en allant en diagonale, tu as plus de chance d'avoir une différence d'altitude plus élevée qu'avec la case à côté.

        Est ce que tu pondères la différence d'altitude avec la distance ? vu que tes tuiles sont carrées, on peut considérer qu'une case sur le coté est à une distance de 1 et qu'une case sur la diagonale à une distance de \sqrt{2}

        • [^] # Re: Rivière en diagonale, et taille des rivière?

          Posté par . Évalué à 3.

          Non, pour l'instant, je ne pondère rien. Et ça me paraît même compliqué de pondérer. Parce que la pondération, elle est relative à une position. Or, pour ma file de priorité, j'ai besoin d'avoir des informations absolues, pas relative. Il faudrait revoir complètement l'algorithme ou alors ne plus considérer les déplacements diagonaux (mais dans mon souvenir des premiers essais, ça ne rendait pas très bien).

          • [^] # Re: Rivière en diagonale, et taille des rivière?

            Posté par . Évalué à 2.

            Ça complique la chose en effet.

            Mais quand tu insères ta case dans ta file, tu sais d'où tu viens, non ? donc tu peux utiliser une altitude absolue "ajustée" pour le tri à ce moment là.
            Et si tu retombes sur la même case en venant d'ailleurs, rien ne t'empêche de l'insérer une seconde fois avec une autre altitude ajustée !

            Ça te parait raisonnable ?

            • [^] # Re: Rivière en diagonale, et taille des rivière?

              Posté par . Évalué à 2.

              et tant qu'on y est, si cette solution marche, on pourrait même imaginer favoriser les lignes droites de la même façon, en ajoutant un petit aléa dans les altitudes des cases adjacentes.
              Alea inférieur à la différence d'altitude minimale entre 2 cases, car cela reste le critère le plus important, mais qui aurait un légère chance d'être plus élevé si la rivière continue en ligne droite plutôt que de tourner !

              • [^] # Re: Rivière en diagonale, et taille des rivière?

                Posté par . Évalué à 2.

                Mais quand tu insères ta case dans ta file, tu sais d'où tu viens, non ? donc tu peux utiliser une altitude absolue "ajustée" pour le tri à ce moment là.
                Et si tu retombes sur la même case en venant d'ailleurs, rien ne t'empêche de l'insérer une seconde fois avec une autre altitude ajustée !

                Dans une file de priorité, il n'y a qu'une seule fonction de tri (en plus déterminée à la compilation en C++). On ne trie pas la file plusieurs fois, ce n'est pas possible. Si on voulait faire comme tu le suggères, il faudrait une autre structure de données, je pense, et ça serait plus lent. Pour un gain pas forcément important.

                et tant qu'on y est, si cette solution marche, on pourrait même imaginer favoriser les lignes droites de la même façon, en ajoutant un petit aléa dans les altitudes des cases adjacentes.

                Oui, ça c'est une idée. Utiliser du bruit (plutôt que de l'aléa) pour éviter les formes trop géométriques. Maintenant, ça va se jouer à pas grand chose, est-ce que ça vaut vraiment le coup de le faire ? Je ne sais pas trop.

                • [^] # Re: Rivière en diagonale, et taille des rivière?

                  Posté par . Évalué à 3.

                  Dans une file de priorité, il n'y a qu'une seule fonction de tri (en plus déterminée à la compilation en C++).

                  Hum j'ai l'impression qu'il y a une mésentante. Tu met des cases dans ta file, lui te propose de mettre des couples case + direction (un angle), donc le tris prendrait 2 paramètres.

                  je pense, et ça serait plus lent

                  Et alors ? Tu génère ta carte 60 fois par seconde ?

                  Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                  • [^] # Re: Rivière en diagonale, et taille des rivière?

                    Posté par . Évalué à 4.

                    Hum j'ai l'impression qu'il y a une mésentante. Tu met des cases dans ta file, lui te propose de mettre des couples case + direction (un angle), donc le tris prendrait 2 paramètres.

                    Effectivement, je crois qu'il y a du flou. Parce qu'il parle de mettre une case potentiellement deux fois, ou de mettre à jour son potentiel. Dans les deux cas, je ne vois pas bien comment on fait.

                    Et alors ? Tu génère ta carte 60 fois par seconde ?

                    Dans ce genre d'algo de parcours de graphe, il faut faire très attention parce que tu peux très très vite exploser le temps de calcul (un algorithme exponentiel est si vite arrivé). Mes étudiants qui ont dû expérimenter sur ce genre de chose s'en sont très vite rendu compte. Entre l'algo que je décris qui met quelques millisecondes et les premiers algos qu'ils m'avaient pondu qui mettaient plusieurs minutes (quand ils s'arrêtaient), il y a un gouffre. L'important n'est pas la vitesse mais la complexité. Même si on ne le fait pas 60 fois par secondes, on souhaite quand même que ça aille vite pour expérimenter au maximum avant de trouver une carte convenable.

                    • [^] # Re: Rivière en diagonale, et taille des rivière?

                      Posté par . Évalué à 2.

                      Effectivement, je crois qu'il y a du flou. Parce qu'il parle de mettre une case potentiellement deux fois, ou de mettre à jour son potentiel. Dans les deux cas, je ne vois pas bien comment on fait.

                      je parlais bien de mettre une case avec son potentiel dans la liste. ET à ce moment là, si la même case se retrovuve avec un potentiel différent (car venant d'ailleurs), cela fait un élément different de la liste, donc pas de soucis.

                      enfin, pour le tri, tu ne le fait que sur le potentiel, donc cela ne devrait pas etre beaucoup plus lent (en fait, j'avais plutôt cru comprendre que c'est une insersion triée que tu fais et pas un tri global à chaque fois)
                      La complexité est ajoutée au moment d'ajouter un élément dans ta liste triée. Il faut pondérer son altitude absolue par un facteur "judicieusement" choisi.
                      Et ça, je conçois tout à fait que ça n'est pas trivial.

                      Mais une fois ce mécanisme en place, tu peux essayer plusieur facteurs de pondération et voir comment ils influent sur le résultat ! (cf, le second message de mes 2 posts successifs)

                      • [^] # Re: Rivière en diagonale, et taille des rivière?

                        Posté par . Évalué à 2.

                        en fait, j'avais plutôt cru comprendre que c'est une insersion triée que tu fais et pas un tri global à chaque fois

                        En fait, ce n'est ni l'un ni l'autre. C'est une file de priorité. C'est une structure de données qu'on appelle aussi un tas, ça permet d'insérer en O(log n) et d'avoir accès au plus petit élément en O(1). En revanche, les autres éléments ne sont pas triés globalement mais grossièrement on va dire. En fait, un tas, c'est un arbre binaire pour lequel tu as deux propriétés : un nœud est plus petit que tous ses fils, et l'arbre est presque complet (c'est-à-dire qu'il manque uniquement des nœuds sur la dernière ligne). En pratique, ça s'implémente très efficacement avec un tableau. Avec une liste triée, tu insères en O(n), tu ne peux pas faire autrement, et du coup, c'est moins efficace.

                        La complexité est ajoutée au moment d'ajouter un élément dans ta liste triée. Il faut pondérer son altitude absolue par un facteur "judicieusement" choisi.
                        Et ça, je conçois tout à fait que ça n'est pas trivial.

                        Surtout, le problème que je vois, c'est que les cases sont en plusieurs exemplaires dans la file. Comment tu gères ça ?

                        • [^] # Re: Rivière en diagonale, et taille des rivière?

                          Posté par . Évalué à 2.

                          ça permet d'insérer en O(log n)

                          c'est donc unse insertion triée ;) ce que tu décris, c'est une std::map (implémenté par un red/black tree au moins dans la lib c++ livrée avec gcc)

                          Surtout, le problème que je vois, c'est que les cases sont en plusieurs exemplaires dans la file. Comment tu gères ça ?

                          Un élément de ta file, c'est (case, altitude), si deux paires (case, altitude) sont identiques, l'insersion n'a rien à faire, sinon tu as un nouvel élément qui est différent.

                          Au moment de transformer une case de terrain en rivière, tu prends le premier élément de ta liste, et si c'est déjà de l'eau (parce qu'il avait été inserée et déjà converti avant), et bien tu le zappes juste.

      • [^] # Re: Rivière en diagonale, et taille des rivière?

        Posté par . Évalué à 2.

        Autre question j'ai pas vue de notion de débit ou de largeur de rivière qui augmente au fur et a mesure de la distance, de l'arrivée d'un affluant ou même lorsque le terrain s’aplanit?

        Dans les versions préliminaires, j'élargissais la rivière au fur et à mesure. En fait, elle était générée de la même manière mais au moment de l'afficher, j'affichais soit le point tout seul, soit le point et les quatre points adjacents (horizontaux et verticaux) à partir de la moitié, soit le point et les huit points adjacents (horizontaux, verticaux diagonaux) à partir des 3/4. Je pense que je vais le réintroduire parce que ça marchait plutôt pas mal. Et maintenant, avec les améliorations des biseaux, ça peut rendre vraiment bien. Surtout que les rivières sont assez peu larges comparées au personnage.

        Effectivement ça serai déjà plus réaliste.
        Mais le truc que je vois c'est que si tu élargie artificiellement tu risque d'avoir par endroit des aberrations.
        Par exemple si tu as une rivière qui longe une falaise si tu élargies tu auras un bout de rivière qui montera sur la falaise (un peu cheulou comme résultat non ?). Dans la réalité tu devrais avoir juste le niveau de l'eau qui monte ou la rivière qui s'étend du coté opposé uniquement.
        Un rivière réaliste devrait également être capable de se diviser pour former plusieurs bras qui donnent naissance à des iles/delta.
        Après on est d'accord qu'il faut s'avoir s’arrêter et placer le curseur au bon endroit entre réalisme et complexité.

        Sinon j'ai une autre question comment gère tu la profondeur de l'eau (et donc la hauteur de la surface)?
        La question est aussi valable pour les rivières mais c'est plus visible sur les lacs car si je comprend bien ton algo, il suit le fond du lac mais dans le rendu la surface de l'eau doit être à l’horizontal comment règle tu ce point?

        • [^] # Re: Rivière en diagonale, et taille des rivière?

          Posté par . Évalué à 2.

          Après on est d'accord qu'il faut s'avoir s’arrêter et placer le curseur au bon endroit entre réalisme et complexité.

          Je pense personnellement que trop de jeux essayent d'être réalistes alors que le but n'est pas le réalisme mais le plaisir de jouer.

          La question est aussi valable pour les rivières mais c'est plus visible sur les lacs car si je comprend bien ton algo, il suit le fond du lac mais dans le rendu la surface de l'eau doit être à l’horizontal comment règle tu ce point?

          La réponse est toute simple je pense : son jeu est en vue de dessus, tu ne vois donc pas l'altitude.

        • [^] # Re: Rivière en diagonale, et taille des rivière?

          Posté par . Évalué à 2.

          Par exemple si tu as une rivière qui longe une falaise si tu élargies tu auras un bout de rivière qui montera sur la falaise (un peu cheulou comme résultat non ?).

          Les altitudes, c'est pour avoir un truc de base, mais après, cette information disparaît complètement dans la carte finale, donc il n'y a pas de truc chelou. Ou ça ne se voit pas trop.

          Sinon j'ai une autre question comment gère tu la profondeur de l'eau (et donc la hauteur de la surface)?

          Très simple : je ne la gère pas ;) Sur un jeu en vue de haut, ça ne sert pas à grand chose. Dans mon cas, il va y avoir des rivières que tu ne peux pas traverser et tu en seras empêché physiquement. Et des gués par lesquels tu pourras passer. Donc, ça ne sert à rien de gérer une profondeur.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.