Log In  

Cart #41492 | 2017-06-09 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

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

-- bdel(store, entity) to remove an entity

-- remember you can maintain multiple stores based on the needs of your game!
P#41493 2017-06-09 15:26 ( Edited 2021-08-08 03:34)

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 ( Edited 2017-06-09 20: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 ( Edited 2017-06-09 21: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 ( Edited 2018-03-13 19:41)

When spiders attack !

P#54841 2018-08-07 22:27 ( Edited 2018-08-08 02:27)

I used that technique for Nuklear Klone and that’s really super fast.
I would not have managed so many bullets/entities without.
(that is, as long as all your entities are not at the same spot!)

Edit: looking at the code, couple of thing that bothers me:

  • don’t use for/all, that’s dead slow
  • should not use string coordinates, the algortithm assumes the world is a grid, use that (eg. index=x+world_size*y)
  • the most critical part is the iterator. You should not be creating another array + you should deduplicate entities

Extract from Nuklear Klone:

-- collision map for a max 128x128 world
-- provide o(1) lookup for proximity checks
— call cmap_del before updating entity pos (or entity death)
— call cmap_add after updating entity pos
local cmap={}
local cmap_cells={0,1,129,128,127,-1,-129,-128,-127}
function cmap_op(obj,fn)
    if bor(obj.w,obj.h)!=0 then
        for x=flr(obj.x-obj.w),flr(obj.x+obj.w) do
            for y=flr(obj.y-obj.h),flr(obj.y+obj.h) do
function cmap_add(obj,cmap,h)
    cmap[h]=cmap[h] or {}
function cmap_del(obj,cmap,h)
    if cmap[h] then
        -- remove empty sets
        if #cmap[h]==0 then
local cmap_session,cmap_i,cmap_cell,cmap_h
-- creates a nearby iterator
-- filters by side
-- warning: not reentrant
function cmap_iterator(x,y)
function cmap_next()
    while(cmap_cell<=9) do
        local h=cmap_h+cmap_cells[cmap_cell]
        local objs=cmap[h]
        if objs and cmap_i<=#objs then
            local obj=objs[cmap_i]
            -- avoid duplicate entities
            if obj.cmap_session!=cmap_session then
                return obj
    return nil
P#54847 2018-08-08 01:36 ( Edited 2018-08-08 05:53)

(ahah just saw OP is from ages ago...)

P#54848 2018-08-08 02:23 ( Edited 2018-08-08 06:23)


  • don’t use for/all, that’s dead slow

isn't it the same as pairs these days?

  • should not use string coordinates, the algortithm assumes the world is a grid, use that (eg. index=x+world_size*y)

I'm not using a fixed grid so no and no

  • the most critical part is the iterator. You should not be creating another array + you should deduplicate entities

there are no duplicate entries and why would you want to avoid returning found entities in an array? not like there's a memory constraint here?

P#63976 2019-04-25 23:33

the response was written before 12c!! and there is still a perf penalty for all.

overall, the main problem I see with your solution is that it does not take into account the width of the sprites. Eg a bug should be registered all the buckets that the sprite overlaps.
That’s why you can have multiple times the same entity when iterating over neighbors.

P#63981 2019-04-26 05:47

@freds72 in my lib you provide a grid cell size, as long as that's bigger than your entity dimension you'll get everything that could be touching within manhattan distance. Usually you run a second distance check if you need circle overlaps or whatever.

Look these kind of spatial hash sweeps have been around forever, mine is fine, it doesn't have performance problems, there's no need to keep popping in here trying to invent things that are wrong with it.

P#67948 2019-09-20 17:54

Sorry if this is a silly/newbie question, but how do I remove something from the store after adding it?

P#89043 2021-03-16 06:32

@amiantos apologies for the ommision, bdel(store, entity) will remove something from a store

P#95770 2021-08-08 03:35

[Please log in to post a comment]