I’m trying to design a system by which my entities can see each other. It occurs to me that this is essentially a collision problem. I’m planning to have my game be tiled based and turned based.
There are a variety of collision detection methods I was able to research so as to do things efficiently. But it seems like sometimes the simplest solution may be the best depending on how many entities you have.
The 1st part of my question is how many entities do you have to manage at a time before brute force collision checks of every entity against every other becomes less performant than more complex solutions? It seems like that threshold would be particularly high for a turn based game that has a tile system and nothing is bigger than a tile. But it seems like at some point a data structure is advisable.
Thus the 2nd part of my question: If there is a need to use a more advanced collision system, Then what should I do? Some of the more complicated approaches seem like overkill given my constraints… I feel like bucketing the entities by the x-coordinate so that collision is a matter of checking the Y coordinates of the nearest buckets might be something but then the cost of maintaining those buckets probably is only justified at a certain threshold.
Finally , maybe I’m wrong. Maybe entities being aware of each other is better modeled as not a collision problem at all. If so please let me know a better approach.
A Grid (tile based) is already a system of spatial partition in its own - in many cases just using a grid is a viable solution. It’s basically a tree structure with just 1 level. Now if you add more levels (like combining each 2x2 grid cells into another grid of fewer cells) you basically get a quadtree (or octree in 3d). A simple grid has unbeatable random access & neighbour access … as long as you only need 1 neighbour for each cell (collision shapes not bigger than single cell)
It really depends about the games properties to find a fitting structure for the optimal solution, there is multiple sorts of tree structures out there.
I once had something with orbiting units and my spatial partitioning was based on some arbitrary planes projected on a flat array … which worked very well for collision checks, but less well for frustum culling (as there was no real connection to screen space whatsoever)
talking about frustum culling - if your spatial structure can be used for both you may be able to do multiple things in the same loop, which may not be faster on its own, but combined with the time you spare by not having a distinct loop for something else can be a benefit as well.
In the end it always comes down to bucketing the data so you don’t need to inspect every entitiy with every other entity and the best approach may often depend on the sort of data you handle.
Yeah, in terms of actual collision “IsInSameCell()” is an easy algorithm, but the problem is that things can see across multiple cells.
Im considering making a list sorted by x and one by y. Walk a list, inserting elements within range of each other for that axis into rows of a matrix. Do the same for the other list. Now sort each and walk the matrices in parallel, getting the union of the sub lists, and those are your collisions.
Of course, I’d have to be careful about too much pointer chasing, and I’d have to test it.