This library helps to find nearby objects in constant time O(1) instead of naive approaches that run on O(n) thanks to a binning algorithm. Ideal for collision tests (do not perform test on every object but only check with nearby objects), physics engines and AI engines (for steering behaviours such as obstacle avoidance)
I hope you find it useful! I’ve been using that algorithm in my engine ROYGBIV for a long time and am very satisfied with the results : )
Very interesting indeed.
I’m still curious if I may ask. Do you need any processing time to create any cache to prepare the binning ?
Does this handle the case where objects dynamically change position, or do you have to run any other computation to update the binning algo each time ?
This reminds me of the ANN = Approximate Nearest Neighbor algorithm
It also runs well for dynamic scenes, with minimal GC activity. I’m using some three dimensional Map to hold object representations. The first implementation was done with JS Object, then I switched to Maps, which for some reason made it much faster. So you may insert/delete objects on the run.
For instance, in this demo the cubes are being updated in the Nearby world as you shoot them.
Thanks for the hint about maps and objects, I can believe that, lot of articles comment on that. After all when it comes to large scale performance where development cost doesn’t matter, I start to see lots of wasm projects out there.
Thanks for sharing a useful tool with the community.
Unless I’m forgetting my algorithmic complexity knowledge, O(1) is constant complexity. Your table on the repo doesn’t reflect that, it reflects some kind of O(log(n)) complexity perhaps.
I mean, if you solve the spatial locality search problem like that - i think it would be awesome.
If you split the whole space into small boxes (bins), then unless you assume uniform distribution as well as constant relationtionship between number of boxes and number of objects - your O(1) claim is… a bit off
I’m all for new things and for trying out various approaches. Though.
About GC, my engine meep is super GC-aware, and the spatial index in there has 0 GC overhead, not “little” but 0, when it comes to moving things around.
You make claims that put work of others in the negative light. Personally, I don’t think that my spatial index is overall better than yours, they serve different purposes and have their advantages and disadvantages. I like your stuff, and I hope this doesn’t come off as overly negative.
The benchmarking is performed on “finding the closest object”, which is not what Nearby does.
Nearby finds nearby objects (objects within given radius) in constant time -> just a hash lookup. Since it’s open source, you can have a look at here. I indeed split the scene into uniform bins, that’s why the users specify world limit and bin size when they construct a Nearby world. The bin size also defines what is considered “nearby”.
The benchmarking does not represent the constant time, since after finding the nearby objects, you still need to iterate over them to find the closest one.
You claim that my claims put work of others in negative light. I don’t see how that’s possible. I don’t know about your work, I’ve never mentioned about other works in my README.md, or in this thread. I don’t claim it is better than others. I’ve never in fact talked about any other library. I implemented this lightweight library, I released demos and benchmarking that demonstrate its capabilities.
I feel it’s a bit missleading. If you have a collections of points in 1d, say:
and you split them into bins of size 10. Then ask the question "give me points in the closest bin to coordinate 5.3. Well, technically - it will be correct that you can just return the bin contents, and as long as you don’t do any copying or allocation for each object - it would be O(1). However, I question usefulness of such a system.
What you have created is not O(1) as soon as you started copying contents from the bin to query result.
When you say “hash lookup”, you’re also “technically” correct, in the sense that you use a Map object as a 3-d bin container and you “hash” each coordinate axis of the query. Correct term here is “fingerprint”, because hash is assumed to be constant size and allows collisions, but that’s also just an aside. The important part is - “Map” is not necessarily implemented as a “Hash Map”, which means that your “Map.get” may or may not be O(1). Incidentally, hash map is O(1) in best-case scenario, which assumes no collisions, in the worst case where all hashes collide it devolves into O(n).
Hope that’s useful.
By the way, this line here creates a new iterator.
That’s potentially… what, like 333 = 27 iterators per query? All of which are going to be garbage once you exit the function.
A tree needs to be reconstructed in that case, which triggers GC activity
If you had qualified and said “some game engines” - that would be true, sure. But you didn’t.
A tree does not, in fact, need to be reconstructed for all of the operations. You can have an expanded octree down to a certain level that would basically be a hierarchical binning structure, just like yours, except it permits object sizes greater than the bottom-level bin size. Such an approach requires no reconstruction.
If a tree does need to be reconstructed, based on your chosen implementation - you could always use a custom memory management scheme, such as an object pool, in which case you can avoid GC altogether.
So, let’s say I use an Octree in my work. Your statements say that my work is deficient in pretty serious ways, which is not necessarily true. You did not say “engine X is bad”, but you said “technology Y is deficient”, if engine X uses Y, by proxy it has a deficiency in that.
The library is lightweight, and I do think that it is pretty neat.
The inner for loops you pointed out does not make the algorithm non-O(1) since BIN_SIZE there is constant and in terms of complexity it’s negligable. As you can imagine, each loop runs 3 times, since it starts from -BIN_SIZE and goes till BIN_SIZE, increasing BIN_SIZE each time. Usually when we talk in terms of complexity, n refers the size of the data set. Since the execution time of this algorithm do not depend on the data set, it is constant time -> O(1) (it finds nearby objects in X ms. no matter if your world contains 1M objects or 100 objects, or the difference is negligable in terms of complexity).
I’m not sure if res.keys() create a new object, I don’t develop browsers myself. It could be that it returns an already created iterator too (or a cached one?). Thanks for pointing this out though. I also stated minimum amount of GC activity, not 0 GC. As declaring an integer could also trigger GC activity. 0 GC activity is quite a strong statement, and I have no internal browser knowledge to back that up. I can only guarentee the library reuses as much as it can.
I’m aware the worst case&best case implementations of a Map. However I’ll stick with the term O(1) here as benchmarking proves so. It’s browsers responsibility to come up with smart hashing algorithms.
Thanks for stating it’s neat! Maybe fix the README with a PR then : ) I’m open to contributions.
PS: map.keys() === map.keys() returns false, so it probably does not return a reusable iterator. Thanks again for pointing that out. Maybe I’ll improve that in the future.