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.
I feel like there might be a lot of âQuantumâ games lol. The working title for my current idea is âQuantum Displacementâ.
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!
Here is a GIF of resolving the collision by checking each rectangle against every rectangle in a query provided by the Quadtree based on the rectangleâs bounds.
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!
lol hey great minds think alike
Having implemented numerous spatial indexing methods myself, including quadtrees, I have to say my most preferred is the spatial hash. For the things Iâve built, it just seems to perform and scale much better than quadtrees. 
Btw, did you optimize your first example before moving on to quad trees? Seems like a big jump. Are you planning on having that many colliding entities in your game?
Good job though, spatial indexing and separating axis theorem were some of my favorite to figure out and implement.
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!
Behold, a slope!
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!
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
We need to change the update method to use delta time, but what exactly needs to be multiplied by delta time in the first place?
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!
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.
(I would like to note that c can also be thought of as initial velocity).
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!
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.
Before we continue, letâs just visualize this.
(The slider on the bottom represents the frame rate. Also donât forget that 1 / frame_rate is how to calculate delta time).
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.
In Part 1 I explained that simply multiplying horizontal movement by delta time creates consistent movement across different frame rates. This works because there is no acceleration in the x direction. Our jump code does have acceleration, gravity in this case, so using delta time gets a little tricky.
In order to implement delta time into our method properly we need to use an integrator.
An integrator allows us to step through time very slowing and approximate physics. One of the most common approaches for game development is using Eulerâs Method. (If youâre interested in other methods then check out Verlet Integration and the Runge-Kutta method).
Explaining exactly why Eulerâs method works is outside of the scope of this explanation, but at the end of the day implementing Eulerâs method in code is actually really easy! The new update method would look like this.
def update(delta_time):
if pressed(JUMP_BUTTON):
velocity.y = -jump_velocity
location.y += velocity.y * delta_time
velocity.y += gravity * delta_time
We simply rearranged the location and velocity lines and multiplied each of them by delta time. Now the player jumps consistently across different frame rates!
This is great, but what if we want to have more control of our jump code. For example, what if we want the player to jump n amount of pixels high in k amount of time? Well now that we are using an integrator we are actually simulating real-world physics, and we can use fundamental kinematic equations to achieve this.
So we want to manually specify a jump_height and jump_duration variable in our code. For this example letâs have the player jump 32 pixels high in 1 second. We also need to calculate what value gravity and jump_velocity must be to reflect the jump_height and jump_duration variables.
First we can solve for gravity by using this kinematic equation for a free falling object.
Now that we found gravity we can use another kinematic equation to find what the initial jump velocity should be.
That wasnât too bad. Here is what our new initialize method looks like.
def initialize():
jump_height = 32
jump_duration = 1
gravity = 2 * jump_height / (jump_duration * jump_duration)
jump_velocity = gravity * jump_duration
velocity = Vector2(0, 0)
location = Vector2(0, 0)
We can check if all this is correct by graphing out our acceleration, velocity, and position functions. We can do some quick calculus to find these functions given a constant acceleration.
Now we can visualze these functions and see if manipulating jump height and jump duration works as intended.
Well looks like everything works! Here is what our final code looks like.
def initialize():
jump_height = 32
jump_duration = 1
gravity = 2 * jump_height / (jump_duration * jump_duration)
jump_velocity = gravity * jump_duration
velocity = Vector2(0, 0)
location = Vector2(0, 0)
def update(delta_time):
if pressed(JUMP_BUTTON):
velocity.y = -jump_velocity
location.y += velocity.y * delta_time
velocity.y += gravity * delta_time
Quantum Caverns is out!
After a couple of sleepless nights, we just managed to turn the game in on time. Overall, it is far from complete, but Quantum Caverns is an enjoyable experience on the GameShell as is.
Iâll be the first to admit the code got really messy towards the end, but make sure to check out the gameâs inner workings at Quantum Cavernâs Github page nevertheless.
We are going to take a break for a while, but expect bug fixes and more levels in the coming days. Iâm also going to make at least two more devlogs on some useful tricks we learned in the home stretch.
Anyways, best of luck to everyone who entered! I cannot believe the turnout this quarter. I canât wait to try all the submissions out!
