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!
|
This is how Doom engine's blockmap works for tracking walls, sectors, and objects in a given space, right? :3 Ohh, sounds useful.
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 :)
Yes doom uses block map for collisions. The BSP is only for sorting and rendering.
I ported their code to XNA a while ago :)
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
|
- 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?
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.
@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.
Sorry if this is a silly/newbie question, but how do I remove something from the store after adding it?
[Please log in to post a comment]
