{"id":"nightcycle/quad-tree","name":"quad-tree","scope":"nightcycle","platform":"roblox","description":"Speedy implementation of a 2D binary tree","version":"0.1.2","latest":"0.1.2","versions":["0.1.0","0.1.1","0.1.2"],"license":"Apache-2.0","licenseRating":"safe","licenseCaveats":["Modified files must carry a notice of changes. If the package ships a NOTICE file, its attributions must be preserved.","License identified from the packaged LICENSE file; the manifest declared none."],"licenseVerified":true,"dependencies":{"boatbomber/hashlib":{"version":"^1.0.0","alias":"HashUtil"},"nightcycle/maid":{"version":"^2.0.0","alias":"Maid"},"sleitnick/octo-tree":{"version":"^0.3.1","alias":"Octree"}},"integrity":"2c4f27199b3787389d119bc7d9b4b5591925dc8c79da3c241a01ed8d68968c8d","likes":0,"downloads":0,"install":"forest install nightcycle/quad-tree","url":"https://forest.dev/p/roblox/nightcycle/quad-tree","files":"https://api.forest.dev/ai/package/roblox/nightcycle/quad-tree/files","readme":"A binary tree optimized for 2D querying\r\n\r\n\r\n# Search Radius\r\nAllows for searching for items within a set distance from a point, a second method is also available for filtered queries where it skips areas within an inner radius.\r\n\r\n<img src=\"./media/search-radius.gif\" alt=\"search radius\">\r\n\r\n# Search Region\r\nAllows for searching for items within a set bounds, a second method is also available for filtered queries where it skips areas within an inner bounds.\r\n\r\n<img src=\"./media/search-region.gif\" alt=\"search region\">\r\n\r\n# Benchmark\r\nI ran a benchmark with this configuration:\r\n- 1,024 queries per test, across 10,000 tests\r\n- query diameter of 1024 (used as box width and height for region searches)\r\n- points distributed along a range of 32,768 across the x and y axes\r\n- 20,000 points\r\n\r\n<img src=\"./media/bench.png\" alt=\"benchmark\">\r\n\r\nThe fastest was :SearchRegion(), with around 30.3 microseconds per query - allowing for around 32,000 queries a second. The other methods aren't much slower, however filters are slightly slower in general, and region querying is a bit faster than radius querying.\r\n\r\n# Octree Comparisons\r\nHistorically I've used Sleitnick's [octo-tree implementation](https://github.com/Sleitnick/rbxts-octo-tree), which I heavily recommend for 3D querying. However, many of my queries are actually 2D so I theorized I could get performance benefits by writing a solution from scratch for just 2 dimensions + allows me the opportunity to add in some desired filter methods.\r\n\r\nI ran a benchmark with this configuration:\r\n- 2,048 queries per test, across 10,000 tests\r\n- query diameter of 1024 (used as box width and height for region searches)\r\n- points distributed along a range of 32,768 across the x and y axes\r\n- 512 points\r\n\r\n<img src=\"./media/octree.png\" alt=\"benchmark\">\r\n\r\nFor now though, my implementation is unoptimized - if you have fewer than around ~2500 items my quad-tree is faster, otherwise theirs is faster.\r\n\r\n# Further Development\r\nIt's deeply annoying that the octree is faster than this quad-tree one in 2D operations. I'm publishing this now because it has handy APIs and it is technically faster below a certain limit, however expect further development to be in the area of optimization.\r\n","readmeTruncated":false}