Quels sont les bons algorithmes pour générer des bordures / zones d'état sur des cartes 2d étoiles?

J'essaie de générer une carte stellaire bidimensionnelle assez grande qui montre différentes factions / états, chacun possédant un ou plusieurs systèmes stellaires. Je voudrais créer automatiquement des frontières / zones pour les factions.

L'idée est essentiellement de partir de quelque chose comme ça (les points représentent des systèmes stellaires sur un plan 2D, les couleurs sont des affiliations de factions)

pour ça

La génération de cartes comme celle-ci semble être une exigence assez courante, donc ma vraie question est la suivante: existe-t-il des algorithmes standard pour générer des zones d'état comme indiqué? Si oui, pourriez-vous me les signaler? Sinon, pouvez-vous penser à un bon algorithme (l'idée de base ou le pseudo-code sont très bien)?

Les performances de l'algorithme ne sont pas une préoccupation majeure pour moi, donc je préfère avoir une carte "plus jolie" qu'une carte plus rapide à générer. Cette question similaire propose une approche qui est probablement applicable à mon problème, mais avec quelques "améliorations" nécessaires: Comment créer une carte à partir d'un graphique

Permettez-moi d'expliquer ce que je veux dire quand je dis plus joli: au bas de la question liée, le demandeur présente son résultat final après avoir mis en œuvre la réponse acceptée. Mon premier problème ici: les zones pour les nœuds # 6, # 9 et # 12 sont très petites et de forme étrange. De plus, au lieu des arêtes vives, je préférerais un aspect plus lisse et incurvé.

Mes propres idées jusqu'à présent, y compris les inconvénients / questions respectifs que je vois avec eux:

• Générez un polygone de "coque convexe" pour chaque faction, puis développez un peu vers l'extérieur. Problèmes: aucune fonction concave. Aussi, comment gérez-vous les chevauchements?
• Générez un graphique voronoi pour les points, puis utilisez les bords du polygone voronoi entre les systèmes voisins de différentes factions comme frontières. Problème: grands polygones sur les bords de la carte - comment les identifier et les corriger?
• Générez un polygone de taille fixe pour chaque point, réunissez tous les polygones pour une seule faction (résultant en un grand "polygone de faction" potentiellement complexe). Ensuite, faites quelque chose pour réconcilier les zones qui se chevauchent entre deux factions. Problèmes: comment pourrais-je procéder exactement? Pas exactement un processus trivial. Et s'il y a chevauchement entre plus de deux factions?

Votre aide est appréciée.

Addendum: Après avoir réfléchi aux deux premières réponses et à leurs approches respectives pour résoudre le problème, j'ai réalisé que mes exigences ci-dessus sont incomplètes.

Je dois ajouter que la carte peut avoir des zones peu peuplées, ce qui signifie qu'il peut y avoir une étoile isolée ou un groupe d'étoiles. Je voudrais afficher chacun de ces clusters avec leur propre zone colorée contiguë. Quelque chose comme ça:

Je me rends compte que cela pourrait nécessiter une première étape qui identifie les clusters, puis exécuter l'algorithme réel pour chacun des clusters.

Je pense que l'idée de Voronoi est bonne. Chaque étoile devient un point de départ pour Voronoi, puis les régions de Voronoi montrent les zones appartenant à chaque faction. Cependant, il y a quelques changements qui le feront mieux fonctionner:

1. Comme vous l'avez mentionné, il y a des zones vides qui ne devraient pas être attribuées à une faction. Voronoi créera de grands polygones qui s'étendent jusqu'aux zones où la faction ne devrait pas atteindre. Pour résoudre ce problème, utilisez un algorithme de bruit bleu comme le disque de poisson pour remplir l'espace inoccupé avec des étoiles "n'appartenant à personne". Le bruit bleu est aléatoire mais uniformément distribué (il pourrait également être utile pour générer vos emplacements d'étoiles).
2. Voronoi produit des régions en blocs. Pour produire des cellules plus rondes, remplacez le calcul du centre de gravité de Voronoi par un calcul de centroïde. J'ai écrit un peu à ce sujet ici avec quelques images de comparaison.
3. Voronoi produit des polygones, mais vous voulez des zones arrondies. À chaque coin, il y a trois polygones. Lorsque les trois sont la même faction, vous pouvez la laisser seule. Lorsque deux sont la même faction, introduisez une courbe de Bézier quadratique qui déplace la frontière vers l'autre faction. Lorsque les trois factions sont différentes, vous pouvez soit laisser le coin tranquille, soit introduire trois courbes de Bézier pour éloigner toutes les frontières les unes des autres. Je ne sais pas ce qui semble le mieux.

Voici la sortie:

J'ai également écrit une page qui vous permet de peindre les régions pour voir à quoi elles ressembleraient.

L'une des nombreuses méthodes est une carte d'influence . Vous pouvez rechercher des implémentations de code spécifiques, mais l'algorithme de base est assez simple.

Pour chaque objet de faction (par exemple, le système stellaire), attribuez une valeur positive (chaude). Pour tous les autres objets des factions, attribuez une valeur négative (froide). L'ampleur du chaud ou du froid doit être basée sur l'influence que vous pensez que l'objet exerce sur son environnement et ses voisins. Ces valeurs n'ont pas à être proportionnelles si vous voulez finalement garder un "dmz" entre les factions.

Utilisez ces détails pour créer une grille temporaire (par exemple un tableau) qui se rapproche des pixels de votre carte. Vous pouvez créer une telle grille à la résolution souhaitée, y compris 1: 1.

Ensuite, utilisez l'équation de transfert chaleur / champ pour itérer et propager les forces des objets de faction (chaleur) contre les forces des objets adverses (froid) pour chaque cellule voisine de la grille.

Rincez et répétez pour chaque faction sur votre carte en créant des grilles de faction distinctes pour chacune.

Enfin, interpolez les grilles de faction ensemble pour produire un contour d'influence pour chaque faction. Transférez ensuite cette grille sur votre carte de pixels en fonction de la résolution que vous avez utilisée pour la grille (en ajoutant des couleurs spécifiques à une faction, etc.).

L'art dans ce processus est de déterminer quelle influence chaque objet devrait avoir et quels éléments de jeu vous utilisez pour quantifier cette valeur.

Soit dit en passant, les produits de cette méthode peuvent être utilisés pour toutes sortes d'autres choses, comme votre prise de décision par intérim.

Référence supplémentaire: fil de discussion sur les origines de la cartographie de l'influence .

Vous devriez regarder dans les diagrammes de Voronoi. Voici la définition sur wikipedia:

En mathématiques, un diagramme de Voronoi est une partition d'un plan en régions en fonction de la distance aux points d'un sous-ensemble spécifique du plan.

Les points de base sont généralement générés de manière aléatoire et sont souvent appelés nœuds. Dans votre cas, chaque nœud pourrait être vos étoiles. De cette façon, la faction associée aux étoiles peut être associée à la cellule voronoi entourant l'étoile et lorsque chaque cellule a été calculée, vous joignez celles avec la même faction ensemble et vous devriez avoir une bordure assez nette autour de vos étoiles.

La bibliothèque FastNoise prend en charge les diagrammes de Voronoi, alors vous devriez peut-être y jeter un œil.

• Diagrammes de Voronoi sur Wikipédia
• Bibliothèque FastNoise sur GitHub

Lissage des régions

Gardez vos étoiles dans un «tableau sûr» et utilisez une copie de celui-ci où vous ajoutez réellement plus de points via l'interpolation des voisins les plus proches et générez le diagramme à partir de ces points. Cela devrait vous donner des régions plus douces.

Autres idées L'algorithme de fortune est basé sur une ligne droite qui balaye le plan cartésien. Une idée intéressante serait d'utiliser un cercle pour balayer l'avion du centre de votre galaxie / espace à la place, peut-être que cela pourrait aussi conduire à des formes intéressantes.

Manipulation de la géométrie

Votre dernière idée de combiner des polygones plus petits en de plus grands, puis de fixer les bords nécessitera des algorithmes de spline avancés pour modifier les formes. Je ne sais pas si cela le rendrait efficace ou beau. Je suis presque sûr que le diagramme de voronoi avec pavage supplémentaire est la voie à suivre car il résout le problème de bord par lui-même et peut même offrir des données supplémentaires par lui-même comme la distance des frontières (qui pourraient être utilisées pour déterminer les zones de conflit entre les différentes factions, la probabilité de rencontrer différents types de navires, etc.)