Comment générer de manière incrémentielle un graphique?

8

Je viens de commencer un nouveau projet dans lequel j'aimerais que le monde du jeu se compose d'emplacements générés de manière procédurale et connectés par des téléporteurs. Après un peu de recherche, j'ai découvert que cela s'appelait soit «théorie des graphes» soit «compliqué sanglant», selon qui en discutait. Malheureusement, j'ai trouvé très peu d'informations sur la génération de graphiques; la plupart des outils que j'ai vus visent à examiner les graphiques existants.

En supposant que la terminologie soit correctement triée, mes exigences sont que le graphique soit:

  • simple - aucun emplacement (sommet) ne doit avoir un téléporteur (bord) qui se reconnecte à lui-même, ni deux sommets doivent avoir plusieurs bords les reliant
  • connecté - il devrait être possible de voyager entre deux sommets dans le graphique (même si je ne prévois jamais avoir besoin de trouver le chemin; il suffit de savoir que le joueur pourrait en trouver un s'il le souhaite)
  • cyclique - il devrait y avoir plus d'un chemin entre deux sommets
  • non orienté - tous les bords peuvent être parcourus dans les deux sens
  • infini - si le joueur le souhaite, il devrait pouvoir se déplacer indéfiniment, le graphique continuant à générer de manière incrémentielle à mesure qu'il approche de ses sommets les plus extérieurs et inexplorés
  • localement fini - le degré d'un sommet ne devrait jamais changer après que le joueur l'ait visité
  • étiqueté de manière stable - chaque sommet représente un emplacement qui sera lui-même généré de manière procédurale à partir d'une graine; la même graine doit être affectée à un sommet, quel que soit le chemin utilisé par le joueur pour s'y rendre ou la taille du graphique lorsqu'il le fait

J'ai eu quelques idées (que je n'ai pas encore essayé de mettre en œuvre) concernant l'utilisation des maxima locaux du bruit perlin 2D comme sommets (les entrées x et y pourraient alors être utilisées comme étiquette), mais cela semble maladroit et trop compliqué.

Existe-t-il une meilleure façon de générer un graphique comme celui-ci? Je développe en Python 2.6 en utilisant Panda3D et numpy, et je serais bien sûr disposé à envisager d'inclure d'autres bibliothèques si elles peuvent aider à résoudre ce problème!

Éditer

Je pense que j'ai fait un mauvais travail en expliquant certaines de mes exigences, il est donc temps de l'illustration! Espérons que cela clarifiera les choses.

Ce que je veux dire par avoir des étiquettes stables, c'est que je veux, par exemple, que le joueur A puisse faire un tas d'explorations et trouver, entre autres, un chemin cyclique pour retourner à leur emplacement de départ et une montagne qui ressemble à un chat. Son jeu ressemble maintenant à ce qui suit (les sommets sont numérotés avec leur graine et les bords avec l'ordre dans lequel le joueur les a traversés). Il a commencé sur le sommet 8329 (vert) et Happycat Mountain est sur le sommet 6745 (bleu).

Graphique du monde du joueur A

Le bon ami du joueur A Le joueur B est un fan de chats, alors il veut lui montrer. Il lui donne les racines de son monde et des directions le long du chemin le plus court vers la montagne d'intérêt. Son jeu devrait maintenant ressembler à ceci:

Graphique du monde du joueur B

Le problème avec lequel je rencontre actuellement le plus de difficultés est "Comment générer les mêmes graines pour le joueur B lorsque son exploration n'a pas suivi le même chemin?" C'est ce qui m'a amené à l'idée d'utiliser le bruit de Perlin - tant que la même racine racine est utilisée, les maxima ne bougent pas, donc leurs coordonnées pourraient être utilisées comme graines de vertex stables.

Ben Blank
la source
Pourquoi un graphique connecté ne conviendrait-il pas à cela? mathworld.wolfram.com/ConnectedGraph.html Je manque peut-être le point. Si un utilisateur veut aller d'un endroit à l'autre et qu'il est tous connecté, donnez-lui une liste d'emplacements et déplacez sa position sur la carte du monde vers le nouvel emplacement.
brandon
@brandon - "Connected" est la deuxième propriété que je liste. :-)
Ben Blank
mon point est, si vous pouvez passer d'un nœud à un autre. Quand ils visitent un téléporteur, donnez-leur une liste de tous les nœuds qu'ils ont visités, sauf celui-ci. Il n'est pas nécessaire d'avoir un graphique, vous conservez une liste de tous les nœuds visités et leurs emplacements et vous vous téléportez simplement à l'emplacement qu'ils choisissent. Suis-je incompréhensible?
brandon
presque toutes vos descriptions de ces termes sont correctes, à l'exception de "cyclique" et "localement fini". Le premier restreint vos graphiques à ce à quoi ils ressemblent - un cercle. Un terme que vous pourriez utiliser pour l'exigence qu'il y ait plus d'un chemin d'un sommet à un autre est "2-connecté". "Localement fini" signifie simplement que chaque sommet a un nombre fini d'arêtes.
Harry Stern
@Harry Stern - Je crois comprendre que les graphiques cycliques sont des graphiques contenant au moins un cycle de graphique . Il semble que vous parliez d'un graphique de cycle , qui est un graphique composé d'un seul cycle de graphique et rien d'autre. Je ne cherche pas spécifiquement des graphiques qui sont "2-connectés" (voir "simple"). Et oui, c'est ce que je voulais dire par "localement fini".
Ben Blank

Réponses:

6

Vous ne pouvez pas faire un graphique infini. Votre mémoire est finie, donc les nombres de sommets et d'arêtes sont également finis. Ce que vous pouvez faire est de créer un graphique fini, puis d'en ajouter d'autres. Vous semblez avoir réalisé cela, mais je pense qu'il est important que cela soit explicitement déclaré afin de ne pas emprunter une voie sans issue.

Vous devez être très prudent lorsque vous parlez de "sommets ultrapériphériques". Un graphique est un ensemble de sommets, un ensemble d'arêtes et une fonction qui relie les deux. Il n'y a pas d'interprétation géométrique définie sauf si vous en appliquez une. Par exemple: ces deux images montrent exactement le même graphique. Dans la première image, le sommet 2 pourrait être considéré comme un sommet "le plus à l'extérieur", mais dans la deuxième image, le sommet 2 ne serait pas considéré comme "le plus à l'extérieur". Si vous considérez trois dimensions, vous pourriez dire que tous les sommets sont "les plus externes".

Graphique 1 Graphique 2

Cela signifie que vous devez avoir d'autres informations pour pouvoir savoir ce qu'est un sommet "le plus externe". Vous pouvez utiliser des paires (x, y) car cela vous donnerait une représentation géométrique facile à visualiser, mais je ne pense pas que vous ayez besoin d'aller aussi loin. D'après ce que vous dites, tout ce que vous devez savoir, c'est déjà quels sont les sommets du graphique.

Si vous l'exécutiez à chaque fois que vous visitiez un sommet:

if(this.needsNeighbours)
{
    List<int> connections = genRandomNumbers(n);
    foreach (int connection in connections)
    {
        //Simple graph
        if(connection == this.seed || this.hasNeighbour(connection))
        {
            continue;
        }
        //Connections to already existing, unvisited vertices
        else if(nodeMap.containsKey(connection) && 
                nodeMap.getByKey(connection).needsNeighbours)
        {
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
        //Grow graph with new vertices
        else
        {
            nodeMap.add(connection, new Node(connection));
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
    }
    this.needsNeighbours = false;
}

votre graphique satisferait toutes vos exigences sauf qu'il est cyclique. Je ne sais pas si vous avez réellement besoin d'une garantie. Si vous le faites, vous pouvez sélectionner spécifiquement un nœud non visité et établir une connexion, ce qui garantirait un chemin entre le nœud actuel et un nœud déjà visité car tous les nœuds non visités sont connectés à au moins un nœud visité et puisque vous avez dû visiter un nœud visité pour arriver là où vous êtes il y a maintenant au moins deux chemins.

C'est simple car il y a une vérification explicite, connecté parce que tous les nouveaux nœuds obtiennent au moins une connexion, localement fini car les bords ne sont ajoutés qu'avant votre visite ou lors de votre première visite, et uniquement aux nœuds non visités. Techniquement, ce n'est pas non orienté, mais fonctionnellement, c'est la même chose que vous créez un bord directionnel dans les deux directions. Vous pouvez étiqueter le nœud comme vous voulez, j'utilise le nombre aléatoire généré, mais vous pouvez ajouter d'autres paramètres au constructeur, l'un étant votre graine.

Chewy Gumball
la source
Vous percevez exactement ce que je voulais dire par «infini» et votre point sur «le plus extérieur» est bien pris en compte - j'ai modifié le verbiage dans ma question. Cependant, soit je ne comprends pas correctement votre générateur, soit j'ai mal expliqué mes besoins, car cela semble ne pas générer les mêmes graines pour des chemins différents vers le même sommet. J'ai ajouté quelques illustrations à ma question qui, je l'espère, clarifieront ce que j'essaie d'accomplir. :-)
Ben Blank
Je comprends ce que tu veux dire maintenant. C'est un peu plus difficile. Ce que vous devez faire est de changer l'appel genRandomNumbers à une fonction qui retourne toujours le même ensemble de nombres pour son entrée et d'utiliser la graine du nœud comme argument. Cela garantirait que vous obtiendriez les mêmes connexions et graines, peu importe le chemin que vous prenez ou le nœud avec lequel vous commencez. Vous devez faire attention à ce que l'ensemble de nombres pour le nœud B auquel A se connecte contienne également A afin que vous obteniez votre propriété de graphique non orienté. Si vous ne le faites pas, vous obtenez un graphique dirigé.
Chewy Gumball
1

Une méthode:

init:
  root = generateLocation using random seed
  store root's seed
  place player in root location

when the player enters a new location:
  release the memory used by locations that are further than 1 edge away, but keep their seeds
  generate some neighbors for the new location. for every neighbor n:
    gen.seed(getSeed(n))
    n = generateLocation using n's random seed
    numCyclicEdges = gen.randint(0, 1)
    create numCycleEdges edges to existing locations

getSeed(n):
  if(n already has a seed) return n's seed
  else return randomSeed()

Il y a beaucoup de détails que j'ai omis, mais cela devrait saisir l'idée générale. Vous souhaiterez peut-être conserver en mémoire des voisins plus éloignés de l'emplacement actuel, en fonction de la distance mondiale entre les portails, de la quantité de mémoire disponible, etc.

Jiahua Wang
la source