Structure de données pour un monde aléatoire

Question

Donc, je pensais à créer un générateur de monde aléatoire simple. Ce générateur créerait une "cellule" de départ qui aurait entre une et quatre sorties aléatoires (dans les directions cardinales, quelque chose comme un labyrinthe). Après avoir décidé de ces sorties, je produisais une nouvelle "cellule" aléatoire à chacune de ces sorties, et je répétais chaque fois qu'un joueur s'approchait d'une partie du monde qui n'avait pas encore été générée. Ce concept permettrait un monde "infini" de toutes sortes, tous générés de manière aléatoire; Cependant, je ne suis pas sûr de la meilleure façon de représenter cela en interne. J'utilise C++ (ce qui n'a pas vraiment d'importance, je pourrais implémenter n'importe quelle sorte de structure de données nécessaire). Au début, j'ai pensé à utiliser une sorte de graphe orienté dans lequel chaque noeud aurait des bords dirigés vers chaque cellule qui l'entoure, mais cela ne fonctionnera probablement pas bien si un utilisateur trouve une place dans le monde, fait marche arrière, et revient à spot d'une autre direction. Le monde pourrait faire des choses étranges, comme générer deux cellules à un endroit.

Des idées sur quel type de structure de données pourrait être le plus efficace pour une telle situation? Ou est-ce que je fais quelque chose de vraiment stupide avec ma génération mondiale aléatoire?

Toute aide serait grandement appréciée. Merci, Chris

Answer 1

Un map< pair<int,int>, cell> fonctionnerait probablement bien; la paire représenterait les coordonnées x, y. S'il n'y a pas de cellule dans la carte à ces coordonnées, créez une nouvelle cellule. Si vous vouliez le rendre vraiment infini, vous pourriez remplacer les ints par une classe entière de longueur arbitraire que vous auriez à fournir (comme un bigint)

Answer 2

Impossible de disposer d'un hachage (ou d'un ensemble STL) stocké une collection de toutes les coordonnées de la grille qui contiennent des cellules occupées?

Ensuite, lorsque vous cherchez à créer une nouvelle cellule, vous pouvez vérifier rapidement si l'emplacement de la cellule candidate est déjà occupé. (Si vous aviez un espace fini, vous pouvez utiliser un tableau 2d - je pense l'avoir vu dans un article du magazine Byte en ~ 1980-ish, mais si je comprends bien, vous voulez un monde qui pourrait s'étendre indéfiniment)

Answer 3

Si les cellules du monde sont disposées dans une grille, vous pouvez facilement leur donner des coordonnées cartésiennes. Si vous conservez une grande liste de cellules existantes, avant de déterminer les exits d'une cellule donnée, vous pouvez vérifier cette liste pour voir si l'un de ses voisins existe déjà. Si c'est le cas, et que vous ne voulez pas avoir de portes à sens unique (graphique orienté?), Vous devrez prendre en compte leurs sorties. Si cela ne vous dérange pas d'avoir des chutes dans votre jeu, vous pouvez toujours choisir des sorties au hasard, assurez-vous juste que vous liez aux cellules existantes si elles sont là. Note d'optimisation: vérifier une table de hachage pour voir si elle contient une clé particulière est O (1).

Answer 4

Je vous recommande de lire sur les graphiques. C'est exactement une application de génération de graphe aléatoire. Au lieu de 'cell' et 'exit' vous décrivez 'node' et 'edge'. De plus, alors vous pouvez faire des choses comme l'analyse du plus court chemin, la détection de cycle et toutes sortes d'autres applications utiles de théorie des graphes.

This vous aidera à comprendre sur les nœuds et les arêtes:

et here est une application finie de ces concepts. J'ai implémenté ceci d'une manière OOP - chaque nœud savait à propos de ses bords à d'autres nœuds. Une alternative populaire consiste à implémenter ceci en utilisant un adjacency list.Je pense que le concept de liste d'adjacence est fondamentalement ce que user470379 décrit avec sa réponse. Cependant, sa solution cartographique permet des graphes infinis, contrairement à une liste d'adjacence traditionnelle. J'adore la théorie des graphes, et c'est une application parfaite.

Bonne chance!

-Brian J. Stianr-