I am writing an top down 2D game like agario/diep.io and I am using spatial hashing for detecting on screen objects. However I find it is too expensive to do a spatial partition a few times a second. (I do it at an interval of 250ms) I have about 5000 objects on the map and 150 objects on screen on average at the same time. I find a post by agario developer on reddit.com which mentioned that we can do spatial partition less often by tracking the player's position and do object insertion on a specific node (using quadtree). I wonder if this can be done using spatial hashing too.

  • \$\begingroup\$ If you have the new position and old position in each player's update function, you can check if it is crossing a boundary (for example, by checking its position mod your cell width) and update only then. \$\endgroup\$
    – Jimmy
    Commented Jul 25, 2017 at 15:47
  • \$\begingroup\$ @Jimmy Thanks for that. I don't understand the "update" part. Normally, I will have to insert every object on the map in a simple spatial hashing cycle. If I "update" only when the player crosses the boundary, what should I insert into the list? Also taken other players/objects into account, wouldn't it be necessary to do a spatial hash more often so that we can get other objects state changes in time more accurately? \$\endgroup\$
    – newguy
    Commented Jul 25, 2017 at 16:07
  • \$\begingroup\$ I mean, at some point an entity is in an invalid cell in your spatial hash (when it has moved too far and is now in a different cell) and you have to remove it from the old cell and add it to the new cell. You can reduce the frequency of the adding and removing by only doing so when you know the entity has crossed a boundary (in their onUpdate function or whatever you're using to update their positions on input) \$\endgroup\$
    – Jimmy
    Commented Jul 25, 2017 at 16:10
  • \$\begingroup\$ @Jimmy You just mentioned one of the situations: entity crossed a boundary. But entities could disappear on the map and new entity will spawn at any position at any time. These changes need to be reflected on the spatial hash too. If I don't do this at a high frequency how can I show this information to player in time in the game? \$\endgroup\$
    – newguy
    Commented Jul 25, 2017 at 16:27
  • \$\begingroup\$ It will more than likely be much faster to just hash the objects, than it will be to calculate if they crossed bounds or not. \$\endgroup\$
    – jgallant
    Commented Jul 25, 2017 at 17:27


You must log in to answer this question.

Browse other questions tagged .