Log In  


Cart [#41492#] | Copy | Code | 2017-06-09 | Link

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)


This is how Doom engine's blockmap works for tracking walls, sectors, and objects in a given space, right? :3 Ohh, sounds useful.

P#41497 2017-06-09 16:23


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


Yes doom uses block map for collisions. The BSP is only for sorting and rendering.

I ported their code to XNA a while ago :)

P#50371 2018-03-13 15:41

Log in to post a comment


New User | Account Help
:: New User
About | Contact | Updates | Terms of Use
Follow Lexaloffle:        
Generated 2018-06-25 19:25 | 0.215s | 1572k | Q:20