Große Tilemap

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.

Unistyle

@hustbaer
Achso, das wusste ich nicht. Man lernt immer weiter aus
Ich ging davon aus, dass wenn man die Kamera an einen anderen Ort bringt, dass zumindest ein wenig speicher freigegeben wird, aber der reservierte Speicher bleibt genau gleich. Aber da hab ich mich wohl geirrt.

Die Fragen kann ich gerne beantworten:

Der Map Editor speichert die map lokal.
Die Level Datei von Tibia ist 93~MB groß. (Es gibt Leute die haben "fast" die ganze map erkundet und diese mit Hilfe eines Programmes als map Datei zusammen"getracked") daher hab ich den Wert falls jemand fragt :p
Wenn die map leer ist sieht man nur einen schwarzen Hintergrund (1kb map file)
Die Hauptebene (Oberfläche der Erde sozusagen) ist schätzungsweise zu 80% belegt. Unterirdisch würde ich sagen sind es um die 50%. Überirdisch dürfte es am wenigsten sein, da es meist nur teile von Häusern sind und Höchstens einige Gebirge -> 30%~

@otze
Ach so meinst du das, aber in wie weit kann mir das helfen?

Ich habe kein besseres Bild auf die schnelle finden können. Das mit dem Layer muss man so sehen: Auf eine Etage können viele Tiles übereinander liegen wie z.B. Terrain -> Tepich -> Tisch -> Buch.

Edit: Ich muss mich bei euch entschuldigen... Aus früheren Foren Diskussionen bin ich davon ausgegangen, dass die Tibia map 32k*32k groß ist. Nachdem ich ein wenig herumprobiert habe um die Fragen von hustbaer zu beantworten habe ich etwas herausgefunden. Und zwar habe ich die Tibia map geöffnet und habe verzweifelt nach dem Inhalt gesucht.

Ich habe folgendes festgestellt:
Die Größe der Map ansich ist schon 32k*32k. Allerdings ist in der Nähe der Postion von 0/0 eine kleine Insel (Nur für die GameMaster/Support) und die eigentliche Spielkarte reicht von 29k/29k bis 32k/32k. Also sind eigentlich nur eine Fläche von 3k*3k wirklich belegt. Diese Größe habe ich dann sofort mal in meinem Programm festgelegt und es wird fast 2GB ram dabei reserviert.
Gibt es eine Möglichkeit den Speicher nur für gesetzte Tile zu reservieren?
Der fertige Map Editor den ich mir angeschaut habe tut dies ja anscheinend und kommt bei einer gefüllten Fläche auf knapp die Hälfte.

Tut mir nochmals aufrichtig Leid für dieses missverständnis.. und wenn euch das hier langsam zu viel wird kann ich das verstehen

cooky451

Das ändert alles überhaupt nichts, alle Antworten sind nach wie vor gültig. Du solltest mittlerweile in der Lage sein das alles problemlos zu implementieren.

Unistyle

Da hast du Recht. Ich setz mich dann nun dran es fertig zu stellen und melde mich wieder. Danke soweit für eure Hilfe

Baldur

Bei so großen Maps ist es ja ansich zwingend notwendig, die Karte in kleinere Abschnitte aufzuteilen.

Wie hier schon mal jemand geschrieben hat:
Du hast z.B. einzelne 100x100 Tiles große Karten-Stücke. Die eigentliche Map hat dann nur noch Referenzen auf diese Kartenstücke. Auf diese weise kannst du leere Abschnitte auch einfach leer lassen, ohne daß sie größere Mengen Speicher verbrauchen.
Das ganze lässt sich auch tiefer verschachteln. Das Basis-Element ist ein Tile. 100x100 Tiles ergeben ein Kartenstück. 100x100 von diesen Kartenstücken ergeben die nächste Ebene, usw. bis man bei der Map als höchste Ebene angekommen ist (ich glaube das war das Grid das weiter oben gemeint war?)

So kannst du recht einfach bestimmen, in welchem Kartenabschnitt sich ein Spieler gerade befindet, und kannst nur die Kartenstücke laden, die gerade im Sichtbereich des Spielers sind. Das Nachladen einzelner Stücke sollte relativ schnell gehen, da die einzelnen Stücke ja recht klein sind, und man kann das Laden ggf ncoh in einen Thread auslagern, damit der Spieler möglichst nichts davon merkt. Die einzelnen Abschnitte können dann zusätzlich noch gezippt oder mit einem anderen Algorithmus gepackt werden.
Man kann auch zu jedem einzelnen Abschnitt eine Prüfsumme berechnen. Betritt der Spieler einen neuen Abschnitt, kann der Client eine Anfrage an den Server stellen, ob sich dieser Abschnitt seit dem letzten Betreten verändert hat, indem die Prüfsumme verglichen wird. So kann man vermeiden die Karte unnötig oft vom Server nachzuladen.

Daß sich die Karte im Lauf der Zeit ändert sollte man in jedem Fall mit einplanen. Auch wenn 100MB nicht viel klingen - wenn 100 Spieler sich nach einem Update einloggen und die neue Karte ziehen sind das schonmal 10GB, von denen man viel hätte einsparen können.
Andere Szenarios die man bedenken sollte ist auch, wie die Map bei den Entwicklern gespeichert wird. Ggf sollen ja auch mehrere Entwickler an der Map arbeiten, ohne sich gegenseitig auf die Füße zu treten. Das geht kaum, wenn die Map nur aus einer einzigen, riesigen Datei besteht. Teilt man die Map auf, kann zumindest ein Entwickler Kontinent A und der andere Kontinent B aufbauen.
Das Datenformat sollte auch erlauben, daß die Map über Versionierungssysteme (Mercurial, Subversion, git, ...) verwaltet und von mehreren Entwicklern gleichzeitig bearbeitet werden kann, ohne daß beim Merge regelmäßig die Datei zerschossen wird oder Änderungen verloren gehen.
Dazu kann die Map auf verschiedene kleine Dateien aufgeteilt werden. Auch ein text-basiertes Format wäre (trotz der Größe) eine Überlegung wert. Das Dateiformat das die Entwickler verwenden muss ja nicht das selbe sein, das dann an die Clients geschickt wird.
Selbst wenn du alleine an dem Projekt arbeitest, bläht eine einzelne riesige Binär-Datei nur unnötig das Repository auf.

hustbaer

Unistyle schrieb:

Edit: Ich muss mich bei euch entschuldigen...

Ne, musst du nicht, ist ja nix schlimmes passiert

Also sind eigentlich nur eine Fläche von 3k*3k wirklich belegt. Diese Größe habe ich dann sofort mal in meinem Programm festgelegt und es wird fast 2GB ram dabei reserviert.
Gibt es eine Möglichkeit den Speicher nur für gesetzte Tile zu reservieren?
Der fertige Map Editor den ich mir angeschaut habe tut dies ja anscheinend und kommt bei einer gefüllten Fläche auf knapp die Hälfte.

Wurde im Prinzip schon beschrieben, aber nochmal konkreter:
Du fasst z.B. 256x256 Tiles zu einem Block zusammen. Für eine 32K*32K Welt brauchst du dann 128*128 solche Blöcke.
Also machst du ein 128128 Array aus Zeigern auf solche Blöcke.
Einträge wo ein komplett leerer Block wäre sind dabei einfach "leer" (Nullzeiger).
Und für Stellen wo nicht alles leer ist erzeugst du einen Block und speicherst den Zeiger auf diesen Block in dem 128128 Array.

Jeder Block ist dann wieder ein Array mit 256*256 Einträgen. Ein Eintrag muss dabei dann nicht immer aus 14*3 Grafiknummern bestehen, auch hier kann man wieder optimieren.
z.B. kann jeder Eintrag wieder ein Zeiger auf ein Array sein (der dann auch wieder Null ist, wenn in dieser Zelle gar nichts ist). Das Array kann dabei z.B. einfach so aufgebaut sein (1 Zeile ist ein Byte):

Etagennummer A + 192
High-Byte Grafiknummer A Layer 0
Low-Byte Grafiknummer A Layer 0
High-Byte Grafiknummer A Layer 1
Low-Byte Grafiknummer A Layer 1
High-Byte Grafiknummer A Layer 2
Low-Byte Grafiknummer A Layer 2
High-Byte Grafiknummer A Layer 3
Low-Byte Grafiknummer A Layer 3
...
Etagennummer B + 192
High-Byte Grafiknummer B Layer 0
Low-Byte Grafiknummer B Layer 0
High-Byte Grafiknummer B Layer 1
Low-Byte Grafiknummer B Layer 1
...
Etagennummer C + 192
...
...
255

Das Array fängt also immer mit einer Etagennummer + 192 an.
Dann kommen zwei Byte für eine Grafiknummer. Ob das nächste Byte eine Etagennummer oder das High-Byte einer Grafiknummer ist kannst du daran erkennen ob es >= 192 ist. Bzw. 255 für die "Ende" Markierung. Damit kannst du 49152 Grafiknummern abbilden (192*256) und 63 Etagennummern (255-192).
Und als Abschluss kommt am Ende eine 255 statt der Etagennummer.

Für eine Zelle mit nur einer Grafik #23 in Etage 1 brauchst du dann 4 Byte: 193, 0, 23, 255.

Wenn du wesentlich mehr Grafiknummern brauchst kannst du auch 3 Byte statt 2 verwenden.

Eine andere Möglichkeit wäre pro Block ein fixes Array mit 256*256 Feldern und 42 (bzw. wie viel du halt braucht) Layern, also 256*256*42*2 = 5,25 MB (2 = 2 Byte pro Grafiknummer). So hältst du aber nur die Blöcke im RAM die gerade angesehen werden. Blöcke die gerade nicht gebraucht werden komprimierst du einfach mit RLE.
RLE ist super einfach zu implementieren und läuft auch recht schnell - sollte keine schlimme Verzögerung geben selbst wenn man schnell in der Map rumscrollt. Und falls doch kannst du immer noch mit der Blockgrösse runtergehen und dafür mehr Blöcke machen.

Auf Disk speicherst du das ganze dann natürlich auch RLE komprimiert.

Das sind jetzt nur zwei von vielen vielen Möglichkeiten wie man sowas machen kann. Überleg dir selbst noch ein paar weitere, schreib dir Pro und Contra Listen. Und dann nimmst du die Lösung die am einfachsten umzusetzen ist