This is a small (259 token) library for finding entities close to a point.
A bucket hash (also called a spatial or grid hash) breaks up space by a grid size, and maintains a sparse table of "buckets" representing a grid location. When entity membership in these buckets is updated, you can quickly
retrieve entities near a given point.
-- usage -- create a data 'store' {size=30,prop="pos"} -- store.prop should match your entities' position property name, -- which should be a 'point' value like {x=0,y=0} -- store.size should be tuned to the max neighbor distance you'll be finding -- periodically call bstore(store, entity) to update their bucket membership -- bget(store, point) returns stored entities from a 3x3 square of buckets around -- the given point, filter these by a distance function if you need more precision -- remember you can maintain multiple stores based on the needs of your game! |
P#41493 2017-06-09 15:26 ( Edited 2018-03-13 15:41)
::
Hmm, Doom uses https://en.wikipedia.org/wiki/Binary_space_partitioning for it's level geometry but I'm not sure how it handles moving objects.
There's more info on this algorithm at https://en.wikipedia.org/wiki/Bin_(computational_geometry) if you're interested :)
P#41501 2017-06-09 17:30
Log in to post a comment |