4
\$\begingroup\$

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.

Thanks!

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – corsiKa
    Feb 27, 2011 at 1:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .