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

Question

I am used to coding in PHP but I am not really proficient with Java and this has been a problem for some time now. I expect it to be a fairly easy solution, however I cannot find any good example code any way I search it, so here goes:

I am programming a game that takes place in a 2d random generated infinite world on a tile based map (nitpicking: I know it will not be truly infinite. I just expect the world to be quite large). The usual approach of map[x][y] multidimensional array started out as a basic idea, but since Java does not provide a way for non-integer (i.e. negative) array key shenanigans like PHP does, I cannot properly have a (-x,+x,-y,+y) coordinate system with array keys.

I need to be able to find the objects on a tile at a specific x,y coordinate as well as finding "adjacent tiles" of a certain tile. (Trivial if I can getObjectAt(x,y), I can get(x+1,y) and so on)

I have read about quad trees and R-trees and the like. The concept is exciting, however I haven't seen any good, simple example implementation in Java. And besides I am not really sure if that is what I need exactly.

Any advice is welcome

Thank you

Facility

I don't know what your target platform is but after coding 2 or 3 prototypes for tilebased engines with Java (aiming applets) I have an fact to keep in mind. Arrays have the benefit that you don't have to store the indizes. Storing 2 int for each tile (or one longer String) can produce an large amount of memory usage for nothing.... so the Map<Integer or String, Tile> approach should only be used if there is no other possible way or memory does not matter. – Tye

@idefix I am targeting Android. So, I have to keep good track of memory. Fortunately I will focus on only high-end devices to run into less performance problems. Nevertheless, if it comes to using so much memory, I may consider caching some of it on the drive. I really need the coordinates. – Supplicant

Should the map be generated on initialization or does it generate whenever the player comes near it (so the level file grows while playing)? – Carrousel

Answer 1

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.

Isar

Answer 2

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)

Unbonnet

Thank you for the advice. The dimensions are not determined, so your 2nd method is not very usable for this situation. However, using a Map looks like an option. But I am a bit confused. What difference would using a Map vs Hashmap make? – Supplicant

@Ayk, Map is the interface, HashMap is an implementation, i.e. a class. A HashMap is a Map. Try googling for what an interface in java is. – Unbonnet

Answer 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.

Monocoque

Answer 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.

Ridgley

@jb-nizet Unfortunately since the boundries of the world are not known, I can't use a limited array. I will look into the Hashmap. Thanks for the advice – Supplicant

Answer 5

you could try a QuadTree (nice example here: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ )

Stralsund

Answer 6

I wrote a couple of experimental spare data structures in Java that you might be interested in.

The most interesting one was the Octreap which is what I believe is a completely novel cross between a Treap and an Octree, which had the following features:

• 60 bit world co-ordinates (aprox 1,000,000 * 1,000,000 * 1,000,000 grid)
• Negative co-ordinates supported
• Empty space requires no storage (supports highly sparse worlds)
• Compresses volumes of identical cells (e.g. large blocks of the same material would get stored efficiently)
• O(log n) for reads and writes

Knawel

Answer 7

How about dividing your map into chunks (yes, Minecraft fans, I know where this is used as well :P)? So you have two coordinate systems, both with the same origin:

• x/y coordinates
• c1/c2 chunk coordinates

A chunk is always a fixed size of real world coordinate (say 128x128). Then you have a class Chunk where you have a fixed array (128x128) with all the information for every pixel. And you store your chunks into a Map<ChunkCoordinates, Chunk> as was already explained by others. I would recommend a HashMap.

Whenever your player is in a certain region, the neccessary chunks are loaded from the map and then you can access the fixed size array in there. If the chunk knows, where it is placed in x/y coordinates, you can even have some support function like Pixel Chunk#getPixel(long x, long y) or so...

Btw: This also gives you an easy way to postpone generation of the whole world until it is really needed: At start, nothing is generated and as soon as a Chunk is accessed in the map, that is not yet generated, you can just generate it then. Or you could fill it up at startup if that's easier for you. (filling an infinite world will take a long time though, even if it is pseudo infinite)

Carrousel

Answer 8

You probably want to use an implementation of Map. HashMap, SortedMap, etc depending on how much data you intend to store and your access patterns (Sorted Map is very good for sequential access, HashMap is better for random access).

You can either use two-dimensional Maps or munge your 2-d indeces into a key for a 1-d Map.

Dzungaria

Most of the time, I will need to access a group of tiles near a specific coordinate probably far away from any edge of the map. I don't think this is sequential. Am I correct? What would be best of Map, Hashmap or Sortedmap? – Supplicant

Answer 9

This is two separate questions: how to simulate negative array indicies so you can have an "infinite" map, and how to store tiles efficiently.

On the first question, one hack would be to maintain four separate matricies (matrixes?), one for each quadrant. Then all the indexes can be positive.

On the second question, you need a sparse map. One not-very-efficient way is to have a hashmap of hashmaps. In fact, that could solve the first problem as well:

HashMap<String, HashMap> x = new HashMap()
HashMap<String, Tile> y = new HashMap()

// get the tile at coordinates 1,2
Tile myTile = x.get("1").get("2");

// this would work as well
myTile = x.get("-1").get("-2");

You could do your own Map implementation that took integers as keys and was much, much more efficient.

Fillmore

@user237815 I see. The 4 matrices idea is intrigueing but I don't think it would be easy to calculate distances etc. I think the Hashmap idea is getting somewhere. How unefficient is it to use hashmap of hashmaps ? – Supplicant

You could calculate distances just by flipping the sign of the appropriate dimensions in each quadrant and using Pythagoras. Hashmap of hashmaps would have a memory overhead of at least two objects per cell. It would have a processor overhead of having to calculate two hashcodes and then traverse two linked lists. If your data is of moderate size the overhead isn't bad. – Fillmore

Answer 10

If you want to be really fast and really scalable definitely go with a Sparse Octree.

http://en.wikipedia.org/wiki/Octree

I am not aware of any implementations in Java, but it is trivial. Just store in a single byte a bitfield for which nodes are currently linked and use a linked list to keep those references (for each Octree-node a separate list of max. 8 entries).

Rabbitry

Wouldn't that be a Quadtree for a 2d map of the world's surface? – Phonolite

Of course! If its only 2D its so much easier to partition the search-space. e.g. quadtree or binary space partitioning. – Rabbitry

This looks like a good structure. As for implementing it, I don't even know where to start. I am just beginning to understand how Java data structures work. Thank you for the advice – Supplicant

@Ayk: don't implement any kind of tree! All the answers suggesting different kinds of trees are insane. The best answer is by xephox (and that is a HashMap<Point, Tile>). Trees have specific – Monocoque

Answer 11

The hashmap style solutions are terrible for adjacency calculations, they require an iteration of the entire dataset.

Something like a quadtree or octree is perfect EXCEPT that it's not infinite, it's an arbitrary size (world of difference there).

However if you think about it, an ArrayList isn't infinite, it's just an arbitrary size that grows, right?

So a quadtree is sparce and pretty good ad adjacency calculations, except for the "infinite" provision it's perfect. Why not just use one of those sized to 100x what you think you might need (it's sparse, not really a big deal). If you ever get to the point where you are near the edge, allocate a new quadtree that is much bigger.

I believe if you are careful (you may have to implement your own quadtree) you can "upgrade" the quadtree with very little effort and no copying--it should be simply a matter of prefixing all your existing addresses with some bits (the addresses are in binary, quadtrees each bit represents dividing the existing universe in half in one dimension or the other).

Mesoglea

Answer 12

Use the Pair class from apache commons. It has a left and a right value, implement x and y coordinate as left/right. Each Pair is also hashed based on its left and right value respectively.

You could then use a HashSet of Pairs (Set<<Pair<Integer, Integer>>) called coordinates. In this way, each coordinate will be unique, as it should be. If you want to link any Object to a coordinate, you can then use a HashMap of the coordinates with their relevant objects.

Stilliform