Java: Was ist eine gute Datenstruktur zum Speichern einer Koordinatenkarte für eine unendliche Spielwelt?
Ich bin verwendet, um die Codierung in PHP, aber ich bin nicht wirklich versiert im Umgang mit Java-und dies wurde ein problem für einige Zeit jetzt. Ich erwarte, dass es eine ziemlich einfache Lösung, aber ich kann nicht finden, eine gute Beispiel-code, wie ich es suchen, so hier geht:
Bin ich Programmier ein Spiel, das stattfindet in einer 2d-zufällig generierte unendliche Welt auf einer Kachel-basierten Karte (Erbsenzählerei: ich weiß, es wird nicht wirklich unendlich. Ich erwarte lediglich, dass die Welt ziemlich groß). Die übliche Vorgehensweise der Karte[x][y] mehrdimensionales array, begann als eine grundlegende Idee, aber da in Java nicht bieten eine Möglichkeit für nicht-ganzzahlige (also negativ), array key-Spielereien wie PHP funktioniert, ich kann nicht richtig ein (-x,+x,-y,+y) - Koordinatensystem mit array-Schlüsseln.
Ich muss in der Lage sein zu finden die Objekte auf einer Kachel an einer bestimmten x -, y-Koordinate, sowie der Suche nach der "angrenzenden Fliesen" von einer bestimmten Kachel. (Trivial, wenn ich kann getObjectAt(x,y), kann ich(x+1,y), und so weiter)
Habe ich gelesen, die über quad-Bäume und R-Bäume und dergleichen. Das Konzept ist spannend, aber ich habe nicht gesehen ein gutes, einfaches Beispiel für die Implementierung in Java. Und außerdem bin ich nicht wirklich sicher, ob das ist, was ich genau brauchen.
Jede Beratung ist willkommen
Danke
InformationsquelleAutor der Frage Aykın | 2011-03-07
Du musst angemeldet sein, um einen Kommentar abzugeben.
Kam ich zu diesem thread mit dem gleichen problem, aber meine Lösung war die Verwendung Landkarte/HashMapsaber diese sind eindimensional.
Um dies zu überwinden, statt eine Karte innerhalb einer Karte (das wäre chaotisch und sehr ineffizient) habe ich eine generische Paar Klasse (nicht etwas, das finden Sie in der Bedarfs-java-Bibliothek), obwohl Sie könnten, ersetzen Sie diese mit einer Position-Klasse (praktisch der gleiche code, aber nicht generisch, anstatt integers oder floats).
Also bei der Definition der Karte:
Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;
Für die Platzierung Kachel-Objekte auf der Karte, die ich verwendet
tiles.put(new Pair(x, y), new GrassTile());
und für das abrufen der Objekttiles.get(new Pair(x, y));
.[x/y wäre jede Koordinate, die Sie platzieren möchten (dies ermöglicht es, negative Koordinaten ohne Sauerei!), "neue GrassTile()" ist nur ein Beispiel, bei dem ein Plättchen eines bestimmten Typs während der map-Erstellung. Offensichtlich - wie bereits erwähnt - die Pair-Klasse ist austauschbar.]
Warum nicht ArrayLists können Sie Fragen? Weil array-Listen sind viel mehr als lineare Abbildung und sind meiner Meinung nach schwieriger zum hinzufügen und abrufen von Fliesen, vor allem auf 2 Dimensionen.
Update:
Für alle Fragen, warum gibt es nicht ein Paar() Klasse in Java, hier ist ein Erklärung.
InformationsquelleAutor der Antwort Liam Gray
1) Statt eines Arrays können Sie ein
Map<Integer, Map<Integer, Tile>>
oderMap<Point, Tile>
das würde natürlich erlauben, negative Indizes2) Wenn Sie wissen, die Dimensionen der Welt aus starten, könnten Sie nur ändern Sie Ihre getter zu ermöglichen, um die API zu akzeptieren, negative und [Linear] verwandeln Sie in positive. So zum Beispiel, wenn Sie Ihre Welt ist 100x1000 Fliesen und Sie wollen (-5,-100), Sie hätte
WorldMap.getTile(-5,-100)
was zu übersetzen, umreturn tileArray[x+mapWidth/2][y+mapHeight/2];
welche (45,400)InformationsquelleAutor der Antwort davin
Ich bin kein Experte in der Spiel-Programmierung, aber wenn arrays sind OK, könnte man einfach übersetzen Sie Ihre Koordinaten (-x, +x) auf (0, 2) (idem für die y-Achse).
Oder, wenn Sie ' re verwendet, um assoziative arrays wie in PHP hat, die Verwendung der entsprechenden Struktur in Java, was ist eine Map (HashMap würde OK sein) : definieren Sie einen
Coordinate
Klasse mit entsprechenden equals und hashCode Methoden, und verwenden Sie eineHashMap<Coordinate>
. Machen Koordinate unveränderlich macht den code robuster und ermöglicht das Zwischenspeichern der hashCode.InformationsquelleAutor der Antwort JB Nizet
Bäume, Quad-Trees, Binary trees, rot und schwarz-Bäume - und alle anderen Arten von Bäumen sind NUTZLOS für Sie (es sei denn, Sie planen, eine Karte zu haben mit einem riesigen Wald).
Spezialisierten Datenstrukturen haben Ihre spezifischen nutzt. Es sei denn, Sie kommen mit einem guten Grund, warum Ihr Spiel braucht einen räumlichen index erstellen nicht. Wenn Ihr typisches Szenario ist "Iteration über den sichtbaren Bereich, finden Sie heraus, welche Kachel ist sichtbar in jedem der Quadrate", dann brauchen Sie eine Struktur, die Ihnen einen schnellen, wahlfreien Zugriff auf einen gespeicherten Wert unter einem bestimmten Schlüssel. Eine solche Struktur ist eine HashMap (was PHP verwendet, ist eine Art von einer LinkedHashMap, aber Sie waren wahrscheinlich nicht mit der "verlinkten").
Müssen Sie xephox Rat (und geben ihm den Kredit), und das ist:
Das beste: wenn Sie zu halten mit der Karte-Schnittstelle, werden Sie nicht gesperrt werden, und Sie werden in der Lage sein, eine Menge von Verbesserungen. Wie das einwickeln der HashMap in ein Objekt, das erstellt Teile der Karte mit einigen algorithmischen Techniken.
InformationsquelleAutor der Antwort fdreger
könnten Sie versuchen, einen QuadTree (schönes Beispiel hier: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ )
InformationsquelleAutor der Antwort Simon Heinen
Wie über die Aufteilung Ihrer Karte in Stücke (ja, auch Minecraft-fans, ich weiß, wo diese verwendet wird :P)? So haben Sie zwei Koordinatensysteme, beide mit dem gleichen Ursprung:
x/y
Koordinatenc1/c2
chunk-KoordinatenEin chunk ist immer eine Feste Größe in der realen Welt zu koordinieren (sagen 128x128). Dann haben Sie eine Klasse
Chunk
wo Sie eine Feste array (128 x 128) mit allen Informationen, die für jedes pixel. Und speichern Sie Ihre Stücke in einemMap<ChunkCoordinates, Chunk>
wie bereits erklärt, von anderen. Ich würde empfehlen, eineHashMap
.Wenn Ihr player ist in einer bestimmten region, die notwendigen chunks geladen sind, von der Karte und dann können Sie auf die Feste Größe array. Wenn der chunk weiß, wo es platziert wird in
x/y
Koordinaten, können Sie sogar einige support-Funktion wiePixel Chunk#getPixel(long x, long y)
oder so...Btw: Dies gibt Ihnen auch eine einfache Möglichkeit zu verschieben-generation die ganze Welt, bis es wirklich gebraucht wird: Beim start, nichts wird erzeugt und, sobald ein
Chunk
erfolgt in der Karte, das ist noch nicht generiert ist, können Sie nur generieren, die es dann. Oder Sie füllen könnte es beim Start, wenn das ist einfacher für Sie. (ausfüllen einer unendlichen Welt wird eine lange Zeit dauern, aber, auch wenn es pseudo-unendlich)InformationsquelleAutor der Antwort brimborium
Schrieb ich ein paar experimentelle spare Datenstrukturen in Java, dass Sie interessiert sein könnten.
Am interessantesten war die Octreap das ist, was ich glaube, ist eine völlig neuartige Kreuzung zwischen einem Treap und ein Octreedie hatte die folgenden features:
InformationsquelleAutor der Antwort mikera
Wollen Sie Sie wahrscheinlich verwenden eine Implementierung von Map. HashMap, SortedMap, etc, je nachdem, wie viele Daten Sie Vorhaben zu speichern und Ihre Zugriffsmuster (Sortiert Karte ist sehr gut für sequentiellen Zugriff, HashMap ist besser für random access).
Können Sie entweder zwei-dimensionale Karten oder munge Ihre 2-d-indeces in einen Schlüssel für eine 1-d-Karte.
InformationsquelleAutor der Antwort patros
Dies zwei getrennte Fragen: wie simulieren negative array-Indizes, so können Sie eine "unendliche" map, und wie zu speichern, Fliesen effizient.
Auf die erste Frage, ein hack wäre die Aufrechterhaltung vier separate matricies (Matrizen?), einen für jeden Quadranten. Dann werden alle Indizes positiv sein kann.
Auf die zweite Frage, Sie brauchen eine sparse-Karte. Eine nicht-sehr-effizienteste Weg ist, um eine hashmap von hashmaps. In der Tat, das könnte lösen das erste problem:
Könnten Sie tun, Ihre eigenen Map-Implementierung, die dauerte ganze zahlen als Schlüssel und der war viel, viel effizienter.
InformationsquelleAutor der Antwort ccleve
Wenn du wirklich schnell sein will und wirklich skalierbar auf jeden Fall gehen Sie mit einer Sparse-Octree.
Ich kenne keine Implementierungen in Java, aber es ist trivial. Speichern nur in einem einzigen byte ein Bitfeld, für welche Knoten momentan verbunden und verwenden eine verknüpfte Liste, um diese Referenzen (für jedes Octree-Knoten eine separate Liste von max. 8 Einträge).
InformationsquelleAutor der Antwort Bernd Elkemann
Die hashmap Stil-Lösungen sind schrecklich für angrenzens Berechnungen, benötigen Sie eine iteration des gesamten Datensatzes.
Etwas wie ein quadtree oder octree ist perfekt, AUßER, dass es nicht unendlich, es ist eine willkürliche Größe (himmelweiter Unterschied).
Aber wenn Sie darüber nachdenken, eine ArrayList ist nicht unendlich, es ist nur eine willkürliche Größe, die wächst, richtig?
So ein quadtree ist sparce und ziemlich gut ad Nachbarschaft Berechnungen, außer für die "unendlich" - Bestimmung ist es perfekt. Warum nicht einfach einen von denen benutzen, die Größe 100x, was Sie denken, Sie brauchen könnte (es ist spärlich, nicht wirklich eine große Sache). Wenn Sie jemals an den Punkt gelangen, wo Sie in der Nähe der Kante, weisen Sie eine neue quadtree, ist viel größer.
Ich glaube, wenn Sie vorsichtig sind (die Sie haben können, um Ihre eigenen quadtree) kann man das "upgraden" der quadtree mit sehr wenig Aufwand und ohne zu kopieren-es sollte einfach eine Frage der, indem Sie alle Ihre bestehenden Adressen mit einigen bits (die Adressen sind in binären, quadtrees jedes bit stellt die Aufteilung der bestehenden Universum in der Hälfte in einer dimension oder die anderen).
InformationsquelleAutor der Antwort Bill K