workspace:FindNearestNeighbors

[acreol (awe)]

Currently it is really hard to find the closest - euclidean distance - parts to a given point efficiently (especially if we’re going to be having >10k part maps). It won’t suffice for us to just do linear searches over all the parts if we’re going to be needing the results many times a second. We could implement our own tree structures that will do this for us, but it would be much more efficient and convenient if they were prebuilt functions.

It would be nice to have functions similar to the already existing Region3 range queries:

FindNearestNeighbors(maxDistance,ignoreDescendantsInstance,maxParts)
FindNearestNeighborsWithIgnoreList(maxDistance,ignoreDescendantsTable,maxParts)
FindNearestNeighborsWithWhiteList(maxDistance,whitelistDescendantsTable,maxParts)

[EchoReaper]

Is there a reason you can’t use Region3? What you’re requesting is a more-restrictive Region3 except using a spherical region instead of a box.

Also, finding the nearest neighbors multiple times a second sounds like a design flaw with your game, and not a problem with Roblox’s API. You should be using something like an octree/similar to keep track of the parts you care about. You don’t need to run each second because you can cache results until you move cells.

[acreol (awe)]

@EchoReaper

Is there a reason you can’t use Region3? What you’re requesting is a more=restrictive Region3 except using a spherical region instead of a box.

This isn’t just a spherical region3, I want an array of closest neighbors returned in sorted order with a maximum distance and maximum number of parts
To achieve this with region3 you would have to find parts in region 3 with bounding box of size <maxDistance*2,maxDistance*2,maxDistance*2> and max amount of parts set to infinity. Then you would have to perform a linear search through all of those parts and find the nearest neighbors. (this solves absolutely nothing for my use case which is with finding the closest node next to the player in a huge map to pathfind from - I’m not using just Roblox default pathfinding because I want to have weighted edges)

An alternative method would be to gradually increase the size of the region 3 query and somehow binary search / use some approximation method for the query size until you get X parts but this still seems VERY messy and if they are all the same distance away then you would still have to do an n lg n sort for them so instead of having an average poly lg n + maxParts query, you now have a super hacky potentially (average approximation iterations) * poly lg n + max parts lg max parts query time

@EchoReaper

Also, finding the nearest neighbors multiple times a second sounds like a design flaw with your game

For my scenario, the game will need to know the closest node for a player and if there are 30 players and I want to update 3 times a second, thats 90 queries per second linearly on the number of nodes (Roblox can definitely get it down to lg N which would be what the octree you suggested would do)

@EchoReaper

You should be using something like an octree/similar to keep track of the parts you care about.

Thats why there is FindNearestNeighborsWithWhiteList, I would have a folder of all of the nodes that need to be searched through

@EchoReaper

You don’t need to run each second because you can cache results until you move cells.

This is forcing me to implement my own version that supports poly lg N nearest neighbor search (which is what I’m trying to avoid by requesting this feature)

Edit
I think that for most use cases - at least mine - if the distribution is uniform enough (not necessarily just the queries because then frame drop might be experienced for certain queries where the distribution is dense), you know the extents of the distribution, and you know the average amount of “parts” that will be searched through (I’m going to be calling this n), you can create an array of size n x n (or n x n x n) where each cell will have children between i*(max - min)/n and (i+1)(max-min)/n (approximately and adjusted for multiple dimensions)
So then this allows nearest neighbor, insertion, and deletion in average O(1) and only takes up O(n) memory? O.O