Question mathématique: génération procédurale d’une galaxie

Je vais créer un espace / trading / jeu de combat complètement généré de manière procédurale. Mais je sais que stocker tous les détails de toute la galaxie en mémoire est irréalisable. En conséquence, je pense que je peux utiliser une graine pour générer un système solaire, et à partir de ce système solaire, vous pouvez utiliser des sauts pour atteindre d’autres systèmes solaires. Le problème est que si je saute sur un autre système solaire à partir du système de démarrage, je dois pouvoir revenir au même système solaire de départ avec exactement les mêmes caractéristiques (planètes, astéroïdes, etc.).

Essentiellement, je dois pouvoir générer une galaxie entière à partir d’un seul numéro. Et à partir de ce chiffre, qui génère un système solaire, je dois être capable de générer tous les autres systèmes solaires qui relient le premier et tous les systèmes solaires qui sont reliés entre eux, etc. Et chaque système solaire doit restr exactement le même, si je reviens à eux. De plus, le nombre de liens de chaque système solaire peut être aléatoire ou fixe, au choix. Aléatoire serait mieux si.

Si vous vous sentez courageux, vous pourriez faire pire que de voir comment Ian Bell l’a fait pour la version originale d’Elite

Découvrez cette série sur Gamasutra:

Un univers procédural en temps réel, les quatre premiers liens

Aussi, ceci: Algorithmes pour un univers infini

Voici l’idée de base telle que je la comprends. Disons que vous êtes arrivé dans le système écanvas n ° 42 et que vous devez savoir ce qu’il contient. Il a des planètes de nplanets – un nombre entre 0 et 10, disons:

 >>> star_system = 42 >>> nplanets = hash('nplanets%d' % star_system) % (10 + 1) >>> nplanets 4 

OK, donc sur la planète # 2, combien de stations spatiales sont en orbite au début du jeu? Trouvez un nombre entre 0 et 3:

 >>> planet = 2 >>> nstations = hash('nstations%d/%d' % (star_system, planet)) % (3 + 1) >>> nstations 1 

Etc. Les nombres sont chacun une fonction de hachage des indices (écanvas système n ° 42, planète n ° 2, dans ce cas), réduite à la plage appropriée. Puisque les fonctions de hachage sont déterministes mais «aléatoires», c’est la même chose à chaque fois, mais une apparence aléatoire pour le joueur.

Bien sûr, le hachage de chaînes avec de longues séquences comme «nstations» en elles n’est pas le moyen le plus rapide d’y parvenir, mais cela montre l’idée.

Jetez un coup d’oeil au jeu original de Worms . Je pense qu’il a prétendu avoir environ 4 milliards de niveaux possibles. Chaque niveau a été généré sur la base d’une chaîne de caractères courte d’environ 20 caractères. Ceci déterminé

  • le thème du niveau (arctique, forêt, etc …)
  • la forme du paysage
  • le glissant du sol
  • le placement de détails de niveau pré-construits (bonhommes de neige, roches …)
  • le placement de votre équipe de vers, de mines et de caisses d’armes.

Si vous avez apprécié un niveau, vous pouvez écrire la chaîne de départ et l’utiliser pour régénérer le même niveau ultérieurement.

Ceci est un exemple d’une fonction très complexe, mais déterministe, avec un seul paramètre d’entrée. Je pense que c’est le concept essentiel de ce dont vous avez besoin.

Tu ne peux pas juste SHA1 l’ID de galaxie, EG:

Galaxy 1

 Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab 

Galaxie 2

 Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0 

Galaxie 3

 Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb 

Vous pouvez ensuite segmenter le code, IE:

4 premiers caractères = nombre de planètes

 356a da4b 77de 

Vous auriez besoin d’une sorte d’algorithme de chaîne en nombre, un simple serait de prendre le code ASCII de chaque caractère non numérique, puis de les multiplier tous ensemble ou quelque chose.

Alors maintenant, nous soaps combien de planètes sont dans notre galaxie, que diriez-vous des dimensions de la galaxie x, y, z?

9 caractères suivants = Dimensions Galaxy (x, y, z)

Même principe que ci-dessus, transformez le code en un grand nombre. Ayez aussi des contrôles de sensibilité, vous ne voulez pas d’une galaxie qui soit 10 milles x 10 milles x 10 milles avec 20 millions de planètes. Avoir une sorte d’algorithme pondéré, comme la taille minimale est # de planètes * 10000. Vous devrez jouer avec les nombres pour vous assurer que les plages sont toutes compatibles et que les caractères sélectionnés du hachage vous donnent une plage raisonnable.

Ou, au lieu de cela, vous pouvez avoir un nombre aléatoire de choisir un nombre entre la taille minimale et maximale de la galaxie, mais utilisez une graine RNG constante, telle que l’identifiant de la galaxie! De cette façon, les tailles des galaxies sont essentiellement «aléatoires» pour l’observateur, mais elles seront identiques à chaque fois.

Etc!

C’est une façon d’obtenir les propriétés de votre univers, mais qu’en est-il des propriétés de la planète? Comme la population et d’autres choses?

Si vous avez Galaxy 1 avec 20 000 planètes, vous pouvez faire:

 Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5 

C’est-à-dire la galaxie, la planète 340. Vous pouvez alors simplement append ce code comme vous le souhaitez. L’avantage d’utiliser un hash est que chaque planète doit avoir un code totalement unique.

Je pense qu’il est intéressant de noter que

  1. un générateur qui produit la même sortie aléatoire pour la même entrée est appelé un générateur de nombres pseudo-aléatoires, “PRNG”. Typiquement, vous lui donnez un numéro d’entrée “graine” au tout début, puis tirez simplement des nombres aléatoires, en l’appelant sans autre saisie. Remarque: vous ne pouvez pas revenir à un numéro antérieur, du moins sans commencer au début.

  2. une fonction de type PRNG appelée avec des coordonnées comme entrée de chaque appel est généralement une fonction “bruit”. Ici, vous n’avez pas le problème “impossible de revenir en arrière” – appelez simplement avec l’entrée “antérieure” à nouveau. Une fonction noise utilise un PRNG (en tant que backend, ou du moins, il le pourrait) qui peut encore être créé au tout début, de sorte que vous ne perdiez pas votre fonctionnalité “univers sur un numéro”.

  3. Bien que vous puissiez simplement utiliser un PRNG et combiner les coordonnées de la galaxie à une “graine” à chaque fois, vous obtiendrez au mieux un “bruit blanc”, sans autres atsortingbuts. Une fonction de bruit est beaucoup mieux adaptée au travail, car elle peut être choisie ou même ajustée pour vous donner une apparence / une forme en spirale / lisse / en spirale. résultats. Par exemple, recherchez des images de texture créées à l’aide du bruit perlin. Je m’attends à ce que vous voyiez qu’avec la même fonction de bruit, vous pouvez créer par exemple des milliers de nuages ​​aléatoires, mais en ajustant la fonction de bruit à vos besoins (pas seulement la graine ou les coordonnées). L’ajustement peut ne pas être sortingvial si.

  4. Le nombre de coordonnées d’entrée pour chaque appel détermine le nombre de dimensions de la fonction de bruit. Pour une carte à deux dimensions (ou une texture, etc.), vous pouvez utiliser une fonction de bruit à deux dimensions. Vous l’appelez alors noise2d (x, y) à chaque fois.

Dans votre situation, j’essaierais une fonction de bruit simplex en trois dimensions (simplex provient de l’auteur du bruit perlin, recommandé comme étant meilleur).

Chaque sortingplet de coordonnées du système d’écanvass vous donne alors un numéro de résultat. La prochaine décision serait: que représente le nombre? Pour bien utiliser le lissage du bruit simplex, je mapperais des nombres plus faibles pour vider les systèmes solaires et des nombres plus élevés pour les systèmes avec plus de masse. Ou, peut-être mieux, pour chaque appel système simplex bruit plusieurs fois avec des sous-coordonnées. Les nombres de résultat de taille moyenne sont alors des planètes, les petits nombres sont le vide ou les astéroïdes. De grands nombres d’écanvass, etc.

Le sujet n’est pas actif et il est ancien, mais les recherches peuvent se terminer ici, comme le mien.

Je ne pense pas qu’il y ait vraiment beaucoup d’informations dans une “galaxie” que vous ne puissiez pas stocker sur les ordinateurs d’aujourd’hui. Supposons qu’une galaxie ait 100 écanvass et que chaque écanvas ait 10 planètes et que chaque planète ait 3 lunes. C’est 100 écanvass + 1 000 planètes + 3 000 lunes que vous devez suivre, soit 4 100 corps.

Voici les choses que nous pourrions vouloir suivre pour une planète.

Masse X, Y, Z Position Durée du jour (temps de rotation sur son propre axe) Durée de l’année Population Nombre de ressources pour 50 ressources différentes

En supposant que chaque valeur nécessite un double pour la stocker, et que nous avons 57 valeurs à stocker (arrondissons-les et disons 100), alors nous avons 100 valeurs * 8 octets * 4100 corps = 3 280 000 octets. Maintenant, c’est 3 Mo de données. Cela peut sembler beaucoup, mais ce n’est vraiment pas beaucoup. De plus, je ne pense pas que vous voudriez vraiment avoir autant d’écanvass dans une seule galaxie. Le jeu serait vraiment trop gros pour être exploré et deviendrait probablement ingérable pour essayer de simuler toutes les choses qui se passent dans une galaxie donnée.

Vois-le de cette façon. Si vous prenez un jeu comme SimCity et que vous considérez chaque carré de la grid de ville comme une planète potentielle, vous réalisez à quel point les informations peuvent être stockées dans un petit fichier, ce qui vous évite de générer quoi que ce soit.

Une graine aléatoire pour chaque système solaire est une solution viable mais j’ai le sentiment que vous aboyez le mauvais arbre ici.

Le joueur peut-il faire quelque chose pour changer ce qu’il y a? (Dites, construisez quelque chose, extrayez une ressource épuisable, etc.?) Si oui, vous devrez quand même sauver l’état.

Le joueur peut-il regarder à quoi ressemblait l’endroit sans avoir à y retourner? (Et s’il ne le peut pas, pourquoi pas?!) Allez-vous chercher ou allez-vous régénérer tout le système solaire pour trouver une information à ce sujet? (la solution PRNG ne vous permet pas d’obtenir une partie seulement du système solaire, vous devez tout fabriquer.)

De combien de détails avez-vous besoin d’économiser?

Supposons que vous commencez avec une graine pour la galaxie, soit 1234, prenez cette graine et générez 10000 nombres aléatoires, chacun représentant un système en écanvas. Lorsque vous vous approchez de l’écanvas, vous prenez le nombre aléatoire de l’écanvas et vous le considérez comme une graine pour une nouvelle fonction aléatoire. Générer un nombre aléatoire pour la quantité de corps célestes en orbite autour de l’écanvas, et générer un nombre pour chaque corps (en utilisant toujours la deuxième fonction aléatoire) et ainsi de suite. Je ne sais pas si cela vous aide, mais vous devez vous rappeler que les fonctions aléatoires sont chaotiques en interne, pour une condition initiale, toute la fonction change.

La graine des écanvass de la galaxie doit toujours produire les mêmes écanvass, la graine des écanvass doit produire les mêmes corps, etc.

Vous pouvez toujours rendre les choses plus intéressantes en utilisant des statistiques, des calculs de densité et en améliorant les résultats. Vérifiez toujours que les fonctions produiront le même résultat pour la même entrée.

Désolé si mon anglais est nul, je viens d’Argentine et la langue anglaise n’est pas une de mes qualités: p

PD: je fais le même type de jeu;)

J’utilise le Mersenne Twister. C’est PRNG qui accepte comme tableau de graine de n’importe quelle longueur.
Par exemple, je veux générer une galaxie sur les coordonnées x = 25, y = 72. Je ré-initie twister avec des graines [25,72].
Si je veux générer 1138ème planète dans cette galaxie, j’utilise [25,72,1138].
Pays? [25,72,1138,10]
Ville? [25,72,1138,10,32]
etc.
Avec cette méthode, vous pouvez générer des milliards de milliards de milliards d’objects en un seul chiffre (celui précédant la coordonnée x, dans notre cas avant 25).
Certains projets l’utilisent maintenant.
Noctis: anynowhere.com/
Infiniverse: http://www.infiniverse-game.com/

Vous pouvez créer un nombre pseudo-aléatoire de N chiffres à partir d’une certaine graine (le “numéro mère”). Ensuite, vous divisez les chiffres en groupes et les utilisez pour répondre à vos questions.

Exemple: N = 20

-> un chiffre: combien de sauts supplémentaires?
-> trois chiffres: graine pour générer les longueurs respectives de chaque saut disponible
-> six chiffres: graine pour générer ce système solaire
-> dix chiffres: graine pour générer une nouvelle graine à 20 chiffres pour chaque système solaire lié

Ensuite, rends-toi. Chaque système (avec des orbites stables, etc.) est généré à l’instant 0, et vous devrez calculer son apparence actuelle .

Bien entendu, cette approche, à partir d’un système mère, signifierait que plus le système actuel est éloigné du système mère, plus il faut de temps pour générer ses données. En outre, cette façon fait un arbre, pas un filet (ce à quoi je m’attendrais).

Je pense qu’il serait préférable de générer des coordonnées – utiliser des coordonnées polaires dans le plan et peut-être un ellipsoïde en trois dimensions.

Je peux vaguement me rappeler que cela a déjà été fait. Au début des années 90, les fractales faisaient fureur et je me souviens d’une entreprise qui offrait des mondes aux programmeurs de jeux. Les avaient créé un univers infini plein de galaxies avec des soleils et des planètes, des événements dans les vallées et des textures de lieux sur les planètes. Ils proposaient de trouver des biens immobiliers virtuels adaptés aux développeurs de jeux. Les développeurs du jeu obtiendraient le logiciel pour le rendre et l’utiliser, ainsi que les coordonnées exactes de leur propriété dans cet univers fractal.

J’ai googlé pendant quelques minutes pour “l’univers de planète de jeu de fractale” et tel, mais ne les ai pas trouvé. C’était peut-être Pandromeda , mais je ne m’en souviens pas.

Vous devriez étudier les fractales pour cette idée. Tout ce dont vous avez besoin est un champ continu de nombres que vous pouvez recréer à partir d’une graine, puis présentez ces nombres sous forme d’écanvass, de planètes et de satellites aux propriétés différentes.

Si vous voulez vraiment revenir à un état fixe, je ne pense pas que la génération procédurale à partir d’une valeur unique soit la bonne solution.

Supposons que vous ayez une grid fixe de 256×256 systèmes dans chaque plan et 16 plans dans l’univers. Chaque avion a jusqu’à 512 stations de trading et jusqu’à 8 liaisons vers d’autres avions. Toutes les stations de trading et les liens sont sur une position fixe. Votre valeur initiale doit être d’au moins 2 ^ 76 pour encoder tous les univers possibles. Ajoutez d’autres objects (planètes, vaisseaux, …) et le nombre augmente de manière exponentielle.

Edit: C’est un peu moins si vous n’autorisez pas plus d’une station de trading ou d’un lien dans chaque système. J’utiliserais un stockage permanent, peut-être une firebase database intégrée comme Firebird ou sqlite. Incidemment, je développe actuellement un tel jeu.

Voici ce que j’ai imaginé. Dunno si ce sera la version finale cependant.

Imaginez une grid hexagonale et à chaque sumt un système solaire. Puisque nous sums sur une grid hexagonale, il n’y a que trois lignes allant de n’importe quel sumt. L’un est toujours horizontal et les deux autres sont des diagonales. Si on donne à la graine de départ une valeur de n, on peut donner au système solaire connecté horizontalement au sharepoint départ la valeur n + 1, les autres obtenir la valeur de n + 2 et n-2.

Oh merde. Nous ne recevrons pas nécessairement une grid. Bon sang. Essayons encore.

Si vous utilisez un générateur de nombres pseudo-aléatoires, vous pouvez garantir que chaque nombre aléatoire généré apparaîtra dans le même ordre à partir d’une graine donnée. Le code permettant de générer un système doté d’un nombre donné apparaîtra à chaque fois que vous le générerez.

Utilisez le premier numéro du stream de nombres pseudo-aléatoires pour générer le nombre de “portes”. Parcourez chaque porte et obtenez une valeur du stream de numéros pour affecter et amorcer chaque système cible.

Générez les performances de chaque système en fonction de cette graine.

Il existe plusieurs algorithmes connus pour générer des graines aléatoires.

Donne un twister à la Mersenne

Tant que vous appelez srandom () avec la même graine, vous obtenez les mêmes valeurs en aléatoire (). Donc, il suffit de tout baser dans un système en écanvas sur un seul appel à srandom () … Ensuite, vous n’aurez qu’à stocker 1 entier (le germe) pour un système en écanvas entier. Maintenant c’est la compression!

Ceci est ma deuxième solution améliorée. Le joueur démarrera dans un système solaire généré aléatoirement. Chaque système est connecté entre 1 et 4 autres systèmes. Considérez-les comme des systèmes nord, sud, est et ouest. Si un joueur devait traverser la porte nord, il sera conduit à un système dont la graine est supérieure à celle du système précédent. S’il va au sud, la graine pour ce système sera une de moins. 2+ et 2- pour l’est et l’ouest respectivement. Les distances par rapport à ces systèmes (en parsecs ou années-lumière ou autres) sont calculées avec la graine du système et la direction dans laquelle vous arrivez. De cette façon, la taille de la galaxie n’est limitée que par le nombre maximum et minimum du nombre utilisé pour contenir les graines.

Les trous de distorsion destinés à d’autres galaxies seront placés à une certaine distance du système de départ. La galaxie suivante sera simplement comme une continuation de cette galaxie en ce sens que le nombre de graines sera incrémenté de la même manière et que le système qui se trouve à l’autre extrémité du trou de chaîne galactique sera juste un “est” ou un “nord” “connexion du système de démarrage.

En passant, cette utilisation de semences incrémentées conduit à un Web, contrairement à la solution ci-dessus. En outre, vous pouvez voir que cette méthode utilise des quadrilatères alors que la solution ci-dessus utilise des hexagones, ce qui rend impossible la création d’un site Web.

Bien sûr, tout cela repose sur l’hypothèse que toutes les graines génèreront une séquence aléatoire de nombres différente de toute autre séquence. Cela fait en sorte que chaque système est unique.

Je soupçonne que le plus gros problème que vous allez rencontrer est d’avoir un système de nommage pour nommer tous ces objects d’une manière cohérente et significative pour le joueur – bien que nous ayons des schémas pour nommer systématiquement les objects réels. J’oublie si la convention de nommage d’Elite s’est effondrée après un certain point …

Mathématiquement, vous voulez générer aléatoirement / pseudo-aléatoirement un graphe connecté non dirigé. Dans ce graphique, chaque nœud serait un système solaire et chaque bord serait une porte de saut.

1) Créez N nœuds et assignez chacun au hasard une coordonnée spatiale. Ces nœuds finiront par devenir vos systèmes solaires.

2) Générer des arêtes en utilisant l’algorithme de sortingangulation de Deluanay. Je suggère la sortingangulation de Deluanay car elle créera une carte assez jolie sans aucune intersection, mais vous pouvez réellement utiliser n’importe quel algorithme. Je ne sais pas vraiment ce que tu cherches.

3) Si vous avez utilisé la sortingangulation de Deluanay, je vous suggère d’éliminer un certain nombre d’arêtes pour créer une «dispersion». Cela rendra la carte plus intéressante car certains endroits deviendront des hubs de transport, tandis que d’autres seront simplement des arrêts aux stands.

4) Enregistrez ce graphique. Ceci est votre univers. Ne pas égarer ou jeter votre univers. Stockez-le aussi efficacement que vous le souhaitez, mais ne supprimez aucune information.

5) Atsortingbuez à chaque nœud une graine et utilisez cette graine pour générer chaque système solaire.

6) Félicitations, vous avez maintenant un univers avec un nombre arbitraire de systèmes solaires et de portillons.