Comment dois-je construire la structure de données pour un «labyrinthe» dynamique de taille illimitée?

43

Je ne suis pas vraiment sûr que «labyrinthe» soit le terme correct. Fondamentalement, les utilisateurs démarrent dans un fichier unique Roomcomportant 4 portes (N, S, E et W). Ils peuvent aller dans n’importe quelle direction et chaque pièce subséquente contient une autre pièce pouvant contenir de 1 à 4 portes menant à d’autres pièces.

Le "labyrinthe" est censé avoir une taille illimitée et se développer lorsque vous changez de pièce. Il y a un nombre limité de Roomsdisponibles, mais le nombre disponible est dynamique et peut changer.

Mon problème est, je ne suis pas sûr de la meilleure structure de données pour ce type de modèle

J'ai d'abord pensé à utiliser simplement un tableau d' Roomobjets [X] [X] , mais je préférerais vraiment éviter cela, car l'objet est censé évoluer dans n'importe quelle direction et que seules les pièces "visitées" doivent être construites.

L’autre idée était de faire en sorte que chaque Roomclasse contienne 4 Roompropriétés liées pour N, S, E et W et crée un lien vers la précédente Room, mais le problème que je ne vois pas, c’est que je ne sais pas comment identifier si un utilisateur se rend dans une pièce a une pièce adjacente déjà "construite"

Par exemple,

--- --- ----------
| | | |
   Début 5 4
| | | |
--- --- --- ---
--- --- ---------- --- ---
| | | | | |
| 1 2 3
| | | | | |
--- --- --- --- ----------

Si l'utilisateur quitte Start> 1> 2> 3> 4> 5, alors le Roomn ° 5 doit savoir que W contient la salle de départ, S est le local n ° 2 et, dans ce cas, ne doit pas être disponible, et N peut être un neuf Roomou un mur (rien).

Peut-être ai-je besoin d'un mélange du tableau et des pièces liées, ou peut-être que je regarde cela de la mauvaise façon.

Existe-t-il un meilleur moyen de construire la structure de données pour ce type de "labyrinthe"? Ou suis-je sur la bonne voie avec mon processus de pensée actuel et manque-t-il juste quelques informations?

(Si cela vous intéresse, le projet est un jeu très similaire à Munchkin Quest )

data-structures game-development Rachel
la source
Je ne pense pas que n'importe quel type de tableau fonctionnerait, car les salles grandiraient dans n'importe quelle direction ... Donc, si vous commencez à [0,0] et que vous vous déplacez à gauche? il essaierait [-1, 0].
Paul
@Paul Ajoute une ligne / colonne, décale toutes les données du tableau, puis décale toutes les positions du joueur pour correspondre au nouveau tableau de la carte. Lent et peut être difficile en fonction de ce qui doit être déplacé, mais possible. Néanmoins, la réponse de Bubblewrap est bien meilleure.
Izkata
Je me trompe probablement, mais est-ce que cela ne serait pas mieux sur GameDev.SE?
Dynamic
1
@Dynamic Ceci est une question de structure de données, donc cela convient parfaitement ici.
Izkata

Réponses:

44

Donnez les coordonnées de chaque pièce (le début serait (0,0)) et stockez chaque pièce générée dans un dictionnaire / hashmap par coordonnées.

Il est facile de déterminer les coordonnées adjacentes pour chaque pièce, que vous pouvez utiliser pour vérifier si une pièce existe déjà. Vous pouvez insérer des valeurs null pour représenter des emplacements où il est déjà déterminé qu'aucune pièce n'existe. (ou si ce n'est pas possible, je ne suis pas sûr que atm, un dictionnaire / hasmap séparé pour les coordonnées qui ne contiennent pas de salle)

Papier bulle
la source
2
Assurez-vous que chaque objet Room contienne des informations nord-est-sud-ouest par rapport aux autres objets Room, de sorte que vous puissiez utiliser le dictionnaire / hashmap ainsi que les indications cardinales Room pour naviguer dans le labyrinthe (vous aurez parfois besoin de trouver des coordonnées absolues). Parfois, vous voudrez savoir ce qui se trouve au nord de l'objet Room X).
Neil
2
@Paul Je pense que l'idée est de créer un dictionnaire de pièces et, lors de la construction d'une nouvelle Roompièce, cherchez les pièces adjacentes dans le dictionnaire et ajoutez leurs liens à l' Roomobjet avant d'ajouter de nouvelles pièces aux côtés restants. Le seul moment où la recherche par le dictionnaire aurait lieu est lors de la création d'un nouvel Roomobjet, et non pas entre deux voyagesRooms
Rachel
7
Il n'y a aucune raison de stocker des liens vers d'autres pièces à l'intérieur d'un Roomobjet. Si vous êtes dans la même pièce (x,y)et que vous souhaitez parcourir le nord, vous consultez (x,y+1)le dictionnaire et le créez s'il n'existe pas. Dictionnaire sont très lookups rapide, O(1).
Karl Bielefeldt
3
@KarlBielefeldt: La pièce @ (x,y+1)peut exister, mais ne pas être navigable depuis (x,y)le nord. C'est-à-dire qu'un bord ne peut pas aller directement de (x,y)à (x,y+1).
Steven Evers
2
Vous faites ça compliqué les gars. C'est fondamentalement la même chose qu'un tableau .. sauf que vous le cherchez dans un dictionnaire plutôt que dans un tableau à deux dimensions. Tous les problèmes que vous rencontrez avec un tableau seront également présents ... mais il allait quand même utiliser un tableau.
user606723
15

Dans la plupart des cas, ce que vous décrivez ressemble à un graphique. Compte tenu de certaines de vos exigences (l'aspect croissant), je choisirais probablement une liste de contiguïté comme implémentation (l'autre option courante serait une matrice de contiguïté ).

Je ne suis pas sûr de la langue que vous utilisez, mais voici un bon tutoriel / explication avec les détails de l'implémentation d'un graphique implémenté avec une liste de contiguïté dans .NET .

Steven Evers
la source
1
Pas sûr qu'un graphe soit suffisant pour décrire cela, car N / E / S / W ne fait pas vraiment partie du concept de graphe; il n'y a que connecté et éventuellement in / out.
Edward Strange
3
@CrazyEddie: N'oubliez pas que la structure de données / a n'est pas destinée à être mappée directement sur un domaine particulier (c'est en effet leur avantage). Dans cet exemple particulier, le graphique serait directionnel et les arêtes peuvent être annotées de manière triviale avec une énumération.
Steven Evers
L'annotation pourrait trivialement renforcer la relation est-ouest, voire nord-sud. Cela éliminerait les problèmes de déplacement de la pièce A vers la pièce B, puis de la pièce B vers l’est (à la place de la pièce A), en raison d’un mauvais lien.
Peter Smith
3
Disons que nous voulions mettre en place une salle composée d'un sorcier qui se protège en téléportant le joueur dix cases dans une direction aléatoire. Trouver ce point dans une structure de données basée sur un graphique serait très coûteux, surtout si cette pièce n'existait pas et que vous deviez générer toutes les pièces reliant cette pièce à une autre pièce du graphique (car la structure ne permettait pas plusieurs, sections de donjon mutuellement déconnectées).
Mark Booth
2
@MarkBooth mais ensuite nous avons changé les exigences, non?
Joshua Drake
9

Quelques réflexions sur la mise en œuvre (j'ai pensé à Carcassonne qui présente un certain nombre d'aspects difficiles pour construire la matrice - c'était même une question d'entrevue que l'on m'avait déjà posée).

Certaines questions sont posées à cette structure:

  1. Y a-t-il une pièce à X, Y?
  2. Y a-t-il une pièce [N / S / E / W] de l'emplacement vide X, Y?

Le problème avec les simples listes et graphiques

La difficulté avec les listes simples est qu’il faut parcourir la structure pour vérifier si quelque chose peut être placé à un endroit donné. Le système a besoin d’un moyen d’accéder à un emplacement arbitraire O (1).

Considérer:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Pour trouver l’information sur l’emplacement possible '?', Quand à 3, il faut parcourir tout le chemin pour aller à 4. La réponse de link avec des informations supplémentaires sur le nombre de nœuds sautés (de sorte que 3 soit lié à 4 avec un 'saut 1' supplémentaire) nécessite toujours des marches pour trouver la contiguïté de '*' à partir de 6 ou A.

Simple, grand, tableaux

Il y a un nombre limité de chambres disponibles

S'il ne s'agit pas d'un nombre important, créez simplement un tableau de 2N x 2N et laissez-le là. Un tableau de 100 x 100 est 'seulement' 10 000 pointeurs et 50 objets. Index directement dans le tableau.

Cela pourrait être réduit à seulement NxN si des activités hors limites déplaçaient le tableau pour rester toujours dans les contraintes. Par exemple, si vous souhaitez ajouter une pièce qui submerge le tableau, demandez à la grille de décaler chaque élément d’une position afin qu’il n’y ait plus de débordement. À ce stade, la taille du monde pour 50 salles serait de 2 500 pointeurs et de 50 objets.

Tableaux et matrices clairsemés

Pour créer cela de manière plus optimale, examinez un tableau fragmenté dans lequel la majorité des éléments sont 0 ou nuls. Pour deux dimensions, il s’agit d’une matrice clairsemée . De nombreux langages de programmation ont différentes bibliothèques pour travailler avec cette structure. Si la bibliothèque se limite à des entiers, vous pouvez utiliser cet entier comme index dans un tableau fixe de pièces.

Mon approche préférée serait de disposer les pièces comme structure (pointeurs vers les pièces adjacentes et coordonnées) et que la pièce soit également un pointeur à partir d'une table de hachage hachée en coordonnées. Dans cette situation, demander quelle est la pièce [N / S / E / W] d'une pièce nulle, interrogerait la table de hachage. C'est d'ailleurs le format 'DOK' pour stocker une matrice fragmentée.

Communauté
la source
1
Belle réponse, comme le suggère Bubblewrap cependant, un dictionnaire avec un tuple de position comme clé est une structure raisonnable à utiliser pour mettre en œuvre une matrice clairsemée.
Mark Booth
2

Que dis-tu de ça..

Donnez à chaque cellule un lien vers chacun de ses voisins. Donnez à chaque cellule une sorte de nom (par exemple "0/0", "-10/0" (supposons que vous commenciez à 0,0)). Ajoutez un hachage contenant tous les noms. Lorsque vous essayez de passer à une autre cellule, vérifiez simplement que le voisin n'existe pas déjà dans le HashSet.

De plus, si vous créez une ouverture sur une autre pièce, cela signifie-t-il que les pièces existent? Vous créez donc un lien vers une pièce vide sans lien vers aucune pièce. Vous voudrez probablement aussi vérifier les nouvelles chambres des voisins. S'il en existe un et qu'il s'ouvrirait sur votre nouvelle pièce, ajoutez une porte à cette pièce.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ....} 1,0: W = 0,0 / Porte; 1,0: N = 1,1 / vide; E = 2,0 / porte; S = 1, -1 / mur

Vous devez également vous assurer de donner à chaque nouvelle pièce au moins une porte non adjacente (vers une autre pièce) afin que le labyrinthe puisse croître dans cette direction.

Paul
la source
1

Ce que vous concevez ressemble beaucoup à un graphique.

Un graphique du labyrinthe

Celles-ci sont souvent représentées par un ensemble d'états Q , un état initial q 0 ∈ Q et quelques transitions Δ . Donc, je vous suggère de le stocker comme ça.

  • Un ensemble Q : {s, 1, 2, 3, 5, 6}
  • Un état initial q 0 : s
  • Carte des relations de transition Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

La plupart des langues raisonnables ont à la fois des cartes et des ensembles.

kba
la source
0

Vous pourriez envisager une liste chaînée 4 voies ...

J'ai d'abord pensé à utiliser simplement un tableau [X] [X] d'objets Room, mais je préférerais vraiment éviter cela, car l'objet est censé évoluer dans n'importe quelle direction et que seules les pièces "visitées" doivent être construites.

Vous pouvez toujours utiliser un [] [] pour cela. La dynamique de croissance peut être lente, en particulier lors de l'ajout au début, mais peut-être pas si mal. Vous devriez profiler pour vérifier. Essayer de manipuler une liste ou une carte liée pourrait en fait être pire, et à un niveau constant plutôt qu'occasionnel.

Vous ne pouvez créer que des salles visitées en implémentant une évaluation paresseuse. Un objet peut contenir une pièce et ne pas construire cette pièce tant qu’il room()n’est pas appelé. Ensuite, il retourne simplement le même à chaque fois par la suite. Pas difficile à faire.

Edward Strange
la source
1
Pourriez-vous préciser ce que vous entendez par "liste chaînée"? La seule chose que j'ai pu trouver était un article CodeProject, qui se résumait à être une liste de contiguïté.
Steven Evers
0

J'ai appris à le faire via le livre "Création de jeux d'aventure sur votre ordinateur". Si vous êtes prêt à fouiller dans le code BASIC (le livre est si vieux), allez lire ici:

http://www.atariarchives.org/adventure/chapter1.php

Pour le raccourci, ils ont un tableau de pièces, un élément de chaque tableau étant un pointeur vers une autre pièce où vous pouvez aller, 0 (je voudrais utiliser -1 ces jours-ci) pour indiquer que vous ne pouvez pas Va dans cette direction. Par exemple, vous feriez une structure de pièce (ou classe ou ce que vous avez)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Ensuite, vous pouvez avoir un tableau ou une structure de liste chaînée ou bien d’autre part vous souhaitez gérer vos salles. Pour un style de tableau (ou des vecteurs C ++), j'utiliserais ce code et les instructions contiendraient l'index de la pièce à laquelle elles sont liées; pour une liste chaînée, vous pouvez utiliser des pointeurs vers la pièce suivante.

Comme d'autres l'ont déjà dit, vous pouvez également le faire si vous devez générer de manière dynamique de nouvelles salles lorsque des personnes y entrent.

laaph
la source
0

N'essayez pas de résoudre tous les problèmes avec une seule structure.

Définissez votre objet room pour stocker des informations sur la pièce, pas ses relations avec les autres pièces. Ensuite, un tableau 1D, une liste, etc. peuvent croître à votre guise.

Une structure distincte peut contenir "l'accessibilité" - les pièces accessibles depuis la pièce dans laquelle je me trouve. Décidez ensuite si l'accessibilité transitive doit être un calcul rapide ou non. Vous voudrez peut-être un calcul de force brute et un cache.

Évitez l'optimisation précoce. Utilisez des structures très simples et des algorithmes stupides, faciles à comprendre, puis optimisez ceux qui sont utilisés.

julien
la source