Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a rectangular tile-based layout. It's your typical Cartesian system.

I would like to have a single class that handles two lookup styles

  1. Get me the set of players at position X,Y
  2. Get me the position of player with key K

My current implementation is this:

class CoordinateMap<V> {
    Map<Long,Set<V>> coords2value;
    Map<V,Long> value2coords;

    // convert (int x, int y) to long key - this is tested, works for all values -1bil to +1bil
    // My map will NOT require more than 1 bil tiles from the origin :)
    private Long keyFor(int x, int y) {
        int kx = x + 1000000000;
        int ky = y + 1000000000;
        return (long)kx | (long)ky << 32;

    // extract the x and y from the keys
    private int[] coordsFor(long k) {
        int x = (int)(k & 0xFFFFFFFF) - 1000000000;
        int y = (int)((k >>> 32) & 0xFFFFFFFF) - 1000000000;
        return new int[] { x,y };

From there, I proceed to have other methods that manipulate or access the two maps accordingly.

My question is... is there a better way to do this? Sure, I've tested my class and it works fine. And sure, something inside tells me if I want to reference the data by two different keys, I need two different maps. But I can also bet I'm not the first to run into this scenario.


share|improve this question

Have you considered using a Hilbert R-Tree? I use it for doing computation on points with CUDA on the GPU, since "flattening" out multidimensional data in this way preserves data locality and results in fewer cache misses.

share|improve this answer
Well, I just spent the last 30 minutes researching the R Tree. I do like the idea of it. I also think it could do the job. I also see a significant amount of overhead with it. The idea of "find all T within d of X" is nice. I'm debating if it would have use in the engine. I could see "Player p says <message> - notify other players within d" or "Action a happened - notify other players within d" or "For each monster, find all players within d - if found player and aggressive to player attack". Thanks for the idea, I'm going to put some thought in it. – corsiKa Feb 27 '11 at 1:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.