Efficiently looking up array element based on x/y coordinates

Question

I've written a java top-down 2d game that uses generated tiles for the map. Each tile is described by a Tile class that contains its x/y coordinate.

I need to be able to get the tile a player is "on" as they move around the map. The player class knows its current x/y, and the Tile class knows the x/y it was assigned to.

Currently, all of the tiles that need to be rendered are stored in a Tile[][]. I'm fairly new to java but it doesn't seem like it's a good idea (if even possible) to simply use the x/y coordinates I want for the array indices - mainly because the tiles I'm currently rendering may not always start at 0,0. Say the player loads a saved-game when they were at 1000,1000 - I certainly wouldn't load tiles from 0,0 when I don't need them.

So, what would be the best way for me to store those coordinates?

In PHP it could be done since I know arrays don't care about indexes starting at 0:

$tiles[1000][1000] = new Tile()

But I'm not sure what the recommended method in Java is. It feels highly inefficient to have to iterate through every single tile and check the x/y for matches.

Answer 1

Honestly, what you're asking is a quite advanced topic. This sort of project that involves such large maps really can't be accomplished with a simple array. Some people will suggest using a simple offset and dynamic array, but this is extremely inefficient.

I can give you a suggestion, however. You can load the tiles in chunks. Say, each chunk is a 2D array of 32 by 32, for instance. Instead of generically loading tiles that surround the player's location, you can load the current chunk and surrounding chunks. For instance, let's say that the position 1000, 1000 falls in chunk C. You then load chunk C and all of the surrounding chunks. When you move from chunk C into chunk D, you offload the chunks that surround C, and instead load the chunks that surround chunk D

A chunk class might look something like this:

class Chunk {
    private Tile tiles[32][32];
    private Coordinate origin; // (0, 0) on this chunk's array is actually equal to origin on the map
    // Example: if the chunk started at (128, 128), then origin would be (128,128)
    ...
    public static Chunk loadChunk(...) { ... }
    ...
}

And you would need Map class to assist with locating and loading chunks:

class Map {
    public Chunk currentChunk;
    public ArrayList<Chunk> loadedChunks;
    ...
    public ArrayList<Chunk> getSurroundingChunks( Chunk ch ) {...}
    ...
}

Loading by chunks is the way that almost all games with large maps do it (minecraft is a notable example, though that game is pretty poorly programmed in general).

Of course, it is algorithmically complex, and you'll need to research it further than just reading this post. But it should give you a robust system that works for any size of map, and has been proven to work in the real world.

One of the weaknesses of this system is that unloading can be hard to predict in java, due to garbage collection. However, I'm not aware of a robust loading system that isn't at least slightly hurt by Java's garbage collector.

NOTE

This type of technique is also called lazy loading. It means that you only load what you really need into memory. It's the best technique to use for loading large amounts of predictable data because it allows you to minimize both loading time and memory consumption. Chunk-based loading is not the only kind of lazy loading, but I would go so far as to say that it is probably the best kind.