Sign in to follow this  
Thevenin

Reducing RAM consumption for Tile-Based map.

Recommended Posts

Pictures two tile-based RPG games that have equally sized (continous [No loading]) game worlds. One game uses 42MB of RAM to store the map data. The other uses 7MB of RAM to store the map data. Both worlds are huge, 2000x2000 x 11 layers. My approach (Bad, 42MB): -> Create a giagantic linear array, and store all the data in it. Their approach (Good, 7MB): -> "We'll never tell you, buahahahah!" Loading only one layer at a time could do it, but at least 5 layers have to be loaded for multi-story buildings and mountains to be drawn. Perhaps storing the ground floor as a linear array, and the other floors as (X,Y,Tile#) structures? I'm not sure, please help! [depressed]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I dunno if this is better, but i know when i was experimenting with a tile engine, i used a multidimensional array, so it was like X,Y, Tile#, Flag. I used the flags to determin if it was walkable or it had treasure or something. it seemed to work out very well..dunno how much ram it took up thou...

Share this post


Link to post
Share on other sites
There are a few options here. One is using metatiles, which if your maps have repetitive tile data can cut down on the space you use by a huge amount. If you use a 2x2 metatile system, you would replace your original map with one that was (width/2)x(height/2) instead. Right there you have close to a 4x memory savings. Now you just need to create the metatiles. So let's say your original map which was 6x2 looks like this (tiles go from 0-9):

016901
501250

Your new metatile map would be a 3x1 map, looking like this:

010

Metatile 0 would have the following information:

01
50

Metatile 1 would have the following information:

69
12

So as you can see, if the maps have a lot of repitition (and empty space is very repetitive), then you can get a massive space savings. You can use different metatile sizes as well, such as 4x4 or even 8x8 if you have large areas of repitition.

Edit: Also, of course they could be loading the areas that they need dynamically from disk in a seperate thread. But it's more likely they are using a metatile system.

Share this post


Link to post
Share on other sites
For a meta tile system... how does that work if I have several different types of tiles?

eg... building a metatile consisting of 3x3, I'd have to have the map as a linear array of longs (Instead of characters), because....

(150 different tiles)^(3*3) = More possilbilities than can fit on a char.

Edit: Perhaps I don't understand the metatile system, brb doing a google search. xD

Double Edit: No good results off google [bawling]. My map has ALOT of areas that are just grass or water, metatiles is sounding very promising, but I need a better explanation of it, because I get confused on how it would be used when you have more than 5 different types of tiles... lol

Share this post


Link to post
Share on other sites
How densly populated are the higher layers?
Doing some maths tells me that you're simply using a gigantic char array for the whole thing. I would say that both using the meta-tile approach outlined above and for all but the base layer use a collection of
struct SomeNeatoName
{
short x,y;
char tile;
};

that will save space assuming that <= ~1/5 of all tiles in that layer are occupied.

Share this post


Link to post
Share on other sites
Another approach is to treat the world as a collection of separate regions, each region having a location and size in tile coordinates, and each having a rectangular array of tiles.

Your base would be one big region and floors of buildings would be smaller regions stacked on top. Some simple maths would allow you to work out which region the player would be in at any given time. You wouldn't have to worry about tiles that are of different sizes either.

For instance, say your world is 100x100 tiles in size, and 10 tiles high. Most everything is at ground level, but you have one building starting at tile 50,50 that is 10x10 tiles square and 5 tiles high. Here's how you could define this:

Region 1: (main world)
x,y = 0,0
w,h = 100,100
Tiles[100][100]

Region 2: (building 2nd storey [first storey is in region 1] )
x,y = 50,50
w,h = 10,10
Tiles[10][10]

Region 3: (building 3rd storey)
x,y = 50,50
w,h = 10,10
Tiles[10][10]

etc.

Hopefully you get the idea. The naive approach would be to create ten 100x100 arrays to hold the tiles, which would require storage for 100,000 tiles. The above approach would use a one 100x100 array and four 10x10 arrays, for a storage requirement of 10,400 tiles.

Share this post


Link to post
Share on other sites
Yes, I'd go for the "blocks" approach. Have a 2d array of "blocks", then have each block contain a 100x100 tilemap or something.

If a given block is *entirely* empty, you can just omit it, putting a null in there or something. That means that those areas won't get stored at all.

Likewise, you could, in principle, dynamically load / save blocks of the tilemap, but that may prove unnecessary if your map is sufficiently sparse.

Mark

Share this post


Link to post
Share on other sites
Ýeah, I'd say storing objects such as buildings etc. in a separate list sounds like a good idea. Also, you shouldn't have five layers just for multi-story buildings, I'd try to find a different way to do that if I were you. 11 Layers sounds pretty insane to me, at least.

Share this post


Link to post
Share on other sites
It's late, so I admit that this may be a realy bad idea, but:

Could you use a quadtree to store rectangles with the same tile(s) in them, where each child node could override whatever the current tile setting is?

It seems like that would be an efficient way to store your data and still have something that's easy/fast to render. One problem I can think of is that it might be tricky to write an algorithm that automatically creates or optimizes the tree for you in your level editor...

If you have a bunch of prefabricated (That is, common building designs are cloned all over the place), you might want to just make a big list of those common pieces and have your map only store those. A *LOT* of games, both old and new, 2D and 3D use this technique. Remember the original Lemmings game? Their levels were made out of pure prefabs (at least on disc). I didn't figure out if they expanded all of those out into a big pixel grid when the level loaded, or figured out what sections you borrowed through in a big diff table or what.

Share this post


Link to post
Share on other sites
The need for 11 layers confuses me, unless you mean layers as in the player can wak up a staircase onto another layer and move about.

Anyways, the MetaTiles would probably work well with dynamic loading. Imagine.
You have the world split up into a 16x16 grid, but you only have a 3x3 part of the world loaded at any time. One square on this grid is 256x256 of normal tiles (I assume stored in a char, or 4 layers worth stored in an int). When the player moves between (0,128) on one grid onto (255,128) on the grid to the left, the 3 right most grid blocks are discarded and the 3 leftmost are loaded. By drawing the grid blocks together, the player never relaly notices these boundaries (unless you lock up to load), and your memory usage would be 576k for a layer's worth of data, or 6.2 megs for 11 layers worth. Sure sounds like 7 megabytes, doesn't it?

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
Loading only one layer at a time could do it, but at least 5 layers have to be loaded for multi-story buildings and mountains to be drawn.

Perhaps storing the ground floor as a linear array, and the other floors as (X,Y,Tile#) structures? I'm not sure, please help! [depressed]

Might try:
* divide the full area into smaller blocks, each storing their respective part of the 11 layers
* for the chunks which don't have to be shown, compress the data (even something as simple as RLE method used by .tga files can work... if the world has many places where number of layers is not utilized, or they use the same tile type, the savings should be huge)

this way you only need to have at most 4 screens worth of data in uncompressed form (9 if you want to keep amount of unpacking down) ... everything else can be packed and just sitting there waiting for its 15 minutes of fame ;s

Share this post


Link to post
Share on other sites
Just to clarify here: you are talking about 2000x2000 TILES and not 2000x2000 PIXELS?

Anyway, here's a graphical representation of metatiles I just did on my lunchbreak: http://students.uww.edu/gilardijd05/metatiles.jpg

Share this post


Link to post
Share on other sites
Quote:
Original post by Funkapotamus
Anyway, here's a graphical representation of metatiles I just did on my lunchbreak: http://students.uww.edu/gilardijd05/metatiles.jpg


Cute. (Guys can say 'cute' right? [looksaround] )

And yes, 2000x2000 tiles, but there are some 150 different types of tiles....

@Inmate2993
Yes, the layers are merly floors on different elevations.

@DigitalDelusion
Yes, the dungeons && upper floors are not dense, << 1/5.

@default
I'm still deciding which approach to use. [smile]

[Edited by - Thevenin on June 22, 2005 1:38:11 PM]

Share this post


Link to post
Share on other sites
Create an array to store your 'working' tiles that is 4x the size of the display. ie, if you display 15x10 tiles at a time, make it 30 x 20 and, as the player moves, use spare cycles to pre-fetch the map in the direction he's moving. You should always have enough buffer room in the array to allow time to finish loading the off-screen tiles before they need to be displayed.

~Pax

Share this post


Link to post
Share on other sites
Well... you've probably already covered this, but if the layers after the first don't completely cover the area, you can save memory by using linked lists for the tiles..

Another idea similar to metatiles (I think), is to use an RLE method. Run-length encoding is the compression style that PCX files use.. it's very simple. Basically, you could use RLE but on a tile basis instead of pixels. That way you can store one tile and then a number indicating how many of these exact tiles follow in a row. (Whoops.. I just noticed somebody else mentioned the RLE method).

Of course, if the layers are different floors, and you can't see from one floor to the next, you could load each layer as you move to the corresponding floor.

Another probably obvious thing (for the graphics) is to use tile flipping by X and Y; while it may not save that much room, it may be worth a try.

Another idea.. use bigger tiles. Fewer tiles will save memory.

For graphics.. if you happen to have any tiles that are a solid color, you could save the room by doing a floodfill instead of storing the tile... that's not really the map data structures though, more the graphics..

Still another option would be to do some sort of global/spatial compression on the map.. as you move from part of the map to another, you decompress during run time...

Just try to think outside the box and I'm sure you'll come up with some sort of interesting way in accomplishing your goal.

Share this post


Link to post
Share on other sites
I've been out for two years due to me serving a mission, so I hope that this helps! A bit rusty though...

An idea:

Use the metatile for general background, such as grass, forest, whatever that you need. For more detail, such as caves, towns on world, etc, set up a trigger list that stores different areas that requires more detail. When you get into that area, it loads up the tiles and "overlays" the metatile, therby saving memory. So you have two main types of tiles, the metatiles, and detail tiles. But if you have many detail tiles, this might not be a practical approach...

Just an suggestion...

Share this post


Link to post
Share on other sites
a method I have not yet seen suggested is to simply store the *unique* tile information, then just use pointers. A pointer is only 4 bytes long, no matter what it points to, whereas a tile structure could easily be 8 times that. Your milage will vary dependant on how many duplicate tiles there are, and how large the tile structures are. This may not work at all in your situation, but I thought I'd suggest it.

Share this post


Link to post
Share on other sites
Quote:
Original post by PaxNoctis
Create an array to store your 'working' tiles that is 4x the size of the display. ie, if you display 15x10 tiles at a time, make it 30 x 20 and, as the player moves, use spare cycles to pre-fetch the map in the direction he's moving. You should always have enough buffer room in the array to allow time to finish loading the off-screen tiles before they need to be displayed.
~Pax


Wouldn't this require threads? [caution]

Or can 2MB worth of data be loaded quick enough?

Share this post


Link to post
Share on other sites
I would give each layer a different tile 'map'. Each tile with different, but fixed dimensions..
Where there is collision detection involved, there would be much more data needed than background tiles. If one layer only needs 16 tile types, than 1 byte in an array can hold the info of .. 16 tiles! (with some logic calculations) .. but it's a bit freaked, ok i know.

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
Or can 2MB worth of data be loaded quick enough?

You don't need to load it all in one go. Taken to extreme, you can reduce it to a point where when the player moves one tile left/right you only fetch single "new" column worth of data from respective direction (so at worst you just load single column and single row when player moves diagonally)

Share this post


Link to post
Share on other sites
Quote:
Original post by tolaris
Taken to extreme, you can reduce it to a point where when the player moves one tile left/right you only fetch single "new" column worth of data from respective direction...


I would have thought the seek time would be the greatest slowdown factor.

eg...

Loading 1 KB = 10ms
Loading 1 MB = 11ms.

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
I would have thought the seek time would be the greatest slowdown factor.

eg...

Loading 1 KB = 10ms
Loading 1 MB = 11ms.

Well, that's something for profiling to find out (given the O/S is likely to add couple cents here with the caching and whatnot) ... but if it turns out you can load 2 MB in total of (10 ms access + relatively insignificant extra time needed for data read) then there's hardly problem with fetching data for whole next tile fast enough in one go, isn't it? ^^

Share this post


Link to post
Share on other sites
been a while for me to but alot of the methods mentioned above are good

first off dont use a 2000x2000 tile map unless you can help it even if you are only using and 8bit varible to store your layer of tile data you still have to looking at about 4mb of data per-layer use a base layer using

correct me if i'm wrong but the old snes only had like 5 layers and 2 layers to background 2 sprites and 1 to above effects and they were able to get some really kick ass stuff of that. you need to rethink your system alittle bit.

*you should only need 1-2 layers for your base
*add a structure that contains building data with all the floors and stuff
and put that in a linked list and then draw that in

*when you say layers do you mean levels because from the what you are saying thats seems to describe what you are doing more

*i'm sure your little compition with 7mb ram is using all those tricks mentioned above

splitting the map in to section and loading off the sections as the play nears them is a good plan loading a diffrent section or area when you go up a floor will help with design and memory usage and give you more levels up and down

using a simple RLE compression well help greatly

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
Quote:
Original post by tolaris
Taken to extreme, you can reduce it to a point where when the player moves one tile left/right you only fetch single "new" column worth of data from respective direction...


I would have thought the seek time would be the greatest slowdown factor.

eg...

Loading 1 KB = 10ms
Loading 1 MB = 11ms.



And it is! Take a game like Ultima VII, for example. Smardrive made a huge performance improvement, probably by avoiding unecessary disk accesses.

However, if the world is, say 10000x10000, why not store a (for ex.) 200x200 region, and let's take a 20x20 visible area(I'm making these numbers up).

Now, whenever the player moves, start "shifting" and prefetching tiles, preferably in a "lazy" way.

Since you've got a good buffer, you don't need to start fetching tiles right away. You can give your player a small room to move about before getting crazy with tile loading. Might even have a special code to handle the worst case: a player running non-stop in a single direction. And this tile loading could be backgrounded, you could have something to predict player movement and so on.

Those ideas are untested, but I've been thinking about it for some time now. It seems it would work just fine for tiles, but NPCs would give you character some trouble.

My advice? Download Exult and play with it. It's a engine to replace the aging(read: impossible to run today) and proprietary Ultima VII engine. Then look at the source, you might get some good pointers.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this