Comment j'ai créé des cartes des continents pour mon jeu

Partie 1. SVG et systèmes de coordonnées

Jusqu'à récemment, les tailles de carte dans mon jeu Dragons Abound étaient fixes et quelque peu non déterministes. Je les considérais comme «régionales» - pas des cartes du monde entier, mais ses parties importantes, comme, par exemple, la côte ouest des États-Unis ou une partie de l'Europe. J'étais assez satisfait de cette échelle, mais je voulais expérimenter un peu avec le jeu pour voir si je pouvais générer des cartes du monde entier (ou au moins une plus grande). Mais avant de commencer, parlons un peu des cartes du monde fantastique.

Le monde est un grand espace. La plupart des cartes «monde» fantastiques ne ressemblent même pas à la vraie taille. Prenons, par exemple, la Terre du Milieu, dans laquelle se déroule l'action du Seigneur des Anneaux:


Bien qu'il semble qu'un immense monde y soit capturé, en fait, la Terre du Milieu a été créée sur la base de l'Europe.


Autrement dit, la vraie carte du «monde» pour le monde de Tolkien sera environ 50 fois plus grande que la carte de la Terre du Milieu (!). En fait, la plupart des cartes du monde fantastique que j'ai vues reflètent un territoire de la taille d'un continent:


Cela semble être la plus grande zone bien visualisée dans un style de carte fantastique.

Autrement dit, la tâche de générer de véritables «cartes du monde» est probablement trop ambitieuse. Il vaut mieux viser à créer une carte du continent (ou d'une partie du continent). (Cependant, il est encore plus pratique de considérer la carte comme la taille du "monde".) Alors, quelle taille doit avoir la carte? Si les cartes Dragons Abound actuelles ont une taille «subcontinentale», nous pouvons supposer que vous devez générer des cartes 8 à 10 fois plus grandes.

Avant de passer à la tâche de générer de grandes cartes, je dois mieux comprendre les différents systèmes de coordonnées utilisés dans mon jeu. J'ai emprunté beaucoup de systèmes de coordonnées au code source de Martin O'Leary, et leurs interactions peuvent être déroutantes même lorsque vous travaillez avec eux pendant deux ans. Habituellement, je pouvais le faire sans les expérimenter, mais il est évident que je devrai le faire pour générer de grandes cartes.

Pour commencer, le «monde» de la carte régionale est en cours de génération dans un carré unitaire. Chaque carte régionale a des coordonnées de (-0,5, -0,5) à (0,5, 0,5), et l'origine (0,0) se trouve au milieu de la région.


L'une des bizarreries ici est que l'axe Y est inversé par rapport à ce que nous avons étudié en géométrie scolaire. -0,5 est en haut de la carte et 0,5 en bas. En infographie, l'axe Y est souvent inversé. J'ai entendu que cela s'explique par la façon dont les premiers moniteurs (téléviseurs) ont effectué un balayage de haut en bas, c'est-à-dire que la première ligne de balayage était en haut, la suivante immédiatement en dessous, et ainsi de suite, c'est-à-dire que l'index Y des lignes de balayage est passé de zéro en haut à un certain nombre positif en bas. Quoi qu'il en soit, le même système de coordonnées est utilisé au format SVG (Scalable Vector Graphics), c'est pourquoi Dragons Abound aussi.

Ce système de coordonnées est indépendant de la façon dont la carte est affichée. C'est juste un système sans dimension pour créer le monde - la ville est située à (0,12875, -0,223), la frontière passe de (0,337, 0,010) à (0,333, 0,017), etc. Et bien que mes cartes régionales actuelles soient limitées à une plage de 0,5 à -0,5, ce n'est pas la limite du système de coordonnées. Je peux créer un monde au-delà de ces frontières.

Le prochain système de coordonnées est ce que SVG appelle viewbox. Il définit les vraies coordonnées qui seront utilisées pour dessiner les graphiques. Par exemple, Dragons Abound au début définit la zone de visualisation sur les coordonnées (-500, -500) et elle a une largeur de 1000 et une hauteur de 1000:


(Il y a une faute de frappe dans l'image, le haut de l'axe Y doit être -500, désolé.)

Vous pouvez remarquer que dans ce cas, la transformation entre le premier et le deuxième système de coordonnées consiste uniquement à multiplier le tout par 1000. C'est-à-dire. afin de dessiner quelque chose, le jeu trouve les coordonnées de cet objet, les multiplie par 1000 et dessine SVG dans ces coordonnées.

Autrement dit, je peux utiliser les coordonnées de la fenêtre d'affichage pour me permettre de tracer une ligne de (0, 0) à (250, 250). Mais en fait, je ne veux pas tracer une ligne de (0, 0) à (250, 250) sur l'écran de l'ordinateur. Cela signifierait que si je veux afficher la carte à un autre endroit de l'écran, je devrai changer les coordonnées de tous les objets de la carte et les redessiner. Ce serait un travail énorme.

Pour contrôler les coordonnées d'affichage des graphiques à l'écran, SVG dispose d'un troisième système de coordonnées appelé viewport. La fenêtre d'affichage est la partie de la page dans laquelle les graphiques doivent être dessinés (sur la page Web, il s'agit de l'élément <svg>). Il a une largeur, une hauteur et un emplacement. L'emplacement correspond aux coordonnées du coin supérieur gauche de la fenêtre. Autrement dit, si je devais afficher la carte dans la fenêtre avec les coordonnées (30, 100), qui a une hauteur et une largeur de 800, le système de coordonnées de la fenêtre ressemblerait à ceci:


Dans SVG, la boîte de vue et la fenêtre des systèmes de coordonnées sont connectées l'une à l'autre, et SVG s'occupe lui-même de la transition entre elles. Nous dessinons simplement dans le système de coordonnées de la fenêtre d'affichage et tout le rendu est affiché à l'emplacement de la fenêtre correspondante. (Il y a quelques problèmes lors de la création d'une fenêtre et d'une fenêtre avec des proportions différentes. Ensuite, les objets sont soit tronqués, soit étirés, selon la valeur de l'attribut preserveAspectRatio . Je recommande de ne pas le faire du tout.)

Pour résumer: une ville située dans les coordonnées mondiales (0,10, 0,33) est dessinée en coordonnées (100, 330) et affichée à l'écran en (110, 764).

Vous pouvez maintenant comprendre pourquoi cela peut prêter à confusion!

Que se passe-t-il si je modifie chacun de ces systèmes de coordonnées? Supposons que dans le premier système de coordonnées, je vais générer un monde allant de -0,25 à 0,25 sur chaque axe. Le monde résultant sera alors quatre fois plus petit que le monde habituel et ne remplira que la partie centrale de la fenêtre:


(Vous pouvez également remarquer des artefacts sur les bords, qui sont généralement cachés.) De même, si je double la taille du premier système de coordonnées (SK), nous ne verrons pas la majeure partie de la carte, car elle sera située à l'extérieur des bords de la fenêtre.

Que se passe-t-il si je double la taille de la fenêtre d'affichage? Eh bien, si je double également le rapport entre le premier SC et la viewbox (de 1000 à 2000), alors rien ne changera beaucoup. Si le rapport reste égal à 1000, la carte sera à nouveau divisée par deux.


Cependant, cette fois, la carte a une zone initiale de 1x1. Nous pouvons à nouveau remarquer des artefacts aux bords qui sont généralement cachés (par exemple, des parties convexes de forêts). Vous pouvez également voir que le modèle de l'océan est incorrect - je dois avoir câblé certaines hypothèses sur la taille de la fenêtre d'affichage. De plus, il semble que la boussole ne se trouve pas sur le coin de la carte, mais sur le coin de la fenêtre d'affichage.

Et vice versa, si je réduis de moitié la taille de la fenêtre d'affichage, cela créera un effet de zoom sur la carte:


Ici, nous ne voyons que le quart médian de la carte. Ce n'est pas un moyen très pratique de zoomer, car seule la moitié de la carte affiche des problèmes - par exemple, le marqueur de ville «South Owenson» est allé au-delà de l'écran. De plus, cela double la taille des polices et d'autres choses dont je n'ai pas besoin.

Un aspect plus utile de la fenêtre d'affichage est de modifier l'origine. Jusqu'à présent, la fenêtre d'affichage était centrée sur la carte, mais ce n'est pas nécessaire. Par exemple, je peux déplacer la carte vers la droite en centrant la fenêtre d'affichage sur un point sur le côté gauche de la carte:


Nous pouvons à nouveau remarquer les effets sur les frontières et certains autres problèmes, mais essentiellement la carte s'est déplacée vers la droite. L'utilité de cela peut ne pas être évidente, mais imaginez que je vais générer une carte dont la largeur est le double de la largeur d'une carte normale. Par défaut, cela ressemble à ceci:


Cela ressemble à n'importe quelle autre carte, mais en réalité ce n'est que la partie centrale d'une carte plus grande. Autrement dit, je peux maintenant modifier la fenêtre d'affichage pour transférer d'autres parties de la carte dans la fenêtre de vue d'ensemble:


Ici, j'ai déplacé le point de vue vers la gauche, nous voyons donc une partie du monde à l'est de la vue d'origine. Certains noms sur la carte ont changé car Dragons Abound remplit certaines fonctions (par exemple, donne des noms aux objets) selon qu'ils sont visibles. Je vais devoir changer cela pour que lors du déplacement de la fenêtre d'affichage, la carte reste constante. Cependant, plus tard, je pourrai déplacer la fenêtre d'affichage sur une grande carte et générer des cartes régionales de toute zone souhaitée. Autrement dit, je peux générer et afficher de grandes cartes de la taille d'un continent, mais je peux également générer des cartes régionales de zones au sein d'une grande carte.

Pour résumer: le jeu utilise trois systèmes de coordonnées. Le premier est un SC abstrait pour les objets du monde. La seconde est la fenêtre de visualisation, elle définit la zone visible du monde. La troisième est la fenêtre, elle contrôle où la carte sera dessinée à l'écran. Pour dessiner un monde plus grand, j'ai besoin d'étendre le premier SC. Pour afficher plus à l'écran, vous devez agrandir la fenêtre d'affichage. Je peux également déplacer la fenêtre d'affichage pour afficher différentes parties du grand monde.

Partie 2. Rendre les cartes permanentes

Dans la partie précédente, j'ai exploré les systèmes de coordonnées et appris à déplacer la fenêtre SVG pour n'afficher que des parties individuelles du grand monde. Cependant, cette approche a quelques problèmes, car plus tôt j'ai supposé que tout ce qui nous était invisible n'a pas d'importance. Dans cette partie, je vais éliminer ces hypothèses afin qu'il soit possible de générer et de visualiser différentes parties de grandes cartes immuables.

Le problème du placement des noms, que j'ai décrit dans la partie précédente, est évidemment perceptible sur ces deux types de carte:


Voici le même monde, seule la vue est décalée vers la gauche:


Vous remarquerez peut-être que la géographie est la même, mais de nombreux noms ont changé. Étant donné que dans deux types différents objets sont visibles et que le processus de création de noms est contrôlé par des nombres aléatoires, des noms différents sont obtenus.

En regardant le code, j'ai constaté que presque tous les objets sont nommés en fonction de leur visibilité. Mais il n'y a qu'une seule exception qui rend difficile de donner des noms à tous les objets suivants. Dans notre cas, l'exception est que Dragons Abound ne génère que des côtes visibles. Les raisons de cela sont très déroutantes. En fait, il y a un «littoral» le long du bord entier du monde, mais la création de cette ligne détruit une partie de la logique du programme, car elle embrasse le monde entier. Pour éviter cela, je viens de générer uniquement le littoral visible. Maintenant que la carte peut s'étendre bien au-delà de la fenêtre, cette solution ne semble pas bonne. Au lieu de cela, je dois arrêter de générer des côtes lorsque je me rapproche du bord réel de la carte. (Ce que je laisse toujours hors écran pour masquer les problèmes sur les bords.)

Après avoir éliminé ce problème, les noms sur les deux cartes restent constants:


et:


Autre remarque pour l'avenir: si j'utilise la fonction d'interactivité pour changer les noms des objets de carte, ce changement ne sera pas recréé sous sa forme actuelle, et ne sera probablement même pas reproductible. Ça vaut la peine d’y penser.

Si vous regardez attentivement la carte précédente, vous pouvez voir que la zone océanique près de la partie centrale inférieure de la carte a une étiquette suspendue «Meb Island». Cela est arrivé parce que Dragons Abound croit réellement que la région de l'océan est une île. Je n'entrerai pas dans les détails techniques, mais il est étonnamment difficile de distinguer les îles des lacs lorsqu'ils dépassent la carte. L'algorithme porte à confusion avec le changement que j'ai apporté à la génération de côtes invisibles, et pour éviter de tels problèmes, cela doit être corrigé.

Maintenant, quadruplons la taille de la carte et n'en affichons qu'un quart dans la fenêtre de la carte:


En général, tout semble bon (il y a un système de rivières intéressant sur la carte, un grand lac, mais vous pouvez voir que les villes sont très rares. C'est arrivé parce que Dragons Abound génère 10-20 villes. Cet intervalle est bien adapté pour un monde de taille normale, mais mauvais, lorsque la taille est quatre fois plus grande. Par conséquent, l'intervalle doit être modifié en fonction de la taille relative du monde. Probablement, cela doit être fait à plusieurs endroits.

Voici la même carte après avoir résolu le problème:


Maintenant, sur la carte, il y a un nombre plus logique de villes et villages, mais cela nous montre un autre problème. Vous pouvez voir beaucoup de noms supplémentaires sur les bords de la carte, par exemple, Nanmrummombrook, Marwynnley et Noyewood dans le coin inférieur gauche. Cela se produit car la méthode du code de placement essaie de les placer là où ils sont visibles. Auparavant, cette procédure n'avait jamais à se soucier des étiquettes en dehors de l'écran, car dans les cartes de taille régionale, le monde entier est généralement visible. Mais maintenant, il peut y avoir des villes et d'autres objets situés hors de l'écran. Par conséquent, je dois ajouter une logique à la procédure de placement d'étiquette qui n'essaie pas de créer des étiquettes pour les objets de carte invisibles.


Maintenant, l'image est plus logique. À droite, Cumden est à peine visible sur la carte, mais l'étiquette est toujours située là où elle est visible.

Il y a un aspect qui n'est pas immédiatement perceptible sur les grandes cartes: le nombre d'emplacements dans le monde n'a pas changé. Bien que la carte (dans un sens) soit devenue 4 fois plus grande, sa superficie totale est toujours limitée par le même nombre d'emplacements. L'étape initiale de la génération de la carte était de couvrir le monde avec un diagramme de Voronoi avec un nombre constant d'emplacements. Autrement dit, lorsque la carte devient plus grande, les cellules de Voronoi deviennent également plus grandes.

Il serait logique de mettre à l'échelle le nombre d'emplacements en fonction de la taille de la carte, mais malheureusement, la dépendance de la vitesse d'exécution de Dragons Abound sur le nombre d'emplacements est bien pire que linéaire, c'est-à-dire que générer une carte avec un grand nombre d'emplacements peut prendre beaucoup de temps. Voici un exemple de carte avec une résolution quadruple (nombre d'emplacements):


Les emplacements ajoutés modifient le processus de génération, le terrain est donc différent des cartes illustrées ci-dessus, mais vous pouvez y voir les détails supplémentaires sur les côtes.

Heureusement, lors du profilage des performances de génération de grandes cartes, j'ai remarqué que la majeure partie du temps processeur est occupée par des problèmes évidents. Après le débogage, j'ai éliminé les plus dérangeants, ce qui m'a permis de créer encore plus de cartes. Voici la carte 4x entière:


Zoom de 25% effectué. Cela ressemble à peu près à la taille maximale de la carte que Chrome peut afficher. La procédure de génération mondiale peut traiter des cartes plus grandes, mais en essayant de les afficher, le navigateur se bloque. En ce sens, Firefox semble être plus fonctionnel; Il peut afficher des cartes 9 fois plus grandes que la taille d'origine. Voici une partie d'une telle carte - je l'ai laissée en taille réelle, vous pouvez donc l'ouvrir dans une fenêtre séparée pour mieux comprendre la taille et les détails.


Firefox est capable de générer des cartes de cette taille, mais je ne peux prendre des captures d'écran qu'à la taille maximale de la fenêtre du navigateur. J'ai une fonction pour enregistrer la carte en tant que fichier PNG, mais elle ne peut enregistrer que la partie affichée de la carte. Je pense que vous pouvez faire défiler la carte, capturer des écrans individuels et les connecter ensemble, mais cela prendra du temps.

La meilleure solution consiste à enregistrer le SVG lui-même afin qu'il puisse être ouvert dans un programme comme Inkscape.

Auparavant, je pouvais couper et coller des cartes SVG dans Inkscape, mais les SVG pour les cartes du monde sont si gros que lorsque j'essaie de couper le navigateur, il se bloque! Heureusement, j'ai trouvé FileSaver.js et vous pouvez l'utiliser pour enregistrer le SVG directement dans un fichier, puis l'ouvrir dans Inkscape, créant ainsi une très grande image.

Du moins théoriquement. Lorsque j'essaie d'ouvrir ces cartes dans Inkscape, je rencontre quelques problèmes.

Le premier problème est que les hypothèses d'Inkscape sont différentes des hypothèses de Chrome et Firefox sur la façon d'ouvrir SVG. En particulier, si la couleur de remplissage n'est pas spécifiée dans le chemin, les navigateurs supposent qu'il n'y a pas de remplissage; Inkscape suppose que le contour est rempli de noir. Par conséquent, lorsque j'ouvre le SVG enregistré dans Inkscape, il est presque entièrement noir, car la couche supérieure de la carte ne contient pas de couleur de remplissage. Cela peut être résolu en spécifiant «fill: none» aux endroits nécessaires afin que les contours apparaissent également dans le navigateur et Inkscape.

Le deuxième problème est qu'Inkscape a des erreurs dans le traitement des masques. Inkscape semble créer des masques avec un seul élément et gère mal les masques avec plusieurs éléments. Dragons Abound crée de nombreux masques avec plusieurs éléments. Vous pouvez contourner ce problème en regroupant tous les éléments de chaque masque de jeu en un seul élément de groupe (facultatif).

Le troisième problème est lié aux images et autres ressources téléchargeables. Dans le SVG d'origine, les références à celles-ci sont indiquées sous une forme relative, par exemple, «images / background0.png». Mes sources sont organisées de manière à ce que le serveur Web distinct que j'utilise puisse trouver ces ressources aux endroits spécifiés. Lorsque je prends le même SVG et que je l'ouvre dans Inkscape, ces chemins relatifs sont traités comme l'URL «fichier:» et Inkscape recherche des ressources par rapport au dossier dans lequel le SVG a été enregistré. Ce problème peut facilement être contourné en enregistrant le SVG dans un dossier dans lequel il existe déjà des ressources aux bons endroits; il peut s'agir du même dossier racine utilisé par le serveur Web, ou d'un autre emplacement dans lequel se trouvent des copies de ressources sur les mêmes chemins (relatifs).

Le quatrième problème concerne les polices. Dragons Abound utilise à la fois des polices Web et des polices stockées localement; les deux au format WOFF2. Dans le navigateur, elles sont appliquées au texte en utilisant le style de famille de polices CSS, et avant de générer la carte, toutes les polices possibles sont téléchargées sur la page Web pour être prêtes à l'emploi. Lorsque le même fichier est ouvert dans le jeu, il recherche les polices dans le répertoire des polices système et il semble qu'aucun autre répertoire de polices ne puisse être spécifié de quelque manière que ce soit. Une solution simple (au moins sur la machine sur laquelle je développe) consiste à installer les polices utilisées par le jeu dans le répertoire des polices système. Cependant, ce n'est pas aussi simple qu'il y paraît, car les noms de police doivent correspondre, et sous Windows, il n'existe aucun moyen facile de modifier le nom de la police. Mais, bien sûr, un tel schéma ne fonctionnera pas sur les ordinateurs sur lesquels toutes les polices nécessaires ne sont pas installées. Une solution plus portable consiste à incorporer des polices SVG dans les cartes . Ce sera sur ma liste TODO.

À la fin, je suis arrivé à cette interface de génération de carte:


Les champs de saisie étendus spécifient la taille totale du monde, où 1x1 est la taille des cartes sources. La taille de vbx (viewbox) détermine la taille d'un fragment du monde affiché sur la carte; dans la capture d'écran, il a également une valeur de 1x1, c'est-à-dire que la carte affichera le monde entier. Les champs du centre vbx spécifient l'emplacement du centre de la carte dans le monde; 0, 0 est le centre du monde. Enfin, les paramètres SVG spécifient le nombre de pixels d'écran pour 1 unité de taille de zone de visualisation; à une valeur de 775, une carte 1x1 sera affichée à l'écran au montant de 775x775 pixels. C'est pratique lorsque je crée une très grande carte. En définissant le paramètre sur une valeur faible (par exemple, 150 pixels), je peux adapter une grande carte à l'écran dans son ensemble.

En modifiant ces six paramètres, je peux contrôler la taille du monde et la fraction du monde qui est affichée sur la carte. Le bouton Générer fonctionne exactement comme vous pouvez le deviner; le bouton Afficher affiche simplement une partie du monde, c'est-à-dire que je peux générer un monde, puis afficher ses parties individuelles, en modifiant les paramètres de la zone de visualisation sans avoir à recréer le monde. (Un programmeur implémenterait mieux cela comme mise à l'échelle et défilement.) Le bouton Enregistrer PNG enregistre la carte visible sous forme de fichier PNG; Le bouton Enregistrer SVG enregistre le fichier SVG de la carte entière. Le bouton Test It est utilisé pour exécuter le code de test, qui change au cours du développement de diverses fonctions.

Maintenant que je peux générer et refléter toutes les parties du grand monde, je peux passer à l'adaptation de la forme du terrain à des cartes plus grandes.

Partie 3. Formes de sushi

Après avoir apporté diverses modifications dans la partie précédente, je peux maintenant générer des mondes beaucoup plus grands que les précédents (jusqu'à 8 fois plus) et les enregistrer en tant que grandes images graphiques:


(Ouvrez l'image dans une fenêtre séparée pour voir la carte en pleine résolution 4800x2400 sur Flickr.)

Je génère ces cartes en utilisant la même génération procédurale qui a créé les cartes régionales. La carte ci-dessus a une forme continentale assez régulière et quelques îles extérieures intéressantes. Cependant, cela dépend principalement de la chance. Voici une autre carte:


Cette carte est juste le chaos des îles et du fromage à sushi suisse.

Voici un autre exemple, quelque chose entre les deux cartes précédentes. Ce n'est pas complètement réaliste, mais cela peut être intéressant pour un environnement fantastique:


Il s'agit d'une énorme masse continentale de terres, mais il existe de nombreuses formes de terres étranges et, en général, le monde ne semble pas tout à fait «réel». (Bien que pour quelqu'un, un tel monde semble tout à fait approprié pour la fantaisie.) Alors, quelles formes devrait avoir la carte du «monde»?

La plupart des cartes du monde fantastique que j'ai vues représentent un grand continent insulaire (avec de petites îles autour), par exemple, comme cette carte d' Andelen :


Ou la péninsule du continent, comme sur cette carte d' Angorun :


De temps en temps, une carte est entièrement composée de terres ou de plusieurs continents insulaires, mais ils sont plus susceptibles d'être des exceptions à la règle.

Pour commencer, imaginons la génération des continents «insulaires». Comme il se trouve dans mon jeu, il y avait déjà une fonction qui génère un grand îlot central sur la carte en tenant compte de la taille de la carte, elle devrait donc être adaptée pour générer la forme principale du continent. Le bruit et les îles supplémentaires s'occuperont du reste.


Je ne m'attendais pas à une grande mer centrale sur cette carte, mais c'est une agréable surprise. Voici un autre exemple:


Le problème avec la fonction de l'îlot central est qu'il commence par un cercle qui convient aux cartes carrées que j'ai montrées, mais pas très bon pour les cartes rectangulaires. (Vous trouverez ci-dessous des exemples avec une petite distorsion, afin que les formes de base soient plus clairement visibles.)


Ceci est facilement corrigé en masquant les sushis au lieu d'un cercle avec une ellipse (déformée) prise par la taille de la carte:


Ces îles centrales sont dimensionnées pour remplir la carte, mais dans de nombreux cas, pour les cartes continentales, nous devons laisser une «frontière» autour du continent. Deux paramètres contrôlent la taille de la carte remplissant l'île le long des axes X et Y.


Voici le même système de gestion des frontières avec des distorsions plus logiques:


On peut voir que les parties est et ouest de la carte restent l'océan. (Vous pouvez ouvrir la carte dans une fenêtre séparée pour l'étudier plus attentivement.) Cela signifie que la carte affiche le monde entier (et ses bords droit et gauche peuvent être connectés) ou une partie du monde qui peut être connectée à une autre carte qui a également un océan à partir du bord correspondant.

Un lecteur attentif qui a étudié la carte précédente a peut-être remarqué que les motifs de l'océan et de la terre s'arrêtent au milieu de la carte.Auparavant, je n'avais que des cartes de taille 1x1, de sorte que les tailles des motifs de l'océan et de la terre étaient adaptées à ces cartes. Sur les cartes plus grandes, j'ai besoin de carreler manuellement les motifs sur la carte, j'ai donc ajouté cette fonctionnalité. (Il existe un moyen en SVG pour effectuer un mosaïque de motifs, mais dans Chrome, il contient un bogue, donc je ne peux pas l'utiliser.) C'est une bonne fonctionnalité, car maintenant je peux utiliser des motifs terrestres et océaniques plus petits qui se tuileront automatiquement. Je ne sais pas pourquoi je ne m'en étais pas rendu compte avant!

Ainsi, maintenant les continents insulaires fonctionnent bien, et nous allons passer à la mise en œuvre des continents «péninsulaires» - des cartes dans lesquelles le continent apparaît sur la carte depuis son bord.


Dans ce cas, le continent ne peut pas s'effondrer sur trois bords. Mais la caractéristique principale de ces cartes est qu'elles ont une connexion terrestre significative entre le continent affiché sur la carte et la terre en dehors de la carte.

Le moyen le plus simple de fournir une telle connexion en dehors de la carte est de définir un niveau bas de la mer pendant la génération. Nous allons donc augmenter la zone de terre affichée sur la carte, ce qui augmente la probabilité de grandes masses de terre et la présence de terres (plutôt que la mer) le long des bords de la carte.


Bien sûr, cela ne garantit pas que la masse de terre sera très intéressante, et en effet elle sera unifiée:


La similitude d'un seul continent peut être créée en utilisant la même génération du continent insulaire, mais en déplaçant en même temps l'île au bord de la carte. Vous obtenez quelque chose comme ça:


On peut voir que le continent (principalement) est l'île centrale, décalée vers le haut et vers la droite. Comme il s'agit d'un continent et qu'il n'est pas nécessaire de conserver une forme d'île stricte, vous pouvez ajouter plus de distorsion à la forme.


Évidemment, il existe de nombreuses autres approches pour la génération de secours, mais ces deux, au moins, me donnent l'occasion de générer les formes de terres les plus courantes à l'échelle continentale.

Un lecteur attentif a pu remarquer les formes étranges de forêts sous forme de rayures sur de nombreuses cartes des continents. La prochaine fois, je commencerai à traiter les problèmes des modèles de vent et des biomes qui causent ces bizarreries.

Partie 4. Modèle de vent

Comme indiqué, la taille des continents sur les cartes Dragons Abound a commencé à montrer des modèles irréalistes de temps et de biomes. Cet exemple montre que la forêt est alignée le long de la direction du vent dominant:


La raison n'est pas dans le code cassé; les modèles météorologiques et de biome sont plutôt trop simples, et à grande échelle, cela devient apparent. Pour faire face à ces problèmes, j'ai commencé par réviser le modèle de vent.

J'aimerais que mon modèle de vent reflète mieux la dynamique du vent de la Terre: les cellules de Hadley , les alizés et autres. Une telle dynamique peut aider à éliminer les modèles météorologiques étranges sur les cartes continentales. Cependant, quand ils ont été ajoutés, une insatisfaction douloureuse avec le modèle de vent Dragons Abound , lent et trop compliqué , a de nouveau été révélée . (Lisez ici la mise en œuvre initiale du modèle éolien ..) Après avoir réfléchi à cela pendant plusieurs jours, j'ai décidé que la plupart des problèmes se résument au fait que la carte du jeu est présentée sous forme de diagramme de Voronoi . (Ou plutôt, la triangulation de Delaunay du diagramme de Voronoi.) Il présente de nombreux avantages lors de la génération de terrain - en combinaison avec le bruit, il peut créer des masses terrestres d'aspect naturel. C'est pourquoi il est si souvent utilisé pour générer un soulagement. Mais comme les triangles individuels ont des tailles et des orientations différentes, tous les calculs, y compris les modèles de vent qui utilisent des cellules voisines voisines, deviennent assez compliqués. Il sera beaucoup plus facile de modéliser le vent à travers une grille de zones identiques régulièrement espacées. De plus, le modèle éolien n'a probablement pas à être aussi détaillé que le terrain.

Mais je ne veux pas abandonner complètement le diagramme de Voronoi qui sous-tend les Dragons Abound . (Au minimum, cela nécessitera la réécriture de presque tout le programme!) Au lieu de cela, je veux expérimenter avec la liaison de la carte à une grille uniforme, exécuter le modèle de vent dedans, puis effectuer la liaison inverse. Si la perte de copie dans les deux sens n'est pas trop importante, cela peut rendre le modèle de vent plus rapide et plus facile.

Quelle grille dois-je utiliser? Idéalement, la grille devrait être constituée de zones égales à égale distance de ses voisins. Et cette description est comme une grille d'hexagones.


En fait, une grille d'hexagones est le meilleur moyen de diviser une surface plane en zones égales.

L'étape suivante consiste à déterminer comment représenter la grille d'hexagones dans mon programme. J'ai cherché un peu sur le réseau pour obtenir de l'aide, et chaque lien me renvoyait à la page sur les grilles des hexagones d' Amit Patel ( traduction en Habré). Probablement, il faut commencer par cela; Il est également bon d'explorer d'abord le site Web des jeux Red Blob si vous recherchez des informations sur la mise en œuvre des mécanismes de jeu. Amit explique mieux que moi, donc si quelque chose n'est pas clair, alors lisez sa page.

Le premier choix à faire est la manière de stocker la grille d'hexagones. Le moyen le plus simple consiste à le stocker sous forme de tableau à deux dimensions, puis j'ai besoin de pouvoir lier les cellules de la grille au tableau. Il existe de nombreuses options ici (lire la page d'Amit ), mais j'utiliserai ce qu'il appelle odd-r:


Les nombres dans chaque cellule sont les indices de la cellule dans le tableau à deux dimensions. (L'image est volée sur la page d' Amit . Sur sa page, elles sont interactives, donc je vous conseille de les expérimenter.)

Après avoir fait un choix, je dois maintenant apprendre à attacher des index à une grille d'hexagones. Par exemple, si je recherche une cellule hexagonale (3, 3), quels seront ses voisins? Si chaque cellule a une largeur de 5 pixels, alors quelles seront les coordonnées du centre de la cellule (3, 3)? Et ainsi de suite.Gérer cela peut être difficile, donc je suis content qu'Amit l'ait fait pour moi.

En supposant que nous pouvons voler tout ce dont nous avons besoin à Amit, je dois d'abord comprendre comment organiser les hexagones sur la carte. À ce stade, je n'ai pas encore besoin d'un tableau, je peux prétendre qu'il l'est et voir où seront les hexagones. Si je connais l'emplacement des hexagones, je divise simplement la largeur de la carte par la distance horizontale entre eux pour obtenir le nombre de colonnes, et je fais de même verticalement pour obtenir le nombre de lignes, après quoi je dessine un hexagone à chaque endroit:


Ces hexagones sont beaucoup plus grands que ceux que j'utiliserai pour le modèle de vent, mais ils me montrent que tout est correctement placé.

Ici, j'ai ouvert les bords de la carte et dessiné uniquement l'hexagone central et aux frontières pour vérifier si je ferme vraiment la carte entière:


Le haut et le bas sont en dehors de la carte, mais la présence de plusieurs cellules à l'étranger n'est pas importante si je ne manque pas une partie de la carte.

L'étape suivante consiste à créer un tableau pour la grille d'hexagones et à aligner tous les triangles de Delaunay sur les hexagones correspondants. Étant donné que Javascript ne prend pas en charge les index négatifs des tableaux , je dois déplacer la cellule (0, 0) du centre de la carte vers le coin supérieur droit. Cela fait, je fais le tour de tous les triangles de Delaunay et je les ajoute aux cellules correspondantes de la grille hexagonale. Je peux le vérifier en coloriant les hexagones contenant du terrain:


Pour déterminer si une cellule est un terrain, je fais la moyenne de la hauteur de tous les emplacements qui tombent dans cette cellule. Vous remarquerez peut-être que pour certains hexagones côtiers, la moyenne est inférieure à zéro, même en présence de terre. Vous pouvez également utiliser la hauteur maximale de tous les emplacements dans l'hexagone:


Dans ce cas, la recherche a lieu dans la direction opposée - l'hexagone est marqué comme terrain s'il y a du terrain dedans. Ce qui est mieux dépend de ce dont vous avez besoin.

Dans tous les cas, je peux augmenter la précision en réduisant la taille des hexagones:


Maintenant, la côte s'est beaucoup améliorée, mais un nouveau problème est apparu - de nombreux hexagones internes qui ne sont pas considérés comme des terres. Cela se produit parce que lorsque les hexagones deviennent suffisamment petits, à l'intérieur de certains d'entre eux, il n'y a aucun triangle de Delaunay. Par conséquent, ils n'ont pas de «hauteur». (Cela montre également l'inégalité des triangles de Delaunay.)

Vous pouvez utiliser cette solution - prendre la hauteur des triangles manquants comme la moyenne de leurs voisins, ou comme un maximum de leurs voisins.


En général, lorsque la liaison entre les hexagones et les emplacements n'est pas un à un, des corrections sont nécessaires pour remplir les informations manquantes.

Maintenant que j'ai posé la grille d'hexagones sur la carte, nous pouvons commencer à implémenter le modèle de vent. L'idée principale du modèle de vent est de simuler certains vents (alizés) et de les répartir sur toute la carte jusqu'à ce qu'ils atteignent un état d'immobilité. Au niveau des hexagones (ou au niveau des emplacements, si je le fais sur les triangles de Delaunay), cela comprend deux étapes: (1) nous résumons tous les vents entrant dans l'hexagone actuel, et (2) nous déterminons comment le vent sommé quitte l'hexagone.

La première étape est assez simple. Chaque hexagone a six voisins et chacun de ces hexagones contribue. Si nous considérons chacun des vents entrant dans l'hexagone comme un vecteur, alors le vent total dans la cellule sera la somme de ces vecteurs, c'est-à-dire deux vents strictement opposés de force égale s'annulent.

La deuxième étape (déterminer comment le vent total quitte l'hexagone) nécessite une réflexion. Le cas le plus simple est le vent qui souffle directement à travers l'hexagone:


Dans ce cas, nous nous attendons à ce que le vent se déplace vers la cellule suivante sans changements. (Ici, le vecteur rouge est le vent d'origine et le bleu est le vecteur du vent se propageant.)

Mais que se passe-t-il si le vent ne souffle pas directement sur la cellule voisine?


Dans ce cas, il semble logique qu'une partie du vent souffle dans l'hexagone directement au-dessus de lui, l'autre partie dans la cellule située dans le sens antihoraire de celle-ci, et les proportions devraient dépendre de la direction dans laquelle la flèche pointe. Dans notre cas, la partie principale du vent se déplacera vers la cellule supérieure, et moins vers la cellule voisine.

Il est également nécessaire de décider de la direction du vent qui se propage. Une option consiste à maintenir la direction du vent d'origine:


Il semble que ce soit l'option la plus réaliste, mais il y en a une autre - pour changer la direction du vent en fonction du bord de l'hexagone qu'il intersecte:


Cette approche est moins précise, mais présente un avantage: les vents entrants seront toujours dans l'une des six directions, ce qui peut simplifier les calculs.

Une autre difficulté survient lorsque l'on considère le terrain. Que doit-il se passer lorsqu'une montagne se lève dans le vent?


Dans ce cas, une partie du vent passe au-dessus de la montagne (créant éventuellement des précipitations), mais une partie du vent se tourne sur les côtés.


Par conséquent, la façon dont le vent sort de l'hexagone dépend de sa direction, ainsi que de la topographie des cellules voisines.

Parlons maintenant de la façon de représenter les vecteurs. Il existe deux options principales. Tout d'abord, un vecteur peut être représenté par des valeurs X et Y, par exemple comme ceci:


Si nous dessinons un vecteur commençant à (0, 0), alors (X, Y) sont les coordonnées des points finaux. Un tel enregistrement facilite la somme des vecteurs. Nous additionnons simplement toutes les valeurs (X, Y) et obtenons un nouveau vecteur:


Une autre option consiste à utiliser l'angle et la longueur du vecteur:


Sous cette forme, il est facile d'effectuer des opérations telles que la rotation de vecteurs ou la modification de sa longueur.
Pour la majorité des opérations requises dans le modèle éolien, la première option est meilleure, mais dans certains cas, la seconde est meilleure, il serait donc pratique de basculer entre elles si nécessaire. Afin de ne pas réinventer la roue, j'ai recherché une bibliothèque vectorielle pour Javascript et Victor.js complètement montée , alors j'en ai profité.

Je vais commencer par ajouter un vecteur vent à chaque hexagone et voir si je peux le visualiser:


Il semble bon jusqu'à présent.

L'étape suivante consiste à vérifier si je peux correctement diviser le vecteur vent et le distribuer à la cellule suivante. Tout d'abord, vous devez calculer les angles menant aux autres cellules. J'ai retrouvé la réponse sur la page d'Amit :


C'est-à-dire qu'un vecteur à 0 degré pointe vers un hexagone à droite, à 60 degrés - vers un hexagone en bas à droite, et ainsi de suite. Un vecteur pointant entre ces deux directions est divisé proportionnellement entre deux cellules - c'est-à-dire qu'un vecteur à un angle de 30 degrés sera réparti également entre la cellule à droite et la cellule de bas à droite. Chaque vecteur se situe quelque part entre les coins des faces de deux cellules voisines, alors regardez simplement l'angle du vecteur vent, découvrez qu'il tombe entre les coins centraux de deux hexagones, puis divisez-le proportionnellement entre ces deux hexagones.

Par exemple, si le vecteur vent a un angle de 22 degrés:


puis 38/60 de la valeur se propage à la cellule de droite et 22/60 de la valeur vectorielle à la cellule en bas à droite. Si les vecteurs sont présentés sous la forme d'une paire de valeurs X et Y, vous pouvez les distribuer en multipliant chaque valeur du vecteur d'origine par une fraction (par exemple, 22/60), puis en l'ajoutant au vecteur vent dans le nouvel hexagone.

Pour tester cela, je peux organiser les vents dans différentes directions et les placer en haut et sur le côté de la carte et voir s'ils peuvent se propager correctement sur la carte. Lorsque les vents entrent en collision, ils doivent être combinés et choisir la direction moyenne avec une vitesse accrue:


Ici, nous voyons que les vents se rencontrent le long de la diagonale et se combinent pour souffler vers le coin inférieur.

L'étape suivante consiste à prendre en compte l'influence de la terre sur le vent. Bien sûr, les modèles de vent réels sont très complexes, mais je m'intéresse principalement à la façon dont la géographie des terres affecte les vents de surface. Au niveau le plus simple, il s'agit de l'influence des hauteurs et des basses terres sur la direction et la vitesse du vent. J'ai expérimenté de nombreuses approches différentes, mais en conséquence je me suis fixé deux règles simples :

1. Le vent se détourne des obstacles.
2. Le vent ralentit quand il se lève et accélère, tombant.

Un obstacle se produit lorsque le vent souffle dans une cellule avec une hauteur plus élevée, par exemple, dans une cellule avec une montagne. Lorsque cela se produit, je regarde les deux cellules dans lesquelles le vent souffle, et change l'angle du vent pour qu'il pointe davantage vers le bas des deux hexagones. L'amplitude des changements d'angle dépend de la différence de hauteur de deux cellules, donc lorsque le vent souffle dans deux cellules voisines avec des montagnes, sa direction change peu, mais s'il souffle dans une cellule avec une montagne et une cellule avec une plaine, alors il se tournera davantage vers la cellule vide:


La force du vent peut être ajustée. Sur la carte ci-dessus, il est trop fort, ce qui entraînera l'émergence de nombreux biomes irréalistes. Voici une signification plus logique:


Une grande partie du mouvement du vent causé par les reliefs subsiste, mais les grands écarts et vallées du vent fort sont devenus plus petits.

Une autre caractéristique qui améliore le réalisme est la dispersion du vent. Par exemple, la carte ci-dessus montre que le vent souffle vers l'ouest juste au-dessus de la ville de Breeches. Bien qu'il souffle sur de longues distances, il ne se dissipe jamais comme prévu. Lorsqu'un vent soufflant rencontre un autre air, il entraîne généralement le vent avec lui. Pour simuler cela, je peux prendre une petite partie du vent qui souffle dans chaque hexagone et le redistribuer à toutes les cellules voisines. Voici à quoi ressemblera la carte ci-dessus avec un petit nuage de points:


Comme vous pouvez le voir, maintenant le vent sur la culotte a commencé à se dissiper un peu.

Cette opération détermine la majeure partie des directions du vent. La deuxième partie est la décélération du vent lors de la montée et l'accélération lors de la descente. Je peux le réaliser en regardant la hauteur relative de la cellule d'où vient le vent, et la hauteur de la cellule dans laquelle le vent souffle, et en l'accélérant / le ralentissant si nécessaire.

Voici à quoi tout cela ressemble:


Nous voyons maintenant qu'une partie du vent soufflant à travers les hautes montagnes de la partie centrale de l'île a été coupée. Et vice versa - plusieurs nouveaux vents sont apparus dans la partie ouest de l'île, où l'air se déplace depuis des terres relativement hautes vers la mer. (C'est une brise côtière ! Bien que pas vraiment: le mécanisme est différent là-bas.)

Maintenant, je peux remplacer un nouveau vent dans l'algorithme de précipitation existant. Voici une comparaison (vieux vents à gauche, nouveaux vents à droite):


(Cliquez sur l'image pour voir une version plus grande.) Évidemment, il existe des différences entre les modèles de vent. Sur les deux cartes, le vent souffle de l'est. Les montagnes proches du centre de la carte tournent le vent vers le sud, provoquent de fortes précipitations et créent un marécage et des forêts au sud des montagnes. Dans la partie inférieure, le vent souffle sans aucune interférence, et des forêts se forment le long de la moitié orientale de l'île. Dans le modèle de vent d'origine, suffisamment de vent a traversé les montagnes centrales et les marécages pour créer une forêt dans la partie ouest de l'île. Dans le nouveau modèle, la majeure partie du vent est coupée et des biomes herbeux se forment de l'autre côté des montagnes.

L'ancien modèle a la variabilité des paramètres aléatoires (dans un intervalle donné), et il est probable qu'une certaine combinaison de ces paramètres donnerait une image plus comme une nouvelle carte. Mais en fait, nous n'avons pas besoin de reproduire le comportement exact de l'ancien modèle, juste un modèle qui crée des résultats probants.

Le but de tout cela est d'accélérer et de simplifier la génération de vent afin que de nouveaux comportements de vent puissent être ajoutés aux cartes continentales. Je l'ai fait? J'ai présenté le modèle de vent d'origine et le nouveau modèle à base d'hexagone. Il s'est avéré que le nouveau modèle est 15 à 20 fois plus rapide que l'original (!). Il s'agit d'une accélération très importante qui a peu d'effet sur les cartes. Les expériences montrent clairement que le modèle n'est pas particulièrement sensible à la taille des hexagones, donc si nécessaire, je peux accélérer encore plus l'algorithme en augmentant la taille des cellules.

La prochaine fois, nous travaillerons sur l'utilisation d'un nouveau modèle de vent pour mettre en œuvre des modèles de vent à l'échelle continentale, puis nous les connecterons au modèle de précipitations et aux biomes.