Java: Quelle est une bonne structure de données pour stocker une carte de coordonnées pour un monde de jeux infini?

1) au lieu d'un tableau vous pouvez utiliser un Map<Integer, Map<Integer, Tile>> ou Map<Point, Tile> , qui permettrait bien sûr des index négatifs

2) Si vous connaissez les dimensions de votre monde depuis le début, vous pouvez simplement modifier votre getter pour permettre à L'API d'accepter les négatifs et de les transformer [linéairement] en positifs. Par exemple, si votre monde est 100x1000 tuiles et que vous voulez (-5, -100), vous auriez WorldMap.getTile(-5,-100) qui se traduirait par return tileArray[x+mapWidth/2][y+mapHeight/2]; qui est (45,400)

Je ne suis pas un expert en programmation de jeu, mais si les tableaux sont OK, vous pouvez simplement traduire vos coordonnées de (-x, +x) à (0, 2x) (idem pour l'axe y).

ou si vous êtes habitué à des tableaux associatifs comme PHP, utilisez la structure correspondante en Java, qui est une carte (HashMap serait OK) : définissez une classe Coordinate avec les méthodes appropriées equals et hashCode, et utilisez un HashMap<Coordinate> . Rendre les coordonnées immuables rend le code plus robuste, et permet mise en cache de la hashCode.

Arbres, Arbres quadrilatères, arbres binaires, rouges et noirs-et tous les autres types d'arbres sont inutiles pour vous (à moins que vous ne prévoyez d'avoir une carte avec une énorme forêt).

les structures de données spécialisées ont des utilisations spécifiques. Sauf si vous pouvez trouver une bonne raison pour laquelle votre jeu a besoin d'un index spatial, ne construisez pas un. Si votre scénario typique est "itérer sur la zone visible, savoir ce qui est visible à chacun des carrés", alors vous avez besoin d'une structure cela vous donne un accès rapide, aléatoire, à une valeur stockée sous une clé spécifique. Une telle structure est une HashMap (ce que PHP utilise est une sorte de LinkedHashMap, mais vous n'utilisiez probablement pas la partie "linked").

vous devez suivre le Conseil de xephox( et lui donner le crédit), et qui est:

• faire une catégorie qui décrit un emplacement (paire, emplacement, Point, peu importe);
• rend tous les champs (probablement x et y) définitifs. Il est important que l'emplacement lui-même ne peut pas changer (il feront de votre vie BEAUCOUP plus facile);
• générer equals et hashcode méthodes (tous les IDE va vous aider avec ça. Rappelez - vous que les implémentations doivent utiliser à la fois x et y-un assistant dans votre IDE vous aidera);
• votre carte sera: Map map map = new HashMap ();

La meilleure chose: si vous continuez à utiliser l'interface de la Carte, vous ne serez pas verrouillé, et vous serez en mesure de faire beaucoup d'améliorations. Comme envelopper le HashMap dans un objet qui crée des parties de la carte en utilisant des techniques algorithmiques.

vous pouvez essayer un QuadTree (bel exemple ici: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation / )

Que Diriez-vous de diviser votre carte en morceaux (oui, fans de Minecraft, je sais où cela est aussi utilisé :P)? Vous avez donc deux systèmes de coordonnées, tous deux ayant la même origine:

• x/y coordonnées
• c1/c2 coordonnées partielles

un morceau est toujours une taille fixe de coordonnées du monde réel (disons 128x128). Alors vous avez une classe Chunk où vous avez un tableau fixe (128x128) avec toutes les informations pour chaque pixel. Et vous stockez vos morceaux dans un Map<ChunkCoordinates, Chunk> comme d'autres l'ont déjà expliqué. Je recommande un HashMap .

chaque fois que votre joueur est dans une certaine région, les morceaux nécessaires sont chargés à partir de la Carte Et alors vous pouvez accéder au tableau de taille fixe dans là. Si le morceau sait, où il est placé dans les coordonnées x/y , vous pouvez même avoir une fonction de soutien comme Pixel Chunk#getPixel(long x, long y) ou ainsi...

Btw: Cela vous donne aussi un moyen facile de reporter la génération du monde entier jusqu'à ce qu'elle soit vraiment nécessaire: au début, rien n'est généré et dès qu'un Chunk est accédé dans la carte, qui n'est pas encore généré, vous pouvez juste le générer alors. Ou vous pouvez remplir jusqu'au démarrage si c'est plus facile pour vous. (remplir un monde INFINI prendra cependant beaucoup de temps, même s'il est pseudo-infini)

j'ai écrit quelques structures expérimentales de données de rechange en Java qui pourraient vous intéresser.

le plus intéressant était le Octreap qui est ce que je crois est un croisement complètement nouveau entre un Treap et un Octree , qui avait les caractéristiques suivantes:

• 60 bits mondiale de coordonnées (aprox 1,000,000 * 1,000,000 * 1,000,000 grille)
• coordonnées négatives supportées
• espace Vide nécessite pas de stockage (prend en charge très clairsemée mondes)
• comprime des volumes de cellules identiques (par exemple, de grands blocs du même matériau seraient stockés efficacement)
• O (log n) Pour Lit et écrit

vous voulez probablement utiliser une implémentation de Map. HashMap, SortedMap, etc selon la quantité de données que vous avez l'intention de stocker et vos modèles d'accès (Carte triée est très bon pour l'accès séquentiel, HashMap est meilleur pour l'accès aléatoire).

vous pouvez soit utiliser des cartes bidimensionnelles ou munge vos indeces 2-d dans une clé pour une carte 1-D.

il s'agit de deux questions distinctes: comment simuler des indices de matrice négative pour que vous puissiez avoir une carte" infinie", et comment stocker efficacement des tuiles.

à la première question, un piratage serait de maintenir quatre matrices distinctes (matrices?), un pour chaque quadrant. Alors tous les indices peuvent être positifs.

à la deuxième question, vous avez besoin d'une carte clairsemée. Une façon pas très efficace est d'avoir un hashmap de hashmaps. En fait, cela pourrait résoudre le premier problème aussi bien:

HashMap<String, HashMap> x = new HashMap()
HashMap<String, Tile> y = new HashMap()

// get the tile at coordinates 1,2
Tile myTile = x.get("1").get("2");

// this would work as well
myTile = x.get("-1").get("-2");

vous pourriez faire votre propre mise en œuvre de carte qui a pris des entiers comme clés et était beaucoup, beaucoup plus efficace.

si vous voulez être vraiment rapide et vraiment évolutif certainement aller avec une Octree clairsemée.

http://en.wikipedia.org/wiki/Octree

Je n'ai connaissance d'aucune implémentation en Java, mais c'est trivial. Il suffit de stocker dans un seul octet un bitfield pour lequel les noeuds sont actuellement liés et d'utiliser une liste liée pour conserver ces références (pour chaque Octre-noeud une liste séparée de max. 8 entrées).

les solutions de style hashmap sont terribles pour les calculs de contiguïté, elles nécessitent une itération de l'ensemble des données.

quelque chose comme un quadtree ou une octree est parfait sauf qu'il n'est pas infini, c'est une taille arbitraire (monde de différence là).

mais si on y pense, un ArrayList n'est pas infini, c'est juste une taille arbitraire qui croît, Non?

donc un quadtree est clairsemé et assez bon ad calculs de contiguïté, à l'exception de la disposition" infinie", c'est parfait. Pourquoi ne pas utiliser une de ces tailles à 100x ce que vous pensez que vous pourriez avoir besoin (il est clairsemé, pas vraiment une grosse affaire). Si jamais vous arrivez au point où vous êtes près du bord, allouer un nouveau quadtree qui est beaucoup plus grand.

je crois que si vous êtes prudent (vous pourriez avoir à mettre en œuvre votre propre quadtree) vous pouvez "mettre à niveau" le quadtree avec très peu d'effort et aucune copie--il devrait être simplement une question de préfixer toutes vos adresses existantes avec quelques bits (les adresses sont en binaire, quadtrees chaque bit représente diviser l'univers existant en deux dans une dimension ou l'autre).