clockworkpi

Quantum Caverns Devlog

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. :stuck_out_tongue_winking_eye:

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.

4 Likes

I feel like there might be a lot of “Quantum” games lol. The working title for my current idea is “Quantum Displacement”.

1 Like

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.

quad_tree_off

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.

quad_tree_on

WOW :scream: 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!

2 Likes

lol hey great minds think alike :stuck_out_tongue_winking_eye:

1 Like

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. :man_shrugging:

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.

1 Like

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. :grin: 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.

1 Like

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!
collision_testing

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.
jump_60fps

This is fine, but check out what happens if I lock the framerate to something else like 30 fps.
jump_30fps

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! :grin:

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.

image
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.

a(t)
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.

velocity_math

(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!

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.

(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.

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.

Well it’s a start, but we still need to fiddle around.

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!

The Importance of Delta Time (Part 4)

Tying it all together

We set out to find a parabolic function where the maximum is 32 and the zeros are 0 and 10. After some quick math we ended up with a(t), a function that achieves just that.

hello

If we wanted the player to jump 32 pixels in the air in 5 frames and fall back down in another 5 frames then we are all set. Although, what happens if we aren’t happy with these values, and want to tweak them later on? Wouldn’t it be cool if we just had a general purpose function where you could plug in any jump height and jump duration and everything would just work? Well good news, we can do just that!

Recall that we originally wanted the player to jump 32 pixels high and for the player to complete their jump in 10 frames. Both of these values showed up in the final function a(t), but there is also this weird 25 in the function. The 25 is actually the maximum value of the function b(t). Now that we know what each value corresponds to we can start to create the general purpose function.

Okay this is looking promising, but having to find the maximum of a separate function isn’t very elegant. We can combine b(t) into a(t) by finding an equation where when given the duration we can get the maximum of b(t). Finding this equation would involve taking the derivative of b(t), setting it to zero, solving for t, plugging t back into b(t), and simplifying that equation.

Now that we don’t need that extra b(t) let’s see the new function.

Let’s plug this into a graph and see if it works!


(The sliders j and d represent jumpHeight and duration respectively).

Well look at that, it looks like everything works! Although, we aren’t quite done just yet. For starters, we still need to find the new velocity and acceleration functions. That’s not too hard, we can do that first.

more_math
Now that we have the acceleration and velocity function we can apply this to our code. The acceleration function contains our new gravity value, and the second part of our velocity function is our new jump_velocity value. Although, there is one last step we must do before we can apply this to our code.

So jumpHeight is simply how many pixels we want the player to jump, but what exactly would duration be? Well right now duration is the amount of frames the jump takes to complete. If I taught you anything then you should know that leaving duration in terms of frames is going to cause inconsistencies across different frame rates.

Duration should not be measured in frames. Instead, duration should really be a familiar measurement of time. So how can we tweak duration to represent, for example, milliseconds?

To achieve this we need to multiply how long the jump is in milliseconds, convert that to seconds, and then multiply that by the amount of frames in one second. Wait, but how do we know how many frames are in one second? Easy, that’s just the game’s frame rate! Okay but how do we get the frame rate?

Here is were delta time saves the day!
duration
Let’s use our new duration calculation and graph it to see if the math checks out.

final_function
(The sliders j, m, and f represent jumpHeight, milliseconds, and frameRate respectively).

Is this working?

Well lets analyze what’s happening. The maximum point is always at y = 32 despite changing the frame rate, so that means the jump height is consistent across different frame rates. When the frame rate is 30 the jump ends in 30 frames, but when the frame rate is 60 the jump ends in 60 frames. Is this behavior correct?

Yes, everything is working correctly! The jump should take 1000 milliseconds to complete, and 1000 milliseconds is just 1 second. So if the game is running at 30 fps then the jump ending in 30 frames means the jump ends in 1 second. If the game is running at 60 fps then the jump ending in 60 frames means the jump also ends in 1 second!

Wow we finally did it! Okay let’s apply this to our original code.

def initialize():
    jump_height = 32
    jump_duration = 1000
    gravity = 0
    jump_velocity = 0
    velocity = Vector2(0, 0)
    location = Vector2(0, 0)

def update(delta_time):
    frameRate = 1  / delta_time
    duration = (jump_duration / 1000) * frameRate
    gravity = -8 * jump_height / (duration * duration)
    jump_velocity = 4 * jump_height * duration

    if pressed(JUMP_BUTTON):
        velocity.y = -jump_velocity 

    velocity.y += gravity
    location.y += velocity.y

This code snippet fixes inconsistencies across different frame rates, and even lets you explicitly change the height and duration of the player’s jump.

Quantum Caverns works alright on the GameShell now. :relieved:
jump

3 Likes

Quantum Caverns is out! :grin:

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!

Crab

2 Likes