battleMETAL - Why that was a bad idea, a terrible idea - Part 3 - Collision Systems

About those multi-part models

Collision systems a core part of any video game engine. From the first version of Pong up to the latest games on any platform, these systems are responsible for processing impacts between game objects in the game space. In general, like most computer code, collision systems have to be built at some point because a computer does not intrinsically know when two ‘objects’ have hit each other. The complexity of these systems can vary wildly depending on how detailed the game wants to get for collisions and how complicated the game itself is. Quake’s collision system is fairly simple for a 3D FPS.

The collision system for Quake starts with a series of boxes, or specifically, axis-aligned bounding boxes (AABB). Woah there’s some jargon, AABB simply means that the collision model for a game object is a box (technically a rectangle because box proportions can be altered). The axis-aligned part means that this bounding box does not rotate. The model can change angles all it wants, but in the eyes of the collision system, it never rotates - this is an important distinction.

Here we see Quake Guy and his AABB. Whenever Quake Guy hits another entity, or is hit by entity, the game doesn’t check the Quake Guy model for this collision. Instead, the game sees if Quake Guy’s AABB was contacted; which is mathematically simpler and therefore a faster calculation. The downsides to simple AABB is the lack of detail in collision detection, this can be best seen when Quake Guy is standing on a staircase or slope. Notice how only a few corners of the AABB are touching the ground?

Let’s make one quick jump back to the previous post about models, specifically the models that make up a mech in battleMETAL. These entities use a move type called movetype_follow which tells the game to always keep the entity’s center as an offset from a code-defined center in game space. There’s one important detail here, entities with movetype_follow cannot have a collision AABB. As a restriction, this exists because the use-case for movetype_follow is for cosmetic models put on the parent entity - weapons, clothes, etc. For battleMETAL, this means that the various mech parts that are seen on-screen don’t actually have a link to the collision system. Hm, but battleMETAL requires a feature where mechs various parts can be blown off the mech.

The solution implemented is a bit obtuse to manages to satisfy the requirement and still work. The player seen on screen is a heavy composite of several code pieces and models. To start, the player doesn’t actually have a model bound to its entity structure. Rather, the visual components - the mech piece models - are all separate entities using the movetype_follow functionality to appear in the correct location during gameplay. From the perspective of the collisions system however, these pieces are ‘wrapped’ inside the player’s main AABB. When a player is struck by a weapon, the following is executed in the code:

1. Determine the gamespace location of the hit, this is a 3D vector of X Y Z
2. Query the gamespace location of every mech piece that the player-being-hit owns.
3. Find the closest mech piece to the hit origin.
4. Closest mech piece becomes the area that is ‘hit’.

More modern game engines can execute what is called Per-Poly collision where the gamepsace location of a collision between objects can be focused on the smallest parts of the models themselves. Quake is much more primitive as we have seen. The solution that battleMETAL uses is not the most precise for players, but works surprisingly well in-action. The majority of hits against a target are applied to the correct piece of the mech (if the target is a mech) and battleMETAL uses this multi-part collision detection only in very limited cases. Every weapon strike is a short loop through all the mech parts of the mech target, which can get computationally expensive if a lot of mechs are on screen.

There are some quirks to the written algorithm as well.

1. Ignores the volume of each model piece on the mech
2. An imprecision thats hard to detect
3. Effects on mech design
   

In the end, this was deemed acceptable if it allowed players to destroy components of mech models in the game. There are several other problems with the collision system being so primitive - such as interactions between moving objects and the terrain models. The 4-point ground detection code can get a bit cagey when trying to detect collisions with a terrain piece that changes its slope too quickly- something like a really bumpy road or rocky area. This necessitated keeping terrain features more simple in their mesh complexity.

battleMETAL - Why that was a bad idea, a terrible idea - Part 2 - Model Mishaps

Compromises were made
Models are a good enough place to start about things that went awry. The most complicated models so far in battleMETAL are the star units themselves, the metals. The game requires that certain game units have multiple hit locations that can be destroyed before the entire unit is killed. In the case of the mechs, the locations are the center torso, left and right torsos, left and right arms, and the legs. 5 locations total for every mech unit. To better communicate damage to players, it was decided that arms and torsos should be ‘blown off’ when the health of those areas reach zero. This translates to each mech piece its own disconnect mesh, like a lego piece.

Most FPS games don’t deal with complex vehicles, they are scaled to people-sized players and monsters fighting. The models for each of this units is usually 1 solid, animated mesh. Despite complexity of the model, the fact that model is 1 contiguous piece of geometry makes working with them fairly easy. Having five sub-models that make up one complete mech model gets heavy very quickly. It increases the number of files per game unit, makes coding for game units a bit more complex. More modern game engines can handle this complication using techniques like bone-based modeling. Quake was made slightly before skeletal animation became an industry standard. Half-Life is credited with bringing skeletal animation to the mainstream and Half-Life’s engine is a heavily modified version of the Quake 1 engine.

Darkplaces does allow for skeletal animation but it comes with some severe catches. The quake c code for Darkplaces can utilize bones but only on the client-side. Now why is this a problem? I think I mentioned client-side prediction as an issue in previous posts. The snag with this approach is that the bones are only rendered on the client’s side of the game code. If the bones are only on the client then the location in game-space of those bones becomes an issue due to discrepancies between server and client game states. If Darkplaces came with out-of-the-box client-side prediction for programmers to work with, then this might be less technical debt. As it stands, client-side prediction was left up to the individual coder for some...reason...and not every programmer is up to the task of solving a such a complex issue.

The other possible option for skeletal animation is found in the Quake 3 model format called md3. This model format was made for Quake 3, itself a multiplayer-centric, fast-paced, arena FPS from late 1999. Quake 3 also made an attempt to fix client-side issues of skeletal animation but John Carmack went about it in his own unique way. MD3 models can be given little ‘tag’ triangles (a triangle being made up of 3 vertices in the model). Each ‘tag’ would then be given a unique name within the model for later reference. The technical debt of this approach is how tags are organized. When making a model, the tags have to be made, pointing in the desired direction of orientation for the mesh that will be attached there. The tags themselves are not saved when the model is exported to md3, thus any subsequent work on the mesh will require remaking the tags in their specific location.

For Quake 3 models that only ever had 1 or 2 tags per model, the ‘tag’ method was an ok solution. battleMETAL however, breaks this through complexity of the models in the game. The solution I settled on isn’t exactly performant for multiplayer gaming (thankfully battleMETAL is more a single-player game), but it does work. Remember how every model is an entity in quake c? Entities can be given specified ‘movement’ types to reflect, in the engine, how the entity is supposed to move. Player entities have MOVETYPE_WALK which is for handling player movement and physics. Darkplaces expands this functionality by adding a new MOVETYPE_FOLLOW. This movement mode is for objects that cannot collide with anything, and is for entities that, well, follow another entity.

General use-case for movetype_follow in the context of Quake is things like, having the gun model that a player is holding reflected externally by having a gun entity set to movetype_follow. Using this, battleMETAL treats all mech model pieces as separate entities with the movetype_follow. The locations of the pieces are set in relation to the controlling player’s origin point. In this way, the requirement of having hit locations, and visible damage have been satisfied without resorting to time consuming or costly programming quirks. The code uses the Factory Pattern to turn a mech data file into a mech, including the construction of the model component entities.

battleMETAL was able to use some animation for the mech models in the end. The leg models for every mech are animated in the model creation program and exported to the md3 format when animations are complete. The quake c code then controls the playback of those animations. Although this means animations are comparatively ‘stiff’ when put next to modern games, they are sufficient for the project.

battleMETAL - Quake/Darkplaces was a bad idea - Part 1

This was a terrible idea

Late again with the blog post, ach, about 2 weeks out from moving to a new location. This part is a quick overview detailing all the fun to be had pointing out why Quake / Darkplaces was a terrible choice. A feeling that I had upon reaching spring 2018, having been working on battleMETAL since July 2016, was that of exhaustion. Any strengths that the Darkplaces engine might have offered turned out to not really offset the Technical Debt that was incurred by the requirements of the game.

A great example of this situation was level creation. For original Quake, the best way to make levels is to use one of a few tools specifically dedicated to this task. Tools like GTKRadiant, QUARK, or TrenchBroom. These tools facilitate level creation by providing a means for designers to create the terrain for a level, place objects such as lights, monsters, player start point, select textures for the levels, and modify lighting. The level building tool then compiles all this information into a .bsp file that Quake loads when entering a level. Mapping for Quake is a well documented process, the advantage of being a popular and easy-to-mod game from 1996. There was just one big hitch in the process - Quake can’t really do outdoor terrain, cue the record-scratch sound.

See, in 1996 - and even well into the late 90’s and very early 2000’s, outdoor terrain was hard to achieve. Computer power was more limited despite the advances since 1993’s DooM game. Many games achieved a feeling of outdoor space through camera tricks, data storage techniques, or even art / design aesthetics. The method that Quake uses for creating level terrain is called Binary Space Partition or BSP. We’re not going to go deep into that particular set of computer programming, rather here’s the gist: the game (Quake) creates walls, floors, doors, ceilings, ramps, stairs, etc out of chunks of 3d space called brushes. When the map is compiled, the compiler takes the interior space of these brushes and compiles them into one large mesh of vertices. For computers in the 90’s, this was a level format that was easy to render without killing frame rate.

The Quake level design tools allow the user to create, reshape, change size, change textures of all brushes in a map. However, as we’ve seen with these old 90’s games, the brush-based system of level making results in very….chunky world aesthetics. There are ways to generate ‘realistic’ terrain with this brush method, but it results in map files that take several minutes or hours to compile. For battleMETAL a work around was found, by treating the terrain mesh as 3d model like any other 3d model, the game now had a way for realistic terrain. The sacrifice was that this terrain model does not show up in the map editors available, leaving the user to guess where to place other objects on the map. By requiring more accurate terrain models for the game, battleMETAL lost the ability to leverage Quake level makers which is a large trade-off indeed. This next part of the blog series will be just as the subtitle describes; why that (choosing Quake / Darkplaces ) was a bad idea.

battleMETAL - Why Quake / Darkplaces - Part 7 - Input Layer

It's a bit more tricky than one thinks 
One very important aspect of game engines is reading player input. Kind of hard to play a game if a player can’t actually control anything, right? Avoiding a more technical conversation of engine frames, processor cycles, and the like, game input is important because it needs to be timely. When picking game engines to use, input configuration is also a specific feature to compare. Quake has a few points towards itself in the area of game input, making configuration and custom behavior easy to create and maintain. Starting at the top level, Quake has multiple ways for a player to assign keys and bindings for behavior.

The 2 primary ways to change key bindings are using a console command ‘bind X key <action>’ and the second is modifying the .cfg config file. Using the bind console command, a player can change key bindings at anytime during gameplay. This is great for players and programmers. The config file is just another format of console commands, rather then being used in the console, the commands are loaded from a text file on start up or whenever the user enters the ‘reloadconfig’ command.

In the Quake C code, there exists functions to get the action bound to any given key and a way to programmatically set a keybinding. This allows the programmer to determine what keys are being used, and how, as well as make easier the task of custom key actions. Both the server and the client (remember Client-side Quake C?) can intercept key button presses for even more custom code or to consume a key press so that it does not go on to the other end of the network. A fun extension to the Quake engine provided by Darkplaces are key bindings for controllers and joysticks. Controllers and Joystick bindings aren’t a priority but if possible to implement, it’d be a welcome addition to the types of players of battleMETAL.

Custom, game-specific action code can read for player input within 2 ‘channels’ so-to-speak of input. There are impulse commands, and button commands. Impulse commands are used for one-off key presses. The engine can only read 1 impulse per frame - wait, that sounds limited? Ah ha, says the game engine, consider this: Although the game engine can only read 1 impulse per frame, the entire engine is running anywhere between 60 frames per second or higher on modern systems. This frame rate is high enough where the player will never notice that the engine is only reading 1 impulse per frame! Impulses are stored in a variable on the player’s entity under the name ‘impulse’. The engine runs the function, ImpulseCommands() on every player on the every frame. The programmer puts their custom code into that function, allowing for custom code to be bound to specific impulses.
 
The second piece are ‘buttons.’ These are slightly different than impulses. The state of a Button is not cleared every frame, whereas impulses are. So if the player is holding down the ‘forward’ button, then every frame knows the player is holding down that button. This difference is important because Buttons are used for constant-on commands such as moving forward, or jumping, or attacking. Another key difference between Buttons and impulses is that there are only a set number of ‘Buttons’ that the engine can recognize. These aren’t buttons on your keyboard, but a specific set of buttons numbered 0 to 9 internal to the engine. Quake generally uses ‘button0’ as the ‘fire weapon’ button, and this is generally bound to Mouse1 - your left mouse button.
 
In summary, Quake and by extension Darkplaces, have a tight handle on player input. Allowing for both player and programmer a level of flexibility not seen in most other engines. Out of the box, Quake’s input system is understandable by both player and programmer. Of all the parts of battleMETAL that had to be coded, the input system was one of the easiest. 

And this wraps of the 'Why' of using Quake/Darkplaces, in the next segment we will see why that was a really bad idea in the long run!

battleMETAL - Why Quake / Darkplaces - Part 6 - Menu Systems Layer

Click on the thingie, no wait, that thingie!

Quake was never known for its menus, in fact most iD games skip out on menus in any detail. There’s a workman-like quality to them, simple layouts and input. It also makes sense given that Quake came out in 1996, unless a game was menu-driven (like RPG’s or RTS) a game’s menu system were fairly plain. For Quake, it has all the necessary menus a player would need for an FPS. Building on DooM’s template, there are more options for graphics, and for multiplayer settings. Interestingly enough, iD did setup the code for their menu system fairly well, having console commands that can immediately bring up any particular menu.

Darkplaces however expands the capabilities. This being 2018, menus have advanced a bit since the days of 1996 and most people enjoy having a useable mouse for the menus. In Darkplaces, the source port exposes the menu entry functions to the Quake C code that modders can use. This in turn allows modders to create any and all menus they’d like to in almost any fashion they’d prefer. There are 2 layers to menus in Darkplaces, each being compiled to their own code base. The big one is called CSQC or Client-side Quake C. Original Quake, all custom code (written in Quake C) was packed into a single compiled file called progs.dat. However CSQC is packed into its own file and only used by the player’s local game of Darkplaces.

CSQC can access almost everything about the player’s game. The programmer can customize the HUD, can create their own menus, change runtime variables through the console, intercept input commands, and very importantly - define communications with the server. This last piece is helpful, this allows custom data transmission between the server and player. The coder can setup custom server-drive events, or pass specific game updates to the player for notification. Quake itself never needed to do a whole lot with this, but a mech game in 2016? Oh yes, this feature was very much needed.

The other big menu module is the specific menu layer. Quake source ports and modders never really settled on a ‘standard’ way of remaking / extending / modding Quake's original set of menus, so several options exist. One way many modders do is add the features to the CSQC described above. Another way is the menu.dat. Remember how CSQC compiles to its own file? Well its the same idea with the menu.dat code. Darkplaces looks for a menu.dat file, if it exists, Darkplaces then runs the menu code found in that file. The framework for the menu code is similar to CSQC but slightly more limited to just rendering menus and executing player input. I chose this solution for my main menus because I liked the separation of concerns that this approach offered - all the menu code is in its own folder and cleanly separated from all other code.

In summary, Darkplaces offered several flexible albeit a tad labor-intensive approaches to implementing new User Interface upgrades to the original Quake engine. I considered this sufficient at the time when selecting to go forward with Darkplaces. The available documentation on CSQC was easily found, but not the most detailed. The menu.dat code required going into the engine code to figure out how it worked. In hindsight now, despite the flexibility offered, both features actually incurred a large amount of technical debt. Newer engines handle UI systems more effectively both for the player and for the programmers.

battleMETAL - Why Quake / Darkplaces - Part 5 - Network Layer

Connecting for long distance mech mayhem
 
I will try to keep out of the deep end for this portion of the blog series. I forgot that these sections aren’t meant to be a detailed breakdown of the Quake engine or the Darkplaces source port. Rather, these posts are laying out the battleMETAL project’s discovery and assumptions before the work of battleMETAL truly began. In that spirit, these posts should be fairly short and mostly general about tech, code, architecture, etc.

At the time I was deciding whether or not to roll forward with Quake / Darkplaces for an engine, the concept of having multiplayer stood out. A mech game with some dedicated multiplayer would surely be a great game to try, and maybe even with friends. Quake’s network architecture, despite being a tad dated, is fairly robust. DooM’s network layer was peer-to-peer, where game-state was sent around to every player on the server; Quake’s networking is client-server. A main server of the game is started, and then all players connect to the server as clients. This is a server-authoritative design, where game-state is held on the server and then sent to clients. While this scales more nicely than DooM’s peer-to-peer system, the architecture wanders into sticky issues like client-side prediction and lag.

Deep diving into game networking aside, Quake had the feature set that overlapped with battleMETAL’s requirements nicely. Out-of-the-box, Quake allows any players to create their own servers, configure those servers (map, game mode, number of players, certain game rules, etc) and Quake has functionality for server-browsing. Although the menu system for Quake was rudimentary (even by late 90’s standards) it demonstrated that this functionality could be accessed by modders and programmers using custom code. The end result is customized server-browsing menus and features that have been added to battleMETAL.

In game code, Darkplaces also had mapped out functions for processing player input, data transmission between client and server, and functionality for fully customizing the player’s client-side view. Now that said, the exact knowledge for implementing these features was a bit more esoteric, but we will get into that later. Knowing that the network layer was securely placed in the engine code, vs the game code that battleMETAL would be using, Quake really had an attractive feature set for networked gameplay. One benefit of using a source port like Darkplaces is that there have been some key updates to the original Quakes network code. A little bit of client-side prediction which alleviates latency between server and client. Also increases the packet size, allowing more data to be transferred between client and server (after all, network speeds have increased since 1996.)

Further on in this series we will see that some of these initial assumptions might have been a tad generous or very much off the mark of what was actually useable. For now, let’s stick with the bright and rosy details that Quake was setup to be a multiplayer game and that therefore battleMETAL would be inheriting this functionality with little trouble.

battleMETAL - Why Quake / Darkplaces - Part 4 - The Game Loop

...and looping through it
The core of any game is the ‘main loop’. There’s a reason why we developers throw around the word ‘engine’ when talking about games. The best analogy I use is a car engine. The car burns fuel, which moves pistons that turn a camshaft. That camshaft then turns a belt called the ‘timing’ belt. The timing belt is the clock of the car engine. A game engine is very close to this. The base code is setup to run through a series of functions in a specific order, and there’s a ‘timing belt’ that keeps internal time. In Quake that ‘timing belt’ is a variable nicely called time.

Entities, remember those little guys from earlier? also form the only true ‘object’ for the Quake C language. Quake C is a cut-down version of the C language, which is powerful but does not do ‘objects’ very well. Quake C gets around this but ever so slightly. There is only 1 type of entity and all extensions to that entity are given to every entity. What this means is, if there is a custom value, such as ‘weapon type’ for an entity, every entity will now have this variable regardless if it used by that entity. This design paradigm is a blessing and a curse. The blessing is that it means creating customized entities is as simple as just assigning values to the programmer’s desired variables. The curse is that it means the code will bloat-up really fast, leaving hundreds of entities with unused values.

When a player launches a game of Quake, after going through the menu system, and launching into a desired map; the engine creates a list of entities. Almost every object on-screen is an entity. Quake organizes its entities into a list, or more specifically in-code, an array. The wonky aspects begin here. This array of entities has a fixed limit, ie how many total entities the engine can have ever. Original Quake can only handle about 640….Darkplaces however upped this cap to 32,768. Quite an improvement, eh? However there’s still a quirk remaining. The array of entities in Quake is more like a slot-system. Each of those 32,000 places in the array is a slot with a number. When the code wants to create a new entity, it finds the next available slot to place the entity...based on where the slot counter is. It is never a guarantee that the next entity the code creates is right after the current entity the code is on.

This also kinda creates a problem with removing entities. Quake never technically ‘removes’ an entity from the array. Instead, it ‘zeroes out’ the entity’s variables, removing things such as any model assigned to it, and other variables. This is was an intentional design by iD Software. Although there’s a difficulty in determining if any given entity is ‘empty’, it allows the system to ruthlessly clean up ‘unused’ entities to keep system cost down. Darkplaces keeps this paradigm in place, allowing for a fast run through of all the entities in the main array.

Entities can be invoked with the spawn() which returns an entity, usually the code will load this entity into a variable for modification: local entity foo = spawn(). From there, the programmer then must assign the variables they want to go into the entity. If the programmer wants the entity to do something in the future, they would assign a .think() function. A think() function is any code that is executed every time that entity is activated in the entity array. There are several other ‘template’ functions that can be used for various parts of entity behavior. Want to have custom code run when one entity touches another? Give that entity a .touch() function.

A programmercan also create their own child functions for the parent entity, such as entity.thisFunction(). And thanks to the code being C-like; this specific function can be whichever function the coder wants to point to. This allows for neat tricks where a set of entities can have the same function, .thisFunction() but for each entity, the actual function is completely different, like this example:

  Entity A

     .myFunction() = fireWeapon_Type_1()

  Entity B

     .myFunction() = fireWeapon_Type_2()


So when the code calls .myFunction(), if the entity is A, then fireWeapon_Type_1 is called. There’s a bunch of other C language quirks that are leveraged in Quake C, but that’s drilling down into programming language design.
Despite some of the limitations with the programming language, I liked the straightforward approach to the code design. 

I figured I could apply higher level code principles to the Quake C language to get around some of its limitations - a fine example is using the Factory Pattern for entity creation. I don’t need to rewrite the same entity customization when making, say, a missile entity. Instead, I can invoke a makeMissile function that does it all for me. Entity cleanup is a bit trickier, and checking if an entity is truly ‘empty’ or ‘null’ (in code parlance) remains a problem that has to be accounted for. Writing interfaces was sort of out of the question, but I think the entity object in Quake C qualifies as an abstract class which is super helpful.