Archive

Programming

Godot is a reasonably light-weight, highly featured, open-source game engine that's been in development for more than a decade. I started playing with it not long after it was mentioned by TheHappieCat on YouTube and found myself enjoying it in most every respect. The editor was, as the tagline implied, small and lightweight while being very feature complete. Version 3.0 brought with it high-fidelity visuals (a la PBR), a new physics system, and a slew of other additional enchancements. Fun on most every front.

The one area where I found Godot most lacking was GDScript. Coming from languages like Python and Kotlin and Java and C, I found it to embody most of the pieces I didn't like about Python with none of the things I did like. It was just similar enough to cause problems and be unintuitive. As good as the documentation is, the language is fundamentally too limited for the kinds of things I like to do in games. (Has anyone written a matrix library for GDScript?)

Enter GDNative: what appears to be the ability to simply build a DLL and then call the methods from GDScript! We're saved!

Almost.

GDNative doesn't provide a way to call arbitrary methods in a DLL or .so and, from what I can gather in the IRC and Discord channels, there's no intent to include Dylib or another system for gathering those. Instead, there are key methods which are exported and need to be defined so that the DLL can register with Godot. The problem then is nontrivial, but it's not impossible.

What We Want:

There are plenty of paths that let us go from Kotlin to Godot and it's worth describing the desired output before we enumerate them.

We could want nothing more than to produce some exported methods that take standard data types and return standard data types. This was my desired use case. I had two methods I wanted for my game, Terminus. Those were compile(string code, byte[] memory) that accepted a string and compiled it into instructions for the virtual CPU. I didn't need to define any special node type or interface with other Godot types. I just wanted to put two methods into a DLL and call them.

Another option is interop with the other Godot node types. This means having the ability to subclass Godot's Node and interact with Variants. This provides, arguably, the most versatile of solutions at a small amount of added complexity.

Options:

The most obvious path forward is to have Kotlin Native produce a DLL that we can import as a native library. When I last tried this I ran into an issue where it's not possible to define the name of a method in the DLL with Kotlin Native**. I considered then building a static library and having a small C wrapper that defined the required nativescript_init method. This, too, turned out to not be an option. Kotlin Native can produce a KLIB library file, but not a lib. Finally, I turned to building bytecode with LLVM and then using that in place of a static library. The process for setting up LLVM in Windows is straightforward, but between fighting with MSVC, not being able to find link.exe, and a handful of other technical issues, I thought this would be too cumbersome a path for the average user.

The next path, then, is to use the cinterop tool along with the Godot header files to produce a klib file that can be used by Kotlin native. With a little fandangling, this can be wrapped up and shipped nicely as just the KLib and a build.gradle file, allowing for a quick and painless way of producing nodes with Kotlin. This is the approach I'm trying to implement right now, and it remains to be seen how trivial the process is.

** Note: As of Kotlin/Native 0.6.0, exporting function names with @CName is possible. One must simply figure out how to import kotlinx.cinterop. I'm currently working on that.

UPDATE: 2018/03/26: This issue is now tracked on YouTrack at https://youtrack.jetbrains.com/issue/KT-23455

It's done enough!

tl;dr: Download a Runnable Jar Here

Standalone PC/OSX builds are pending.

Kudos to Peter Queckenstedt (@scutanddestroy) for doing an amazing job on the Proctor, Hillary, and Trump.

Post-Mortem:

‚ÄčThis has been a positive experience. I love games that actually have nontrivial interactions in them and completely open-ended text inputs. I'm a fan of interactive fiction, but hate that feeling when you're digging around and grasping for action words like some sort of textual pixel-hunt.

The language processing systems in DS2016 aren't particularly complicated, but they're more simple than I'd like. In the first week of the jam I started writing a recurrent neural network to parse and analyze the sentiment of the player's comments. I realized, perhaps too late, that there wasn't enough clean data for me to use to accurately gauge the sentiment and map it to social groups. Instead, I wrote a basic multinomial naive bayes classifier that takes a sentence, tokenizes it, and maps it to 'like' or 'dislike'. Each group has its own classifier and tokenizer, so I could program demographics with a base voting likelihood and give each of them a few sentences on the "agrees with" and "disagrees with" sides, then have them automatically parse and change their feelings towards the player.

A usability change that came in later than one would guess was as follows: I had originally grabbed the demographic with the largest emotional response to a comment and displayed them with the sentiment change. Unfortunately, this turned out to over-exaggerate one particularly noisy group. Another change, shortly thereafter, was masking the exact amount of the change. Instead of saying +1.05% opinion, it simply became "+Conservatives" or "-Hipsters". This was visually far easier to parse and I think helped the overall readability of the game.

There is still a call to add some more direct public opinion tracking in the game, letting players know in closer to real time how they're doing among the demographics. I may find it in myself to introduce that.

The last interesting aspect that I noticed during playtesting: I had slightly over-tuned the language models to my style of writing. Instead of opining on matters at any length, people were making enormous run-on sentences which appealed to every demographic at the same time. These statements, often self-contradictory, were not something I expected or handled well. I found the game to be rather difficult, but it looks like playtesters had a dandy time making the states go all blue.

Godot is a really honkin' neat engine. If you haven't tried it, I strongly recommend playing around with it. Take a look at https://godotengine.org.

I found myself in a position where I needed to build a native library. Here's my experience doing that on Windows. I can't attest to the accuracy or repeatability of these steps, but I'm leaving them here so I can revisit them when I need to. Just remember: GDNative is a way to call into shared libraries from Godot. NativeScript is the other way -- native code that can call into Godot.

Overview:

Prerequisites and Setting Up

You will need:

  • Microsoft Visual Studio
  • Python 3 + pip (or scons installed)
  • Git
  • A really good reason to need to build a native library

Godot is built with Scons. The process is relatively painless compared to the dependency hell that you can get into when building other tools, but it's not without challenges. I'm going to assume that you've installed Microsoft Visual Studio and can run the following on the command line:

cl.exe

Your output should be this:


(scons) D:\Source\TerminusExperiment\CPU_v1>cl
Microsoft (R) C/C++ Optimizing Compiler Version 19.00.24215.1 for x64
Copyright (C) Microsoft Corporation. All rights reserved.

usage: cl [ option... ] filename... [ /link linkoption... ]

If you don't see that, you'll probably need to search for a shortcut to "VS2015 x64 Native Tools Command Prompt". That will, in turn, include a script to call the following bat file: "%comspec% /k ""C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\vcvarsall.bat"" amd64"

CHECKPOINT: Visual Studio is installed.

Next is Scons. I'm not going to go into any depth about installing and setting up Python on Windows, but I've had more luck using Chocolatey than Anaconda. Install Python 3, pip, and virtualenv.

Make a new virtual environment somewhere with python -m venv my_scons_venv (Mine is called just 'scons' and is stored in C:\Users\Jo\virtualenvs).

Activate the new virtualenv. If you're on Windows, that means calling C:\Users\Jo\virtualenvs\scons\Scripts\activate. (This is approximately equivalent to Linux or OSX's . ./scons/bin/activate)

Install scons in your virtual environment. pip install scons

CHECKPOINT: Scons is installed. You can build Godot.

Downloading and building Godot with Scons

Now we'll pull the Godot source. There may be a way to make do without this, but I've not had luck.

I keep my projects in D:\Source. I opened my command prompt and did git clone https://github.com/godotengine/godot.git

Get some coffee while the repo comes down.

Change into the Godot directory. Build Godot with scons platform=windows.

Wait.

You should see your executables in "D:\Source\godot\bin". Try double clicking on the tools.64.exe if it's built. Fun, eh?

CHECKPOINT: Godot is built from sources.

Building The CPP Shared Library

Go back to your source folder. For me, that's "D:\Source". Now we'll clone godot-cpp so we can build our .lib file. git clone https://github.com/GodotNativeTools/godot-cpp

We're going to edit the SConstruct file.

I set my "godot_headers_path" to godot_headers_path = ARGUMENTS.get("headers", os.getenv("GODOT_HEADERS", "D:\\Source\\godot\\modules\\gdnative\\include"))

Note that it might be necessary to use double backslashes because Windows uses the wrong slash direction for their paths. Note that godot_headers_path points into the Godot build we cloned and into the GDNative module's include folder.

Update the "godot_bin_path" to point to our executable. godot_bin_path = ARGUMENTS.get("godotbinpath", os.getenv("GODOT_BIN_PATH", "D:\\Source\\godot\\bin\\godot.windows.tools.64.exe"))

Invoke scons platform=windows generate-headers=yes.

There will be a short span while the lib is created. When it's all done, check your bin folder. You should see "godot_cpp_bindings.lib".

CHECKPOINT: You've got the godot_cpp_bindings library built

Make a new folder. I put it in my project directory, "D:\Source\Terminus\CPU_v1\". CPU_v1 will be my native module. My game involves doing some CPU emulation.

Into that directory, copy D:\Source\godot-cpp\include. Also make a folder called 'lib' and put "godot_cpp_bindings.lib" in it.

Your directory structure should look like this:

D:\Source\TerminusExperiment\CPU_v1
- include
 |- core
 | |- AABB.hpp
 | \- ...
 |- AcceptDialog.hpp
 |- AnimatedSprite.hpp
 \- ...
- lib
 \- godot_cpp_bindings.lib
- src
 \- init.cpp (THIS IS YOUR CPP FILE!  Get a sample one from [x].)

Finally, we can build our CPP file using this command in the root of CPU_v1: cl /Fosrc\init.obj /c src\init.cpp /TP /nologo -EHsc -D_DEBUG /MDd /I. /Iinclude /Iinclude\core /ID:\Source\godot\modules\gdnative\include

Make a good note of those trailing '/I's. The specify the include folders. If you get a message about "Missing whatever.h" then you've got one wrong.

/Fosrc\init.obj specifies the output object. /c src\init.cpp specifies our source file.

CHECKPOINT: We have our .obj file from our init.cpp!

Last step, we can link our two objects together. cl /LD lib\godot_cpp_bindings.lib src\init.obj /link /DLL /OUT:init.dll

This will take our lib and our source object and will produce init.dll -- something we can use in Godot's Native library.

Shout out to MathJax/ASCIIMath for being awesome.

If you don't care about any of the details, you can click here to jump to the code.

Motivation and Problem Statement

We're launching a ball with a great deal of force at a wall. We can describe our wall with four points in 3D space: `a = [x, y, z]`, `b = [x, y, z]`, and so on for `c` and `d`. Our ball travels along a straight line path called `bbL`. It's origin is `p_0` and it's moving towards `p_1`.

There is some redundancy. I picked four points for our wall because it makes intuitive sense, but we're going to be applying this method on only three of those four points, the triangle `Delta abc`. If you feel the compulsion to run this on a square, you can easily extend the approach to two triangles.

Let's begin with describing our plane. There are a few different formulations of the plane in 3D. For our purposes, the 'normal + offset' configuration is the easiest. We'll figure out the normal (think a straight line pointing out of the wall) from our three points.

A quick review of dot and cross

I'm going to assume that the idea of cross-product and dot product are familiar, but here's a very quick review in the interest of completeness.

`a = (x, y, z)`
`b = (x, y, z)`

`a o. b = a_x * b_x + a_y * b_y + a_z * b_z`

`a ox b = [[a_y*b_z - a_z*b_y], [a_x*b_z - a_z*b_x], [a_x*b_y - a_y*b_x]]`

Note that the dot product is a scalar and the cross product is a vector.

One other thing to realize: the dot product of orthogonal vectors is zero. The cross product of two vectors produces a vector that's orthogonal to both. If that's not clear, don't worry.

The Normal

Let's get back to the wall. We've got `a`, `b`, and `c` and we want to figure out the normal. If these three points make up an infinite plane, then the normal will jut out of it straight towards us. Recall (or look at the notes above) that the cross product of two vectors makes an orthogonal vector. We can convert our three points to two vectors by picking one to be the start. Let's say our two new vectors are `r = b-a` and `s = c-a`. That means our normal, `bbN` is just `r ox s`! And since we picked `a` as our origin, our formula for the plane is `(P - a) o. bbN = 0` for some point `P`. Put differently, if we have some point `P` and it's on the plane, when we plug it into that formula along with `a` and `bbN` we'll get zero.

Enter: The Line

We mentioned before that our line `bbL` has a start point of `p_0` and an end of `p_1`. This means if a point `P` is on the line, then there's some value `t` where `P = p_0 + t*(p_1 - p_0)`. Now comes the fun part. We want to figure out where this line intersects with our plane (if it does). To do that, we'll plug in the formula for a point on our line into the formula for a point on our plane.

`(P - a) o. bbN = 0` // Point on plane.
`(((p_0 + t*(p_1 - p_0)) - a) o. bbN = 0` // Replace `P` with the formula.
`(((p_0 + t*(p_1 - p_0)) o. bbN - a o. bbN = 0` // Distribute the dot.
`(((p_0 + t*(p_1 - p_0)) o. bbN = a o. bbN` // Add `a o. bbN` to both sides, effectively moving it to the right.
`p_0 o. bbN + t*(p_1 - p_0) o. bbN = a o. bbN` // Distribute again.
`t*(p_1 - p_0) o. bbN = a o. bbN - p_0 o. bbN` // Subtract p_0 o. bbN from both sides.
`t*(p_1 - p_0) o. bbN = (a - p_0) o. bbN` // Pull out the dot product.
`t = ((a - p_0) o. bbN) / ((p_1 - p_0) o. bbN)` // Divide by `(p_1 - p_0) o. bbN` on both sides.

Our final answer, then, is

`t = (bbN o. (a - p_0))/(bbN o. (p_1 - p_0))`

If the denominator is zero, there's no solution. This can happen if the plane and line segment are perpendicular. Otherwise, we can plug t back into our line equation to get some point on the plane!

Inside the Triangle

We have a point `P` that's on the plane and the line, but is it inside the triangle defined by `Delta``abc`? There's a fairly easy way to check for that. If you've got a triangle, as we have, then any point in that triangle can be described as some combination of `a + u*(b-a) + v*(c-a)`, where `u` and `v` are in the interval `[0,1]`. If `u` or `v` is less than zero, it means they're outside the triangle. If they're greater than one, it means they're outside the triangle. If their sum is greater than one, it means they're outside, too. So we just have to find some `u` and `v` for `P = a + u*(b-a) + v*(c-a)`.

Systems of Equations

It might not seem possible. We have two unknowns and only one equation. However, there's something we've overlooked. `P = a + u*(b-a) + v*(c-a)` actually has three equations. We've been using a shorthand for our points, but `u` and `v` are scalars. Really, we should be looking for a solution for this:

`P = a + u*(b-a) + v*(c-a)`

`P - a = u*(b-a) + v*(c-a)`

`[[b_x - a_x, c_x - a_x], [b_y - a_y, c_y - a_y], [b_z - a_z, c_z - a_z]] * [[u],[v]] = [[P_x - a_x], [P_y - a_y], [P_z - a_z]]`

BAM! Two unknowns, three equations. You might also recognize this to be of the form `bbAx=b`. You'd be correct. If there were three unknowns and three equations, we could have been fancy and used Cramer's Rule. It's not a hard thing to solve, however.

`bbbAx = b`
`bbbA^TbbbAx = bbbA^Tb` // Start by making `bbbA` a square matrix.
`(bbbA^TbbbA)^-1 bbbA^TbbbA x = (bbbA^TbbbA)^-1 bbbA^T b` // Since it's square, it probably has an inverse.
`bbbI x = (bbbA^TbbbA)^-1 bbbA^T b` // Cancel the inverse.
`x = (bbbA^TbbbA)^-1 bbbA^T b` // Simplify.

And now we've got x in terms that we know (or can calculate)!

Inverse of a Square Matrix

`(bbbA^TbbbA)^-1` looks like a mess, but it's not as bad as it seems. I'm going to multiply it out and simplify it again.

`bbbA^T bbbA = [[b_x - a_x, b_y - a_y, b_z - a_z],[c_x - a_x, c_y - a_y, c_z - a_z]] * [[b_x - a_x, c_x - a_x], [b_y - a_y, c_y - a_y], [b_z - a_z, c_z - a_z]] = ` an unholy mess.
To cut down on that, I'm going to let `b-a = r` and `c-a = s`. If we rewrite the above using that, we get something more manageable.

`bbbA^T bbbA = [[r_x, r_y, r_z],[s_x, s_y, s_z]] * [[r_x, s_x], [r_y, s_y], [r_z, s_z]]`

Since we're basically multiplying things component wise, we can reuse our code for dot product!

`bbbA^T bbbA = [[r o. r, r o. s], [r o. s, s o. s]]`

That's an easy to calculate 2x2 matrix. As an added bonus, there's a closed-form solution for the inverse of a 2D matrix. You can probably work it out yourself easily enough, but we've gone through a lot already, so here's the solution:

`if bbbA = [[a, b], [c, d]] => bbbA^-1 = 1/(ad-bc) [[d, -b], [-c, a]]`

So we calculate `r o. r`, `r o. s`, and `s o. s` and plug them into the inverse matrix. Then we multiply the inverse and `bbbA^Tb` et voila: we've got our values for `u` and `v`.

`bbbA^T bbbA = [[r o. r, r o. s], [r o. s, s o. s]]`

I'm running out of letters!

`alpha = r o. r`
`beta = r o. s`
`gamma = r o. s`
`delta = s o. s`

`(bbbA^T bbbA)^-1 = 1/(alpha * delta- beta * gamma) * [[delta, -(beta)], [-(gamma), alpha]]`

And in all its glory:

`(bbbA^T bbbA)^-1 bbbA^T b = 1/(alpha * delta - beta * gamma) * [[delta, -(beta)], [-(gamma), alpha]] * [[r_x, r_y, r_z],[s_x, s_y, s_z]] * [[P_x - a_x], [P_y - a_y], [P_z - a_z]] = [[u],[v]]`

Whew.

Closing: Just Show Me The Code

The moment for which you've been waiting. Here's an EMScript6 implementation of the Point and Triangle objects.

A Gist is available on GitHub at https://gist.github.com/JosephCatrambone/578c22f6e507dc52420752013a45b92b.js or you can play with this interactively on JSFiddle: