Comme écrit dans
des articles de blog
récents , j'ai eu du mal à obtenir les bons détails du littoral dans mon jeu
Dragons Abound . Ma déception est survenue lors de la mise en place des
îles-barrières . Pour créer l'île la plus étroite possible, je leur ai fait un emplacement de large - dans la figure ci-dessous, chaque emplacement est un triangle de Delaunay:
C'était plutôt désagréable - à la fois parce que l'île s'est avérée très cassée et parce que la taille des pièces était trop grande. Il semblait qu'avec une forte augmentation du nombre de triangles Delaunay (c'est-à-dire avec une forte diminution de leur taille), ce problème serait résolu - mais la densité de triangles dont j'avais besoin a entraîné un crash du navigateur.
J'ai résolu ce problème en séparant les contours du terrain de la représentation interne des lieux. Cela m'a permis de dessiner des îles de toute taille ou forme, quelle que soit la grille de localisation sous-jacente:
Le problème est donc résolu! Cela m'a permis de dessiner les îles barrières, et comme le littoral n'est plus obligé de suivre la grille de base, si nécessaire, un littoral plus détaillé pourrait être créé de la manière habituelle, puis ajouter des détails.
Mais ... comment ajouter des détails au littoral? Ce n'est pas aussi facile qu'on pourrait le penser. Comme je voulais créer un littoral fractal, j'ai envisagé d'utiliser des
fractales pour ajouter des détails au littoral:
Après avoir expérimenté les paramètres, j'ai pu ajouter beaucoup de détails et de choses intéressantes au littoral. Cependant, le système n'a pas pu créer quelque chose ressemblant à une telle carte:
Le bruit de Perlin
peut créer ce type de terrain avec une grille de base suffisamment détaillée, mais cela peut-il être fait
sans stocker les hauteurs d'élévation dans la grille de base avec la résolution souhaitée (après tout, je sais que cela va casser mon code)? Jusqu'à ce que je comprenne comment le faire. Le littoral est essentiellement un chemin à travers tous les points où la fonction de bruit Perlin a une valeur nulle. Bien que nous puissions apprendre directement de la fonction de bruit Perlin la valeur dans un emplacement spécifique (X, Y), nous ne pouvons pas trouver (par exemple) «tous les emplacements dans lesquels la fonction a une valeur nulle». Autrement dit, il est difficile de voir comment dessiner un contour de hauteurs sans grille de base.
Pire encore, j'ai demandé à
Amit comment procéder, et il ne connaissait pas non plus la réponse. C'est une chose quand je ne peux pas dire cela, mais quand même une personne aussi intelligente ne peut pas donner de réponse, je commence à penser que cela ne peut pas être fait. C'est triste. Je peux donner au littoral toute forme dont j'ai besoin, mais je ne peux pas obtenir les formes dont j'ai besoin sans une grille de base très détaillée.
Alors, comment puis-je obtenir une grille haute résolution sans casser le code?
L'une des solutions qui m'est venue à l'esprit me rappelle ce
qu'a fait Azgaar dans son générateur de cartes: les cellules Voronoi de taille variable. L'idée principale est d'augmenter la densité (et de diminuer la taille) du maillage de base le long des côtes et de maintenir une densité plus faible dans les océans et d'autres zones qui ne nécessitent pas de détails. Avec cette option, je disposerai de nombreuses cellules maillées uniquement dans les zones où vous avez besoin de détails. Ce changement sera assez difficile à implémenter dans
Dragons Abound , mais je veux y réfléchir. D'un autre côté, Azgaar lui-même
n'était pas très satisfait de cette approche , il faut donc également en tenir compte.
En parallèle, je voulais étudier les causes d'un plantage du navigateur lors du traitement d'un tas de triangles. Les outils de développement de Chrome m'ont fourni des informations détaillées sur les performances. Je ne suis en aucun cas un expert dans l'utilisation de ces outils, mais de nombreuses fonctions sont assez simples à comprendre. Si vous souhaitez connaître la quantité totale de mémoire utilisée dans le programme, l'onglet Mémoire contient des informations sur la capacité actuellement utilisée:
Dans ce cas, j'ai ouvert la page Web Azgaar, et elle occupe un modeste 20 Mo de mémoire. Vous pouvez utiliser cet outil pour connaître la quantité de mémoire
occupée par Dragons Abound et pour déterminer le moment où l'onglet se bloque.
Le paramètre de base qui contrôle la résolution du maillage sous-jacent dans
Dragons Abound est habilement nommé «npts» (nombre de points). Pour chaque zone d'unité de la carte (les cartes des régions que j'utilise habituellement comme exemples ont une zone de 1 unité)
Dragons Abound crée un nombre donné d'emplacements de la grille de base. J'utilise généralement 16K (16384) pour npts, ce qui signifie que chaque emplacement de grille correspond à environ 70 pixels carrés de l'écran à une échelle de zoom standard.
Bien sûr, la quantité exacte de mémoire utilisée dépend de la carte, mais pour la carte illustrée ci-dessus avec 16 000 points, vous avez besoin d'environ 92 Mo:
C'est moins que ce à quoi je m'attendais et, pour être honnête, un chiffre assez modeste.
Si vous doublez le nombre de points dans la grille de base, la capacité de mémoire augmentera à 138 Mo:
La taille de la mémoire occupée n'a pas doublé, car une partie de cette mémoire est occupée par des ressources et d'autres structures de données dont la taille n'a pas changé. 16 000 points supplémentaires "pèsent" environ 50 Mo de mémoire, c'est-à-dire que chaque point occupe par conséquent environ 3 Ko de mémoire. C'est plus que ce à quoi je m'attendais, mais en général le volume est encore assez modeste. Sur un ordinateur avec 64 Go de mémoire, 150 Mo sont à peine perceptibles.
Après avoir fait quelques doubles supplémentaires, j'ai trouvé que l'onglet avec
Dragons Abound se bloque généralement à environ 128K points. Si nous l'attrapons avant qu'il ne vole et vérifions la mémoire, nous verrons ce qui suit:
J'ai supposé que l'onglet se bloque en raison de la mémoire occupée, mais généralement le problème n'est pas dans la mémoire. Pourquoi l'onglet se bloque-t-il? Le seul indice est que l'onglet ne plante pas avant la fin de la carte, et c'est probablement une indication qu'un crash se produit pendant le rendu.
Il est logique de supposer que le SVG que je crée surcharge le rendu du navigateur en raison de sa taille ou de sa complexité. Pour commencer, je peux savoir combien d'éléments SVG je crée. En D3, je peux obtenir le nombre total d'éléments SVG créés en utilisant
svg.selectAll('*').size() .
Courir à partir de 16 000 points et vérifier le nombre d'éléments SVG m'a montré ce qui suit:
32K points ont 65457 éléments et 128K points ont 258823. Chaque point ajouté à la grille de base ajoute deux éléments à la carte. Je pense avoir trouvé une source de malheur.
Chaque point de la grille de base ajoute des éléments SVG en raison de la façon dont
Dragons Abound rend la terre (et l'eau). Le terrain est rendu en rendant chaque emplacement de base sous la forme d'un polygone rempli, puis en les floutant tous. Cela permet à
Dragons Abound de donner au terrain un beau motif ou d'utiliser la hauteur du terrain pour rendre le terrain avec un ombrage 3D, comme indiqué ici:
Vous pouvez désactiver la visualisation de la terre et de l'océan pour vérifier le nombre d'éléments SVG créés. À 256 000 points:
Wow, le nombre d'éléments SVG a considérablement diminué. Comme je l'espérais, la carte est maintenant rendue sans planter! Autrement dit, si vous évitez d'utiliser une grille pour rendre la terre et l'eau, vous pouvez créer une grille beaucoup plus dense qu'auparavant.
Maintenant que j'ai un réseau Voronoi beaucoup plus dense, je veux vérifier s'il me permet de générer les éléments de relief dont j'ai besoin, comme les îles côtières. Le maillage dense de Voronoi crée d'autres problèmes (en particulier avec les rivières), donc je désactiverai tout sauf les côtes pour accélérer les tests et me concentrer sur eux. Voici le rendu original de certains littoraux à 256K pixels et avec du bruit standard:
Il s'avère que la carte est bien rendue et crée déjà un littoral beaucoup plus beau.
Même sans réglage minutieux, le résultat est bien meilleur. Le bruit crée les types de côtes fractales et d'îles côtières que j'ai indiquées sur la carte ci-dessus.
Voici les îles avec une augmentation de 300%:
Avec cette augmentation, vous pouvez remarquer des artefacts de triangles dans la grille de base, mais même ainsi, les îles peuvent créer des formes intéressantes. Vous pouvez utiliser l'anti-aliasing (comme je le fais sur la version actuelle des cartes) pour se débarrasser de certains des artefacts les plus visibles des triangles. Au grossissement standard, cela fournit un littoral moins accidenté, mais élimine également certains petits détails:
Vous devez probablement vous connecter pour trouver un terrain d'entente.
La plupart des générateurs de sushis procéduraux utilisent le bruit Perlin pour créer une carte de hauteur. Nous devons trouver les paramètres de bruit appropriés, sélectionner une graine, puis utiliser la valeur de bruit à chaque emplacement (x, y) pour définir la masse du terrain. Un aspect pratique de la création d'un terrain est que si vous avez besoin de plus de détails sur le littoral, vous pouvez simplement ajuster les paramètres de bruit.
Cependant,
Dragons Abound ne crée pas de terrain de cette façon. (Ou du moins, cela crée plus que cela.)
Dragons Abound utilise de nombreuses méthodes différentes pour créer des sushis. Bien qu'ils utilisent tous le bruit à un degré ou à un autre, très peu créent des terrains directement à partir du bruit. Par exemple, le jeu a une procédure pour créer une île qui crée un masque pour l'île (généralement une ellipse), utilise du bruit pour donner à l'ellipse une forme plus naturelle, puis applique un bruit différent pour remplir approximativement le masque. Chaque carte particulière est généralement créée par une combinaison de plusieurs procédures différentes. Par conséquent, l'ajout de détails en ajustant les paramètres de bruit pour
Dragons Abound n'est pas très approprié.
Pour mes besoins, il vaut mieux aborder le problème sous un angle légèrement différent. Si j'ai une carte d'élévation spécifique qui définit les masses terrestres, comment puis-je ajouter des détails aux bords de ces masses terrestres? Cela peut nous conduire à l'idée que nous devons reconnaître les bords des masses terrestres et masquer le reste de la carte, etc. Mais, d'un autre côté, je ne suis pas du tout contre l'ajout de détails supplémentaires au reste de la carte. Si la terre est un peu plus accidentée ou que le fond de l'océan est un peu plus accidenté, c'est normal.
Que signifie l'ajout de détails au littoral? Un littoral est simplement une ligne de contour dans laquelle une carte de hauteur a une valeur nulle. (La valeur est arbitraire, mais un tel principe est utilisé dans tous les générateurs de terres procédurales.) Pour rendre cette ligne plus détaillée, vous devez légèrement déplacer légèrement la terre à côté de cette ligne de contour, de sorte que les côtes simples deviennent plus complexes, des parties de la terre dépassent dans l'océan et deviennent îles, etc. Mais cela ne devrait pas arriver tout à fait par accident, je veux que les changements semblent naturels. Nous résumons tout cela, et il semble que vous devez ajouter une petite quantité de bruit à toute la carte. Et en fait, c'est exactement ce que j'ai fait dans l'exemple original ci-dessus.
Bien sûr, cela doit être fait avec soin afin de ne pas effacer les masses terrestres créées et de créer d'autres problèmes. Essentiellement, je dois configurer trois paramètres.
Le premier est l'échelle du bruit. Une échelle est simplement un intervalle de valeurs pour ce bruit. Dans notre cas, je souhaite abaisser certaines zones vers le bas et augmenter certaines, de sorte que la plage de valeurs doit être de négative à positive. Cependant, je ne veux pas ajouter de nouvelles montagnes ou créer un océan loin du littoral existant, je ferai donc de la valeur maximale (absolue) du bruit une petite fraction de la hauteur standard du terrain.
Le deuxième paramètre est la fréquence principale du bruit. La fréquence détermine la vitesse à laquelle le bruit change à l'intérieur de l'emplacement. Le bruit à basse fréquence change très lentement, donc une zone positive avec du bruit à basse fréquence peut (par exemple) couvrir toute la carte. Le bruit à haute fréquence change rapidement, donc une région positive avec du bruit à haute fréquence peut (par exemple) avoir la taille d'une petite île. Dans notre cas, la fréquence de bruit principale détermine les plus grands éléments de relief que nous verrons dans le bruit. Autrement dit, si je veux que le bruit ajoute (disons) de petites îles (mais rien de plus grand qu'eux) à la carte, alors je dois sélectionner la fréquence principale de la taille d'une petite île.
Vous pourriez penser que c'est facile à faire (il suffit de mesurer une petite île et d'affecter cette taille à la fréquence principale). Cependant, la fréquence est mesurée dans les coordonnées de la fonction de bruit, pas dans les coordonnées de la carte! Une fonction de bruit typique peut avoir un intervalle de 0 à 255 dans chaque coordonnée, et une carte peut avoir un intervalle de -1 à 1 dans chaque coordonnée. Pire encore, les coordonnées de bruit sont réduites, et de nombreux utilisateurs qui utilisent le bruit ne s'en rendent même pas compte. La traduction d'une unité à l'autre et la détermination des fréquences appropriées sont source de confusion, il est donc généralement plus facile de simplement expérimenter avec des intervalles de fréquence et de choisir celui qui crée les éléments de carte de la bonne taille.
Le troisième paramètre est le nombre d'octaves de bruit. Les octaves sont des couches supplémentaires de bruit. Chaque couche double généralement la fréquence et réduit de moitié l'échelle de bruit. Autrement dit, chaque nouveau calque ajoute des éléments en relief deux fois moins que le calque précédent, mais également deux fois plus faibles. Autrement dit, vous devez sélectionner le nombre d'octaves qui donnent les plus petits éléments dont nous avons besoin, et pour cela, vous devrez peut-être ajuster l'échelle de bruit, car il est toujours suffisamment fort dans l'octave la plus élevée pour apparaître sur la carte. Comme je le fais intentionnellement pour rendre les côtes très complexes, j'utiliserai pas mal d'octaves de bruit.
Commençons par la configuration. Pour commencer, je vais générer un exemple de carte sans bruit supplémentaire:
De toute évidence, c'est un littoral ennuyeux, avec des lignes douces et seulement quelques grandes îles. Voici le même littoral avec l'échantillon de bruit d'origine:
Le bruit a considérablement changé la forme de la carte, transformant de grands fragments de terre en océan, et vice versa. De nombreuses îles sont également apparues, y compris loin dans la mer. Tout cela indique que l'échelle de bruit est trop grande. Les plus grands éléments de relief individuels ajoutés par le bruit devraient être la taille des petites îles de la carte d'origine. Il s'agit probablement de la nouvelle taille maximale des éléments, ce qui prouve que la fréquence principale du bruit est approximativement choisie correctement. Enfin, de nombreux petits détails sont apparus, jusqu'aux limites de la taille d'affichage, ce qui montre qu'il y a suffisamment d'octaves. (Cependant, le nombre d'octaves peut être plus que nécessaire. Cela n'affecte pas l'apparence de la carte, mais est inefficace.) Il semble que, fondamentalement, vous devez ajuster l'échelle de bruit.
L'ajustement du bruit est une opération assez compliquée car je veux que ce bruit affecte principalement la terre et l'eau à environ une ligne de contour avec une hauteur = 0. C'est-à-dire que j'ai besoin d'une échelle relativement petite, mais il n'est pas clair comment choisir le bon nombre, car dans différentes cartes, la distribution des hauteurs varie. La solution est de trouver la bonne échelle à la volée. Vous pouvez prendre toutes les valeurs absolues des hauteurs sur la carte, les trier et trouver le point de coupure qui sélectionne (disons) 10% des emplacements autour de zéro. Tous ces emplacements tombent dans l'intervalle (par exemple) [-0,05, 0,05], puis je peux utiliser la valeur 0,05 pour déterminer l'échelle du bruit ajouté.
(J'écris des «définitions» parce que pour diverses raisons, vous ne pouvez pas simplement utiliser 0,05. Vous devez d'abord transformer la terre en eau et vice versa. L'ajout (disons) de 0,002 à -0,05 n'apportera aucune modification visible à la carte. Autrement dit, l'intervalle devrait être bien supérieur à 0,05. si je veux convertir une proportion significative d'emplacements d'une hauteur de -0,05 de l'eau à la terre. Deuxièmement, les fonctions de bruit ne sont pas
réparties uniformément , donc avec une échelle de 0,05, la fonction de bruit ne retournera jamais réellement la valeur 0,05! En pratique, la difficulté est que l'échelle doit être beaucoup plus grande que les plus grandes valeurs que nous voulons voir assez souvent.)
Après avoir expérimenté, j'ai trouvé une valeur qui ajoute de la complexité aux côtes, sans les modifier de manière significative, et crée également un petit nombre d'îles:
Comme toujours, ces paramètres dans le jeu peuvent prendre un intervalle de valeurs, donc je peux obtenir un large éventail de cartes: des cartes avec des côtes assez lisses aux cartes avec des banques cassées et complexes. En laissant le programme sélectionner les valeurs, j'ai obtenu le résultat suivant:
Les côtes sont plus douces, mais il y a encore la plus grande partie de la complexité supplémentaire de l'échelle moyenne et un nombre suffisant de nouvelles îles.
Lors de la mise en œuvre des côtes fractales, j'ai réalisé la capacité de contrôler le niveau de fractalisation à l'aide de la fonction de bruit, de sorte que certaines zones auront des côtes lisses, tandis que d'autres auront des côtes complexes. Je pensais que cela augmenterait considérablement l'intérêt de la carte et qu'elle serait moins «générée», alors j'ajouterai cette fonctionnalité ici. L'idée est assez simple - avant d'ajouter du bruit de côte à la carte, je le multiplie par la sortie de la deuxième fonction de bruit, qui va de zéro à 1. Lorsque cette fonction est petite, de petits détails seront ajoutés aux côtes. Lorsqu'il est proche de 1, des détails supplémentaires seront ajoutés en totalité. En sélectionnant l'échelle de la deuxième fonction de bruit, qui varie lentement tout au long de la carte, j'obtiendrai certaines zones avec des côtes complexes, d'autres avec des lignes simples et des transitions logiques entre elles:
Ici, j'ai rendu les paramètres côtiers grands, de sorte que la différence soit plus visible. Nous voyons des côtes sauvages et accidentées au nord-est et des plages plus lisses à l'ouest.
Nous avons donc considérablement amélioré la génération du littoral, mais je ne parviens toujours pas à générer une carte avec autant de triangles de Delaunay. Je n'affiche que les cartes de contour car de nombreux autres éléments de carte sont cassés. Il doit être corrigé.
Le reste du programme ne fonctionne pas bien avec autant de triangles Delaunay (avec des paramètres actuels de 256K). Le principal problème est que
Dragons Abound dessine la terre et l'eau en dessinant tous les triangles individuels, et tant d'éléments SVG provoquent le crash du navigateur. J'ai donc dû désactiver complètement le rendu des sushis. Il existe probablement un moyen de contourner ce problème, mais le fait d'avoir autant de triangles crée d'autres problèmes. Par exemple, certaines parties du programme doivent traiter l'intégralité de la carte. Chacun d'entre eux devient seize fois plus lent à 256 000 emplacements qu'à 16 000 emplacements. Dans le code, il existe également des parties (par exemple, un nouveau modèle de précipitation) qui se brisent lorsque vous travaillez avec autant de triangles. Et de la création d'une grille de localisation aussi détaillée, nous ne gagnons rien - après avoir généré le littoral, rien ne s'améliore de la complexité supplémentaire. Par conséquent, bien que je puisse revoir le programme et corriger les zones où un grand nombre d'emplacements ralentit ou casse trop le code, il semble plus facile de réduire la résolution de la grille de la carte après la création des côtes.
Comme indiqué ci-dessus, Azgaar a déjà effectué des
travaux pour modifier la résolution de la grille de Voronoi sous-jacente à la carte. Il a réalisé la possibilité de changer la résolution de la grille à la volée dans le processus de génération, c'est-à-dire qu'il pourrait (par exemple) augmenter la densité des emplacements le long de la côte. Cependant, un changement local de densité a ses inconvénients - en particulier, il crée d'étranges triangles le long de la frontière. Azgaar a
suggéré plus tard que le système était trop complexe et ne valait pas la peine. Azgaar sait généralement de quoi il parle, donc je vais croire sur parole et je n'essaierai pas de reconditionner le maillage fini.
Au lieu de cela, j'ai créé une deuxième grille avec la résolution souhaitée (inférieure), puis copié la carte d'élévation dans cette nouvelle grille. (N'oubliez pas que
Dragons Abound stocke désormais les côtes séparément de la grille, donc après leur création, elles ne dépendent plus de l'ajustement exact de la grille. Pour ce faire, c'est un peu compliqué. Étant donné que la grille d'origine a une résolution beaucoup plus élevée que la nouvelle, de nombreux emplacements dans l'original la grille sera superposée à un emplacement dans la nouvelle grille. Chacun de ces emplacements source a une hauteur différente sur la carte de hauteur, comment puis-je les copier? Utiliser la moyenne? Ou la hauteur maximale (minimale)?
Pour commencer, je sélectionne simplement un emplacement aléatoire pour voir si la nouvelle grille fonctionne avec le reste du programme:
Tout s'est étonnamment bien passé. Un bug mineur se produit lorsque les nouveaux emplacements ne sont pas correctement marqués comme terre, côte ou eau, mais après avoir résolu ce problème, la génération de la carte a bien fonctionné. Vous devez nettoyer les défauts mineurs (par exemple, le tag Palmanor qui est sorti sur l'eau), mais dans l'ensemble, il semble bon. Même les petites îles se sont avérées magnifiques.
Au final, j'ai décidé qu'avec une diminution de la résolution de la grille de Voronoi, chaque emplacement serait la moyenne des emplacements de base. Cela semble être une sage décision, et si nécessaire, elle peut toujours être modifiée. Cette image montre comment, en conséquence, les côtes ont été séparées du maillage fini:
Pour résumer: dans
Dragons Abound , une grille de triangles Delone à très haute résolution est utilisée lors de la génération de la carte de hauteur. Après son achèvement,
Dragons Abound définit les côtes en suivant les transitions des valeurs négatives aux valeurs positives dans la carte des hauteurs. Ensuite, le jeu copie la grille haute résolution dans une grille de résolution beaucoup plus basse, en faisant la moyenne des emplacements qui tombent dans un emplacement de la nouvelle grille. Ensuite, la grille haute résolution est supprimée et le reste de la génération procédurale et de la visualisation se poursuit sur la grille basse résolution. Une question intéressante est de savoir si l'utilisation du maillage de Delaunay a une quelconque valeur à ce stade; il pourrait être utile de copier sur une grille d'hexagones ou quelque chose de similaire.