Dev Blog #2 - Onward we go.

Welcome back!

The last couple weeks have been quite productive. I’d put more jokes into this post, but I’ve had a long day - give me a break!! I’m going to keep it short, sweet, and to the point. I can’t say whether my compatriots will do the same, though… apparently, they’ve both made enormous writeups, with lots of juicy details.

Let’s jump right in!

Fun Art Stuff

Laurence (@iguanamouth) and myself have been working on some wonderful concept stuff for some new and upcoming worlds that will be featured in the game. Here’s some super sketchy stuff - expect to see some more detailed artwork (and potentially an ingame draft) somewhat soon!

Here’s a proof of concept for one of our upcoming backgrounds - one where the stage takes place on a moving path through the world.

It won’t look anything like this, most likely! This is just to prototype the effect of the level moving through space.

One of our other developers has a big ol’ writeup to share, now.

Take it away, CraftedCart!

Big changes - slow progress

So last update I mentioned about really needing to make some cleanups to the code base. There I mostly focused on just generally refactoring the code to remove our synchronization and multiplayer woes.

Notably, one of the points I briefly mentioned last time was…

Baking fixed stage transforms into the vertex data on import, rather than transforming it after-the-fact (which makes for some fun for the physics crew)

I figured I’d start the cleanups by trying to fix stage import transforms, and then… well, you know how things go sometimes where one thing leads to another, which leads to another.

Redoing stage loading pretty much entirely is something that had been planned for a while. Since we were going to chop up the code base anyway, I decided that now would be a good time to start doing this.

New stage config format!

Oh yeah I wasn’t kidding when I said redoing this pretty much entirely.

Before I get into the details of what we have in the works for the new config, let’s go over what was wrong with our current one. If you’re not familiar with how the current configs look, here’s a couple snippets from a static and an animated one.

Why is it bad?

One: It’s XML

XML is… not great for configs for a couple of reasons. Firstly XML is slow to parse… like really slow. A while back I did a few benchmarks just to see how slow parsing XML is, compared to a couple other formats. I took all three-hundred-and-something of our XML stage configs and converted them (badly) to JSON and MsgPack. These were all compressed with gzip as well as we were experimenting with ways to save on file size.

The test was simple: I asked Python to decompress and parse every stage config as quickly as it could. In between all the tests I cleared the disk caches to ensure that I/O speeds were more-or-less fair for every run.

Format	Time to parse
.xml.gz	9.14s
.json.gz	3.65s
.msgpack.gz	2.77s

Yup. XML is slow alright.

In addition, XML is insecure. There are ways to exploit the XML format that can easily cause a computer to start hurting. One of the more notable ones is the billion laughs attack. XML lets you define “shortcuts” that can expand out into multiple other entities when parsing, which can expand again, and again, and again, etc. As you may imagine, this makes easy to create a billion entities from just a few, consuming large amounts of memory and CPU time to parse.

“Well just download stages from trusted sources,” I hear you say. Well hold on a few moments before you try to dismiss me. Our server will have to parse configs too, meaning the scope of this attack is not just restricted to you, the player.

Note that there are various other vulnerabilities in XML too, but just this one should be enough to help you understand why it may not be such a good choice. In the end, we settled on JSON. While MsgPack is faster to parse, the difference is negligible and JSON is far easier for humans to read and modify.

Two: There’s no curves

XML uses <pointy angle brackets> everywhere…

Ok terrible joke aside, all keyframe interpolation is linear - there’s no way to define keyframes with other kinds of interpolation with our current configs. This lead to some very, very messy configs with thousands of keyframes, just to recreate animation curves set-up in Blender.

Each one of those orange dots represents a keyframe in the config… and all this just for a simple curve! Wouldn’t it be much better if we could just define this in, say, three keyframes.

Ah! Much better.

Three: Special objects (such as goals) were never defined in the config

If you’ve dabbled with custom stage creation, you may have noticed how the Blender plugin creates objects with special tags in their name, such as [GOAL_B] or [BANANA_S]. These tags aren’t just used by the plugin or as a human-readable name for the objects, the game also uses them to determine where to place these special objects. We knew this was a hack from day one, but this hack has stayed in here since then.

Why is this an issue? Well this means special objects are not very flexible at all. There is no way to define custom properties (such as a wormhole destination) for these objects beyond just making a new [TAG] to represent a variant.

What’s new?

Our proposed new stage config format looks a bit like this at the moment. I’ll go ahead and summarize the more notable changes to spare you the time trying to compare walls of configs yourself.

One: Metadata and stage configs have been combined into a single file

There’s been an amount of confusion about why stages definitions are split over a config and a metadata file. I’ve always just said that the metadata file is supposed to contain information that makes sense to be searched and indexed, with everything else going in the config file, however this line can be quite fuzzy depending on what users may want to search for and be able to see at-a-glance. Heck even I forget whether the bonus flag goes in the config or the meta file.

Combining the two files into one should help reduce the confusion about that goes where. While the new config format does have a metadata section in it, this will be restricted to information that cannot be inferred elsewhere from the config, such as the stage name and tags. A stage layout and objects should still remain the same even if its metadata is completely changed. It also means if I ever wish to index information that can be inferred about the stage (such as the number of goals), only a single file would need to be read.

Two: Stage names and descriptions can now have translations

I don’t think I need to explain why this is a benefit.

Three: The model file has become a mesh library

The config will now define which objects should be placed in the world and all their parent/child relationships, as opposed to the model file dictating the hierarchy and all objects that should exist. This will help when it comes time to implement the in-game stage editor, as now a config can be used to refer to objects without a bundled model file, such as meshes built-in to the game.

Four: Materials are now defined in the config

The game will be able to provide multiple base materials (Such as opaque textured, masked transparent, translucent, to name a few examples) with various parameters that can be overridden in the config. The config will also now define what materials different meshes should use. This again will help with an in-game stage editor to enable easy skinning of built-in meshes.

Five: Animation curves

Heck yeah this should simplify configs a lot if I can just copy keyframe data from Blender without needing to write out a bajillion lines. At the very least, I’d like to support Bezier and linear curves given that the majority of animations you may typically create will be using these curves.

What’s been going on in the code?

Unsurprisingly, I’ve been writing code to parse this new config format. I’ve also been writing a lot of data structures to contain information about the new configs, and a lot of validation code such that a malformed config won’t crash the game any more.

One of the biggest changes in the code is that I can no-longer rely on UObjects. Unreal Engine provides these convenient objects which take care of a lot of work for you, such as memory management, and bridging the gap between C++ and Unreal’s Blueprint visual scripting. If you’re not familiar with Blueprint, an example showing confetti particles spawning on-goal is shown below.

Unfortunately UObjects are unsafe to use outside of the main game thread, as those automatic memory management conveniences start losing track of things when it comes to multiple threads (It would be disastrous if Unreal decided to free some memory I was in the middle of using). I would really love to have the game be able to load stages on a separate thread, meaning I can pre-load bits of the next stage when playing through a course, as well as hopefully speeding up the incredibly slow stage indexing on first launch. This means I’m going to need to untie some functionality from Blueprint (which should be a good thing in the end as Blueprints are a pain to collaborate on anyways).

tl;dr

I started trying to clean up stage loading which lead to developing a new stage config. I’m now writing code to take these configs and make them in-game playable stages, which is going slowly due to large amounts of new data structures, validation, and decoupling stuff from Blueprint visual scripts.

Physics

We’re almost done, here… just one last writeup about our physics overhaul, from CraftSpider!

The Basics

Lets talk a bit about real-world physics. In the real world, no matter how fast you move, you’ll never just spontaneously pass through an object – ignoring quantum mechanics, because you are not a particle. The issue is that in a game, physics must be imperfect. Most physics engines have a limitation in their tick rate - everything is only calculated so many times per second. This is done, in part, to allow the assumption that most motion is actually a straight line between two points, as that saves us from having to do many different integrals of distance and speed.
So, what’s the downside? Aside from effects which aren’t generally noticeable to the human eye, there is a major fault: if either you or a wall is travelling very quickly, it’s possible for you to pass straight through an object. You can start a tick outside an object, move very quickly through it, then at the end still not be colliding with it. This phenomenon is referred to as ‘tunneling’, and in the context of most games, not a big deal. But in Rolled Out! even in regular gameplay, the stage and the ball can move very fast. So, we need a ‘continuous’ solution, where no matter how fast any object moves, the ball will never spontaneously pass through it.

What Doesn’t Work

As mentioned before, tunneling is an issue in many physics engines. Given this fact, there have been written a wide variety of solutions - each with their own issues that come with them. I’ll go over some of the things we tried already - this won’t be an exhaustive list, but it should give you an idea of the challenges we’re facing. Before that, a quick list of 3 ideal principles we want for the physics (Not a promise for the final game, just some goals):

• The physics should be independent of framerate
• The physics should behave the same on all systems
• The level creator should not have to worry about colliders, collision bounding, or anything but the level mesh.

Unreal Default

Unreal is a popular game engine, with its own built in physics engine, called PhysX. The biggest drawback with this system is that the physics tick rate is tied directly to the game’s framerate. So if you run the game at 30 FPS, the physics ticks 30 times per second. If you run the game at 60 FPS, the physics ticks 60 times per second. On many computers, this number will fluctuate up and down. As a result, physics can be inconsistent from moment to moment. For example: a weaker computer running at a lower framerate would be more likely to experience the ‘tunneling’ phenomenon, where the ball goes through an object. Also, in general, physics will behave slightly differently. The ball will speed up, slow down, and bounce slightly differently on every computer with different loads.

PhysX Ourselves

So, we can’t use the built-in physics. Maybe we can still use what it gives us? Unreal does expose a lot of more precise functions, to allow you to handle motion and tracing yourself. Our early physics solution used these functions on their own, calling them at a fixed tick-rate. It also calls the sphere trace in a loop, possibly hitting more than one object per tick. One big issue with this is that PhysX still only updates its cache and object info once per frame, so certain math which relies on object velocities is still very inconsistent.

Naive Depen

Depenetration is the act of moving an object which is intersecting with another object. Currently, we do this every time a stage object moves into the ball. This first version, though, was ‘naive’, in that it simply looked for the first object it could find you intersecting with, and pushed you out of it a fixed amount. This works fine for many cases, but breaks down for thin walls. Additionally, the stage is still capable of moving through you, even though you can no longer pass through the stage.

The First Solution

All of this was work done before I began my physics overhaul. Starting out the overhaul, I took those 3 principles above, and attempted to come up with a single solution that would satisfy all 3 constraints. I also wanted to avoid changing the current physics too much, as it would provide faster results to simply retrofit something while leaving the parts that already worked in place. Thus, I decided to aim at the goal of making an ‘intelligent’ depenetration system. This system would check not just for one place where the stage hit you, and not just after the stage was moved. It would sweep the entire stage from its old to its new position, ensuring that if the ball was hit, it would be placed at the logical end point of the stage’s motion. Thus the stage could never pass through the ball, and the ball could never pass through the stage. Though this solution was supposed to be faster to implement than a rewrite from scratch, it took months from when I first conceived of it until it even matched the existing system in terms of ability. Unreal has no good built-in Triangle object, so I added one of those. Then I had to implement the (unoptimized) continuous depenetration algorithm.

function getDepenetration(Ball: Sphere, Mesh: StageMesh, StartTransform: Transform, EndTransform: Transform):
    OutCollision = Null

    for Triangle in Mesh:
        -- Get Triangles used for testing
        StartTriangle = Triangle.GetTransformed(StartTransform)
        EndTriangle = Triangle.GetTransformed(EndTransform)
        if sign of StartTriangle.Distance(Sphere) != sign of EndTriangle.Distance(Sphere) or Absolute(Sphere.Distance(EndTriange)) < Sphere.Radius:
            -- We might have hit it, do a more accurate check
            Steps = (EndTransform.Translation - StartTransform.Translation).Length() / Sphere.Radius
            for i in Range(Steps):
                TestTransform = LerpTransform(StartTransform, EndTransform, i / Steps)
                TestTriangle = Triangle.GetTransformed(TestTransform)
                if TestTriangle.Touches(Sphere):
                    -- There was a collision!
                    Collision = MakeCollision()
                    if Collision.Time < OutCollision.Time:
                        OutCollision = Collision
    return OutCollision or Null

We iterate through every triangle in the stage. For each triangle, if the ball is touching its plane or it may have passed through us entirely, we sweep the triangle by steps of the ball’s radius, checking for a hit. If there was a hit, we detect a collision. If that collision occurred before the current earliest collision, we set it to be the collision returned. Once everything is done, if there was a collision, we return it.

Overall, this solution actually works very well. It can detect most cases, and correctly remove you from the stage in them. However, it was still imperfect. It was a massive pain to fix any errors, as most all bugs were deep within geometric math. There were tons of edge cases which gave anything from slightly to wildly incorrect results. These could have been fixed with some further checks and math, and that was the plan.

It was then, though, that ComplexPlane joined the team.

The New Solution

He and I sat down and talked through the current physics solution. He had an idea, did out some math for himself, then proposed a new idea to me.

If we’re already tracing the ball while the stage remains static, why not work the stage’s motion into that trace? That becomes difficult if we assume it’s the ball moving around the stage, but velocity is relative. We can map the ball as static, add its velocity to the stage’s end transform, and write up a new function that traces the stage itself.

This merges the continuous power of my depenetration with the existing power of the sphere trace for returning times of first collision. And, because it is also continuous and uses a lot of similar triangle tracing principles, the math and logic can mostly be taken straight from my depenetration system. This new system is incredibly powerful, allowing the stage and ball to move in nearly any relative way, and still result in correct motion. Now, the only time depenetration becomes a factor is if the stage squeezes the ball into a space too small for it to fit. This case can be detected, and rules written to prevent it from breaking the physics.

Now, I am in the process of converting this idea to reality. Predictions have held, and in a much shorter time than the first system, physics is already approaching ‘playable’, if not quite to ‘release ready’.

Though there is a lot more to get into with the new system, this article is already getting quite long. Once the physics overhaul is further along, I’ll write up a more detailed explanation of the new physics system.

That’s all for today. I hope you enjoyed this delve into the world of game physics!

See you all on the 15th.