This article is from HERE
Hey guys, we are going to try and document the development process of our entry for the 3rd Game Jam! No promises, but we will try our hardest to keep this up to date.
Fundamentally our entry is going to be a 2D platformer called Quantum Caverns. You can take a sneak peak of the game, and even check out our code, at the game’s Github page as development progresses.
Anyways, we are still in the planning stage, but here is a neat graphic for what we have so far.
As mentioned earlier we are using Python and the pygame library for Quantum Caverns’ development. During Diner Mafia’s development we learned the hard way just how taxing and slow Python can be when poorly optimized. Our code was a mess, but we managed to improve performance on the GameShell just before the game jam ended. Although, the optimizations were rushed, and there was still a lot of room for improvement.
This time it’s going to be different! We aren’t starting late this time, so optimization for the GameShell is a top priority. After all, a 2D platformer has to have tight controls and smooth movement.
After some research into the topic, we’ve learned about Quadtrees. If you’re new to game development I would definitely recommened reading this article and researching some more about the topic, and eventually implementing the data structure into your own code. In summary, proper use of a Quadtree can yield significant performance improvements because of how efficiently queries can be used to iterate through objects.
We implemented a QuadTree data structure into pygine, the engine we made for GameShell game development, and made a simple scene to test it out.
The scene consists of 500 rectangles moving around the screen, which isn’t too expensive for Python to handle. However that’s too boring, we want the rectangles to bounce off of each other if they intersect! The inclusion of this simple collision is where things get complicated.
Here is a GIF of resolving the collision by checking each rectangle against every other rectangle.
As you can see, the program is having a really hard time keeping up. The frame rate is terrible. This is where the Quadtree can come in handy!
WOW look how much faster that is!
All those black rectangles in the background are a visualization of the Quadtree in action. Each rectangle is basically a section of the Quadtree that’s used by the querying algorithm.
This is going to be really useful for collision checking in Quantum Caverns. I hope you got something out of reading this post. Implementing a Quadtree may seem intimidating, but I assure you its easier than it looks and its definitely worth it!
While researching Space partitioning I noticed Bins included on the list of common data structures, which I presume is another name for spatial hash, but I opted for Quadtrees just because of how visually pleasing their recursive pattern can be. Although I’ll definitively try and implement a spatial hash based on your experience.
Some research is in order, but from what I’ve read, I think a spatial hash would be ideal for resolving collision against static blocks, while a quadtree could be used for any moving entities in the game. I’m not sure though, but at least the fun part is testing it out!
After going to sleep and taking a second look at the GIFs, I’m starting to think the software I used to record the GIF may have done something to make the make the game look faster than it actually was. The first GIF wasn’t optimized at all ( O(n²) ), just the second GIF ( O(nlog(n)) ). In practice I highly doubt there will be that many entities, but when it come to Python any improvement goes a long way.
Anyways thanks for the feedback! I’m planning on getting a simple prototype of the platforming mechanics done today, but I’ll also include my findings about trying out a spatial hash.
For the past couple of days we have been doing various behind the scene tasks to ensure Quantum Caverns will run optimally on the GameShell. Unfortunately most of this stuff is too boring to talk about, but we finally have something to show off!
Now this might not be that impressive, but this new collision system opens up so many possibilities in terms of level design.
If you want to learn more about 2D collisions then this article on the Separating Axis Theorem is a great place to start!
The Importance of Delta Time (Part 1)
Despite our best efforts, Quantum Caverns is not locked at 60 fps on the GameShell. Based on some initial prototyping, the fps fluctuates anywhere between 40-60 fps when on the GameShell. Now this shouldn’t be a problem, but due to some naive programming on my part, this is actually game breaking.
See for yourself. This is the player jumping when the game is locked at 60 fps on my computer.
This is fine, but check out what happens if I lock the framerate to something else like 30 fps.