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):
velocity.y = -jump_velocity
velocity.y += gravity
location.y += velocity.y
Simply changing the update method to use delta time, as shown below, might make intuitive sense, but in practice we still have inconsistencies across different frame rates.
// Won't actually solve anything :(
def update(delta_time):
if pressed(JUMP_BUTTON):
velocity.y = -jump_height * delta_time
velocity.y += gravity * delta_time
location.y += velocity.y
In part two of this post I’ll over complicate all of this and lay down some calculus and physics to show you a solution to this whole ordeal, explain why this code works in the first place, and show you a couple of ways to use the physics behind this to improve your platformer jump code. Stay tuned!
The Importance of Delta Time (Part 2)
Physics Breakdown
Before we tackle this problem we must first understand why the code below causes the player to jump in a parabola.
def initialize():
gravity = 10
jump_velocity = 100
velocity = Vector2(0, 0)
location = Vector2(0, 0)
def update(delta_time):
if pressed(JUMP_BUTTON):
velocity.y = -jump_velocity
velocity.y += gravity
location.y += velocity.y
There are multiple ways to go about explaining this. With that said, note that the explanation below will assume prerequisite knowledge of some intermediate physics and calculus.
Although, I will keep the jargon to a minimum, attempt for the explanation to at least make somewhat sense without fully understanding either subject, and even provide some additional resources to further your understanding.
Anyways.
According to Newton’s laws of motion, an object will only accelerate if acted upon by a net force. Furthermore, net force is simply the product of mass and acceleration.
Force = mass * acceleration
This concept is fundamental to any physics engine (e.g. Box2D), but you may be wondering how this applies to the measly 12 lines of code above. After all, there isn’t even a mass or force variable anywhere in the code. There isn’t even any multiplication anywhere!
Now this is the beauty of abstraction. You could use this code in any platformer and the player will jump in a parabola. You don’t need to know why, it just kinda works. Come to think of it, I’m not even sure how or where I learned this code in the first place. I must have copied it somewhere and stuck with it ever since.
This philosophy can be extremely detrimental in the long run, especially for programmers. How can you fix a bug if you do not even know what the code does?
So we need to break down the nature of the code in order to solve our bug. We can start by, well, looking at nature! After all, if you jump up as high as you can right now, the motion of your jump could be tracked as a parabola.
The similarities between the motion produced with the code above and the motion produced in real life would suggest that F = ma is in fact used implicitly somewhere in our code. So let’s try and found out how.
If we consider the fact that acceleration is really just the change in velocity, then that would mean that wherever we change the velocity in our code we are really applying acceleration. This is happening in this line of code.
velocity.y += gravity
That means that the gravity variable in our code is actually acceleration! So the player accelerates downward 10 pixels per frames². We can express this as a function of time.
With just the acceleration function we can work backwards to find out what the velocity function is. We can do this by taking the antiderivative of the acceleration function as shown bellow.
So now if we graph the velocity function and acceleration function we get this.
Finally, if we take the antiderivative of the velocity function we get the position function.
Now if we graph all three function we finally see our parabola!
Okay so we are getting somewhere. We worked backwards and came to realization why the jump code produces a parabola. But now what? How does this help us with our bug? You haven’t even mentioned delta time in this part, wasn’t that important?
I guess you’ll just have to find out in PART THREE!
The Importance of Delta Time (Part 3)
Graph Manipulation
Before we can address our bug, we must first understand what each axis of the graph represents in the context of our code. If this was your average textbook physics problem then the y axis would probably represent distance in meters and the x axis would represent time in seconds. In the context of our code, the y axis still measures distance and the x axis still measures time, but the units are not meters and seconds respectively. Instead we are working with pixels as a unit of measurement and frames as a unit of time.
Now that we have the correct units, we can begin to analyze the graph. The maximum value of the position function occurs at the point (10, 500), and the function crosses zero for the second time at (20, 0). Therefore, the player will jump 500 pixels into the air in 10 frames, and then fall another 500 pixels to complete the jump in a total of 20 frames. If the game was running at 60 fps then 20 frames would amount to roughly 0.333 seconds. If the game was running at 30 fps then 20 frames would amount to roughly 0.667 seconds. In other words, the faster the frame rate the faster the jump is completed.
This is bad.
Recall how in Part 1 I explained that simply multiplying horizontal movement by delta time creates consistent movement across different frame rates. I also mentioned how taking a similar approach and multiplying gravity and jump_height by delta time still results in inconsistencies. Here is the flawed code once again.
// Won't actually solve anything :(
def update(delta_time):
if pressed(JUMP_BUTTON):
velocity.y = -jump_height * delta_time
velocity.y += gravity * delta_time
location.y += velocity.y
Now that we have a visual representation of this code, we should also multiply our functions by delta_time and see what happens.
As the frame rate increases the maximum value of the position function decreases. In other words, the higher the frame rate the lower the player jumps. This explains the player’s behavior in the very first two GIFs in Part 1.
So far it looks like multiplying gravity and jump_height by delta_time was a failure. Now instead of just jumping too fast, the player jumps too fast and jumps at a different height depending on the frame rate.
Things aren’t looking too good.
At this point it’s a good idea to take a step back, and ask ourselves what the problem is in the first place.
The player should jump in the form of a parabola.
We want the player to jump x amount of pixels into the air in y amount of time.
The jump height and jump duration should be consistent across different frame rates.
We already know how to achieve point one, and we can’t yet figure out point three, and in regards to point two . . . well actually I don’t think we’ve even given that a try! In fact, let’s just completely forget about point three and just address point two.
So we want to construct some parabolic equation where we can specify a jump height and a jump duration. Here is the process to achieve just that.
This is the part where we use some more calculus to find out what we need to multiply t by (this value will be represented by v) in order to achieve the correct maximum point. All we have to do is find where the derivative of the position function is zero and see what v must be at that point for the modified position function to be the maximum height.
Alright now let’s plug this into the graph.
Okay so everything is working so far, but we aren’t done just yet. I guess you’ll just have to see what happens in the finale. We are so close!