Web
Analytics
Log In  

4

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

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!
library
P#41493 2017-06-09 15:26 ( Edited 2018-08-08 02:23)

::

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

::

When spiders attack !

P#54841 2018-08-07 22: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
                fn(obj,cmap,x+128*y)
            end
        end
    end
end
function cmap_add(obj,cmap,h)
    cmap[h]=cmap[h] or {}
    add(cmap[h],obj)
end
function cmap_del(obj,cmap,h)
    if cmap[h] then
        del(cmap[h],obj)
        -- remove empty sets
        if #cmap[h]==0 then
            cmap[h]=nil
        end
    end
end
local cmap_session,cmap_i,cmap_cell,cmap_h
-- creates a nearby iterator
-- filters by side
-- warning: not reentrant
function cmap_iterator(x,y)
    cmap_i,cmap_cell
    cmap_h=flr(x)+128*flr(y)
    cmap_session+=1
end
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]
            cmap_i+=1
            -- avoid duplicate entities
            if obj.cmap_session!=cmap_session then
                return obj
            end
            obj.cmap_session=cmap_session
        end
        cmap_i=1
        cmap_cell+=1
    end
    return nil
end
P#54847 2018-08-08 01:36 ( Edited 2018-08-08 01:53)

::

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

P#54848 2018-08-08 02:23

Log in to post a comment

user:
password:

New User | Account Help
:: New User
X
About | Contact | Updates | Terms of Use
Follow Lexaloffle:        
Generated 2018-11-19 07:09 | 0.219s | 1835k | Q:25