Catjam Collision and Optimizations

kyleperik.com

–

It's been 10 days since the start of catjam, I have a working MVP.

Blocks fall from the sky, and there's a little sprite that can wall jump and platform off of them, climbing up as the blocks form a tower of rubble below. Most of the work was accounting for all the moving parts, doing collision checks and responding to collisions.

The latest challenge has been making the collision checks efficient, up until yesterday every block would run a collision check off every other block, that amounted to roughly n^2 collision checks, so with 256 blocks that's 65,536 checks every frame.

My plan was to make sure the blocks are sorted on the y axis, then for each block, check the blocks directly below for collision until we reach a block that can't possibly be reached (32 hex pixels in distance), then stop and move to the next block.

In addition, I realized I didn't need to run collision checks at all for blocks that are not moving, so I filtered those out.

I ran some tests with about 200 blocks, without the optimizations I was getting 15,000 checks as expected, but with the optimizations I got down to 50 checks, which is 1/4 the number of blocks on screen, so I could that as a success!

Next I'm going to focus on making movement smooth and make it into a complete game with a little menu screen. After that hopefully I'll have lots of time to add win/loss conditions, passive items and extra challenges into the game.

Thanks for reading, I'll plan on giving a few more updates before the end of catjam so check back to follow along.