Tile Map als Array?

[Legion]

Hallo!

ich frage mich, wie könnte man ne 2D (tile)map am besten repräsentieren?
es geht mir hier nicht um pacman oder so mit 15x15 tiles, sondern ich rede von zb diablo 2 (weil das die meisten wohl kennen) oder ultima online. eine riesige map aus tiles. wie ist sowas im ram? is das ein riesiges array? wie könnte man das am klügsten machen?
wenn die map nicht rechteckig ist, dann hat man mit dem array auch viel overhead...

danke!

 

[Marco13]

Die Empfehlung, für eine Map eine Map zu verwenden klingt im ersten Moment nach einer Veräppelung Aber sowas wie
Map<Point, Tile> map = new HashMap<Point, Tile>();
wäre ja eine Möglichkeit. Da steht nur drin, was man braucht, und man kann einfach Teile löschen oder hinzufügen.

 

[Guybrush Threepwood]

Nachfrage: Meinst Du die Darstellung am Bildschirm oder die Datenstruktur?

 

[Legion]

naja, sowohl als auch. ich frag mich hald wie das in den spielen gelöst wurde. also eine effiziente lösung um die map zur laufzeit zur verfügung zu haben und gleichzeitig relativ komfortabel darstellen zu können.

 

[Guybrush Threepwood]

Offen gesagt überlege ich mir das im Moment auch. Es gibt im Netz ein paar Beispiele, die ich noch nicht 100% ideal finde. Interactive Pulp - PulpCore schaut recht interessant aus, wobei ich das ganze in Swing brauche, was leider nicht mit PulpCore geht. Ich überlege mir, ob ich nicht tatsächlich eine quadratische Karte über ein int[][]-Array generiere, bei der die jeweiligen Elemente (Mauern, freie Felder etc.) einfach über den Wert der einzelnen Zellen kodiert sind, und zeichne jeweils eine Karte, die ein bisschen größer ist als der Bildschirm. Nach dem Scrollen bei Bewegungen wird das Bild neu generiert. Ich weiß aber nicht, ob das sinnvoll ist, oder nicht.

Viele Grüße!

 

[Legion]

ich würde auch gern swing benutzen.
die idee von dir hatte ich schon auch, das scheint ja der übliche ansatz zu sein. ich würde aber ein byte oder short array benutzen. hab irgendwo gelesen, arrays verbrauchen je nach inhalt weniger speicher und da es ja nicht sooo viele tiles gibt... egal.
da kann man natürlich sehr leicht und schnell zeichnen. wenn die map aber nicht quadratisch ist, dann hat man viele "nutzlose" werte.
ich hab mir auch überlegt, dass man ein relativ kleines array verwendet, sagen wir zb 50x50, das etwas größer ist als der bildschirm. wenn man sich nun über die map bewegt und man langsam an den rand dieses array ankommt, dann lädt man aus einer datei auf der festplatte weitere inhalte der map und ersetzt die daten im array, über welche man schon hinweg "gescrollt" ist duch die neuen daten und zeichnet dann wieder in der mitte des arrays weiter. (falls das verständlich war )

 

[Marco13]

Das "Problem" bei einem 2D-Array ist, dass er sehr starr ist. Angenommen, man hat in einen [10][10]-Array den sichtbaren Ausschnitt seiner 100x100 tiles großen Welt gespeichert, und man läuft 1 schritt nach oben, dann muss der komplette Array ersetzt werden. Bei einer geeignet gewählten Map müßte man nur eine neue Zeile einfügen. (Mit ein bißchen tricksen (WeakHashMap oder so) könnte man vielleicht sogar erreichen, dass man die rausgescrollte Reihe nicht mal explizit entfernen muss, aber das müßte man sich noch genauer überlegen)

 

[Legion]

ok. ich verstehe was du meinst. ja, das array müsste dann irgendwann vollständig ersetzt werden.
dein ansatz mit der hashmap ist echt interessant. ich kann dir nur nicht ganz folgen was das mit dem "nachladen" angeht.
wenn sich die ganze map in der hashmap befinden würde, dann ist mir klar wie das geht, aber wie meinst du das, dass man nur eine zeile nachladen müsste? bzw. wie müsste das mit der hashmap laufen, damit die quasi stets nur den relevanten teil der map speichert?

 

[Marco13]

Hm. Für die konkrete Implementierung gibt es (speziell wenn noch dazukommt, dass man nur bestimmte Teile laden will, und ggf dynamisch wieder vergessen usw) SO viele Freieheitsgrade, dass ich nicht sicher bin, wie "pseudo" der "pseudocode" sein sollte, den ich schreiben könnte. Anstatt
array[x][y] = theTile;
verwendet man
map.put(new Point(x,y), tile);
Wobei es sich ohnehin grundsätzlich empfiehlt, die Landkarte erstmal als Interface zu beschreiben, um sich klar zu machen, was sie können muss - ob mit einem Array oder eine Map kann man später entscheiden...

interface GameMap
{
    Tile get(int x, int y);
    void set(int x, int y, Tile tile);
    void load(...) ???
    void setVisibleArea(...) ??
    ... ???

 

[Legion]

ja, so hab ich mir das alles schon gedacht. konkreter code wäre garnicht nötig gewesen, trotzdem danke
es ging mir jetzt nur um den groben ablauf. wie würdest du das machen? du speicherst in der hashmap also nur einen bereich (sichtbarer bereich und bisschen drum herum). sobald man sich bewegt lädtst du einen neuen bereich in die map? die tiles von denen man sich weg bewegt werden gelöscht? wie?

noch ne andere frage, was spricht dagegen nur ein point objekt zu verwenden und nur die coordinaten zu ändern und das dann immer beim einfügen/auslesen der map zu benutzen?

 

[Marco13]

du speicherst in der hashmap also nur einen bereich (sichtbarer bereich und bisschen drum herum). sobald man sich bewegt lädtst du einen neuen bereich in die map? die tiles von denen man sich weg bewegt werden gelöscht? wie?

ICH mache gar nichts Das war nur der Hinweis auf die Möglichkeit, eine Map zu verwenden. Wie gesagt hängen die konkreten Implementierungsdetails dann davon ab, was man in dem Spiel erreichen will und wie der Ablauf sein soll - ob Levelweise geladen werden soll, wie groß die Map ist, welche Änderungen es an der Map gibt etc. etc....

noch ne andere frage, was spricht dagegen nur ein point objekt zu verwenden und nur die coordinaten zu ändern und das dann immer beim einfügen/auslesen der map zu benutzen?

Vorsicht: Ein Objekt, das einmal als Key einer HashMap verwendet wurde, darf NICHT mehr verändert werden! Dadurch würde sich der hashCode des Objektes ändern, und die HashMap (oder auch jede andere Map) würde "durcheinanderkommen".

 

[Legion]

lol. natürlich meine ich nicht, dass du was machst. ich wollte sagen, "stellst du dir das so vor?".
wie gesagt, meine frage bezieht sich auf eine riesige map a la ultima online.
ich glaube ich probier mal ein bisschen rum mit der hashmap. scheint mir ein besseres konzept zu sein als das array...

ok, das mit dem hashwert leuchtet mir ein. ich hab dafür aber ne eigene klasse verwendet (nicht point) und da wird der hashwert berechnet anhand der koordinaten...

 

[fastjack]

Benutze Chunks. Ein Chunk ist ein Teil der Map, z.B. mit 256x256 Tiles. Der Hintergrund ist der, daß Deine Welt nicht mehr aus einzelnen Feldern besteht,sondern aus Chunks. Deine Weltkarte besteht z.B. aus 32x32 Chunks, als 32*256 x 32*256 Felder insgesamt. Du mußt wissen in welchem Chunk ein Spieler gerade ist und zu den Grenzen hin das benachbarte Chunk laden. Schon kannst Du mit relativ wenig Speicher riesige Weltkarten abbilden

 

[Marco13]

Das ist eine Möglichkeit - Falls es sowas wie "Level" gibt (ich kenn das angesprochene Spiel nicht) könnte man aber auch ein "Level=Chunk" in Erwägung ziehen - falls die Level nicht auch zu groß sind. In jedem Fall wären die Chunks etwas, was man ggf. hinter dem Interface verstecken könnte. Und wenn man dann immer weiß, dass man nur 1+8 Chunks laden muss (das mit dem Spieler und die 8 benachbarten) könnte man auch wieder über einen Array nachdenken - diese Chunks wären dann ja immer (gleich große) Raster....

 

[Legion]

hmm... ok, das beispiel ultima war schlecht. (bei ultima gibt es keine leeren stellen. die map ist eine solide rechteckige fläche)
bzw. in dem fall scheint array und chunk offensichtlich. ich würde aber gerne zerklüftete maps nutzen in sämtlichen formen. da scheint mir eine hashmap besser geeignet. ist auch die frage was wohl schneller ist bzw speicherbedarf...

 

[Marco13]

In gewissen Grenzen kann ein Array ja auch "zerklüftet" sein - wenn er z.B. an den "leeren" stellen einfach 'null' drin hat. Aber sicher kann man sich Formen vorstellen, für die ein Array eher sch... lecht geeignet wäre In bezug auf Laufzeit und Speicher: Sicher ist ein HashMap-lookup langsamer als ein Arrayzugriff, aber das sollte vermutlich nicht das Bottleneck sein. Und wenn's hinter einem Interface versteckt ist, kann man's ja austauschen....

 

[Evil-Devil]

Naja, in Diablo 2 und auch schon in Diablo 1 waren die Maps nicht gerade klein. UO kenne ich jetzt nicht. Bei D2 könnte ich mir vorstellen das von Gebietskarte zu Gebietskarte getrennte Datencontainer genutzt werden. Also zb. ausgehend von Akt 1: Stadt, Blut Moor und Höhle, etc. Und dann vielleicht noch zusätzlich die Unterteilung in die Chunks. Man müsste mal auf Gamedev/Gamasutra schauen ob es Artikel zur verwendeten Technik gibt.

Eine andere Möglichkeit die mir einfällt, wären LinkedLists. Letzten Endes muss man sich immer nur ein Tile heraussuchen das in einer der Ecken steht und von dort aus drauf los zeichnen.

Falls wer D2 nicht kennt, hier ein Bild mit einem der Dungeons die je nach Schwierigkeitsgrad auch noch wachsen.

 

[AngryDeveloper]

Für Diablo 2 gibt es sogar einen Map Editor:
Diablo II DS1 (map) Editor - Download Page

Sourcecode ist in C++.

Wenn man sich dafür interessiert, kann man sich da bestimmt auch etwas abgucken, wie da der Aufbau der Maps ist. Da bei Diablo 2 Maps generiert werden gibt es immer auch einzelne feste Bestandteile die dann zusammengesetzt werden.
Wie viel man aber tatsächlich aus dem Code des Editors erschließen kann, weiß ich nicht genau. Selbst angeschaut hab ich mir den jetzt nicht.

Ansonsten geht es schon in die Richtung wie es fastjack und Evil-Devil gesagt haben.

 

[fastjack]

In Diab 2 gab es einen anderen Chunk-Gedanken. Jeder Level soll anders aussehen, bei jedem neuen Spiel. Levels wurden in 4 Chunks geteilt. Für jedes Chunk existierten 4-8 unterschiedliche Versionen, die aber zusammenpassen und drehbar waren. Damit wurde ein großes Spektrum von Möglichkeiten im Levelaussehen erzeugt.

In Ultima 1-5 war die Map ein 2D-Feld. Ganz flach, es wurde nur der Index auf das Tile gespeichert.

In Ultima 6 wurden dann Chunks eingeführt (16x16 Tiles). Intern wurden die Chunks dann nochmal in vier Teile zerlegt (je 8x8). Die Maps wurden als Zahlenpaare dargestellt, die jeweils auf ein 8x8 Teilchunk zeigten.

 

[Legion]

ok, fastjack hat recht. zumindest habe ich mir das dateiformat von ultima angeschaut und das ist für diese chunks optimiert bzw sind die teile der map chunk weise gespeichert.
damit haben wir uns schonmal darauf geeinigt, dass nicht die ganze map im ram liegt sondern nachgeladen wird.
die frage bleibt wie sich am besten der ausschnitt im ram repräsentieren lässt. glaubt ihr, dass die map auf dem screenshot von evil-devil auch als array im ram ist (zumindest ein ausschnitt davon)?
in dia2 werden die maps ja random generiert. glaubt ihr, dass die dann erst mal in eine datei geschrieben werden nur um dann chunkweise wieder gelesen zu werden? oder werden die teile "on-the-fly" generiert?

 

[fastjack]

Das Herz von Diab 2 ist eine 2D Iso-Engine. Die Maps bestehen aus einzelnen Tiles sowie aus Tilegruppen. Line of Sight usw. wurde direkt die Maps eingebaut, der Leveldesigner mußte sich also darüber schon Gedanken machen und entsprechende Bereiche markieren. Die Map selbst ist ein bestimmtes c++ struct und wird mit ihren Daten einmal komplett geladen, d.h. zuerst randomisiert generiert. Im Singleplayer werden Map-Infos im Savegame untergebracht. Nachgeladen werden/können Grafiken/Sound, also Resourcen aller Art. Hast Du schon mal vor Baal gestanden und bist dann draufgegangen, weil es laggte, gerade wenn ein Riesenmob spawnt?

Ich würde mir Ultima 7 (sourcecode gibs in exult) ansehen, 2D + Pseudo-Iso + Physik (ok, die Physik-Anfänge gab es bereits in U6). Meiner Meinung nach eine der besten Engines, die jemals entwickelt wurden. Es gibt Tiles, Chunks und Regionen. Die WorldMap enthält 12x12 Regionen, eine Region enthält 16x16 Chunks, ein Chunk 8x8 Tiles. Bei wenig Speicher wird an allen Ecken und Enden nachgeladen, was damals den gewaltigen Hardwarehunger auslöste.

die frage bleibt wie sich am besten der ausschnitt im ram repräsentieren lässt.

Möglichst flach und speicherarm

glaubt ihr, dass die map auf dem screenshot von evil-devil auch als array im ram ist (zumindest ein ausschnitt davon)?

ja, intern ist es aber ein c++ struct.

in dia2 werden die maps ja random generiert. glaubt ihr, dass die dann erst mal in eine datei geschrieben werden nur um dann chunkweise wieder gelesen zu werden?

nein.

oder werden die teile "on-the-fly" generiert?

Zu Levelbeginn werden sie generiert und in den Speicher geladen. Speicherst Du ab, werden Infos in das Savegame geschrieben. Beim Multiplayer hält der Server diese Infos vor.

 

[fastjack]

Kleiner Nachtrag: Wenn Ihr wissen wollt, wie man die "Engine" aus Diablo rausholen kann

Removing the Engine From a Diablo 2

 

[Legion]

-.- boah war der low...

 

[fastjack]

Gelle, der war gut ne?