I need to find the k nearest actors of a specific type efficiently in Blueprints. In this specific demo, I’m trying to have each bird find the k birds nearest to its location. Of course this is an O(N) operation for each bird, so it’s O(N^2) for all birds, and must be executed quite frequently. I would like for this to work up to quite large N, but I’m not sure how to do this efficiently in Blueprints. Given that the birds exist in a physical space, maybe it’s more effective to check actors within a local volume, filter to birds, and scale that volume as necessary (up to some cutoff distance)?
Open to tips and suggestions other than “Do this in C++”. I agree that this is something better done in C++, but for the purposes of my task, this has to be done in Blueprints. This isn’t a commercial product, so “best I can get” is acceptable, however it is a learning project, so I would like to be as efficient as possible within these constraints so that I might learn useful techniques for commercial work.
The most obvious thing to try is a collision sphere on each bird, and collecting the overlapping birds.
But, that’s hideously inefficient, because once we know bird A is near B, C and D then we also know that C, D and E are near A. So we’re wasting time.
I see from your terminology, that you’re already wondering about nearest neighbor algorithms. I think computing something from a central point once for all birds would be the best way forward.
Something where you only have to consider each pair once, and build some sort of proximity data structure. Then the bird can each be give a list of neighbors each time this code runs. That brings the order of complexity down to NC2, which is better than N^2
I would try the overlap method anyway, because the engine code is pretty efficient, and it may still win over a central process.
Yes, (N^2)/2 is the same time complexity as N^2. Time complexity analysis looks at the shape of the scaling law, not additive or multiplicative constants. Helpful explainer:
( I don’t see any plugins, even for Btree ).