Data structures for loading huge tilemaps

Game Play & Game Design
#1

Hey guys! Been a lurker here for a while, I quite recently took up game development as a hobby, and it kind of turned into a passion. I’m a second-year CS&Systems Design student in uni.

I’ve been reading up on a lot of material for the past six or so months and I decided to make my own game from the ground-up - a pixel-art old school 2D RPG (with a lot of modern elements in combat/mechanics). Main reason for doing my own engine is

  1. I think a challenge is incredibly fun
  2. I want and love to learn!

I’ve come quite long already and have got many systems I’m happy with (for now) in place for most of the things you’d want out of a basic 2D-engine in place. My next step is allowing my engine to load huge tile-maps with multiple layers in an efficient way.

I’ve written my own XML-parser for Tiled-maps that can handle everything except for polygon-colission (as of yet). The way I’m doing it now is just loading the entire tilemap into arrays and only updating/rendering my players viewPort + x.

My question is if you have any guidance on an implementation for loading my arrays from chunks of a HUGE tileMap into the relevant data structures for collission-checking/updating/rendering based on my player’s location in the world.

My thought process right now is it would be incredibly useful if I wouldn’t have to divide my tileMap-file into many small chunks, but maybe get away with eight chunks on hard-storage, and load the entire big chunk with its data into I guess a treeMap? This might consume 1GB of memory at most, and I think I’m fine with that right now. (If I’d need to trim that down I could just make sure the solution is scalable and divide the map into more chunks later on).

Then based on X,Y I would load in a few extra screens surrounding the player into my arrays from the treeMap and only update/render relevant screens, with x screens away updating less frequently etc.

The way I’m thinking about it right now is (simplified):

Say I have a TileMap, 2000x3000 tiles, divided into
8/16 “worldChunks”.

Loading it into my game I would:

  1. Load one of X “big-chunks” into my TreeMap (“WorldMap”).

  2. Based on player X,Y - calculate an area of X screens surrounding the player and
    load into memory.

  3. When I get close to an edge, save the state of npcs/mobs/objects on these screens

  4. Load next X screens into memory, free up previous chunks for GC to collect

Is this a reasonable approach to solving the problem? Do you have any useful tips/guidance or other ideas for me to think about? Any warnings of an approach like this?

Basically, any tips or inspiration for a scalable solution here would be greatly appreciated!

#2

Nice :slight_smile: gamedev is good choice if you are looking for challenge. Personally I would not recommend RPG as first choice. It’s attractive vision to create own RPG but usually it ends up as a failure if you don’t have enough experience. One of the hardest genre.

Could you post some screenshots of this map?

2000x3000 tiles takes 1GB? How xD

Your approach is ok in general. That’s how seamless spaces works. Save chunk state only when chunk is going down. Not when new one is rising up.

I am using zones instead of openworld in my game so it’s much easier. I’ve used something similar to this chunks solution for rendering

#3

For really large maps (much more than 2000x3000, because that’s not very much, actually), you might run into problems when traversing between two of your big “world chunks”, because you would have to load both of them. What about having a variable number of smaller chunks with a fixed size that are lightweight to load, update and render at the same time?
IIRC Minecraft also has very small chunks compared to the world size.

Cheers

#4

Thanks for your replies!

What I meant with 1gb ram is that I can live with that kind of memory-commitment, not that my actual tile map would be that in its final shape.

I know it’s nothing extreme at all (though to a one man-venture I think it’s enough work!) however I believe something like 2000x3000 is a size I can actually manage and the world I create could be something interesting and fun for the player to be in - more is of course possible but not realistic.

However - I would like my solution to be scalable so I can just add another 2000x3000 tileMap in case I’d feel like it - I guess maybe I could look into a zone-based system as well…

What I’m really after is minimizing the work I have to do when managing map creating, do a lot of iteration by trial and error and trade system resources (memory) for creative output when it comes to designing a static/fixed RPG-world and at the same time making sure it can scale. I guess loading screens could work in case the bigger chunks become a problem.

How do people go about this in larger 2D games - many small chunks? Any solution where you just load the entire map in a tree and fill data structures as you go?

#5

Yeah. Many small chunks are much more flexible.

This one may be helpful:
https://minecraft.gamepedia.com/Chunk

#6

My tile-based system is as follows:
TileMap, which is composed of Regions (these are the container files stored on disk). The regions themselves contain chunks, which contain tiles. Regions exist to reduce the amount of files on disk but they don’t really affect anything in the engine as far as what you can see.
Chunks are used to do a quick check of what is/isn’t on screen before getting down to a per-tile basis. Creating a huge map will store a ton of chunk objects that have a marker specifying that they need to be loaded from the region files, so until they are loaded their footprint is tiny. This is how I implemented map streaming.
Each chunk is compressed into a string which is essentially a sequence of tile IDs stored on a per-line basis (so you go from x=0 -> x=32, and then down by 1, then repeat). The compression algorithm can tell if there are repeating IDs and it reduces it down, and it can pick up repetition across multiple lines.