Große Tilemap

Unistyle

Guten Tag,

ich zerbereche mir schon seit einiger Zeit den Kopf wie eine große Tilemap zu handlen ist.

Ersteinmal zu mir: Ich programmiere mit der Sprache C++ und nutze die Multimediabibliothek SFML. Ich bin in der Lage eine Tilemap zu programmieren.
Jedoch begrenzt sich mein können auf eine Tilemap Größe wie sie in einem Vektor im
Arbeitsspeicher möglich ist.

Mein Vorhaben ist inspiriert von dem Spiel "Tibia" (ein MMORPG).
Natürlich fange ich klein an und beschäftige mich wie das Spiel es schafft eine große map in laufzeit zur Verfügung zu stellen.
Und zwar ist die map soweit ich mich erinnern kann "32000 x 32000" (Höhe mal Breite). Außerdem gibt es 14 verschiedene Etagen, also wird auch eine Höhe simuliert. von oberen Etagen kann man die unteren sehen. Und von unten kann man
auch z.B. Gebäude nach obenhin einsehen.

Jede Etage hat schätzungsweise 3 Layer. Jedes Feld ist 32x32 pixel groß.
Die Größe der Map scheint also enorm, zumindest für mich.

(32000 x 32) x (32000 x 32) x (14 x 3)
= 1024000px x 1024000px x 42layer ist die map groß wenn ich mich nicht irre.

Da das Spiel in einem Raster (32x32) zu spielen ist kann man das ganze ja auf:
32000 x 32000 x 42 beschränken. Dies ist aber dennoch zu groß um die gesamte Map im RAM zu halten
Ich habe schon viel gesucht zu dem Thema. Allerdings finde ich größtenteils Informationen zu kleinen Tilemaps wie Super Mario ect.

Ansonsten habe ich Stichpunkte wie Sparse Matrix und Chunk Loading gefunden.
Die Recherchen dazu sind aber ziemlich mager oder ziemlich kompliziert erklärt.

Für mich scheint es die beste Lösung zu sein die map in einer Datei gespeichert zu haben und je nach Kamera Position einzelne Teile aus der Map Datei zu laden.
Da ich aber erstmals mit einem Map Editor anfange, weil ich keinen finde der eine Einstellung für solch eine große map bereit stellt müsste die map auch während sie erstellt wird in die Datei ausgelagert werden und zusätzlich teile nachladen. Ich weiß jetzt nicht ob man in der Map Datei navigieren kann, ohne die ganze Datei durchlaufen zu müssen.

Ich weiß, meine Gedanken sind ein wenig ungeordnet. Ich habe auch keinen wirklichen Anhaltspunkt und hoffe, dass mir hier jemand helfen kann wie das
am besten zu Lösen ist

Mit freundlichen Grüßen,
Robin.

otze

Ich würd dir raten, erst einmal mit kleinen Projekten anzufangen. Wenn dir nicht klar ist, wie das bei *gigantischer Tilemap* funktioniert, dann implementiere erstmal den Normalfall.

Unabhängig davon ist es wahrscheinlich, dass das Spiel nur jewils einen kleinen Teil dieser großen Karte im Ram hat.

Unistyle

Den Normalfall habe ich ja hinbekommen und den Index für die Koordinaten genutzt.
Also ist der Map Editor mit einer beschränkten map größe kein Problem.
Es wird auch nur der Teil gezeichnet der zu sehen ist, wie es auch von den meisten empfohlen wird (ist ja auch logisch).

Ich könnte mir auch niemals vorstellen, dass alles im RAM ist.
Nagut angeblich soll es mit einer Sparse Matrix möglich sein, die verstehe ich allerdings nicht. Nur soviel, dass nicht jede Koordinate mit Inhalt gefüllt ist und irgendwie kein Speicher für diese Stellen reserviert wird, was ja bei mir oft der Fall ist.

Ich wäre schon darüber froh wenn mich jemand auf eine nützliche Seite verweisen könnte die mir im Ansatz helfen könnte

Mechanics

Ich seh bei einer Tile Map keine sparse matrix, außer du meinst du Tiles, die sich wiederholen, z.B. Wänder. Da seh ich aber nicht so viel Einsparpotenzial.
Ich würd die Map komprimiert in einer Datei speichern und die Tiles bei Bedarf nachladen, was genau ist das Problem?

Unistyle

Nunja ich dachte es gibt vielleicht eine effizientere Lösung als das nachladen, oder evt. Tipps dazu. Ich schau mal wie weit ich komme, da ich bisher einfach nur Dateien gefüllt habe und noch nie genau durchnavigiert habe.

hustbaer

@Unistyle
Die Map mag insgesamt 32k*32k gross sein (wobei ich schätze dass hier eher Pixel gemeint sind und nicht Tiles).
Nur ist davon sicher das meiste einfach leer.
Und selbst dort wo nicht einfach "Nichts" ist werden die meisten Bereiche sich auf einen oder zwei Layer beschränken.

Was du z.B. machen kannst ist die Map hierarchisch aufzubauen. Also Stücke zu z.B. je 32x32 Tiles zu einer "Superkachel" zusammenfassen, dann wieder 32x32 solche Superkacheln zu einer "Level 2 Superkachel" usw.
Und wenn ein ganzer 32x32 Block irgendwo leer ist, dann wird eine Ebene höher eben nur vermerkt "hier ist nix" statt einem Zeiger auf den 32x32 Block.

Weiters kannst du, wenn du wirklich grosse "unbewohnte" Bereiche haben willst wo aber trotzdem "etwas" ist, also Wald und Flüsse und so Zeugs, prozedural generierte Teile verwenden.
Dazu müsstest du statt des jeweiligen Blocks dann abspeichern nach mit welcher Funktion er zu generieren ist plus die für den Generator nötigen Parameter (Seedwerte für Zufallsgenerator und so Zeugs).
Wenn dann jemand an diesen Bereichen etwas ändert kannst du sie während das Spiel läuft zu "normalen" Bereichen "upgraden", indem du die Information "prozedural generiert mit Parameter ..." entfernst und statt dessen einen normalen Block hinterlegst.

Das ganze kannst du im Prinzip für jeden Layer einzeln machen. Dadurch werden dann alle Layer bis auf einen fast ausschliesslich aus "hier ist nix" Einträgen bestehen.

Und beim Abspeichern kannst du alles nochmal RLE komprimieren. Dadurch sparst du bei Layern die nicht ganz aber fast leer sind auch nochmal ordentlich Platz.

@Mechanics
Klar kann man bei einer Tile-Map viel einsparen. Die RPG Dungeons die ich so im Kopf habe sind alles andere als Rechteckig, da sind riesen Bereiche wo einfach nur Nichts ist. Dann sind Dungeons auch nicht überall, an den meisten Stellen gibt's keine "Unterwelt".
Und auch die Oberwelt wird bei einem Spiel das erstmal nur eine riesen Map hat vermutlich zu grossen Teilen leer oder fast leer sein.

Wenn das ganze natürlich irgendwann mal "voll" werden soll, weil einfach massiv viele Spieler in der gleichen Welt spielen, dann muss man das System natürlich von vornherein darauf auslegen dass es damit klarkommt. Wenn es aber erstmal einfach nur gross sein soll, um den Eindruck von ... naja Grösse und Freiheit und so zu vermitteln, dann kann man irre viel Platz einsparen.

hustbaer

ps:

otze schrieb:

Ich würd dir raten, erst einmal mit kleinen Projekten anzufangen. Wenn dir nicht klar ist, wie das bei *gigantischer Tilemap* funktioniert, dann implementiere erstmal den Normalfall.

+1

Mach erstmal ein Spiel das es wert ist gespielt zu werden. Dann kannst du dir - z.B. für's nächste Projekt, oder Version 2 - den Kopf darüber zerbrechen wie du mit grösseren Maps umgehen kannst.

cooky451

Holzhammer wäre File Mapping.

hustbaer

Auf 64 Bit Systemen ginge es sogar
Irgendeine Kachelung der Kacheln sollte man aber auch da machen. Sonst zersägt man sich die Platte mit den vielen unnötigen Seeks.

Was ist denn mit Mipmaps? Man lädt die gesamte Karte in den Ram, allerdings nur mit vielleicht 1600x1600 Auflösung. Dann kann man schonmal alles sehen und für 90% der Umgebung ist man weit genug weg, dass man es nicht merkt. Für die Map in der Umgebung des Spielers wird die detaillierte Map geladen, damit man die vollen Details hat. Das hat den zusätzlichen Vorteil, dass man auf einem eigentlich zu langsamen Rechner nicht warten muss oder es ruckelt, sondern man vorübergehend qualitativ nicht so dollen Texturen sieht, bis die hochauflösende geladen ist.
Man muss natürlich etwas mit Ferngläsern und Teleports aufpassen. Die Mipmaps kann man manuell laden und entladen und die Grafikkarte macht den Rest.

rapso

ist das nicht ein online spiel? wartest du zu irgendeiner zeit um dir die GB an tile maps zu laden?
die 'map' ist also in stuecke zerteilt, wenn es 64x64 eintraege grosse tile maps sind, dann deckst du immer noch 2048x2048 pixel ab. (64*32), du zerlegst also die map in 512x512 tile maps, die jede 64x64 ist, die dann auf 32x32 grosse tiles/sprites referenziert.
jede dieser 64x64 maps kannst du vermutlich sehr gut packen, im einfachsten fall bmp mit zip gepackt, oder als png.
dazu ein paar tiles die einfach nur wiederholend sind, z.b. wasser, erde, grass. schon hast du aus den terrabyte an daten vielleicht insgesammt 512MB gemacht.

die kannst du dann zur laufzeit nachladen wenn du sie brauchst, programmiertechnisch waere es sinnvoll wenn du dir eine kleine verwaltungsklasse bastelst. diese macht nichts anderes, als pointer auf bilder zurueck zu liefern (vielleicht mit refcounting, google ). falls ein bild noch nicht da ist, wird es geladen (von festplatte oder spaeter vom server).
am anfang laedst du die 512x512 uebersichtsmap, dann je nachdem wo der player ist, die 64x64 tilemaps und beim zeichnen die 32x32 pixel sprites/tiles.

du kannst ein speicherlimit setzen, z.b. 256MB, wenn beim laden von den sprites das limit ueberschritten ist, loescht du die am laengsten nicht mehr benutzen bilder bis du wieder unter dem limit bist.

eine simple implementierung sollte auf heutigen rechnern schnell genug sein. mach nichts kompliziertes und es wird gut laufen.

DNKpp

Naja, an sich würde ich das so regeln, das du die Map in verschiedene Grids einteilst (praktisch Grob- und Feinkoordinaten), und dann Gridweise lädst, was du benötigst, wie rapso das schon ganz richtig gesagt hat (sollte bei entsprechende klein gehaltener Größe kaum merklich sein).
Was er allerdings mit "Bildern" meint, verstehe ich nicht ganz. Möchtest du die Tilemap so speichern?

rapso

eine tile map ist eine matrix mit eintraegen (vermutlich uint32_t falls es diese groesse hat).
auch in einer hierarchie waere jede hierarchy vermutlich so aufgebaut.
ein sprite/tile ist eine matrix mit farb eintraegen (vermutlich uint32_t).

zusammengefasst brauchst du also immer

int width=...;
int height=...;
std::vector<uint32_t> Buffer(width*height);

von mir "bild" genannt.

Ethon

Bei meinem Projekt ist das so gelöst: Eine definiere einen Chunk als einen Mapteil in der Größe des Spielfensters (800x640). Jetzt lade ich eine 3x3 Chunk-Matrix, wobei der mittlerer Chunk (M[1, 1]) der ist, auf dem sich der Spieler befindet. Bewegt sich der Spieler in einen anderen Chunk, wird wieder die Matrix geladen etc.
Ich halte alle Chunks in einem Cache solange der Spieler höchstens n Chunks entfernt ist, danach fliegt der Chunk raus und müsste neu geladen werden.
Allerdings ist n bei mir gleich UINT_MAX, da ich es nicht mal im Ansatz schaffe viel Speicher zu verbrauchen.

Unistyle

Danke erstmal für die zahlreichen Antworten

Also ein Grid besteht bereits. Tut mir Leid wenn dies in meinem ersten Post nicht hervorgekommen ist. Also ein Feld ist 32x32 Pixel groß.
Wenn ich die tilemap zeichne nutze ich also komprimierte Koordinaten oder wie man des auch nennen mag. Sprich 1/1 wäre die Koordinate 32/32.
2/2 = 64/64. Gridkoordinaten wäre glaub ich der richtige Begriff. Dieser wird einfach x32 berechnet um die Original Koordinate zu berechnen z.B. zum Zeichnen.

Zum Thema "mach erstmal ein kleines Projekt":
Ich hatte jetzt erst einmal vor mich auf den map Editor zu konzentrieren.
Das Spiel kommt später dran, sobald der Map Editor die wichtigsten Funktionen besitzt um eine Karte zu erstellen.

Vor längerer Zeit hatte ich einen Map Editor und das Spiel mit dem Game Maker programmiert, bis ich die Grenzen der IDE erkannt habe. Viele Funktionen laufen auch ziemlich langsam ab. Deshalb bin ich zu der Sprache C++ gewechselt.
Schon bei einfachen Sachen konnte ich einen hohen Leistungsanstieg sehen, was ja auch zu erwarten war.

@hustbaer
Es sind schon 32k*32k Tiles. Ich habe gerade einen Map Editor getestet der für das Spiel Tibia programmiert ist. Dem reservierten Speicher zufolge wird kein Tile in der Laufzeit ge- oder entladen. Es ist mir ein Rätsel :p

Hier ist ein Bild von dem Spiel welches ich mir als Vorbild nehme. Vielleicht hilft es zum Verständniss:
http://www.mobygames.com/images/shots/l/576650-tibia-browser-screenshot-on-the-streets-of-thais-tibia-s-largest.png

Es sind auch definitiv mehr als 2 Layer pro Etage möglich:
http://dc469.4shared.com/img/ZZ5pXZLK/s7/exemplo.PNG

Wenn ihr weitere Links zum Verständnis braucht worauf ich hinausarbeiten möchte (z.B. der Tibia Map Editor ect.) schreibt mir eine PN da diese denk ich nicht in den Thread gehören

Edit: Ich seh gerade ich schreibe solange, dass es wieder Antworten gibt :p
Feinkoordinaten brauche ich bei diesem Aufbau nicht. Ich nutze eine Grafik in der alle Tiles enthalten sind und teile diese im Programm in einem 32*32 Raster auf. Die Tiles sind alle gleich groß (32*32), wenn dies noch nicht ganz klar ist.

@Ethon
Deine Lösung hört sich sehr Speichersparend an, sowas in der Art ist mir auch in den Sinn gekommen [=

hustbaer

Unistyle schrieb:

@hustbaer
Es sind schon 32k*32k Tiles. Ich habe gerade einen Map Editor getestet der für das Spiel Tibia programmiert ist. Dem reservierten Speicher zufolge wird kein Tile in der Laufzeit ge- oder entladen. Es ist mir ein Rätsel :p

Wie willst du das am Speicherverbrauch ablesen?

Unistyle

Ich gehe davon aus, weil der Speicherverbrauch steigt wenn man Tiles setzt und nicht runter geht, bzw. gleich bleibt selbst wenn ich bei einer map größe von 32k*32k oben links tiles setze und mit der Kamera nach unten rechts navigiere.
Ich hatte eigentlich erwartet, dass bei nicht sichtbaren Teilen Speicher gespart wird.

Dies war aber nur darauf bezogen ob etwas in einer Datei ausgelagert und daraus je nach Situation der Kamera wieder geladen wird.
Natürlich wird Speicher reserviert wenn neue Tiles gesetzt werden. Das zweifel ich nicht an. Nur wunder ich mich nur wie der Programmierer die tilemap behandelt wenn die map so groß wird.

Server/Client technisch wird das ganze aber schlau gelöst. Informationen über Teile der map werden den Spielern beim spielen vom Server zum Client gesendet.
Bei max. 1000~ Spielern pro Server scheint es auch gut zu laufen.
Pro: -Map muss nicht auf dem PC vorhanden sein = weniger Speicherverbrauch
-Map wird nicht für Privat Server geklaut

Kontra: -Server braucht eine dementsprechende Bandbreite(sollte aber heutzutage kein Problem sein)

Aber über den Client und Server mach ich mir erst Gedanken wenn es irgendwann soweit ist :p

DNKpp

Unistyle schrieb:

Server/Client technisch wird das ganze aber schlau gelöst. Informationen über Teile der map werden den Spielern beim spielen vom Server zum Client gesendet.
Bei max. 1000~ Spielern pro Server scheint es auch gut zu laufen.
Pro: -Map muss nicht auf dem PC vorhanden sein = weniger Speicherverbrauch
-Map wird nicht für Privat Server geklaut

Kontra: -Server braucht eine dementsprechende Bandbreite(sollte aber heutzutage kein Problem sein)

Verschätz dich da mal bitte nicht. Der Trend geht hin zum Mobilen Netz, und die haben bekanntlich eine Drossel drin bei zu hohem Traffic. Ich für meinen Teil wollte deswegen kein Game zocken, das ständig irgendwelche Maps vom Server lädt, obwohl diese sich nichtmal ändert
Einmal laden ist ok, aber jedes mal wenn man in Sichtweite kommt wieder laden ist unsinnig, und ist technisch nicht hinnehmbar!

EDIT: warum sollte denn der Speicher mehr werden? Wenn du beim Mappen lediglich nur die Infos speicherst, wo du ein Tile änderst, wird das ziemlich lange dauern, bis da merklich was dazu kommt. Ich weiß nicht wie das System funktioniert, kann mir aber vorstellen, das er nur die Änderungen im Speicher hält, und nicht das komplette Abbild der Map.

Unistyle

Mit der Bandbreite ist mein vorheriger Beitrag auf Computer/Laptop beschränkt
An Mobilgeräte hatte ich garnicht gedacht und ich finde solche Spiele gehören da garnicht hin solange es solche Beschränkungen gibt.

Das Spiel Tibia speichert nur erkundete Bereiche der map als Minimap.
Diese ist aber nur mit bestimmten Farben gekennzeichnet.
Dass Teile der Map geladen geladen werden merkt der Spieler beim Spielen nicht, also stört es mich nicht groß. Ich selber bevorzuge aber wenn dann Teile lokal aus einer Datei zu laden. Ich weiß nur noch nicht wie weit ich dies hinbekomme, aber das werde ich sehen

@Edit:
Ja das wüsste ich ja nur zu gern wie er es gemacht hat
Er hatte den Source Code einer mittlerweile veralteten Version zum download bereit gestellt. Allerdings bin ich nicht so gut darin tausende von fremden code zu verstehen^

hustbaer

@Unistyle
Viele Heap-Implementierungen geben Speicher nie wieder an das OS zurück, auch wenn er im Programm freigegeben wurde.
Man kann also leider aus keiner der Zahlen die man im Task-Manager sieht ablesen ob ein Programm Speicher wieder freigibt oder nicht.

Mich würden folgende Punkte interessieren, mag mir dafür aber nicht extra diesen Map-Editor installieren:

Speicher der Map-Editor die Daten lokal, oder editiert man damit Daten die direkt auf irgend einem Server gespeichert sind?
Falls lokal, bzw. falls du Zugriff auf so einen Server hast: wie gross sind die Level-Files dann?
Wie sieht eine "leere" Map aus, ist die wirklich komplett leer, oder ist die voll mit lauter "generischer Landschaft"?
Wie sieht eine "übliche" volle Map aus, wie viel Prozent davon sind wirklich belegt, bzw. falls die leere Map schon voll mit Landschaft ist: wie viel Prozent davon wurden wirklich gegenüber der "Default-Landschaft" verändert?

otze

Unistyle schrieb:

Also ein Grid besteht bereits.

Ließ nochmal die Posts. Wir meinen ein anderes Grid. Stell dir vor, du legst ein weiteres, gröberes Gitter über deine Map, welches nun 32x32 diner Gridzellen umfasst.

Es sind auch definitiv mehr als 2 Layer pro Etage möglich:
http://dc469.4shared.com/img/ZZ5pXZLK/s7/exemplo.PNG

Ich sehe keine Layer.Ich sehe unbegehbares Terrain und begehbares Terrain welches mit der Textur "treppe" markiert ist.