Un moyen de stocker des données cartographiques 2D potentiellement infinies?

29

J'ai un jeu de plateforme 2D qui peut actuellement gérer des morceaux avec 100 par 100 tuiles, avec les coordonnées des morceaux stockées en tant que longs, c'est donc la seule limite des cartes (maxlong * maxlong). Toutes les positions d'entité, etc., sont pertinentes pour les blocs et il n'y a donc pas de limite.

Le problème que j'ai est de savoir comment stocker et accéder à ces morceaux sans avoir des milliers de fichiers. Avez-vous des idées pour un format d'archive HD de préférence rapide et à faible coût qui n'a pas besoin de tout ouvrir en même temps?

Blam
la source
2
Certaines structures de données que vous pourriez examiner pour plus d'inspiration sont des matrices clairsemées et des tableaux de pages (à plusieurs niveaux) .
Andrew Russell
Faible priorité: pourriez-vous préciser si le type de données «long» est 32 ou 64 bits?
Randolf Richardson
2
@Randolf étant donné qu'il s'agit de C #, il signifie probablement le C # longqui est 64 bits (donc maxlong l'est Int64.MaxValue).
Andrew Russell
Notch a des choses intéressantes à dire sur les cartes infinies dans Minecraft dans son blog ici: notch.tumblr.com/post/3746989361/terrain-generation-part-1
dlras2

Réponses:

17

Créez un format de carte personnalisé pour votre jeu. C'est plus facile que vous ne le pensez. Utilisez simplement la classe BinaryWriter. Écrivez d'abord l'en-tête en quelques ints ou uints. Informations à inclure dans l'en-tête:

  • La chaîne magique / nombre magique de votre format de fichier.
  • Le début / fin / taille des morceaux décrits dans ce fichier

et aussi (et voici la partie critique de la performance

  • entiers qui décrivent la position de départ à l'intérieur du fichier. Vous n'avez donc pas à rechercher de morceaux spécifiques.

Avec la méthode ci-dessus, vous pouvez (et devriez) créer un index du contenu de vos fichiers, contenant une sorte de description (un nom spécifié par l'utilisateur pour la région / le morceau, ou juste les coordonnées) et comme deuxième valeur la position dans le fichier.

Ensuite, lorsque vous souhaitez charger un morceau spécifique, il vous suffit de rechercher dans l'index. Lorsque vous avez obtenu la position, définissez simplement fileStream.Position = PositionOfChunkFromIndex et vous pouvez la charger.

Il s'agit de la conception du format de fichier avec l'en-tête décrivant le contenu du fichier le plus efficacement possible.

Enregistrez simplement les fichiers avec une extension personnalisée que vous avez créée et c'est parti.

BONUS: Ajoutez la compression BZip2 à des régions spécifiques du fichier / tout le contenu (pas l'en-tête !!), afin que vous puissiez décompresser des morceaux spécifiques du fichier, pour une très petite empreinte mémoire.

Riki
la source
12
Il convient de souligner que si vous souhaitez modifier ce fichier à la volée, vous souhaiterez un en-tête / index de taille fixe ou externe, de sorte que vous pouvez ajouter des morceaux au fichier sans avoir à réécrire le fichier entier (en raison de la modification des décalages).
Andrew Russell
À ce stade, vous n'implémentez pas simplement une base de données de fichiers plats?
Ape-inago
13

J'ai rencontré un problème similaire et j'ai décidé de créer ma propre structure pour gérer les données. Il est vaguement basé sur un quadtree, mais a une extensibilité infinie (au moins aussi grande qu'un Int) dans toutes les directions. Il a été conçu pour gérer des données basées sur une grille qui se sont développées à partir d'un point central, tout comme Minecraft le fait maintenant. Il est peu encombrant en mémoire et très rapide.

Vous pouvez spécifier une magnitude minimale pour chaque nœud (une magnitude de 7 serait 128x128) et une fois qu'un nœud a un pourcentage spécifié de ses sous-nœuds peuplés, il s'aplatit automatiquement en un tableau à deux dimensions. Cela signifie qu'une partie très densément peuplée (par exemple, un continent complètement exploré) aura les performances d'un réseau (très rapide) mais une partie peu peuplée (par exemple, un littoral quelqu'un a erré de haut en bas mais n'a pas exploré l'intérieur des terres) avoir de bonnes performances et une faible utilisation de la mémoire.

Mon code se trouve ici . Le code est complet, testé (tests unitaires et de charge) et assez optimisé. Le fonctionnement interne n'est pas encore trop bien documenté, cependant, mais toutes les méthodes publiques le sont donc il devrait être utilisable. Si quelqu'un décide de l'essayer, n'hésitez pas à me contacter pour des questions ou des commentaires.

Je ne l'ai pas encore utilisé pour stocker des données dans un fichier, mais c'est un problème intéressant et je pourrai y remédier ensuite.

dlras2
la source
Il s'agit donc essentiellement d'un arbre extensible, non? Qu'est-ce que je rate?
kaoD
2
La plus grande amélioration par rapport à un arbre extensible est qu'il aplatit certains nœuds de l'arbre qui sont fortement peuplés (70% par défaut) dans des tableaux 2D, plutôt que de les garder structurés comme des arbres. Cela vous donne la vitesse d'une recherche de tableau, sans la taille (infinie) d'un tableau infini.
dlras2
Les nœuds foliaires et intérieurs, non? Idée intéressante, pourrait donner de bons résultats, je vais l'essayer si jamais j'en ai besoin. Btw, +1 pour avoir donné le code et la réponse rapide! Oh, et les tests unitaires sont également effectués, je ne le fais (malheureusement) jamais dans mes projets personnels :)
kaoD
Nous ne faisons pas de tests unitaires dans mon travail, donc c'est malheureusement ma façon de me rebeller. jours donc c'est présentable, je le posterai ici aussi. Cela a beaucoup plus de sens lorsque vous le voyez.
dlras2
1
Je l'ai perdu de vue, désolé! Je voudrais toujours le nettoyer, mais je retravaille lentement une partie du code entre la classe et les devoirs, donc ce ne sera pas pour un moment. Pour le moment, l'ancienne démo peu jolie est ici: j.mp/qIwKYt Par non jolie, je veux dire en partie qu'elle nécessite beaucoup d'explications, alors n'oubliez pas de lire le README et n'hésitez pas à poser des questions ici ou par email.
dlras2
3

Vous pouvez utiliser une base de données à la place - PostgreSQL a des capacités d'indexation spéciales optimisées pour ce type de données qui sont localisées par les coordonnées X et Y. Vous pouvez également spécifier que les données renvoyées se trouvent dans un certain rayon plutôt que dans une zone de forme carrée ou oblongue.

  PostgreSQL (gratuit et open source)
  http://www.postgresql.org/

Il existe également d'autres bases de données, et pour le côté client, vous pouvez trouver certains types mieux adaptés à cela car ils peuvent fonctionner de manière autonome (initié par votre application cliente de jeu) ou peuvent être inclus dans le cadre d'une bibliothèque de code que vous pouvez "simplement utiliser". L'avantage est que vous n'avez pas à concevoir un schéma d'indexation car la plupart des moteurs de base de données SQL le font déjà très bien.

Un avantage de l'approche de base de données est que vous pouvez réduire la taille de vos morceaux (ou vous débarrasser complètement des morceaux et simplement utiliser des tuiles directement, mais l'utilisation d'au moins de petits morceaux / groupes de nombreuses tuiles peut être plus efficace selon votre conception), puis utilisez la requête SQL pour apporter une zone plus grande que celle visible. En préchargeant pour chevaucher les zones non visibles à proximité, les carreaux peuvent être préparés avant le joueur ne déplace son personnage, ce qui donne une meilleure expérience de jeu (espérons-le plus fluide).

J'ai remarqué que certains jeux gardent un "cache" des données cartographiques sur le disque dur local après l'avoir obtenu la première fois (c'est sans doute pour réduire les E / S réseau), comme Ashen Empires:

  Ashen Empires (gratuit pour jouer, belle implémentation 2D)
  http://www.ashenempires.com/

Garder une trace des horodatages "dernière mise à jour" avec chaque bloc / tuile sera également utile car, pour les données stockées localement, la requête SQL peut inclure une clause supplémentaire "WHERE timestamp_column> $ local_timestamp" afin que seuls les morceaux / tuiles mis à jour soient récupérés. téléchargé (deux avantages d'économiser de la bande passante comme celui-ci sont des coûts de connectivité plus faibles et moins de décalage pour vos joueurs, ce qui deviendra plus évident lorsque votre jeu deviendra populaire).

Une capture d'écran d'Ashen Empires (quelques personnages se trouvent dans une banque locale, et d'après l'apparence de ces os sur le sol, il semble que quelques monstres squelettes aient erré et aient probablement été abattus par les gardes de la ville locale):

entrez la description de l'image ici

Randolf Richardson
la source
2

Ne les stockez pas et n'y accédez pas, ne stockez que les graines aléatoires nécessaires ainsi que les modifications du joueur sur la carte. Générez ensuite les portions requises au moment de l'exécution (exécutez votre algorithme de génération, puis appliquez les modifications du joueur). Avec une procédure de génération correcte et cohérente, la carte résultante sera toujours la même pour la même graine de départ.

Théoriquement, vous pouvez faire une carte littéralement infinie qui sera enregistrée de cette façon dans un très petit fichier.

code sh
la source
@Josh Petrie merci pour les corrections linguistiques et stylistiques importantes et remarquables apportées à mon message. dommage que je ne puisse pas voter pour une modification :-D
sh code
1

Existe-t-il un moyen de partitionner des morceaux (une sorte de «sous-continents / pays» dans votre monde)? Alors peut-être que vous pouvez avoir une sorte de fichiers d'index qui vous permettent de trouver rapidement quel sous-fichier / partie de fichier plus gros que vous devez charger pour avoir un morceau en mémoire ...

phtrivier
la source
il y a toujours un moyen de partitionner des morceaux. TOUJOURS. qu'ils soient visibles pour le joueur / pertinents pour le reste du système ou non, il existe toujours un moyen de partitionner les données mondiales en morceaux, généralement de plusieurs manières différentes.
code sh
0

Vous pouvez reprendre l'idée de Minecraft. À l'origine, ils avaient un fichier par morceau. Maintenant, ils utilisent le format MCRegion, qui regroupe les morceaux en zones 32x32 et en stocke un par fichier.

Le canard communiste
la source