This makes it the first time I'm posting here, so apologies if I stumble over beloved conventions.
Currently, I'm trying to figure out how I want to handle collisions for a large number of entities on screen (a bullet hell, top-down shooter). I've done a prototype of the game with some friends in the past before and we reached about 300 circular entities (a point with a radius "hitbox") checked against 3 every 1/60 seconds before considerable performance drops. The implementation was cringe worthy; due to lack of experience and a very stringent deadline, we didn't have time to do anything but a brute force distance check with each entity, making 900 pythagorean calculations per game loop.
This time I'd like to approach it with some intelligence. Since I'm simply checking for collision and not retaining any kind of directional information, I've managed to come up with two strategies. Unfortunately, they have their benefits and drawbacks:
Localized Checking - Essentially, creating a 2D array and checking only cells that the 3 entities exist in. The problem with this is that edge cases become an issue - say, if an allied entity is on the edge of a cell and an enemy entity is on the adjacent edge of an adjacent cell, I should have to check both, meaning there would be additional adjacent cell checks. While I can overcome this with a mandated "all cells that share a vertex" check and reduce the size of the cells to [standard entity radius * 2], it restricts the size of entities or forces me to use a separate system of checking for larger-than-standard entities. Obviously, avoiding this would be ideal.
- More importantly, while this drastically lowers calculations made during collision detection, the reassignment of an entity to another cell due to movement would create a computational step on all moving entities (most of them) during each iteration of the game loop. Furthermore, an additional call must be made to move an object from one cell to another when it has to migrate into another cell, which will be much more common as the cell size drops. This is not ideal.
Mathematical Checking - The theory goes that if we think of bullet patterns not as separate entities but as mathematical formulas expressed as the intersection of equations (linear, quadratic, etc.) and a sinusoidal function (determining position of an entity based on the y position on that function), checking would be simplified to 3 entities against the sum of all formulas present. Unfortunately, I lack the mathematical background to do this. Furthermore, designing bullet patterns becomes a giant headache, so the cost of designing levels rises (and I am of the opinion that the most expensive work is that performed by humans).
- What's more, if we take a basic curved formula such as a hyperbola, it is incredibly difficult to keep entities perfectly circular along the curves. Without a really good grasp of math, entities would appear oblong or pinched as the entity moves across the curve. This is extremely difficult to graphically represent without doing it dynamically, which would limit the visual vocabulary I am able to utilize. Also not ideal.
I'm not exactly sure how I'd like to proceed with this. Any thoughts out there? Standards that I've managed to miss?
