I've known for awhile that it's better to index everything into a giant grid and then query said grid for entities, than querying the entire world.
I do have a few questions left unanswered, and I hope some of you can shed light on this.
I’ve tried to write this in an understandable way, and I even provide some illustrations.
A perfect situation of querying a grid, would be this:
The circle represents your entity, and it should be clear that the entity is indeed in cell (1, 1).
It’s easy to ask (in code) “Hey! Is anything in the way, over at (1, 1)”, and it’s easy to find out that the circle is there.
Consider this next scenario:
The circle is the same. It still fits within one square, but it’s not entirely inside a single square. This scenario is possible within a ton of games, but how do we handle it?
What cell is it actually inside? If we decide that it’s still (1, 1), then what happens if we need to check if there are no collisions in cell (2, 1)? Obviously the outcome isn’t great, because the game won’t recognize anything in the (2, 1) area.
Here’s an actual question: With the above in mind, do I want duplicate entries in the grid? If yes, I no longer have to worry about -||-
I always thought that I didn’t want duplicate entries, and so I’ve had a few thoughts on how to handle the problem.
Here’s one: I can query multiple cells, based on how big my entities are.
Let’s say that my largest entity, is equal to the size of the blue circle:
Now, if I want to query cell (3, 3), I need to do it like this:
Because my largest entity can leak over 9 cell, I need to query the 8 cell around the starting point to make sure I don’t miss anything (provided that there is only one entry of each entity). That makes performance a lot worse.
Is there any ways around this problem? Is there an easy way to find out what cells an entity is touching, if the entities center vector, and radius is available?
Also, how is pathfinding in an environment like this possible? I would make targets at the center of each cell, and just use the heuristic to get my entity there. That makes it easy to apply A* for instance. However, that way it can easily become difficult to find a valid path.
I don’t want to avoid a cell, just because the edge of an entity is slightly leaking into it. That doesn’t pose an actual obstacle, especially if the mover is a much smaller circle, that can easily maneuver past the edge of the leaking entity, without leaving the cell. I’ve illustrated this below.
Another thing is, how does one query collisions accurately, in this environment? Say, I want to know whether a small circle is intersecting with anything, but it’s radius is a cell’s width 1/20 (like a bullet in a game).
For completely practical reasons: How big should each cell be? Not too small because it’ll be slower, but not too big either. Is there any general rule of thumb, like equal to the size of my smallest entity?
I know a bunch of you have been working with an environment like this, so please enlighten me.
Thanks a ton.