Quantum Caverns Devlog
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.
Notice how the player hits his head on the ceiling in the second GIF. The physics behind the player’s jump is not consistent across different frame rates. As mentioned earlier, on the GameShell Quantum Caverns is running anywhere between 40-60 fps in any given level depending on the complexity of what is on screen. In other words, the player jumps higher when there are more blocks on the screen.
This is bad.
Given the title of our game, I could just make this bug a feature! PROBLEM SOLVED. It all makes sense right? There are uh some quantum mechanics at play in this cave . . . so that’s why the player jumps at variable heights . . . and did I mention he sometimes falls through the world . . . perfect right? Well I’ll admit, that could be an interesting mechanic, but that wasn’t what we were going for so it must be fixed!
Now right off the bat, a lazy fix could be to just lock the game’s frame rate at 30 fps. I have yet to see the game dip anywhere near that when ran on the GameShell. This is a valid solution, but the game feels extremely sluggish at 30 fps so this solution is out the window.
Well then what do we do?
The solution to this problem revolves around the concept of delta time, which is simply the amount of time in between updates. This is a very important concept when it comes to game development and programming in general. Fundamentally, anything involving motion should be multiplied by delta time. This will insure that regardless of the hardware of the computer and how fast it can run your game, movement will always be consistent.
This concept is very trivial, but it introduces something new for the all ready stressed out developer to manage, and for that reason alone is quite often neglected.
While we are on the topic, I would like to give a shout out to Skyrim and Fallout 4 just to show AAA companies make these mistakes too!
Anyways, here is an example on how to apply this concept to your game.
Consider the code below that moves the player horizontally 100 pixels every frame.
def initialize():
location = Vector2(0, 0)
def update(delta_time):
location.x += 100
If the game is running at 30 fps, then this will be applied 30 times in 1 second. So the player will move 3000 pixels in 1 second.
30 * 100 = 3000
If the game is running at 60 fps, then this will be applied 60 times in 1 second. So the player will move 6000 pixels in 1 second.
60 * 100 = 6000
You can tell this discrepancy only gets worse the higher the fps gets, but we can solve this by bringing delta time into the equation. Our new update method looks like this.
def update(delta_time):
location.x += 100 * delta_time
(I should note that delta time is just (1 / frame_rate). Usually your game engine should have this value calculated somewhere for you to use).
If we try out the code now, the player moves 100 pixels in 1 second no matter the frame rate. Multiplying by delta time cancels out the discrepancy.
30 fps Calculation:
delta_time = 1 / 30.0
30 * 100 * delta_time = 100
60 fps Calculation:
delta_time = 1 / 60.0
60 * 100 * delta_time = 100
Okay so now the player moves horizontally consistently across different frame rates, so now all we have to do to get the jump to work is multiply his jump height by delta time right? Well, it’s actually not that easy.
In the case of Quantum Caverns the player jumps in a parabola. This is a result of giving the player an initial velocity and reducing its velocity by gravity every frame. This is how that looks like in code.
def initialize():
gravity = 10
jump_velocity = 100
velocity = Vector2(0, 0)
location = Vector2(0, 0)
def update(delta_time):
if pressed(JUMP_BUTTON):