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.



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.

  • \$\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 '11 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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