Génération de cartes aléatoires - stratégies de diffusion / regroupement de nœuds aléatoires

Je fais un simple jeu de stratégie 4X dans l'espace où chaque nœud est un point d'intérêt (une planète, un astéroïde, etc.).

Pour générer une carte au hasard, je suivrais les étapes ci-dessous

1. Décidez du nombre de types de chaque nœud sur la carte (peut-être, disons, 5 planètes semblables à la Terre, 10 planètes stériles, etc.)

2. Placez chaque type de nœud sur la carte.

Pour l'étape 2, j'aimerais avoir une répartition uniforme de chaque type de nœud. Ainsi, par exemple, je commencerais par placer toutes les planètes semblables à la Terre. Si je fais simplement un rand (map.width, map.height) pour déterminer la position, je pourrais finir par regrouper toutes les planètes semblables à la terre, ce qui profitera au joueur qui commence dans cette zone.

Existe-t-il des méthodes, telles que l'utilisation de différentes fonctions de graphe ou fonction de bruit, qui pourraient générer une séquence de coordonnées (x, y) qui sont réparties les unes par rapport aux autres. De même, existe-t-il des moyens de générer des coordonnées proches les unes des autres?

Le problème auquel vous êtes confronté est que la sélection aléatoire ne fait pas de discrimination, ce qui peut signifier que c'est un ajustement moins qu'idéal pour ce que vous devez faire. Mais, il existe au moins un moyen simple de contourner ce problème:

1. Divisez votre espace en secteurs (par exemple, si vous avez une zone de 100 par 100 et que vous devez générer 100 de ces systèmes solaires, puis divisez votre zone en une grille de 10 par 10 secteurs)

2. Parcourez chaque secteur et répétez l'étape 3 (qui, à son tour, répétera l'étape 4 plusieurs fois)

3. Déterminez au hasard le nombre de planètes pour le système solaire actuel (par exemple, pour une gamme de 3 à 7 planètes, acquérez simplement un nombre aléatoire allant de 0 à 4, et ajoutez 3) dans le secteur actuel (si vous avez plus d'un solaire système dans un secteur, c'est là que vous mettriez en place une autre boucle)

4. Attribuez au hasard vos planètes au sein du système solaire actuel identifié par votre boucle (vous pouvez également utiliser des nombres aléatoires pour augmenter les distances minimales entre les planètes); c'est là que vous décidez des types de planètes, qui peuvent également être déterminés au hasard avec une variété de poids ou selon la méthode que vous préférez utiliser

Vous pouvez également souhaiter définir une zone "hors limites" autour du bord de chaque secteur pour empêcher les planètes des secteurs voisins d'entrer en contact direct les unes avec les autres (juste au cas où elles seraient effectivement situées au hasard côte à côte), ou. ..

Une autre solution pourrait être au point de décider de l'emplacement de chaque système solaire et / ou de chaque planète, pour exécuter simplement un contrôle de proximité rapide par rapport aux secteurs voisins et s'ajuster en conséquence (par exemple, s'éloigner du bord d'une distance minimale plus une distance aléatoire ).

La meilleure façon d'assurer une distribution uniforme est de traiter chaque nœud comme une sorte de particule physique. Faites d'abord une distribution aléatoire sur un plan xy continu (virgule flottante). En appliquant des forces de répulsion entre chaque paire distincte de particules individuelles sur le plan, vous constaterez qu'elles se dispersent lentement. Dans un sens, c'est comme une résolution de collision, seulement il n'y a pas de contact réel à proprement parler. Il est alors simple de reconvertir ce plan (de le «pixelliser») en une grille indexée sur des nombres entiers. Pour commencer, vous pouvez simplement le faire à partir d'une grille indexée sur des nombres entiers, mais il peut être un peu plus difficile de rendre les choses «agréables» - cela dépend de la hauteur de la résolution de votre grille ... plus elle est élevée, mieux c'est , dans ce cas.

De toute évidence, vous voudrez peut-être également appliquer une sorte de force à partir des bords du plan carré, ou bien vous trouverez peut-être beaucoup de particules qui "échouent sur les rives". Alternativement, vous pouvez créer un champ beaucoup plus grand que ce dont vous avez besoin, puis prendre un instantané d'une petite zone de cela - cela évite le problème susmentionné.

Lorsque vous voulez vous assurer le contraire, à savoir que le regroupement ne se produit, regardez ensuite dans la distribution « standard » ou « gaussienne ». C'est pourquoi les champs stellaires générés aléatoirement semblent souvent faux; ils utilisent une distribution aléatoire pure plutôt qu'un modèle de distribution plus naturaliste.

Vous pouvez utiliser un algorithme de distribution de disque de Poisson simple pour obtenir une distribution de "bruit bleu". Il en résulte des points dans le plan qui sont à peu près également espacés les uns des autres. Cela fonctionne non seulement dans votre exemple 2D, mais également en 3D, ainsi que dans les espaces non euclidiens, mais les calculs peuvent rapidement devenir difficiles à gérer.

L'idée de base de ces algorithmes est que vous commencez avec un premier point "initial", puis travaillez vous-même vers l'extérieur en ajoutant des points aléatoires ou pseudo-aléatoires dans l'espace annulaire entre les distances max et min que vous aimeriez avoir à partir du point et éliminer ceux qui sont trop proches les uns des autres. Votre algorithme fonctionne ensuite vers l'extérieur de cette manière, jusqu'à ce que la quantité de points nécessaires soit ajoutée (ce qui vous donne un nuage de points à peu près circulaire) ou que l'espace disponible soit rempli.

Un algorithme alternatif rapide et élégant pour la génération d'un tel bruit 2D, ainsi qu'une brève discussion de ses propriétés, peuvent être trouvés dans " Une structure de données spatiales pour la génération rapide d'échantillons de disques de Poisson " par Daniel Dunbar et Greg Humphreys de l'Université de Virginie.