CODEWITHSUNDEEP
java
Aelast
Aelast

Reputation: 53

Optimal data structures for a tile-based RPG In java

The game is tile-based, but the tiles are really only for terrain and path-finding purposes. Sprite movement is free-form (ie, the player can be half way through a tile).

The maps in this game are very large. At normal zoom tiles are 32*32 pixels, and maps sizes can be up 2000x2000 or larger (4 million tiles!). Currently, a map is an array of tiles, and the tile object looks like this:

public class Tile {

    public byte groundType;
    public byte featureType;
    public ArrayList<Sprite> entities;

    public Tile () {
        groundType = -1;
        featureType = -1;
        entities = null;
    }
}

Where groundType is the texture, and featureType is a map object that takes up an entire tile (such as a tree, or large rock). These types of features are quite common so I have opted to make them their own variable rather than store them in entities, which is a list of objects on the tile (items, creatures, etc). Entities are saved to a tile for performance reasons.

The problem I am having is that if entities is not initialized to null, Java runs out of heap space. But setting it to null and only initializing when something moves into the tile seems to me a bad solution. If a creature were moving across otherwise empty tiles, lists would constantly need to be initialized and set back to null. Is this not poor memory management? What would be a better solution?

Upvotes: 0

Views: 1842

Answers (1)

Neil Coffey
Neil Coffey

Reputation: 21795

  • Have a single structure (start with an ArrayList) containing all of your sprites.
  • If you're running a game loop and cycling through the sprites list, say, once very 30-50 seconds and there are up to, say, 200 sprites, you shouldn't have a performance hit from this structure per se.
  • Later on, for other purposes such as collision detection, you may well need to revise the structure of just a single ArrayList. I would suggest starting with the simple, noddyish solution to get your game logic sorted out, then optimise as necessary.
  • For your tiles, if space is a concern, then rather than having a special "Tile" object, consider packing the information for each tile into a single byte, short or int if not actually much specific information per tile is required. Remember that every Java object you create has some overhead (for the sake of argument, let's say in the order of 24-32 bytes per object depending on VM and 32 vs 64 bit processor). An array of 4 million bytes is "only" 4MB, 4 million ints "only" 16MB.
  • Another solution for your tile data, if packing a tile's specification into a single primitive isn't practical, is to declare a large ByteBuffer, with each tile's data stored at index (say) tileNo * 16 if each tile needs 16 bytes of data.
  • You could consider not actually storing all of the tiles in memory. Whether this is appropriate will depend on your game. I would say that 2000x2000 is still within the realm that you could sensibly keep the whole data in memory if each individual tile does not need much data.

If you're thinking the last couple of points defeat the whole point of an object-oriented language, then yes you're right. So you need to weigh up at what point you opt for the "extreme" solution to save heap space, or whether you can "get away with" using more memory for the sake of a better programming paradigm. Having an object per tile might use (say) in the order of a few hundred megabytes. In some environments that will be ridiculous. In others where several gigabytes are available, it might be entirely reasonable.

Upvotes: 2

Related Questions