Get Nearest Object

Did some searching, but didn’t find the answer I was looking for.

Is there any way to get the nearest object with property X (or even just the nearest object) to another object without having to iterate through the entire list of objects in the scene?

If you’re not sure what I’m talking about:
http://en.wikipedia.org/wiki/Nearest_neighbor_search

I’d prefer to not have to make my own space partitioning algorithm.

Well, I made a function to do this, but just does it based on object positions (obj.getDistanceTo, if I recall). It takes an object list, or will use the current scene’s object list. If you don’t want to loop through the whole scene object list, is there any way for you to only look through a smaller list, like only a list of enemies, or a list of waypoints, for example?

EDIT: So, have you tried composing a global list (logic.enemies, for example) made up of the objects that you want to search through? You can add the objects to the list when they’re created and remove them when they’re deleted or if the reference is invalid (so you don’t have to try to ‘catch’ their deletion; you can delete them normally and then remove the reference later if it’s invalid).

I could make my own list containing only the objects I’ll need to search through, but that’s still a linear search. I’m planning on having thousands of such objects and will need to run the search several times in a row, so I’d prefer to have a faster solution.

Unfortunately this is an NP-Complete problem. In short, this means that to find the “best” target to track to, you must try every single possibility and evaluate it. So no matter how hard you try you have to do a linear search.
What Torakunsama has done for his game project (which is huge if their ever was huge. Huge in the scale of galaxies and planets) is to split his map into segments. Each section has with it a list of enemies contained in it. When hunting for the nearest enemies it only searches in the segment he is currently in, and the ones bordering it.
In this way he can have millions of potential “nearest enemies” without taking up too much processing time.
Of course, finding a way to split them into their sections is an interesting one.

Actually, I’m pretty sure it’s not NP-Complete. Using k-d trees, you can find the nearest neighbor in O(log N) time (worst case O(N)). I was just wondering if Blender had any built in features I could use to take advantage of this without having to implement my own nearest-neighbor search in Python.

A near sensor that looks for that property and sends a message when found?

@Nuances: Nope, he want’s the “nearest” not just near.

Mobius: I’m afraid you’ve gone past my limit in maths. I don’t think blender has any built in functions for this though, I think I’ll wait for monster to show up. (And, I’ll be interested to know how you proceed)

Blender doesn’t. However, there are many Python implementations already written for such tasks. The SciPy module has a kd tree class with a nearest neighbour search. You could just use that.

Remember, for anything you could possibily want to do with Python chances are there’s already a module for it. And just because Blender doesn’t ship with that module or have it as a builtin function doesn’t mean that it wont work within the BGE.

Also, make sure it’s quick enough to run in real-time. BGE doesn’t allow scripts to run over multiple frames.

@sdfgeoff - Not by default, but it’s definitely possible, especially with for-loops. I’ve implemented this as well, actually.

Could you not use generators and store the yield output in the object’s dictionary? That way the function just picks up where it left off each logic tic? Generators would probably give much tidier code than for loops as well. I’ve been meaning to toy with generators in the BGE for some time now but have yet to get round to it.

Yes, it’s possible. As you already mentioned: a space partitioning system would do it.

I’m sure you can find a relatively decent python implementation of a k-d tree (google is your friend), if you don’t want to implement your own.

Absolutely! Generators are perfect for things of that nature (I’m in love with generators, in general).

I don’t know how much experience you have with them, but you should know that it’s exactly the same in the BGE - python is python.

+1

I’ve toyed with them in Python, and they are great, but have yet to use them in the game engine. Good to know they work. I’ve got a for loops that I could improve with generators so I think it’s time to use!

Thanks for all the pointers guys. I’ll do some searching for a k-d tree module and will let you know if I get a decent implementation working.

On a side note, could someone explain what generators are? I’ve never heard of them, but they sound fairly useful.

Well, again, a simple google search should provide fairly relevant links, but in short: You can think of a generator as an extended iterator.

Here’s an example:


>>> def myGenerator(n):
...     i = 0
...     while i < n:
...         yield i 
...         i += 1
... 
>>> it = myGenerator(10)
>>> for i in it:
...     print(i)
... 
0
1
2
3
4
5
6
7
8
9
>>> it = myGenerator(2)
>>> next(it)
0
>>> next(it)
1
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

A typical sequence iterator would simply provide the next item in some predefined sequence. But a generator has to actually “generate” the next value, by running the defined generator function until it “yields” the required value - hence the yield keyword.

So, when yield is hit, the generator function is frozen - the state of it is preserved, so that on the subsequent call to next, execution can continue from where things left off, to yield the next value.

When all yield statements are cleared in the generator function, and you hit the end of the generator function (or a plain return keyword that you explicitly place on one line or another), a StopIteration exception is raised, as with all sequence iterators when they reach the end of the sequence. Typically, this exception is caught in the for loop, but if you’re calling next on an iterator manually, you need to catch it with a try-except block.

Now, I realize that this small example doesn’t really illustrate the true power of generators, but there many benefits to A) Having a function that can preserve state. B) Generating values when they’re actually needed, rather than having to waste a whole bunch of memory on really long sequences.

Interesting/relevant note: In python 3.x (which is what the BGE runs) the well known range function is actually a generator function.

There are also higher concepts lurking in the background, but I don’t want to comment on them here, because, frankly, I’m still trying to fully understand them myself - Although, I’ve learned enough to know that they are very, very powerful.

Hope this helps. :smiley: