Générer des régions égales dans une carte hexadécimale

En prenant par exemple une grande carte hexadécimale (X par Y), comment puis-je la diviser en N régions d'hexs connectés pour simuler des pays?

L'objectif est de générer une carte hexadécimale qui ressemble à une carte réelle avec des pays de formes différentes mais de tailles égales.

Avez-vous essayé l'algorithme de Lloyd ? La procédure est assez simple et générera des régions d'aspect assez régulier (selon le nombre d'itérations que vous exécutez).

1. Mosaïque de la carte avec des hexagones vides pour commencer.
2. Choisissez N hexagones au hasard. Ceux-ci représenteront le "centre de masse" de chaque pays.
3. Marquez chaque hex avec l'hex central dont il est le plus proche ( diagramme de Voronoi ). Le pays i est l'ensemble de tous les hexs les plus proches du ième hexagone central.
4. Calculez le nouveau centre de masse pour chaque pays.
5. Répétez les étapes 3 et 4 autant de fois que vous le souhaitez pour lisser les régions générées.

Vous n'avez pas besoin de l'exécuter très longtemps pour produire une belle carte. Cet exemple n'a nécessité que trois itérations.

Une façon simple que vous pourriez essayer.

1. Sélectionnez au hasard des nhexagones. Chacun commencera un groupe.
2. Pour chaque groupe, essayez d'agrandir l'hex initial dans une direction aléatoire.
3. Si tous les hexagones autour de l'hexagone choisi sont occupés, marquez comme engagés, changez d'hexagone.
4. Répétez jusqu'à ce que chaque groupe soit long de 20 hexagones ou n'ait plus d'espace pour se développer (tous les hexagones engagés).

Je n'ai pas testé, mais cela devrait générer des îles et éviter quelque peu les accolades longues et minces. De plus, il y aura très probablement des frontières avec les voisins mais pas nécessairement chacun sera en contact les uns avec les autres, cette densité dépendra de la valeur de n.
Certains groupes peuvent également être acculés par d'autres et atteindre une taille inférieure à 20, vous pouvez assurer un espace cultivé en créant les hexs de démarrage à une distance minimale les uns des autres.
Testez et ajustez au besoin.


De plus, sans rapport avec ce problème mais très, très utile pour travailler avec des hexagones, visitez cette page: http://www.redblobgames.com/grids/hexagons/#basics
Il regroupe tout un tas d'informations hexadécimales en un seul endroit avec un joli visuel.

Je pense définitivement qu'un certain type de structure de graphique rendrait cela possible. Fondamentalement, créez un bord entre deux nœuds hexadécimaux s'ils sont côte à côte pour simuler l'ensemble de la carte. Cependant, je ne suis pas sûr de l'algorithme exact pour générer un "pays" dans cette carte. Le fait est que, selon la façon dont vous voulez que le pays "regarde", vous aurez besoin de différents algorithmes.

Du haut de ma tête, je recommanderais de choisir un point et de sortir de là, en choisissant une tuile aléatoire dans votre "pays en croissance" qui a une tuile adjacente qui ne fait pas partie du pays.

Un modèle de stratégie pourrait être utilisé pour changer d'algorithmes en fonction du type de pays que vous souhaitez. http://en.wikipedia.org/wiki/Strategy_pattern ie voulez-vous un pays côtier mince comme le Chili? Ou voulez-vous quelque chose de plus rond et de contenu?

Les propriétés du graphique peuvent également vous permettre de modifier à quoi vous voulez que le "pays" final ressemble: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

Vous voulez un grand pays? Ajustez les propriétés du graphique et forcez le pays généré (qui n'est qu'un graphique) à avoir les propriétés qui lui donnent le "look" que vous souhaitez.

Enfin et surtout, les graphiques seront également très utiles pour définir les frontières entre les pays. Vous pouvez créer un graphique qui a une connexion entre deux nœuds si les pays se bordent. Cela peut être utile pour certains types de partitionnement dans votre jeu et vous permettra éventuellement d'optimiser certaines choses plus tard dans le développement.

Une petite remarque: vous dites "ressemble à une carte de la vie réelle avec des pays de formes différentes mais de tailles égales), mais les pays" réels "sont très différents, même dans certaines régions - même les" grands "pays d'Europe peuvent varier énormément, la France étant par exemple plus de deux fois plus grande que l'Italie. Cela dit, il existe évidemment des régions de gameplay pour essayer de garder les tailles à peu près les mêmes - sachez qu'une petite variation ici est probablement une bonne chose!

Mon approche initiale du problème serait «d'évoluer» (plutôt que de «grandir») vos régions:

• Commencez par une division concrète de la carte en morceaux de taille à peu près égale par des lignes droites (par exemple, si vous vouliez 6 pays, alors vous pourriez diviser la carte en trois tranches horizontales, puis diviser chacune de ces tranches `` sur la diagonale '' en deux morceaux). C'est évidemment facile à faire par programme, d'autant plus que cela n'a pas besoin d'être très exact (en fait, ne devrait probablement pas être très exact).
• Faites un premier passage sur la division, construisant une structure de données `` limite '': un ensemble d'hexs qui ont un voisin appartenant actuellement à un pays différent. Ce serait également un bon moment pour compter le nombre d'hexagones dans chaque pays.

Maintenant, aussi longtemps que vous le souhaitez, exécutez le pseudocode suivant:

Pick a random hex A from the boundary list;
Pick a random neighbor B of this hex from a different country;
if (A's country has more hexes than B's country has) {
  change hex A to belong to B's country;
} else if (B's country has more hexes than A's country has) {
  change hex B to belong to A's country;
} else {
  flip a coin to decide which to change;
}
if ( the changed hex's old country has become disconnected ) {
  undo and reject this move;
} else {
  update the boundary list around the changed hex and its neighbors;
}

Cela maintiendra un équilibre approximatif entre la taille de deux pays voisins et la vérification `` déconnectée '' (qui peut être effectuée avec un algorithme de remplissage par inondation simple) garantit qu'aucun pays ne se sépare jamais en morceaux. La mise à jour de la liste des limites est une opération à temps constant - l'hex modifié sera évidemment toujours toujours sur la limite, et vous pouvez simplement vérifier ses six voisins pour voir si l'un d'eux est devenu une cellule de limite (car son voisin est maintenant dans un pays différent) ou a cessé d'être une cellule de frontière (parce que son voisin est dans le même pays maintenant), modifiant l'ensemble de frontières selon les besoins.

Pour affiner cette approche, vous pouvez même rendre la condition de l'hexagone pour changer un peu aléatoire - plutôt que de toujours `` équilibrer '' les deux pays, vous pouvez toujours faire le swap avec une certaine probabilité, et même diminuer progressivement cette probabilité sur temps (similaire au processus de refroidissement dans un algorithme de recuit simulé ) pour commencer à les forcer à avoir à peu près la même taille.

Notez que cela ne garantira pas que toutes les zones sont exactement de la même taille (ce qui est impossible à moins que N ne divise parfaitement la taille de votre grille de toute façon), et cela ne garantira même pas que tous les pays sont à moins d'un hex les uns des autres dans la zone; il doit garantir (exécuter pendant suffisamment d'itérations) que chaque pays n'est pas plus d'un hex plus grand ou plus petit que chacun de ses voisins immédiats.