Right now, I’m using AABB collision detection, and every occupied tile in my tilemap has a collider attached. My tilemap is 64x64, which totals to a max of 4,096 tiles, and 4,096 colliders respectively. My collision detection for moving objects like the player and enemies uses continuous collision detection, where I loop through every solid collider for every pixel until I detect a collision. So if a player was moving 10 pixels down on one frame, it would loop through all 4,096 solid tile colliders at most 10 times, which would require that I check for an AABB collision (at most) 40,960 times in a single frame. This is obviously a costly process, and so I worked on a way of optimizing it.
Now, every frame, every solid collider compares its position to every moving object’s position, and determines if it’s too far away to be possible to hit, in which case it removes itself from the list of all the solid colliders until the next frame. This worked initially, for a single moving object (the player). It even worked when I added in 10 moving objects that simply move and bounce off walls. Once I go above 10, I start losing frames at an exponential rate.
So my question is this: I could simply limit my gameplay to never use too many moving objects in one scene, OR I find a more optimized method of accomplishing the collisions I want. One option is to make a seprate “tilemap” collision system, integrated into my current system, and remove the AABB colliders from my tiles. However, I struggle to see how using a grid-based collision system would be any more optimized then just performing an AABB collision check against all 4,096 tile colliders. I could be wrong, and I’m working right now on implementing a tile collision system without using AABBs for them, but I figured I’d post a little bit about what my issue is in hopes that somebody here might have some tips for this.
Thank you!
So as I was implementing a dedicated tilemap collision system, I found an article which I had read a couple days ago, Jonathan Whiting (link) on this sort of system. I glanced at it before but somehow completely missed an entire paragraph on optimizing his system due to the number of tiles growing quickly larger. So now, I’m working on using the tips he mentions to make this system work, and will update this post shortly when it is finished and tested!
1 Like
So after a bit of working, implementing my grid collision system, it works! It works so well, I can even add in 1000 of my simple traveling test objects and it runs full speed, 60fps! This is wonderful! Hopefully anybody else with a similar problem to what I encountered might find this and be able to implement it. This is truly incredible and so much more optimized!
Right now, the code is messy and clunky, but at least now I know it works, and I know HOW it works, so I can clean up this code! 
1 Like
It sounds like you’ve found a solution, way to go!
When faced with similar issues, I tend to fall back on some kind of world partitioning. I don’t want to compare every moving object against every other object that it could possibly run into, only the ones that it’s likely to run into.
If you’re in a tile engine, which you are, your object that is moving should know which tile grid it’s in. Therefore it should be able to simply query objects that are near where it is and where it’s likely to go. You can just directly look up the coordinates in your array of objects and use that to drastically reduce the number of collision checks you do.
Alternatively, I tend to use a Quad Tree. These are handy little structures that will organize two dimensional world space into sub-divided rectangles that continue to sub-divide until there’s some minimum number of objects that can be fully contained. To query, you match your colliding object’s bounding rectangle to the quad tree and ask it for all of the objects that will intersect with that rectangle. Like the above, the result will be a much smaller subset of your total objects and you can do your collision check against that.
A caveat with the Quad Tree though… there’s a cost associated with inserting to, and removing from, the tree. This is because it has to make sure it sub-divides its space correctly and, when an object is removed, it cleans everything up. Depending on how many objects you have, the performance cost of this can add up. There’s a mitigation to this though, in that you can extend your quad tree structure to support a move. When the object moves, have it check to see if it’s still contained by the quad it was in. If it isn’t, have it move up the tree and check until it can be contained, then have it traverse down the tree, sub-dividing as appropriate, until it finds its new home. It still has a cost, but it’s far less than removing it and re-adding it for every move.
Anyway, those are the two options I generally fall back on.
1 Like
Instead of testing after every pixel of movement you can treat the space between your start and end point as a line and test that line for collisions, if you find a collision then you calculate how far along the line the first collision happened. (Handmade Hero episode 47 and 48 cover this)
To test a shape instead of a point use Minkowski Sum and GJK (Handmade Hero episode 50 covers this).