Sign in to follow this  

Unsure of which multidimensional nearest neighbour algorithm to use

This topic is 1114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

http://stackoverflow.com/questions/27204935/unsure-of-which-multidimensional-nearest-neighbour-algorithm-to-use

 

"

I'm currently working on a project that requires a thread to construct a queue of 30(ish) nearest processes closest to the player within a 3D environment.

All of these processes can move about the environment, as well as leave their starting nodes that they were placed in. I have considered using R trees, but due to its ludicrously high insert times, it does not seem very viable.

KD- Trees would not work, since they tend to only work for static environments.

Note also that this will be running async to the main update thread, so an atomic approach would work best.

Can someone suggest an approach?
"

 

Share this post


Link to post
Share on other sites
How many of these "processes" exist in the entire environment? What kind of thing are they? What do they do?

There are many solutions to your general problem, but finding one for your specific problem will require that you provide some detail.

Share this post


Link to post
Share on other sites

So this for an AI engine. And by player, I mean NPCs and Players. Processes are referring to advertisements.

 

I just didn't want to go into extraneous detail, since I was hoping for a general answer. (I'm seeing now that this isn't a problem where I'd end up getting a general answer)

 

The distribution is a bit interesting. It depends on the scenario, but I would imagine that most of the time advertisements are close together IE: In a kitchen there would be 6 advertisements all relating to cooking in one way or another.

 

The total number of ads is around 50K. Not all of these advertisements are dynamic. Only 20% of them move about. The rest are stationary.

 

What I am using this for is finding a collection of advertisements around the (Player/NPC) to filter through and score. I only care about those within its general proximity (Which is usually about 100 - 200); however, I don't have time to score all 200 of them. If I try, the system just goes to crap.

Share this post


Link to post
Share on other sites
Stationary points can go into a kd-tree which is selectively rebalanced when a new point is added or an old one removed. This should perform more than adequately.

Dynamic points... you have a number of options. Are they limited in range of motion? Can their trajectories be predicted? Can you confine them? etc.

Share this post


Link to post
Share on other sites

For dynamic points, basically they can travel to any point that has a viable path to it (Just a normal A* implementation). The trajectories can be predicted, but not that far before hand. If an NPC grabs food on the way to work, theres a pretty good chance that it will actually get to his job before he eats it.

 

Some could be confined. Most couldn't though. I could say that an advertisement causes strain on an NPC after he's held it for a while (That would make a really nice bounding sphere around cities and stuff). But as you'd imagine, the results would vary

Share this post


Link to post
Share on other sites

much of what you want to do is similar to determining nearby objects for rendering, except that you're doing some sort of processing other than rendering. so algos used for such things (such as the kd-tree for static objects that Apoch suggested) might apply. odds are you'll find that for most AI nearby object algos, there's an analogous graphics algo. you might even find a graphics algo that works better, substituting ads for renderables.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

This topic is 1114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this