Running out of memory when using a Hashmap for storing a psuedo infinite game world in Android

Question

Continuing from a previous question regarding infinite game worlds and coordinate data structures I have decided to go with a Hashmap. However, since I am trying this on Android I quickly ran into problems.

Here is a recap of requirements:

Psuedo-infinite 2D world of tiles. The world will be generated as explored in all 4 directions (2D) So we need something that goes to negative indexes.
Random access will be required for adjacent tiles etc.
Need to be able to retrieve tile from a specific coordinate like get(x,y)

So, here is a snip of code I used to create a hashmap of 600 * 600 tiles.

Class for each Map tile:

public class MapTile {
    public int type;

    public MapTile(int type) {
        this.type = type;
    }

    public boolean is(int type) {
        return (type==this.type);
    }
}

Test code for generating a big map:

long startTime;
long lastTime;    
map = new HashMap<Point, MapTile>();
int x;
int y;
int tile;
startTime = System.currentTimeMillis();
lastTime = startTime;
for (x=-300;x<=300;x++) {
    for (y=-300;y<=300;y++) {
        tile = (x+y)%2; //Just so I differentiate the tiles
        this.map.put(new Point(x,y), new MapTile(tile));

    }
    // Logging each row
    Log.d(this.getClass().toString(), "Generated x:" + x + " Time in ms:"+(System.currentTimeMillis() - lastTime));
    lastTime = System.currentTimeMillis();

}

So, when I run similar code in Java. It completes successfully (eats a lot of memory though). No problem.

But, when I try to do this in Android on a top-end device, it practically halts before reaching x = 190 mark (usually). Garbage collector kicks in, and endless loop ensues:

** snip **
05-26 15:52:19.565  10758-10758/com.ayk.test04        D/class com.ayk.test04.WorldMap2D: Generated x:187 Time in ms:2
05-26 15:52:19.570  10758-10758/com.ayk.test04        D/class com.ayk.test04.WorldMap2D: Generated x:188 Time in ms:6
05-26 15:52:19.575  10758-10758/com.ayk.test04        D/class com.ayk.test04.WorldMap2D: Generated x:189 Time in ms:2
05-26 15:52:19.995  10758-10760/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 66.002MB to 64.000MB
05-26 15:52:19.995  10758-10760/com.ayk.test04        D/dalvikvm: GC_CONCURRENT freed 3K, 2% free 64797K/65543K, paused 4ms+30ms, total 429ms
05-26 15:52:19.995  10758-10758/com.ayk.test04        D/dalvikvm: WAIT_FOR_CONCURRENT_GC blocked 421ms
05-26 15:52:20.335  10758-10758/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 66.002MB to 64.000MB
05-26 15:52:20.335  10758-10758/com.ayk.test04        D/dalvikvm: GC_FOR_ALLOC freed 0K, 2% free 64797K/65543K, paused 341ms, total 341ms
05-26 15:52:20.335  10758-10758/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 64.002MB to 64.000MB
05-26 15:52:20.335  10758-10758/com.ayk.test04        I/dalvikvm-heap: Grow heap (frag case) to 64.000MB for 16-byte allocation
05-26 15:52:20.695  10758-10760/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 66.002MB to 64.000MB
05-26 15:52:20.695  10758-10760/com.ayk.test04        D/dalvikvm: GC_CONCURRENT freed 0K, 2% free 64797K/65543K, paused 12ms+2ms, total 358ms
05-26 15:52:20.695  10758-10758/com.ayk.test04        D/dalvikvm: WAIT_FOR_CONCURRENT_GC blocked 332ms
** thousands of these... snip **

So, pretty much, I am stuck here.
My tiles only contain an int variable for now. This is barebones. So I understand, it is technically impossible to create a Hashmap of 50.000 or so objects? This seems a bit small for me.

Things I want to try are:

Only keeping a live region of the map in memory while offloading the rest to storage. While this may solve the memory issue, I am afraid it may cause performance problems while accessing tiles that are out of the live area.
Somebody suggested using chunks (ala Minecraft). So I keep a hashmap of hashmaps? Would it work? If so, how do I do it?
Am I completely off the target and looking at this the wrong way?

Thanks for any help you may bring in.

Update

Hello again. With your help, I have decided to go with using a database. It works much more efficiently and so far, I haven't run into any problems. For posterity, here is how it works:

The database

Working in Android, I have set up an SQLite database and table for storing each tile. At first, I decided to run an insert query each time a tile is generated. This quickly turned out to be another performance bottleneck because each INSERT took a bit over 2ms to complete, throwing a wrench into even the smallest 300x300 tile generation process. I had to utilize a multiple INSERT query which took many tiles and stored them using a single query. So, I have created an "tile buffer" where each tile is stored with their coordinates:

//A linked list of integers is good enough. 
//The first 2 are X and Y coordinates, the third one is the tile type. 
//I can add more fields if needed.
this.tileDBbuffer = new LinkedList<Integer[]>();

Here is how the buffer is filled:

void addTileBuffer(int x,int y, MapTile map_tile) {
    int maxsize = 10000;
    Integer[] tile_data;
    tile_data = new Integer[3];
    tile_data[0] = x;
    tile_data[1] = y;
    tile_data[2] = map_tile.type;
    if (this.tileDBbuffer.size()>= maxsize) {
        Log.d(this.getClass().toString(), "Buffer filled up... Saving");
        savemapbuffer();
    }
    this.tileDBbuffer.add(tile_data);
}

Once the buffer reaches a certain size (or the tile generation ends) the "savemapbuffer()" function is ran, which basically calls this function first, and then purges the buffer:

public void addTileBulk(LinkedList<Integer[]> map_tiles) {
    Integer[] tile_data = new Integer[3];

    if (db == null) db = this.getWritableDatabase();

    String sql = "INSERT INTO "+TABLE_NAME_MAP+" ("+COLUMN_NAME_MAP_X+", "+COLUMN_NAME_MAP_Y+", "+COLUMN_NAME_MAP_TILE_TYPE+") VALUES (?,?,?)";
    db.beginTransaction();
    SQLiteStatement stmt = db.compileStatement(sql);
    try {
        while (!map_tiles.isEmpty()) {
            tile_data = map_tiles.pop();
            stmt.bindLong(1,tile_data[0]);
            stmt.bindLong(2,tile_data[1]);
            stmt.bindLong(3,tile_data[2]);
            stmt.execute();
        }
        db.setTransactionSuccessful();
    } finally {
        db.endTransaction();

    }

    map_tiles.clear();
}

Hashmap in use

Soon after this, problems occurred while drawing the map. The drawing is done in another thread, so iterating through it while simultaneously generating new tiles threw lots of weird errors. After testing for a bit using "is the map busy" booleans, I ended up using a ConcurrentHashmap instead of a regular Hashmap. It worked.

Chunks

After that, I ended up needing to use "chunks" after all. It was easier to manage discrete sections of the map rather than estimating which tiles to load based on player distance. So now, each HashMap element is a fixed 2 dimensional integer array, containing tiles. I call them Cells

map = new ConcurrentHashMap<Point, MapCell>();

and a cell is something like this:

public class MapCell {
    public int x,y;
    private static int cell_size = 32;
    public MapTile[][] tiles = new MapTile[cell_size][cell_size];
}

Now. I am off to Perlin noise and map generation adventures :) See you next time.

Maybe you could create a backing file for storing your tiles, and use a `MappedByteBuffer`. Easy enough, but requires that each tile is stored with the same number of bytes -- and that you write the serialization/deserialization code for a tile. — fge, May 26 '13 at 13:05

nitegazer2003 · Answer 1 · 2013-05-26T15:10:20.747

0

You might have to go with your first option of keeping a subset in memory, especially if your game world grows much larger. To minimize the performance hit, you can consider something like creating 30x30 subtiles. At any point of time, keep the current subtile loaded while loading the 8 adjacent 30x30 subtiles in the background. When the player character transitions between subtiles it will load fast as it is already loaded, then while he is exploring the new subtile you can load the next one into memory, etc..

If you follow the subtiles strategy (with the subtile boundaries aligned to multiples of 30) you don't have to constantly check, but only when you cross a subtile boundary. Also by loading 30x30 at once you can minimize database or file access. You also don't need to use a HashMap: represent each subtile as a 30x30 array, and store the top left coordinate of the current center subtile. You should then be able to do some math to retrieve the relevant tile in the 90x90 vicinity if needed.

edited May 26 '13 at 15:10

answered May 26 '13 at 13:40

nitegazer2003

1,193
5
10

Thank you for the answer. I am not exactly sure on how to easily switch tiles from memory to storage. I am guessing I will need to use an SQL database of the entire map, then constantly check the map to see which tiles are "out of range" and remove them from the Hashmap? Also, I will probably need to keep more than just the player's whereabouts in memory, because I may need to somehow emulate things that are happening outside of view (NPC movement, enemies etc.) Would this still be useful in a scenario where I have many points of action going on, all keeping parts of the map in memory? – Aykın May 26 '13 at 14:12
Ok, one option for emulating things outside of the map is storing the last time that a particular entity is "activated", and comparing with the current time. For example, say you have a monster that moves right by 1 space every time step, and it is at (0,0). When you next access the monster to update it, you can force it to update 18 time steps, and then resolve the update as a direct movement to (18,0). If the monster's actions are dependent on the player's actions, you can store a history of the player's actions and use it as input. – nitegazer2003 May 26 '13 at 15:02
I would suggest keeping the "map" itself separate from NPCs/mobs on the map, reason being the map is not changing and doesn't require constant updating. Every NPC/mob should remember its own position. – nitegazer2003 May 26 '13 at 15:05
Yes but what about pathfinding? Map is not dependent on monster movement but monster movement is dependent on the map. – Aykın May 26 '13 at 16:17
Thank you for the help. I would upvote it if I could. I have managed to find a way to store everything in a database. I will explain the details via edit. – Aykın Jul 03 '13 at 13:01

Running out of memory when using a Hashmap for storing a psuedo infinite game world in Android

Update

1 Answers1