Comment diviser également la grille hexadécimale entre n joueurs?

15

Je fais un jeu simple basé sur une grille hexadécimale, et je veux que la carte soit divisée également entre les joueurs. La carte est créée au hasard, et je veux que les joueurs aient à peu près le même nombre de cellules, avec des zones relativement petites. Par exemple, s'il y a quatre joueurs et 80 cellules sur la carte, chacun des joueurs aurait environ 20 cellules (il n'est pas nécessaire qu'elles soient précises). De plus, chaque joueur ne doit pas avoir plus de quatre cellules adjacentes. C'est-à-dire que lorsque la carte est générée, les plus gros "morceaux" ne peuvent pas avoir plus de quatre cellules chacun.

Je sais que ce n'est pas toujours possible pour deux ou trois joueurs (car cela ressemble au problème de "colorier la carte"), et je suis d'accord pour faire d'autres solutions pour ceux-ci (comme créer des cartes qui résolvent le problème à la place). Mais, pour quatre à huit joueurs, comment pourrais-je aborder ce problème?

manabreak
la source
Les automates cellulaires sont un moyen simple, similaire à celui-ci: une carte simple, quatre biomes et comment les distribuer
MichaelHouse

Réponses:

3

Voici ce que je ferais:

  1. Attribuez toutes les cellules à des joueurs aléatoires. Sur les grandes cartes, cela devrait très probablement produire un nombre de tuiles assez égal pour tous les joueurs, sur les petites cartes, vous devrez probablement faire quelques corrections.
  2. Brisez les morceaux trop gros. La chose la plus simple à faire serait de prendre toutes les tuiles en morceaux et d'attribuer à nouveau chaque tuile au hasard.
  3. En cas de nombre de cellules déséquilibré (par exemple, le joueur A a 24 cellules, le joueur B en a 16), réaffectez quelques cellules des joueurs surreprésentés aux joueurs sous-représentés.
  4. Vérifiez à nouveau pour les morceaux. Si l'étape 3 a introduit de nouveaux morceaux, revenez à l'étape 2. Sinon, belle carte!
Junuxx
la source
PS Je ne pense pas que ce problème soit jamais impossible, le problème de coloration de la carte est assez différent (d'une part, c'est l'inverse, formes-> couleurs au lieu de couleurs-> affectations de tuiles).
Junuxx
J'aime beaucoup cette approche, mais n'y a-t-il pas une possibilité qu'elle s'exécute pendant une longue période, essayant d'équilibrer les tailles de zone?
manabreak
1
@manabreak: J'ai fait quelque chose pour l'essayer. Avec un petit changement à l'étape 2 (réaffecter en faisant défiler tous les joueurs au lieu de réaffecter au hasard), cela fonctionne assez bien. J'essaierai de l'écrire quand j'aurai le temps.
Junuxx
1
Cela ressemble exactement à ce que je cherchais. :)
manabreak
1

En supposant que vous ayez un hexmap de ncellules au total et des pjoueurs, où p <= nla meilleure façon de résoudre ce problème est la distribution à tour de rôle via des automates cellulaires (CA).

Initialisation

Au hasard (et / ou en utilisant une ou une autre heuristique, comme la distance du centre de la carte), choisissez une cellule de départ pour chaque joueur. Depuis p <= n, cela ne devrait pas être un problème.

Automates cellulaires

Vous avez besoin d'une connectivité complète entre vos cellules hexadécimales. Je suggérerais un tableau à 6 voisins par cellule:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

L'utilisation de tableaux de taille fixe permet au concept de directions topographiques entre les cellules d'exister, ce qui n'existerait pas pour une liste ou un vecteur. Je le recommande, car cela peut faciliter certaines opérations de navigation.

Vous pouvez également stocker votre hexmap dans un tableau 2D, avec des décalages par ligne. Cela peut cependant être légèrement moins intuitif que le stockage d'un tableau voisin par cellule, uniquement en raison du décalage géométrique sur toutes les autres lignes.

Assurez-vous que chaque cellule est connectée à tout ce qui est voisin. Vous pouvez le faire ligne par ligne, cellule par cellule lorsque vous générez l'hexmap complète. PS Si vous voulez en fin de compte une carte hexadécimale non délimitée de manière rectangulaire, vous pouvez alors simplement supprimer les cellules individuelles et les références à ces cellules, pour former des espaces négatifs, vous permettant de créer un contour de carte organique.

Distribution à tour de rôle

Pseudocode:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

Cet algorithme donnera à chaque joueur une chance d'agrandir son territoire d'un point, à la manière d'un tournoi à la ronde, à condition que le territoire du joueur ait encore un espace de croissance valide. Si certains joueurs sont empêchés de croître davantage, l'algorithme continuera malgré tout à étendre les territoires des joueurs qui le font n'ont toujours valide l' espace de plus en plus. Vous pouvez facilement limiter chaque joueur au même nombre de cellules dès que l'un d'eux atteint une limite, mais cela devrait être assez facile pour vous de comprendre, si vous le souhaitez.

Cela fournira des "territoires d'origine" de taille maximale pour chaque joueur. Si vous voulez avoir des territoires "insulaires" en plus, afin de remplir le quota de nombre de cellules pour ce joueur, puis une fois qu'un joueur manque d'espace local pour grandir, vous pouvez alors choisir une nouvelle cellule de départ dans la liste des cellules neutres et procéder avec le même processus de "croissance", à partir de là. De cette façon, vous vous retrouverez avec des ensembles d'îlots cohérents et de bonne taille pour chaque joueur, plutôt que du bruit aléatoire.

Ingénieur
la source
Bien que vous fournissiez une excellente documentation et un pseudocode pour votre algorithme, je ne suis pas sûr que cela corresponde à ce que l'interrogateur demande. La question mentionne que «les plus gros« morceaux »ne peuvent pas dépasser quatre cellules chacun», alors que votre algorithme crée un groupe connecté aussi grand que possible.
fnord
@fnord Non, ce n'est pas le cas. Vous n'avez pas bien lu ma réponse. J'ai explicitement mis une limite dans le pseudocode: "si le joueur n'a pas encore atteint la taille de territoire attendue dans les cellules". Veuillez supprimer votre downvote. N'hésitez pas à consulter l'historique des révisions sur la question pour vous assurer que ce fut le cas depuis avant votre commentaire et downvote.
Ingénieur
La question demande d'avoir "pas plus de quatre cellules adjacentes", mais pour chaque utilisateur d'avoir une portion attendue de la carte. Cela, pour moi, implique que e va vers quelque chose de plus proche de la façon dont les jeux Risk répartissent la carte au hasard pour tous les joueurs. Votre réponse divise la carte en "territoires d'origine de taille maximale". Certes, votre algorithme s'arrête lorsque la limite de taille de territoire attendue est atteinte, mais je ne vois pas de moyen pour ce joueur d'obtenir de nouvelles "îles", bien que vous le mentionniez dans un texte ultérieur.
fnord
@fnord Votre logique est en faute. Dans votre dernière phrase, vous admettez que mon algorithme s'arrête à la taille de l'île n, et par la suite vous contredisez en disant que vous "ne voyez pas de voie" et que je "mentionne [comment obtenir des îles] dans un texte ultérieur". Ai-je ou n'ai-je pas répondu à la question? Cet algorithme généralisé peut être utilisé pour diffuser des cellules (en limitant nà 1) ou pour créer des îlots (en fixant n> 1). Vous avez donc, dans un seul algorithme, non seulement la capacité de se disperser, mais aussi de se regrouper. Comment cela ne répond-il pas à la question du PO? Comment vaut-il un downvote?
Ingénieur
Je voudrais modifier mon commentaire ci-dessus, mais il est trop tard. "Je ne vois aucun moyen dans votre algorithme ". bien que vous mentionniez le concept dans un texte ultérieur.
fnord
0

Une autre approche consisterait à commencer par une distribution qui est «juste» mais régulière, puis à utiliser une approche similaire au recuit simulé pour briser la régularité sans perdre l'équité:

  • Commencez par attribuer des couleurs à toutes les cellules de votre grille selon un motif régulier (par exemple, ayez un motif répétitif «123412341234» sur la première ligne, suivi de «341234123412» sur la suivante, etc.). Cela peut conduire à une distribution non uniforme des couleurs si votre carte est particulièrement mal formée, mais je suppose que vous commencez avec une carte fixe, vous devriez donc pouvoir en trouver une coloration régulière équidistribuée.
  • Ensuite, répétez ce qui suit pour autant d'étapes que vous le souhaitez (il n'y a pas de véritable critère de cuisson, donc l'expérimentation vous dira ce qu'est un nombre minimum d'étapes raisonnable):
    • Choisissez deux éléments de la grille au hasard
    • S'ils ont la même couleur, essayez à nouveau (cela ne sert à rien autrement, car alors l'échange sera un no-op. Vous avez seulement 1/4 chance de frapper la même couleur et 1/16 chance de frapper la même couleur deux fois de suite, vous ne devriez donc jamais avoir à réessayer trop)
    • Échangez provisoirement les couleurs de ces deux éléments
    • Testez les tailles des régions nouvellement formées aux emplacements des éléments après l'échange:
      • faire un simple remplissage vers l'extérieur à partir du nouveau point de chaque élément pour déterminer la taille d'une région de cette couleur que le swap ferait.
    • Si l'une de ces deux régions est supérieure à votre seuil, annulez le swap provisoire; sinon, «finalisez» l'échange des couleurs des deux éléments.

Les clés ici sont que le fait que vous échangez deux points signifie que vous ne déséquilibrez jamais les couleurs, et de même le test que vous faites avant de finaliser votre échange garantit que vous ne créez jamais de régions trop grandes. Si vous avez un moyen d'afficher votre grille, vous pouvez même visualiser ce processus pour voir comment il «construit» ses régions à travers les échanges répétés.

Si vous ne pouvez pas commencer par une coloration régulière équidistribuée, vous devriez être en mesure de faire quelque chose de similaire pour équidistribuer la coloration: bien que votre coloration ne soit pas équidistribuée, choisissez un élément au hasard; puis, s'il s'agit d'une des couleurs surreprésentées, définissez provisoirement sa couleur sur l'une des couleurs sous-représentées, puis assurez-vous que cela ne crée pas une région trop grande de la nouvelle couleur.

Steven Stadnicki
la source
Les approches stochastiques sont inefficaces. Pour une approche comme la mienne qui prend des étapes considérées, le runtime approche O (n) pour n cellules de carte. Pour votre algorithme, c'est O (n * m), où m est le nombre de cellules souhaitées par île (en fait, pour chaque île potentielle). Il est toujours préférable de viser des algorithmes qui ont un temps d'exécution facilement estimable. Au lieu de corriger une carte générée au hasard, mieux vaut générer une carte qui n'est pas cassée ou au hasard en premier lieu, en n étapes, maintenant ainsi un processus contrôlé et efficace.
Ingénieur