Imagine the game handled server sided, don't think of a visual problem.

Given a game 2D map, with size of n * n. The game contains objects (such as door, wall, a table).

Each tile position (x,y) can contain multiple objects, but this is not the catch of the question, it can even be limited to one.

The data structure for the game objects linked to the map is designed like this:

HashMap<Integer, ArrayList<GameObject>>

Where the Key integer represents X position of the object, and the value represents a list of all objects with the same X position, different Y position.

Now, I have a player location, I want to fetch a list of all 10 closest object to the player's position, within 100 tiles distance of the player.

My way of doing so:

Starting from player's position, and simply going x - 1 and x + 1 grabbing the objects lists limited to Z or until you have 10 closest objects collected, and then performing a position distance comparing search on each object. (Note, the objects lists are not sorted)

But this way is not stable, in my opinion, but I am not sure how can you solve this without changing the data stucture?

  • $\begingroup$ Usually asking for the "best" something is not a good fit here, because it is unclear what criteria you would use for determining what you consider best. $\endgroup$ – D.W. Mar 27 '20 at 2:03
  • $\begingroup$ Take a look at near neighbour search. I hope the choice of Map<Integer, List<GameObject>> (let alone HashMap<Integer, ArrayList<GameObject>>) is not from educational material. $\endgroup$ – greybeard Mar 27 '20 at 17:49

If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree indexes, such as quadtrees, R-Trees or kd-trees.


You probably can't. The principled solution is to use a data structure that supports nearest neighbor search.


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.