Quake 2 Angelscript: Non-GPL implementations
Detailing the problems and solutions I faced when replacing GPL parts of the Quake 2 codebase.
As I finished my previous post about looking at Quake 2 I suck around the modding community to learn more. It is still fascinating and inspiring to me that they’re keeping this old game alive by constantly breathing new life into it with new ideas. As I was sticking around talking to people I noticed how Quake 1 has a slightly more popular community than Quake 2. Part of this is probably because the two games has a very different style to them, the first game is very gothic and lovecraftian while the second game is more in the direction of science fiction.
Another reason is that Quake 2 has a higher barrier for entry to get started with making your own mods. It is locked behind a native game DLL meaning that in order to modify it you need a native compiler — C for the original and C++ 17 or 20 for the re-release. This setup can be a big hurdle especially for someone who just want to make small tweaks to the game. In contrast Quake 1 uses Quake C, a modding language that has been around and unchanged for 20~ years that has cross-platform compilers just ready to go. Tools like gmqcc or more modern fteqcc makes it easy to get started without messing with older Visual C++ copies or the newer C++ libraries needed to be setup for the re-release.
To solve this problem, Paril who is a long time member of the Quake community and also developer on the official re-release projets at Nightdive created a project to port the entire game code into a fully scriptable version which greatly lowers the barrier of entry for modders to get to work on quake stuff. This project uses angelscript, a cross-platform scripting language that is also used within newer versions of the unreal engine. It greatly lowers the development cycle through hot-reloading where you basically only edit your source files and then reload inside the game to directly see changes. In addition it’s similar to C++ but its still not C++ so hopefully it can be attractive for both programmers and non-programmers.
At first I was kind of dismissive about this project because for me personally it didn’t really make sense to use a scripting language and I have mostly been against implementing support for them when I do game development but after reflecting a bit on it I realised that I am not really the main target audience. The goals of this project is more than just shortening the development cycle for existing developers or increasing velocity. It is to breathe even more life into the modding scene and more importantly give Quake 2 the love it deserves. I got in touch with Paril and asked to be brought on board on the project and I have since late february helped with various things to remove load of Paril to help the project progress faster and since thats what has taken up most of my spare-time programming I decided to do a small writeup on what I’ve done there so far even though its not the most groundbreaking work.
Some parts of the projects still relies on C++ code, we need code to actually load the angelscript and still keep some parts the interface with the game engine. Some of the code that was left is part of the official re-release DLL codebase which is licensed under GPL and we wanted to rewrite as much of this as possible in order to be able to place it under MIT which can make it easier for other engine developers to consider bringing in support for it to their engines. In order to rewrite these GPL implementations you can’t really have seen the existing implementation and you have to write a new one blindly so what we did was for Paril to provide me with an API and I basically filled in the blanks to the best of my ability.
Dynamic Bitset
Some parts of the Q2 code used std::bitset to keep track of some stuff, one thing that I specifically know is to keep track of who picked up a specific item. Since the code is going to be used from Angelscript we needed another wrapper here and we decided to make our own type rather than using std::bitset and since we want it dynamically growable we will call it dynamic bitset because it will adjust it size depending on where the user attempts to set it's bits.
So already from the start we kind of knew the interface for this and just to make things like copying easier we decided to use std::vector to store the data using booleans to represent the bits. So basically what we had is this:
dynamic_bitset(uint n);
dynamic_bitset(dynamic_bitset &in);
dynamic_bitset &opAssign(dynamic_bitset &in);
void clear();
void resize(n);
uint size();
void set_all();
void flip_all();
bool get_bit(uint i);
void set_bit(uint i);
bool opIndex(uint i);
bool any();
bool all();
bool none();
bool opEquals(dynamic_bitset &in);This interface is quite trivial to fill in especially when you're using a std::vector as your backing type, I wont fill all the functions in here because I think its not really anything interesting to discuss there so maybe you can consider that a exercise for the reader.
An interesting challenge for me was what if we cared more about memory? Technically a bool on our system is 1 byte meaning that it has 8 bits that we can controll. Using a full byte per bit like we would in the implementation using the std::vector. Per bit in this implementation we're actually wasting 7 bits that we could make use of if we wanted to.
Lets play around with the scenario where we are using uint64_t as the backing type and just go back to storing it in a normal array. Now per element in the array we have 64 available bits per element and the problem instead turns out to how we access the individual bits inside the storage.
Let's create a small fixed size structure just to play around with, this class just keeps 2 integers for us that we can access its bits out of.
struct bitset
{
uint64_t bits[2] = {0};
}This bitset type has 128 available bytes inside it. If we were to attempt to index a specific bit for example bit number 42 we would first need to find which integer in the bits array that this bit belongs to. This problem is quite trivial because we know the size of each element in the array so the element index is simply one division away: `size_t element_index = target_bit / 64;`
In order to know which bit on the integer that we're trying to access we can use the modulo operator because it would wrap around for values higher than 64. The only last part is to shift the bit into place and use a bitwise & in order to strip away the bits we're no longer interested in and we can without problem access the bit we're interested in:
bool get_bit(size_t target_bit)
{
size_t element_index = target_bit / 64;
size_t bit_index = target_bit & 64;
return (bits[element_index] >> bit_index) & 0x1;
}The same logic can be applied for when we're setting bits:
void set_bit(size_t target_bit, bool value)
{
size_t element_index = target_bit / 64;
size_t bit_index = target_bit & 64;
uint64_t mask = (uint64_t(1) << bit_index);
bits[element_index] = (bits[element_index] & ~mask) | (uint64_t(value) << bit_index);
}The idea here is that we use a bitmask which is a number with only the specific bits we're targeting is set. This mask is used to clear the target_bit inside the bits array, it works by having the target bit set in the `mask`, flipping the mask and using a bitwise and in order to always set the `target_bit` to zero inside the bits array. After that we are using a bitwise and to set the bit to whatever value that was passed into the parameters for the function.
If you're not that used to using the bit operators in the C-like languages this might seem pretty confusing but if we break stuff into smaller steps like this its not that hard to put together.
Something cool with this is that using more C++ features we're not forced to only use a fixed type, we are free to specify both the type and the number of bits we're expected the data structure to have like so:
template<typename T, size_t number_of_bits>
struct bitset
{
static constexpr size_t bits_per_element = sizeof(T) * 8;
static constexpr size_t number_of_elements = (number_of_bits + bits_per_element- 1) / bits_per_element;
bool get_bit(size_t target_bit);
void set_bit(size_t target_bit, bool value);
T bits[number_of_elements] = {};
}In order to now turn this into a dynamic type we can move the number_of_bits to an internal value that we keep track of rather than passing as a template argument. Growing the bits array using realloc or something will not be that expensive as realistically you won't have to do that too many times, and here you can use the same type of technique as almost any dynamic array implementation uses to double the size everytime it needs a resize.
This addition to the original std::vector type was a fun little experiment.
Improving JSON API
The angelscript implementation makes use of json to store its persistent state for save/load. The library yyjson was used as a backend implementation for parsing and creating json strings. This library is takes the numeric values it finds in string format and assigns it to three possible types:
sint - signed integer.
uint - unsigned integer.
real - floating point.
This itself is fine and makes sense because you would expect for example the number -123 to be signed and 123 to be unsigned by default. There is a problem however that arrise when trying to get the numeric values back into a C value because the functions the library provides to check what type a number is gives you back answers based on the three possible values we listed before.
This means that the library would take the number 123 but the function yyjson_is_sint would return false because the parsed number was an unsigned value not a signed value even though this value can fit in our signed types.
To work around this the angelscript code had to make some crazy checks for almost every value it read from the json and it was just extremely cumbersome to work with so my objective was to make the interface easier to work with and less code to write when actually using the library, the point was if we're expecting a uin32_t we should be able to just check if the value fits in that type and if it does just give it back as a uint32_t.
The yyjson wrapper that the Q2 Angelscript project uses has three different types that we need to take into account, they are q2as_yyjson_mut_val, q2as_yyjson_mut_doc and q2as_yyjson_val.
The mut_val and mut_doc are used for writing and they are coupled in the way that you feed a mut_doc a set of mut_val's and then you can allow yyjson to generate a final string based of that. The q2as_yyjson_val type is what you're given back when you're reading a json document.
Getting started with the project I made an outline of what I needed to do. The doc type didn't need any specifiic logic more than just adding additional overloads for all of the different types that we are looking to support. The val and mut_val both needed verification functions that would allow us to check the underlying type, for example: is_int16. And the val type would also need to include a get function that allows you to directly get a value of desired type.
Normally when doing this type of work I don't start out with making generic functions as the requirements become more obvious if you make 1-2 hard-typed functions beforehand but for this specific case I just jumped into making a templated function from the start because all the expected types would be numeric and kind of similar.
So what I did was create a templated function called q2as_type_can_be whose goal is to answer the question: "Can this given type be the same as my templated argument?". This function ended up just more like a wrapper function because both the val and mut_val types uses an union for the three different supported types underneath and to be safe we decided to access the correct value depending on what the type was expected to store.
template<typename T>
bool q2as_type_can_be(yyjson_val* val)
{
if (yyjson_get_tag(val) == (YYJSON_TYPE_NUM | YYJSON_SUBTYPE_UINT))
{
return q2as_type_in_range<T, uint64_t>(val->uni.u64);
}
else if (yyjson_get_tag(val) == (YYJSON_TYPE_NUM | YYJSON_SUBTYPE_SINT))
{
return q2as_type_in_range<T, int64_t>(val->uni.i64);
}
else if (yyjson_get_tag(val) == (YYJSON_TYPE_NUM | YYJSON_SUBTYPE_REAL))
{
return q2as_type_in_range<T, double>(val->uni.f64);
}
return false;
}So basically this function would just re-use the yyjson functionality of getting the expected type and pass it along to the `q2as_type_in_range` function which I just temporarily stubbed out to be defined as:
template<typename T, typename D>
bool q2as_type_in_range(D value)
{
auto max = std::numeric_limits<T>::max();
auto min = std::numeric_limits<T>::min();
if (value <= max && value >= min)
{
return true;
}
return false;
}The templated arguments for this function was made to be T for the target type and D for the given type that yyjson stores.
For the function that val needed to just retrieve a value of specified type i made the decision to not make verification and instead trust the user to have done so beforehand, this made the resulting function be very simple because we can just return the stored value casted to the desired type like so:
template<typename T>
T q2as_get_value(yyjson_val* val)
{
if (yyjson_get_tag(val) == (YYJSON_TYPE_NUM | YYJSON_SUBTYPE_UINT))
{
return (T)(val->uni.u64);
}
else if (yyjson_get_tag(val) == (YYJSON_TYPE_NUM | YYJSON_SUBTYPE_SINT))
{
return (T)(val->uni.i64);
}
else if (yyjson_get_tag(val) == (YYJSON_TYPE_NUM | YYJSON_SUBTYPE_REAL))
{
return (T)(val->uni.f64);
}
return 0;
}The last part and the part I didn't know had to be this exhaustive is the actual check for if one value's type fits inside another. We have numeric types with the three different properties that yyjson captures, unsigned integers, signed integers and floating point numbers. These are all different things and can't always be freely converted between eachother without loss of data and this loss is what we're checking for.
The following cases we can have are the following:
Same types
Signed integer to signed integer
Unsigned integer to unsigned integer
Unsigned integer to signed integer
Signed integer to unsigned integer
Floating point to floating point
Integer to floating point
Floating point to integer
Same types is the first and very trivial case as the value will always fit inside its own type so this is a simple check we can do and return early if it is the case.
if constexpr (std::is_same_v<TargetType, SourceType>)
{
return true;
}When working with checking the types the C++ numeric_limits library has a lot of the helpers that we need to get a jump start. I used it to first check if the source or target types are integers as well as if they're signed or unsigned. I also used it to get the min and max values for our target type that we can use for checks later.
constexpr bool is_target_integer = std::numeric_limits<TargetType>::is_integer;
constexpr bool is_source_integer = std::numeric_limits<SourceType>::is_integer;
constexpr bool is_target_signed = std::numeric_limits<TargetType>::is_signed;
constexpr bool is_source_signed = std::numeric_limits<SourceType>::is_signed;
constexpr TargetType max = std::numeric_limits<TargetType>::max();
constexpr TargetType min = std::numeric_limits<TargetType>::lowest();Having these variables makes it quite trivial to handle the different cases. First check I do is to see if both types are integers. If they are I can check for the different integer cases that we've prepared before.
If both integers are signed we just need to check that the value we've given fits between the min and max value of the target type.
If both are unsigned we just need to check that the value does not exceed the max limit of the target type. Here we do not need to care about the min value because all unsigned integers has the same min value and it cannot go bellow that.
If we're converting a unsigned to signed it is a similar case, we just need to check that the value is under the max value of the source type as the lowest values of an unsigned value will always fit in a signed one. Here I also decided to use static cast to the source type in order to prevent unsigned to signed promotion.
Finally if we're converting a signed value to unsigned we need to check that the value is above zero and less than or equals to the max value.
if constexpr (is_target_integer && is_source_integer)
{
if constexpr (is_target_signed && is_source_signed)
{
return value <= max && value >= min;
}
if constexpr (!is_target_signed && !is_source_signed)
{
return value <= max;
}
if constexpr (is_target_signed && !is_source_signed)
{
return value <= static_cast<SourceType>(max);
}
if constexpr (!is_target_signed && is_source_signed)
{
return value >= 0 && static_cast<uint64_t>(value) <= static_cast<uint64_t>(max);
}
}If both the target and source type is of floating type we can't do the exact same as for integers. The easiest solution I found was to just cast the values from source to target and perform a check if the value stays the same. Like this:
if constexpr (!is_target_integer && !is_source_integer)
{
if constexpr (std::is_same_v<TargetType, float>)
{
if (std::isinf(value) || std::isnan(value))
{
return false;
}
float f_value = static_cast<float>(value);
// Check for loss of precision.
if (value != static_cast<double>(f_value))
{
return false;
}
}
return value <= max && value >= min;
}Thge check for floating point is only there because if we're trying to put a double into a float. Remember that the function that calls this can only send in uint64_t, int64_t and double as the source types because that is what we're getting from yyjson so we're allowed to make some assumptions here.
Integer to floating point is actually exactly the same, we perform a static_cast and check for loss of precision and wether the value fits within the min and max ranges for the target type, its really nothing more to it.
if constexpr (!is_target_integer && is_source_integer)
{
if constexpr (std::is_same_v<TargetType, float>)
{
float f_value = static_cast<float>(value);
// Check for loss of precision.
if (value != static_cast<double>(f_value))
{
return false;
}
return f_value <= max && f_value >= min;
}
else
{
// Check for loss of precision.
if (static_cast<SourceType>(static_cast<double>(value)) != value)
{
return false;
}
double d_value = static_cast<double>(value);
return d_value <= max && d_value >= min;
}
}The final step is floating point to an integer value and this is really not that different, the only edge case here is that we need to remember that if the floating point number contains decimals it will never be able to be represented as an integer hence we need to perform that check in addition to if the range is within bounds.
In order to check if the value has decimals we use std::trunc on the value and check if the value stays the same. The rason we use trunc floor is because when passing negative values to floor it rounds them down a full number rather than just removing the decimals, almost like an inverted ceil.
The final code ends up like this:
if constexpr (is_target_integer && !is_source_integer)
{
if (std::isinf(value) || std::isnan(value))
{
return false;
}
// Don't allow decimals
if (std::trunc(value) != value)
{
return false;
}
if constexpr (is_target_signed)
{
double double_max = static_cast<double>(max);
double double_min = static_cast<double>(min);
return value <= double_max && value >= double_min;
}
return value >= 0 && value <= static_cast<double>(max);
}After this all I needed to do was add calls to the `q2as_type_can_be` with different type arguments in order to add the checks we needed for the project and it turned out quite nice. If you’re interested in seeing the full code you can view the gist here.
gtime_t
gtime_t represents a timespan. The backing storage is a simple int64_t of milliseconds. The interface that angelscript uses is the following:
class gtime_t
{
// properties
int64 milliseconds;
// behaviors
gtime_t(int64, timeunit_t);
gtime_t(float, timeunit_t);
gtime_t(const gtime_t&in);
// methods
int64 secondsi() const;
float secondsf() const;
int64 minutesi() const;
float minutesf() const;
int64 frames() const;
bool opEquals(const gtime_t &in) const;
int32 opCmp(const gtime_t &in) const;
gtime_t &opAssign(const gtime_t &in);
gtime_t opSub(const gtime_t &in) const;
gtime_t opAdd(const gtime_t &in) const;
gtime_t opDiv(const int32 &in) const;
gtime_t opMul(const int32 &in) const;
gtime_t opDiv(const float &in) const;
gtime_t opMul(const float &in) const;
gtime_t opNeg() const;
gtime_t &opSubAssign(const gtime_t &in);
gtime_t &opAddAssign(const gtime_t &in);
gtime_t &opDivAssign(const int32 &in);
gtime_t &opMulAssign(const int32 &in);
gtime_t &opDivAssign(const float &in);
gtime_t &opMulAssign(const float &in);
bool opConv() const;
}I've not done a lot of work with time before but I got the suggestion to just make a wrapper around std::chrono because it contains basically anything needed for this to work as intended. Which I am fine with as I'm learning about the problem.
The chrono library in C++ contains a little bit about everything when it comes to time. There is a clock type, time point, duration, calendar daets and timezone information. We're mostly interested in the duration part of the library as the description from the official documentation is
A duration consists of a span of time, defined as some number of ticks of some time unit. For example, "42 seconds" could be represented by a duration consisting of 42 ticks of a 1-second time unit.
Fortunate for us it already contains a milliseconds helper type std::chrono::milliseconds whose definition is std::chrono::duration</* int45 */, std::milli> where int45 stands for an integer type of at least 45 bits. When using this type on an x64 machine it uses long long by default. the std::milli type is a helper type for std::ratio which is a C++ class used to perform rational arithmetic at compile time. A millisecond is the same as one thousandth (1/1000) hence as you can imagine the ratio for milli is defined as std::ratio<1, 1000>.
When looking this up I found something pretty crazy and that is that this library defines several literals to help you use the library. For example the library accepts values with the suffix of h for hours, min for minutes, s for seconds etc. Which means that you can write code like:
std::cout << "5 seconds is: " << std::chrono::milliseconds(5s).count() << " milliseconds.\n";I didn't even know you can do this but well, proven once again that C++ can do anything.
Anyway with this we can start with creating out new struct. I decided to name it q2as_gtime just to be clear that its a part of q2as.
struct q2as_gtime
{
// properties
using milliseconds = std::chrono::milliseconds;
milliseconds _duration;
};If we look back to the behaviours of the Angelscript class we can see that it expects three different constructors, two of which expects a new type called `timeunit_t` however when looking at the C++ side of things the methods that it registers for these constructors is a helper function that just creates a new gtime using `from_*` methods that we will get to later.
template<typename T>
static void Q2AS_gtime_t_timeunit_construct(T value, timeunit_t unit, gtime_t *t)
{
if (unit == timeunit_t::ms)
*t = gtime_t::from_ms((int64_t) value);
else if (unit == timeunit_t::sec)
*t = gtime_t::from_sec(value);
else if (unit == timeunit_t::min)
*t = gtime_t::from_min(value);
else
*t = gtime_t::from_hz(value);
}It is defined as a template because we intend to call it with `int64` and `float` which the Angelscript definition displays.
So setting those constructors aside for now we can be satisfied with just adding a normal constructor as well as the copy constructor that Angelscript expects.
struct q2as_gtime
{
// properties
using milliseconds = std::chrono::milliseconds;
milliseconds _duration;
// behaviours
q2as_gtime() = default;
q2as_gtime(const q2as_gtime&) = default;
};Next up is the methods part of the definition. The next 5 methods defined in Angelscript are getter methods used to get whetever value is inside the gtime and return it in the expected format. This is where we can use the duration library to just do all the work for us.
In order to take one duration and convert it to another we just supply the old duration to the constructor of the new one with the expected format.
int64_t seconds() const
{
return std::chrono::duration_cast<std::chrono::duration<int64_t>>(_duration).count();
}
float secondsf() const
{
return std::chrono::duration_cast<std::chrono::duration<float>>(_duration).count();
}We do not need to supply the second template argument to duration because the base time represented in duration is seconds which is the same as std::ratio<1, 1> in this case. Doing the same for the minutes methods requires a slight change because now we are actually converting the duration to another period. Relative to seconds a minute is a ratio of 60/1 so our new methods becomes:
int64_t minutes() const
{
return std::chrono::duration_cast<std::chrono::duration<int64_t, std::ratio<60>>>(_duration).count();
}
float minutesf() const
{
return std::chrono::duration_cast<std::chrono::duration<float, std::ratio<60>>>(_duration).count();
}The last method to add is the frames whose job is to translate the gtime to a duration relative to the server frame time in the engine. The server frame time is globally accessible so we can just implement it by dividing the duration based on that.
int64_t frames() const { return _duration.count() / gi.frame_time_ms; }The last methods that we need to implement in order to complete the interface are just the operator overloads and there is really no magic behind these we already have the underlying duration type which already has these overloads prepared for us so we just need to wrap them all in addition to the occasional cast to int64_t just to be safe cause the underlying duration that we created uses int64_t to store its value.
q2as_gtime operator+(const q2as_gtime& rhs) const
{
return q2as_gtime(_duration + rhs._duration);
}
template<typename T, typename = std::enable_if_t<std::is_arithmetic_v<T>>>
q2as_gtime operator*(const T& rhs) const
{
return q2as_gtime(_milliseconds(static_cast<int64_t>(_duration.count() * rhs)));
}
bool operator==(const q2as_gtime& rhs) const
{
return _duration == rhs._duration;
}
// Basically the same for the other operators..The final thing that we did put off for later was the from_ms, from_sec, from_min and from_hz methods that the Q2AS_gtime_t_timeunit_construct helper function uses in order to construct different gtimes.
These are not really different compared to how we made minutes, seconds or any other method. Here we will also utilize the duration_cast but we will always cast it to our milliseconds type, for example:
template<typename T>
static q2as_gtime from_sec(const T& seconds)
{
return q2as_gtime(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::duration<T>(seconds)));
}This was really all work needed before swapping angelscript to use our new type. I proceeded with running the game and it worked as expected.
This project is very fun to be a part of, it is very programmer heavy and solution oriented and there is tons of interesting problems to tackle still. If you’re interested in the Quake 2 Angelscript project you can find it on Github.
I am going on a 2 week motorcycle trip in the end of this month so I will probably not be able to prepare anything new to read on this website for a while but I plan on writing a bit about a model viewer I’ve been working on and posting about on twitter.