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.