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?
Moderators - Reputation: 10779
Posted 17 October 2013 - 06:29 PM
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.
[Work - ArenaNet] [Epoch Language] [Scribblings] [Journal - peek into my shattered mind]
Crossbones+ - Reputation: 2565
Posted 17 October 2013 - 08:29 PM
- 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.
Crossbones+ - Reputation: 2012
Posted 18 October 2013 - 02:00 AM
Crossbones+ - Reputation: 5658
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."