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?
Find data by two dynamic keys?
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.
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.
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.
- 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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
