Spatial Hash Grid Performance

[willow sundial]

Hi, I'm a JavaScript developer who wanted to start learning go for fun and for having another good language under my belt. I transcribed my JavaScript implementation of a Spatial Hash Grid into go. I believe the code below (specifically, the if grid.grid[key] == nil { line), to be the source of issues of my performance. Is there another way I could do this to make it faster? Thanks!

[high thorn]

why would you believe a nil check to be the source of performance issue?

i dont really see how, but if that's what you believe
(i could see the potential of make being a problem though)
assuming the grid size is known and predetermined, you could just create all the maps first
so you dont have to check and allocate, because you knew everything has been created before hand

this would only work if the size is not dynamic and it make sense to allocate everything
if only certain places will be used while others left touched it might not make sense

[willow sundial]

Yeah I meant the make being the issue

My bad

[willow sundial]

Yeah the goal of my grid is so that it’s dynamic always

My goal is to do a dynamic game with collisions

[high thorn]

how big is the grid is it supposedly infinite right?

i dont see an easy way out then...

what if we force it to be limited in size key % bucket size
now with that in mind we can create a slice of with size of bucket size with preinitialized map

that would not work if you need to get all entities at a certain location

basically i would suggest "maybe try another data structure to store it" but i dont have any idea since i dont know the usecase and design requirements

since i dont see a way going down this path
maybe object pools, but you also gotta remember to cleanup the map once it's unused and return it into the pool
this also assumes you will free some of the map after some time

taking a deeper look at your code
it seems like the larger the object is, the more potential allocations could happen
each x&y get combined together to form a key for that specific xy coordinate
if the coordinate key on the grid wasnt already created, creating one
i think the idea of for y and x to create a key is the root of the problem that leads you down to allocating so much maps

so the options are:

• add some sort of constraint, so you can preallocate for everything
• dont use this datastructure, change to something else
• improve the algorithm and make it fuzzier so that it does not allocate as much(for every single coordinate)

i think if you explain what your end goal is, and what's the role of said system, you might give us a better idea of what we can recommend you to do

[willow sundial]

• improve the algorithm and make it fuzzier so that it does not allocate as much(for every single coordinate)
  It doesn't, the >> grid.positionShift makes it take big chunks and pool them together

[willow sundial]

I'm making a .io style game with lots of entities, and the game instances need to be able to quickly do collision detection between thousands of entities

[spark iron]

I know it doesn't really answer your question, and I really dislike getting "just do it completely differently" answers myself, but in this use case I would absolutely use a quadtree.

[high thorn]

actually you are be correct, i am not so well versed in bitshift ops lol

[high thorn]

regarding this: let me ask the same question in a different way
is the grid "finite" in size? as in your grid have a set size that never grows beyond that
i think dynamic was a bad word choice on my part

i asked this to consider if pre allocation is really not possible
you would sacrifice some ram to avoid allocating at runtime which should be fine if you just want a speedy game server

[willow sundial]

In cases like this, I've always found quadtrees to be slower, and less flexible

Since the map should also be changing sizes periodically

[willow sundial]

is the grid "finite" in size? as in your grid have a set size that never grows beyond that
Not finite size

The map can be small or big

depends on player actions

[willow sundial]

idk if it would be wise to allocate at start, because it seems like if the map grows or shrinks I'd have to allocate even more

If you'd like, I can post the full implementation here

[high thorn]

yeah thats why i asked about your game, to see if that's doable for your game

i dont think i can really help things implementation wise
but you could post it, maybe someone else would be able to give some suggestions