• Create Account

# Find data by two dynamic keys?

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1stein102  Members   -  Reputation: 414

Like
0Likes
Like

Posted 17 October 2013 - 06:19 PM

I need to find if my player is adjacent to any NPCs in my game and I'm having trouble getting it to work. It was easy enough to do for resource nodes, because their positions would be static. However, I'm not sure how to do it for an NPC with a dynamic position. I had my resource nodes stored in a multidimensional array because the position was always static and could simply store them with [x][y], but with NPCs being dynamic, I'm storing them in an arrayList using their ID as an index. What would be a good way to find an NPC based on it's position? Is there a good algorithm for this?

### #2ApochPiQ  Moderators   -  Reputation: 10779

Like
3Likes
Like

Posted 17 October 2013 - 06:29 PM

Unless you're talking about hundreds of thousands of NPCs being queried tens of thousands of times every second, just loop over the array and look for NPCs in range. Worry about more complex options if that's proven to be too slow.

Another option would be to use a spatial subdivision scheme, e.g. where all the NPCs from (0,0) to (100,100) are stored in one array, everyone from (100,100)-(200,200) in a second, and so on (plus of course all the corners so you have a grid of arrays, if that makes sense).

There are more sophisticated data structures for spatial subdivision but they are quite likely overkill.
Maker of Machinery

### #3Nypyren  Crossbones+   -  Reputation: 2565

Like
0Likes
Like

Posted 17 October 2013 - 08:29 PM

One possible technique which can be useful in some situations (excessive amounts of NPCs to test in a sparse area with a commonly used scanning distance):

- Come up with a hash generation function that takes your positions as inputs and snaps them to a grid with spacing equal to or greater than the distance you want to query, then hashes the x,y,(z) coordinates together.
- Place all NPCs you care about into a multimap using that hash function.
- When you want to find NPC(s), your broad-phase is to generate the hash codes of the handful of cells near the location that you want to query, then look up those cells in the multimap. Your narrow-phase is to do your more accurate point-to-point distance check.

Edited by Nypyren, 17 October 2013 - 08:31 PM.

### #4LorenzoGatti  Crossbones+   -  Reputation: 2012

Like
0Likes
Like

Posted 18 October 2013 - 02:00 AM

Consider indexing NPCs and other things by location: (X,Y) pair to NPC id or pointer/reference. This makes finding adjacent NPCs very cheap (no scanning, only walking from the query location to computed adjacent locations to their content). In Java, HashMap would be an obvious choice, perfectly symmetrical with an HashMap similar to what you are currently using. To move a Npc x to a new location p: Location oldLocation= npcLocations.get(x) locationNpcs.remove(oldLocation) locationNpcs.put(p,x) npcLocations.put(x,p) You might have a Set instead of zero or one Npc in each location, introducing a harmless level of indirection.
Produci, consuma, crepa

### #5Bacterius  Crossbones+   -  Reputation: 5658

Like
0Likes
Like

Posted 18 October 2013 - 05:39 AM

And if you really want "the" algorithm - which is probably overkill unless you have many, many NPC's, as Apoch said, and is mostly useless in any case on a discrete map where you can only have integer positions and are looking for immediate neighbours - what you're looking for is a nearest-neighbour query algorithm (also known as kNN algorithms) and a good data structure which achieves this is a point kD-tree, though there are many others. Just posting this in case someone comes across this topic and does need that info.

"The best comment is a deleted comment."

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS