Java: What is a good data structure for storing a coordinate map for an infinite game world?
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
Answer
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)