Game Logic Scripting and Networking

I've been very distracted from working on my project, and this blog, since the holiday season. Various circumstances are resolving themselves, finally, and work will resume. I've also been somewhat stalled out trying to wrap my brain around the topic of this post, and thought it wise to take something of a break from wracking my brain in pursuit of the 'ultimate solution'.

One of the important features of the engine is that it should be easily moddable. My goal is to not only produce a game for people to play, but also a game they can manipulate and customize to further derive enjoyment from. This is also something that I feel affords me maximum engine re-usability insofar as creating and releasing another game is concerned. I have a serious aversion to hard-coding game-specific behavior and logic, because it always gets tangled up in the rest of the engine code, making it a mess to change certain aspects of the engine when trying to build a new game out of it.

The top priority is allowing the people who host game servers online to customize the game in any way they like without players being required to manually download and install anything externally just to play. Server admins should be able to customize everything about the game that people experience when they join their game. Players should be able to see all game servers running on the same engine, and choose between the different games/mods that each server is running. Being that virtually all of the assets and resources used for generating the game experience are scripted procedurally, clients quickly download these procedures and 'rules' upon connecting and the entire game experience they encounter is dictated by the scripted configuration of the game on the server.

Games that are almost entirely hard-coded into the engine usually feature customization of the constant values for things like weapon damage amounts, and other little nuanced values like this, but the behavior of the game itself is otherwise 'stuck' the way that it is. Typically they have some sort of text file where the configuration exists, delineating variables and their values for controlling physics and game behaviors. This is simple enough, and plenty sufficient for smaller projects of a less serious nature.

Most games utilize some form of a scripting language to accomplish the de-coupling of game logic from the game engine itself. There are others which simply incorporate the use of an external compiled binary, e.g. a DLL file. Having a background in reverse engineering and 'hacking' games, I can say that using a DLL is probably the most insecure thing a programmer could do. Operating systems are equipped with all sorts of debugging APIs and features that enable hackers to have a field day with such games.

Another top priority alongside game customization is the quality of multiplayer networking and the resultant online gameplay. It's pretty standard now to just design a server/client model using all the usual tricks that have been around for the past decade to mitigate internet latency and packet loss, to smooth out the appearance of the gameplay that is actually occurring on the host machine that is being simulated remotely. Everything you see on the screen is a virtual lie, and the typical bag of tricks are designed with the intent to please the player with promises that can't always be kept.

It is my opinion that the existing techniques are sub-par and that it is time we begin to explore other options, and come up with new ideas. For my project I am turning conventional networking strategy on its head. In my networking model the client has equal authority as the server and other clients as far as the game state is concerned. The server merely maintains the game rules and authority over who can be connected and participating in the game. It also serves to route the game state between clients as it evolves. No single machine retains the absolute state of the game, and all machines are participating equally in the progress and simulation of the game state as it unfolds.

To make all of this possible, combining a sort of peer-based game state simulation along with client/server networking model, as well as keeping the system for user-made mods in a manageable and user-friendly state, I have opted to use a console-scripted system that is made up of a handful of smaller 'systems' of commands. Everything in the engine is scripted using sets of commands in this fashion.

There are three components to this setup. At the core we have entity 'types', which are a set of parameters that define a specific entity. Properties that don't change about a type of game object are represented as a 'type'. Things like a model, conditional logic, physics behaviors, etc. Properties that are consistent across all instances of an entity type are thus considered aspects of that type.

Secondly, we have entity 'functions'. These are small sets of 'operations' to perform on a given entity. Things like playing sounds, spawning particles, or entities, inflicting damage, etc. These functions are referenced by an entity type's conditional logic definitions. Conditional logic is hard-coded into the engine, there are only a certain set of conditions which the engine detects about an entity and, in turn, executes any logic for those conditions as defined in the entity's type. Conditions such as when an entity touches the world, or another entity, or gets damaged or killed, for example.

Functions can perform a number of operations, but they cannot change anything about the original entity type it is executing upon. However, if something is to change about a specific entity's type, it can simply be changed to a new type with different static properties. If a player is supposed to go from a walking physics to a ragdoll physics, simply change the player entity's type from "player" to "deadplayer", where the physics settings differ accordingly.

This makes the process and/or job of designing entities pretty simple and painless. They can be edited in notepad, and reloaded in a snap. It becomes easy to create variations of the default game.

It also simplifies the networking model. The typical setup most games use for networking the game state do so by 'delta-compressing' entity updates, comparing an older state to the present state to determine what aspects or properties changed and need to be transmitted. This allows developers to define any number of entity changes to occur over the evolution of the game state, and have everything reach from one machine to the other over a network connection.

My implementation boils this same design down around the fact that a lot of times there are many entities which have properties that never change over the course of their existence. These properties can all be lumped together and conveyed in a minimal number of packet bytes by simply indicating which entity should be which type, when that entity becomes that type.

The actual networking system continuously relays 'events' to the other side. The game logic, in the form of entity functions, is responsible for invoking events which have a networked component to them. Events like particles, sounds, etc. all are 'networkable events' - in that they should be seen by other participants in the game. These are queued up to be transmitted in the next outgoing update. An entity's type being set is an example of an event that is serialized and queued up for network transmission.

Not all entity function operations have a networked component. Some things are meant to only occur on the local machine, and even networked operations will stay local if the entity type is defined as being local-only (eg: client-side detail entities). If an entity changes into something completely different, and everything about it changes, this is not a large update. The local machine simply indicates which type the entity is now.

Along with the events queue is a prioritized list of entity positions, velocities, angles, etc.. All the location information about an entity gets tacked onto the update after all the events. Positional updates are 'optional', in that they don't always need to get to the other side the way events are supposed to. Entity positions are prioritized by the entity's proximity to the client's player entity. Entities within a certain distance of the player have their positional information included with every update being sent to them. Once entities become further out, the number of updates they are included in per second begins to lessen down to a bare minimum.

This is a screenshot of the ill-fated Revolude game, circa 2010.

Now one idea I had, back in the Revolude days, was to perform a similar network conveyance of entity properties, and logic, by sending game logic function indices to clients, telling them what functions to execute to bring an entity's state "up to speed". This made sense in my head, but in practice there was an issue between preventing functions from overlapping or overwriting eachother's changes.

The solution was to divide up the game logic into a server-logic and client-logic. Sometimes the two had the same pieces of code but used it in different ways. The server's job was to control the actual state of the game, and direct how clients should be simulating their end, which entities are where, and what functions they are executing.

It never worked out, fully. The Revolude build I still have is wrought with networking bugs. A poorly thought-out event networking system wasn't ensuring all events made it across, in order. Objects can be seen turning topsy-turvy, appearing and disappearing, or never existing (but leaving evidence that they did). It's a nightmare I am happy to never return to.

The networking in BITPHORIA is awesome, though. I am very happy with how the game is coming along.

BITPHORIA, in its current form.

Procedural Modeling and Animation

I failed at maintaining at least one post per month, a lot of distractions are abound! I've been trudging away nonetheless. The project is at a point where I am leaping from one milestone to the next, some days being spent refactoring smaller support code and/or adding functionality to various support systems.

I have just added some code for dealing with quaternions for representing object orientations, as euler angles will just not suffice for the physics interactivity I am striving for. To represent rotational velocities I have also added code to handle axis-angle representations, because quaternions inherently limit rotation to 180 degrees, or in the case of rotational velocity 30 RPM.

One feature of the engine that I was looking to implement is procedural model scripting. The goal here is to allow a user to easily script a game 'model'. A model consists of vertices defined for the three basic primitives which are points, lines, and triangles. Each of these vertices have a RGBA value for rendering a color.

The primary advantage of having scripted models are that anybody can edit them, without learning modeling software. All you need is a text editor - which I aim to build into the engine in some capacity (after making a release) to eliminate the need for alt-tab madness. Scripting a model is a matter of cleverly putting together a series of commands that rotate and translate to reach the desired position of each vertex for the desired primitive type.

Another advantage of using procedurally scripted models is that game server admins can run games with their own custom models, which are quickly and easily transferred over the network to player clients. Clients can then generate the actual models by executing the procedures defined therein. This is huge because it is another goal to allow server admins to run entirely customized games without requiring players to download and install anything manually.

A script for a 'sprial tree' model, demonstrating the use of nested loops.

Scripts are also afforded the ability to 'randomize' various parameters. Things like translate, loop, rotate, etc. can all be randomized using a minimum value and a range value. Each time an entity requests a renderable model 'instance' the system checks if the model is invariant or not. If the model is not invariant, this means it uses randomized parameters in some way, and must be re-generated for each instance requested. This allows the system to take one model script, and generate many variations using different seed values to generate the randomized parameters for the operations that use them.

Another feature of the modeling system is the ability to push/pop the current matrix and loop counters. This allows for recursive modeling of hierarchical things like trees, plants, and other fractal shapes.

Some spiral trees, and dynamic mesh player model.

Along with scripting individual procedural models I have implemented an animation system that I devised a long while back. This was yet another chance to embark on a journey that strayed from the norm. I love skeletal animation, and inverse-kinematics for making a skeletal model interact seamlessly with the game world, but I do not love the mind-numbing rote-implementation of features that all the creative work has already been done around. To me, programming is about problem solving, the deeper and more abstract the problem, the more rewarding it is to me. Infact, making a game all by itself isn't that rewarding to me (earning a living is good, though). It's the process and the challenges of making something involved that I find rewarding, and I wish more programmers felt the same. At any rate...

Conventional animation systems involve manipulating a mesh model using a virtual skeleton with virtual joints. Keyframed animation is stored as angles for each joint, and is easily to interpolate for smooth animation between keyframes. Getting any keyframed animation to smoothly and seamlessly interact with the world and external forces like wind, inertia, gravity, collisions, etc.. is tricky in and of itself. It's a challenging problem. Some games only let the model/skeleton interact when the character is dead, allowing the body to flop around in response to external forces. This is known as 'rag-doll' physics. There are various solutions now for handling these sorts of things, both for animating and dead character models. There's even one solution that dynamically generates/modifies keyframed animations for things like walking, so that it looks as though the character is actually negotiating bumpy terrain with strategic footstep positions.

I did not want to plug in a solution, and I did not want to pursue a solution that was too involved. This is where the dynamesh comes in. Dynamesh is just a abbreviation of the term 'dynamic mesh'. A dynamic mesh is just a spring mesh, where vertices are referred to as 'nodes' and the edges connecting two 'nodes' are called 'links'. This is a simple system where each node is given a size (zero is valid) and a mass, and each link is given a rigidity value that dictates how will it retains it should retain its length.

This system is simple enough to simulate. It consists of two parts - a particle simulation for the nodes themselves, and an iterative link-constraint system that pushes and pulls the nodes of each link in an attempt to 'settle' the mesh.

So far, I have determined three uses for this system:

The first use is entity collision volume representation. Along with using spheres, capsules, axis-aligned bounding-boxes, and the like, it's nice to allow for more detailed collision hulls for bigger more complicated entities.

The second use of the dynamesh system, which operates in tandem with the first use, is rigid body physics. It is an automatic feature of this system to allow all the nodes to be in any orientation, with no real 'orientation' at any point in the code. Discerning anything like an 'orientation' involves examining the relationship between node positions, and comparing it to the original default orientation. This isn't too hard or expensive to do. Entities can use a dynamic mesh as not just their collision hull, but also to innately handle collision response and resolution. This enables highly interactive entity physics behaviors.

The third use is animation. Not only can you define a dynamesh that is rigid, but you can define one for a character, or a vehicle, or anything with moving parts. With one pair of nodes you can have a ball and socket type joint. With three nodes you can have a hinge. Through clever use of nodes and links you can create just about anything, and the neat thing is that simulating the nodes as particles that are affected by external forces and collisions allows for highly dynamic interactivity automatically, without any special-case code at all.

In this case I am using dynameshes for character animation, while allowing for an entity to have one scripted procedural model that is permanently attached to them, as well as one dynamesh, which can have models attached to its links. This makes it simple enough to define a character dynamesh.

Keyframed animation is a matter of storing node 'goals' for each keyframe, and pushing those nodes toward their goals when a specific animation is playing. In this case I am procedurally generating running animations through some simple manipulation of foot/knee nodes. Dynameshes must define anchor nodes, which are used to fix the mesh to the entity using them. Entities are essentially dragging the mesh around the world, unless the entity type specifies that it is to assume the physical state of the dynamesh, then the anchor nodes are used to dictate an entity's position/orientation.


Links:
Lightweight Procedural Animation ... by Ian Horswill
NeHe Productions: Rope Physics
QUELSOLAAR.COM: Confuce - Procedural Character Animator

Collision Detection with Distance Fields

One of the great things about doing a Minecraft-style voxel engine, where the entire world is made of cubes, is collision detection. It's very cheap to detect which voxels one should compare a game entity's collision hull against, and the math is very simple.

Minecraft: The cubic-voxel world game of the century.

One of the lame things about doing a Minecraft-style voxel engine is that Notch did it already (not to mention Minecraft's inspiration: Infiniminer). I am not making a cubic Voxel world. I'm not really even making a voxel world. I'm using voxels as an intermediate representation in generating my world. I don't even plan on making it very big, or modifiable. I'm not using marching cubes to make smooth terrain, and I'm not using boxy voxels either.

my voxel game thus far

After all the generation and stuff, the end product is rendered as polygons (triangles). I could handle collision detection between objects and the world in terms of spheres and triangles, or cylinders and triangles, or any mathematically simple shape and triangles. But triangles are yucky, and I don't like dealing with them. I especially do not enjoy the thought of detecting *which* triangles to test intersections on. Back in the days when I was a big fan of BSP trees, this would have been fun, but not anymore. I've moved on to bigger and better things (or, whatever).

What's nice about cubic voxels is that you can pretty much just index an array using your object's position and see if there are any voxels intersecting. In a Wolfenstein 3D style raycaster this is great for collision detection, it's just so simple to do. That's great and all, but I'm not using cubes. I'm using octahedrons that behave like metaballs and 'merge' when neighboring eachother. This complicates things.

Collision primitives from Cryengine.

My first ideas consisted of first assuming every object to be a sphere, or pill shape, and do a quick (hah) spatial search for the closest voxels. Then detect which faces are facing the entity, which edges and planes it intersects, calculate where any 45 degree planes may be (corners/edges) and handle the collision accordingly by moving the position of the object, and calculating a new velocity based on elasticity and friction values. This method seemed ideal for handling collisions using the sparse volume representation in memory only, and the sparse volume structure doesn't store information about the shape of the voxels, they are all just cubes as far as it is concerned. It was important to me that a slope of voxels could be ran up/slid down/rolled across/etc smoothly, without any stair-stepping. I wanted a 45 degree plane to behave like one.

The most difficult part of this solution was handling large objects with multiple collision points with different groups of voxels around themselves. I quickly realized that a distance field representation of the whole scene would solve all of my problems - efficiently detecting collisions with all object sizes while behaving as though diagonal voxels were one continuous 45 degree surface.

In this video of a 2D prototype I did last week you can see the green 'voxels' and the distance field rendered as a blue/red gradient that is generated using a simple distance transform that propagates distances over the 'volume' in two passes. The circle is just a point in space which is used to index the distance field, which the value returned from is compared against the circle's radius. If the circle's radius is greater than the value at its center in the distance field then it is intersecting. Then it's a matter of checking the surrounding distance field values and calculating the gradient of area of intersection to determine a sufficient approximation of the 'normal' to properly de-intersect the circle and reflect its velocity with some amount of elasticity for a bounce effect.


As a bonus, there are other uses for distance field representations of a 3D scene. Distance representations are very handy for any line/path tracing, so it lends itself well to calculating lighting and shadowing. It is also useful for AI pathfinding and obstacle avoidance. Fluid dynamics can also benefit from a distance field representation for properly drifting particle effects around the scene realistically. I've already uploaded the same distance field to the GPU as a 3D texture to perform some ambient occlusion in the vertex shader, which has increased the visual depth of the game scene. It will also make the job of illuminating game entities much simpler.

The only downside to the distance field representation is memory usage. So far I'm just using a flat array, because I don't really see a very worthwhile means of compressing data as incoherent as a distance field. Conventional sparse structures, like octrees, will not be of much use. What would probably work best is a more continuous approach, like a cosine transform. Maybe dividing it up into 8x8x8 blocks and performing a discrete cosine transform (ala JPEG) would be a decent means of representing the data in memory? Each distance field query would then result in performing a bunch of cosine calls though, unless some quantization could negate most of them. Compression artifacts would yield bumpy surfaces, however.


Links of interest:
Wikipedia: Distance Transform
Gamasutra: Advanced Collision Detection Techniques

World Representation

It's been a while since my last post, a lot of brain storming (as opposed to actual coding) has been going on. I've been exploring world generation and possible data structures for representing the world in memory. This all required that I make some important defining decisions about the world.

At the time of this writing, I have yet to decide on making the world dynamic (modifiable). This is primarily because of the cost of updating the world, finding a balance between CPU/GPU loads, and doing so over the network between the game server and clients. Another issue involves when a client joins a server, they must download the current state of the world from the server as it exists after any modification that has occurred. There are tricks and techniques for minimizing this data flow, so that the entire world volume doesn't need to be uploaded to each connecting client. Right now this is not a priority, or even a necessary feature for what I am trying to accomplish with this current project. This could change!

Being that the world is volumetric (voxels) it was clear that there needed to be a data structure to hold the volume in memory, not just for rendering, but also physical interactions with entities. Following with Revolude's original design - the world would be procedurally generated (as opposed to loaded) when a game was started, or joined. This data structure would require that it could perform efficient read/write access.

I examined the possibilities of a few different algorithms and data structures for dealing with volumetric data. A lot of algorithms for storing compressed volume data rely on the fact that the data represents direct visual data, like the pixels of an image, in the form of red/green/blue/alpha color channels. This allows for all sorts of neat 'lossy' image-compression style tricks to be used, which forsake exact reproduction of the original compressed data in exchange for smaller size. For applications where the volumetric data represents relatively finely detailed data, these algorithms are great.

For my project the worlds are not that large, or that finely detailed. Voxel size is on par with games like Minecraft and Infiniminer. The primary difference from these games is that voxels will not be cubes. Voxels are also represented using a single byte to store a material-type value, allowing for up to 255 different materials (material zero is empty space). Worlds are also not intended to be infinite. Instead of having worlds extend infinitely through procedural means, they will be a finite size, and wrap around seamlessly. There will be no edge to the map, nor will it go on forever into places that nobody will ever go.

I'm still settling on a specific world size. With the sizes I'm considering, storing the raw voxel data becomes feasible, without the use of any sort of sparse data structure. For example, with a world size of 1024x1024x256 the size of the world data is then 256 megabytes. Each horizontal slice of the world is one megabyte. The only qualm I have with just leaving the data sitting in memory, when virtually every machine capable of running the game has enough memory, is cache coherency. The larger the volume, the further apart in memory two neighboring voxels could lie. This is not good for performance!

It's arguable that using flat storage for a finite volume won't produce a significant slow-down when the volume is queried for things like collision detection and rendering. Personally, I just don't want to be using more memory than I need to, especially if a byproduct of reducing the size is gained speed. Above all else, I love the challenge implementing a sparse data structure ;)

The first obvious option on everyone's mind is a sparse voxel octree. This is a wonderful structure, but can become computationally expensive to iterate as it deepens. One strategy I had a while ago to 'enhance' the octree is to allow each node to have more than 8 children. Instead of 2x2x2, it could be 4x4x4, for 64 child nodes. This would allow an octree with a dimension of 1024 (gigavoxel) and 10 tree levels to only have 5 levels to iterate through from root to leaf. The issue here is that there would be excessive 'empty' child nodes all over a volume. This would be the price for faster iteration.

Another strategy, one which I became quite fond of since my last post, is to store volumes as run-length encoded columns. This is especially attractive because it effectively reduces a volume into a few 2D images, and would work extremely well where voxels represent a limited number of materials (as opposed to highly variable 32-bit RGBA values). Many areas of the volume would be one or two column 'segments'. This approach was almost the one that I finally settled with, but I was having implementation indecision issues, trying to find a 'sweet spot' balance between speed, size, and simplicity. My obsessiveness with finding the perfect solution became a hindrance to progress.

Ultimately, this lead me to fall back on an older idea, which is really an amalgam of a few ideas. At the coarsest level, I represent a volume using a sort of hash-table. This is just a flat array that divides the world up into fixed size 'chunks'. The trick here, then, is to use a sparse voxel octree to represent the contents of each chunk. Using some efficient design, a chunk that is entirely one material (including empty) is stored as four bytes. The rest of the chunks, which I call 'boundary' chunks, are stored using a variable number of octree nodes. Each one has its own pool of octree nodes from which it builds the sparse octree representing the organization of voxels and their material indices. This node pool starts out small, and is reallocated as needed by doubling its size each time it fills up.

Currently I am working with chunks of 32x32x32, which is 32768, or 32k, of voxels. This seems like a nice round number, because I can fit an octree node index into 15-bits (16th bit flags leaf-node status). Now, in an octree, if each voxel could be a different material (32k different materials) then there would be an overflow because inner nodes would require more address space for 4680 nodes, but I am willing to bet that with less than 256 possible voxel materials this 'special' case chunk will never occur. Most chunks will never even see 10k of nodes.

With chunks that are 32k voxels in size, this means that a 64-gigavoxel volume (4096^3) would consist of 32k chunks. The flat array of chunks for a 64-gigavoxel volume would be less than a megabyte. The total size of the chunks themselves could vary, but would average less than 100 megabytes. This is really great for 64 gigavoxels. Now, I'm not going to be representing a world that is 64 gigavoxels, I don't think. I'm thinking smaller, because the goal here is a game that is more of a multiplayer online battle arena than some sort of vast expanse for an MMORPG.

This is actually how all volumes will be represented in memory, in terms of materials, and out of chunks. Some game objects will be displayed using volumes, some using other graphical techniques. This is a global 'voxel' solution.


Links of interest:
Visualization of Large RLE-Encoded Voxel Volumes
An Analysis of Minecraft-like Engines
Ken Silverman's Voxlap Page