I (Tuomas) have been working on the engine features for the last month. I basically rewrote the game loop and collision detection system from scratch because the earlier versions weren’t cutting it.
I noticed how the animation was not smooth at all and tracked the issue to bad game loop design. After identifying the problem, I spent a good amount of time researching on how to build a proper game loop. I guess every programmer will eventually end up reading the ‘Fix Your Timestep!’ article by Glenn Fiedler. He does a fantastic job of going through different game loop implementations and explaining why they work or don’t work. You can read the article here. Long story short, I implemented a version of the semi-fixed timestep game loop and it’s working nicely!
Next up was fixing the collision detection system. The earlier version worked fine, but things started to go south when I implemented partial collisions in the game. The partial collisions allow us to define regions of a tile which are not accessible, instead of blocking the whole tile. For example, we can create walls the player can walk right next to, giving the game a sense of depth. Because I didn’t refactor the old collision detection system properly, weird glitches and bugs started appearing when new tiles with partial collisions were created.
What followed was an exercise in rewriting the collision detection system again and again. I have to admit it was really frustrating when you thought you were about to nail an implemention only to realize it would crap out in certain special cases. I could sense when a certain version of the system wasn’t going to work because I started adding a lot of special cases in the code. And sure enough, the special cases were not tight enough and the system would break.
For example, one of the older versions looked like this:
The problem with this system was that the player would get stuck at the edges between the tiles. I tried working around this issue in several ways but all of them ended up breaking the collision detection system in some way or another. Finally, I found out that the way to handle this issue is to collapse all the external edges into combined lines. This fixed the ‘getting stuck’ issue nicely. Having this implementation also enables you to have arbitrary sized shapes in your engine (like we have with different sizes of rectangles). You can see the new collision lines below.
Here’s the algorithm I came up with:
Loading the level
- First find all the external edges in the tiles
- Then sort the edges into horizontal and vertical edges (we only have rectangles in the game)
- Detect adjacent edges by comparing their start or end point. If the edges are combined, keep the combined line and remove the lines you just compared.
- Collide the player rectangle(s) against the lines
- Detect if the lines have a corner point and if the player needs to resolve a corner collision
- Resolve collisions, adjust the player’s x or y position back to the previous position
This is just a high level view of the algorithm, but I think it illustrates how the collision detection works in general.