Dev Blog The Fifth - Nothing Special, No Sirree

Greetings. As you know, it’s Bites. This is the dev update.

My apologies for the somber tone. I have been playing Minecraft recently, and I suffered a great loss…

Racecar's Grave

While we’re on the subject, I wonder if there’s anything fun from Minecraft that could fit well in Rolled Out…?

Maybe we can have a party game where the floor is made of blocks that fall out from behind you while you roll.

Yes, yes! Thinking about it is already helping me move past this grief. You won’t be forgotten, Racecar!!!

Let’s jump into the update.

I’ve been very hard at work on new stages. Here’s just a small sample of what I’ve created in the past few weeks!

stage1
stage2
stage3
stage4

It might be a little difficult to tell, but those are wormholes in that last stage. Look forward to it!

There’s a lot more I could show you, but I think it’d be more fun if I didn’t share every single stage in the game before it comes out.

With that out of the way, here’s a fun writeup from the one and only… CraftedCart!

The quest for FCurves

If you’ve ever dabbled with computer animation before, you may be familiar with the idea of function curves, and how awesome they are. You may recall from post #2, there was a small section on curves.

Blender's graph editor

Well, we now have FCurves in Rolled Out! There’s no editor or even a visual representation for it yet, just code to make curves and get values from them, so instead I’ll just use Blender to show you the interpolation methods we support (how the red line is smoothly or not-so-smoothly joined between the different keyframes).

This, or to be more specific, the Bezier curve part of it, took… a surprising amount of head bashing, likely because I’m not that mathematically inclined.

Problem: How do you get a Y (value) for a given X (time) position for a cubic Bezier curve?

Hey if you found this, looking for an explanation for the problem, this is not the place to be. I may be able to provide a few resources but I don’t fully understand how this works. Thankfully we have Stack Overflow. ;P

If you’re a mathematician, I apologize in advance.

Now with those disclaimers out of the way, let’s start.

If you cast your mind back to high school math, you may recall graphing equations, often in the form of y = something to do with x.

A quadratic graph

These kinds of curves are easy enough to find y positions for a given x, just substitute the x‘s and bam you’ve got an equation.

The equation for a cubic Bezier curve is a bit different from that - Bezier curves are parametric. This means instead of being able to input an x value and get a y value out of a function (or the other way round), we input a t value and can get both x and y values out of a function, where t is the position along the curve we want to find.

A Bezier curve animating as t increases

Thanks for the GIF Phil! Source: https://commons.wikimedia.org/wiki/File:B%C3%A9zier_3_big.gif

As you may imagine, this… makes it tricky to find a y for a given x. And thus began the search for… however you do this thing. Thiiis is where stuff starts to break down.

I figured I’d start by taking a look at how Blender handles it. I cloned the source code and found the code for how it evaluates Bezier animation curves, which is composed mostly of two functions: findzero, and.. uhh.. berekeny. I’ll spare you the effort of trying to figure out what that means - “bereken” is Dutch for “calculate”, so this means “calculate y”. That was fun to figure out… Anyways I could not even begin to make sense of the math inside of the functions - one or two letter variable names and a lack of comments make for even more fun, but after a bit more research I started to gather that findzero tries to find a t value for a given x, and berekeny finds the y value for a given t [citation potentially needed, I don’t trust myself]. If you want to see if you can make sense of it yourself, the source code is at https://developer.blender.org/diffusion/B/browse/master/source/blender/blenkernel/intern/fcurve.c.

Attempt number two: Let’s see how Firefox engine handles it. I figured it must have some code to handle this given cubic-bezier is a thing in CSS, the language used to style web pages. Some more searching around code later and I found this. It seems like Firefox takes a bit more of a brute-force approach, continuously trying different t values and narrowing it down until it is close-enough. I’m sure this would have worked just fine for our purposes, but it just didn’t quite sit right with me, having to brute-force the answer, so I decided to look at…

Attempt number three: How does Chromium handle it? As it turns out, near identical to Firefox.

By this point I was starting to get a tad irritated. Thankfully, this was also the point where I found this book: A Primer on Bézier Curves. Oh would you look at that it even has a section called “Finding Y, given X”. Digging a bit deeper, I found that the person who wrote this section of the book also wrote this Stack Overflow answer. Better yet, this answer even had a code sample. I’m still not going to claim I fully understand how this function works, but I can understand it far better than Blender’s one. Thank you very much Mike. From this I could finally get t value, by inputting the x I want to find t for, as well as the left anchor point x, left handle x, right handle x, and right anchor point x. To top it off, I could plug this in to the Bezier formula and get a y value for a t.

Making Unreal development on Linux easier

On a less frustrating note, I’ve added a compile_commands.json file generator to UnrealBuildTool. As some of you may or may not know, I prefer to work on Linux. While Unreal Engine 4 does support development on Linux, development on it has been… well I haven’t gotten any of the built-in source code accessors to work to any level of competency; most of this time I’ve just been working with no on-the-fly error checking or autocomplete in my editor (Spac)emacs.

Recently I decided to take a dive into the workings of UnrealBuildTool (UBT for short), the program that co-ordinates the compilation of Unreal Engine and its projects, as well as generate files to assist programmers in their editors. UBT generates UBT makefiles, similar to make makefiles, but for UBT. These makefiles contain compilation commands for every source file in a target. From this, I can extract out the commands, filter out the ones pertaining to precompiled headers, and shove them all into the compile_commands.json file.

So what makes these JSON files so awesome? The language server protocol (or LSP for short) is what! All of the C++ LSP servers I’ve found take this file as an input. Instead of having editor-specific plugins or IDEs dedicated to working with certain programming languages, LSP makes it such that a server program runs separate from the editor which handles parsing C++ code, yelling at me when I stuff up, fetching documentation, autocomplete, etc. My editor will have an LSP client plugin, and the two programs can communicate over a common protocol. If I ever desire to switch editors, all it needs is another LSP plugin and I can get the same coding assist features from the same servers.

I use ccls as my C++ language server, which parses the JSON file to be able to help me code. I did however need to add a few workarounds (which I added under a -ccls switch to UnrealBuildTool) to convince it to index Unreal and our game: response files (that thing where you can specify additional command line arguments in a file) on the command line didn’t seem to be expanded out, so I needed to do that manually; and ccls didn’t seem to like -include options once the response files had been expanded, so I resorted to gathering up all included files and stuffing them into a .ccls file, which ccls can also use for configuration. Not the most ideal solution (since all include switches will apply over all files when indexing), but I think it’s the best we’ve got for now.

And now finally, I can have this!

Autocompletion in Emacs

Also documentation loopup

I won’t say it’s perfect though. Better than nothing however.

Some errors showing up with valid code

I’ll throw my UnrealBuildTool tweaks up on GitHub once I’ve cleaned up the code a tad, and confirmed it works on the latest version of Unreal. I’ll also edit this post when that’s there.


And that’s that for today.
Thank you for sticking with us. I’m going to try my best to get the pace to pick up, so we can give you all an awesome game sooner, rather than later.
See you next update!