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

Question

J'ai l'habitude de coder en PHP mais je ne maîtrise pas vraiment Java et cela me pose problème depuis un certain temps déjà. Je m'attends à ce que ce soit une solution assez facile, mais je ne trouve pas de bon exemple de code, quelle que soit la façon dont je le cherche, alors voilà :

Je suis en train de programmer un jeu qui se déroule dans un monde infini généré aléatoirement en 2D sur une carte à base de tuiles (en pinaillant : Je sais qu'il ne sera pas vraiment infini. Je m'attends simplement à ce que le monde soit assez grand). L'approche habituelle d'un tableau multidimensionnel map[x][y] était une idée de base, mais comme Java ne permet pas de faire des manipulations avec des clés de tableau non entières (c'est-à-dire négatives) comme le fait PHP, je ne peux pas avoir un système de coordonnées (-x,+x,-y,+y) avec des clés de tableau.

Je dois être capable de trouver les objets sur une tuile à une coordonnée x,y spécifique ainsi que de trouver les "tuiles adjacentes" d'une certaine tuile. (Trivial si je peux getObjectAt(x,y), je peux get(x+1,y) et ainsi de suite)

J'ai lu des articles sur les arbres quadruples et les arbres R, etc. Le concept est passionnant, mais je n'ai pas vu d'exemple de mise en œuvre simple et efficace en Java. De plus, je ne suis pas vraiment sûr que ce soit exactement ce dont j'ai besoin.

Tout conseil est le bienvenu

Merci.

Answer 1

1) Au lieu d'un tableau, on pourrait utiliser un Map<Integer, Map<Integer, Tile>> o Map<Point, Tile> ce qui permettrait bien sûr des indices négatifs

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

Answer 2

Je suis arrivé sur ce fil de discussion avec le même problème, mais ma solution était d'utiliser Map/HashMaps mais ils sont unidimensionnels.

Pour surmonter ce problème, au lieu d'utiliser une carte dans une carte (ce qui serait désordonné et très inefficace), j'ai utilisé un fichier générique de type Paire (pas quelque chose que vous trouverez dans la bibliothèque java standard) bien que vous puissiez la remplacer par une classe Position (pratiquement le même code, mais pas générique, plutôt des entiers ou des flottants).

Donc, en définissant la carte : Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

Pour placer les objets de type tuile sur la carte, j'ai utilisé tiles.put(new Pair(x, y), new GrassTile()); et pour récupérer l'objet tiles.get(new Pair(x, y)); .

[x/y est une coordonnée quelconque que vous souhaitez placer ( cela permet des coordonnées négatives sans aucun désordre !), "new GrassTile()" est juste un exemple de placement d'une tuile d'un certain type lors de la création d'une carte. Évidemment - comme indiqué précédemment - la classe Pair est remplaçable].

Pourquoi pas des ArrayLists, me direz-vous ? Parce que les listes de tableaux sont beaucoup plus linéaires que les mappings et, à mon avis, il est plus difficile d'ajouter et de récupérer des tuiles, surtout en deux dimensions.

Mise à jour :

Pour tous ceux qui se demandent pourquoi il n'existe pas de classe Pair() en Java, voici une explication .

Answer 3

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

Les structures de données spécialisées ont leurs usages spécifiques. À moins que vous ne trouviez une bonne raison pour laquelle votre jeu a besoin d'un index spatial, n'en construisez pas. Si votre scénario typique est "itérer sur la zone visible, trouver quelle tuile est visible sur chacune des cases", alors vous avez besoin d'une structure qui 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'avez probablement pas utilisé la partie "linked").

Vous devez suivre les conseils de xephox (et lui en donner le crédit) :

• créer une classe qui décrit un lieu (paire, lieu, point, etc.) ;
• rendre tous les champs (probablement x et y) définitifs. Il est important que l'emplacement lui-même ne puisse pas changer (cela vous facilitera BEAUCOUP la vie) ;
• générer des méthodes de type "equals" et "hashcode" (chaque IDE vous aidera à le faire). N'oubliez pas que les implémentations DOIVENT utiliser à la fois x et y - un assistant dans votre IDE vous aidera) ;
• votre carte sera : Map map = new HashMap() ;

Le meilleur : si vous continuez à utiliser l'interface Map, vous ne serez pas bloqué et vous pourrez apporter de nombreuses améliorations. Par exemple, vous pouvez transformer le HashMap en un objet qui crée des parties de la carte en utilisant des techniques algorithmiques.

Answer 4

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

Ou si vous avez l'habitude des tableaux associatifs comme en PHP, utilisez la structure correspondante en Java, qui est une Map (HashMap serait OK) : définissez un fichier Coordinate avec les méthodes equals et hashCode appropriées, et utiliser une classe HashMap<Coordinate> . Rendre Coordinate immuable rend le code plus robuste, et permet de mettre en cache le hashCode.

Answer 5

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