Log In  
Log In  

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

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-08-08 06:23)

:: JTE

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)
:: daivuk

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)
:: dw817

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

[Please log in to post a comment]

About | Contact | Updates | Terms of Use
Follow Lexaloffle:        
Generated 2019-05-22 21:09 | 0.033s | 4194k | Q:40