Java: What is a good data structure for storing a coordinate map for an infinite game world?

Solution 1:

1) Instead of an array you could use a Map<Integer, Map<Integer, Tile>> or Map<Point, Tile>, which would of course allow negative indexes

2) If you know the dimensions of your world from the start you could just modify your getter to allow the API to accept negatives and [linearly] transform them into positives. So for example if your world is 100x1000 tiles and you want (-5,-100), you would have WorldMap.getTile(-5,-100) which would translate to return tileArray[x+mapWidth/2][y+mapHeight/2]; which is (45,400)

Solution 2:

I came to this thread with the same problem, but my solution was to use Map/HashMaps, but these are one dimensional.

To overcome this, instead of using a map within a map (which would be messy and very inefficient) I used a generic Pair class (not something that you'll find in the stock java library) although you could replace this with a Position class (virtually the same code, but not generic, instead integers or floats).

So when defining the map: Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

For placing tile objects onto the map I used tiles.put(new Pair(x, y), new GrassTile()); and for retrieving the object tiles.get(new Pair(x, y));.

[x/y would be any coordinate you wish to place (this allows negative coordinates without any mess!), "new GrassTile()" is just an example of placing a tile of a certain type during map creation. Obviously - as previously stated - the Pair class is replacable.]

Why not ArrayLists you may ask? Because array lists are much more linear than mapping, and in my opinion are more difficult to add and retrieve tiles, especially on 2 Dimensions.

Update:

For anyone wondering why there isn't a Pair() class in Java, here's an explanation.

Solution 3:

Trees, Quad Trees, Binary trees, red and black trees - and all other kinds of trees are USELESS for you (unless you are planning to have a map with a huge forest).

Specialized data structures have their specific uses. Unless you can come up with a good reason why your game needs a spatial index, don't build one. If your typical scenario is "iterate over the visible area, find out what tile is visible at each of the squares", then you need a structure that gives you a quick, random, access to a value stored under a specific key. Such structure is a HashMap (what PHP uses is a kind of a LinkedHashMap, but you were probably not using the "linked" part).

You need to follow xephox's advice (and give him the credit), and that is:

• make a class that describes a location (Pair, Location, Point, whatever);
• make all the fields (probably x and y) final. It is important that a location itself cannot change (it will make your life MUCH easier);
• generate equals and hashcode methods (every IDE will help you with that. Remember that the implementations MUST use both x and y - a wizard in your IDE will help you);
• your map will be: Map map = new HashMap();

The best thing: if you keep using the Map interface, you will not be locked out, and you will be able to make a lot of improvements. Like wrapping the HashMap into an object that creates parts of the map using some algorithmic techniques.

Solution 4:

I'm not an expert in game programming, but if arrays are OK, you could simply translate your coordinates from (-x, +x) to (0, 2x) (idem for the y axis).

Or if you're used to associative arrays like PHP has, the use the corresponding structure in Java, which is a Map (HashMap would be OK) : define a Coordinate class with appropriate equals and hashCode methods, and use a HashMap<Coordinate>. Making Coordinate immutable makes the code more robust, and allows caching the hashCode.