Air, Air Everywhere.

atmosphere_graph

Atmosphere Propagation Graph from Project: Commander

 

I have a personal game project I’ve been contributing to now and again, and it seems to be slowly devolving into a case study of over-engineering. Today I’d like to talk about an extremely robust, and extremely awesome system I got working in the past few days.

The game takes place aboard a spaceship engaged in combat with another ship. The player is responsible for issuing orders to the crew, selecting targets, distributing power to subsystems, and performing combat maneuvers, all from a first-person perspective aboard a windowless ship (after all, windows are structural weaknesses, and pretty much useless for targets more than 10 km away anyway).

Being a game that takes place in space, oxygen saturation and atmospheric pressure is obviously a constant concern, and presents several dangers to the player. I needed a way I could model this throughout the ship in a convincing, and efficient way.

 

What and Why?

We need a solution that handles a degree of granularity (ideally controllable by a designer), is very fast to update, and can handle the ambiguity of characters who may be transitioning between two areas. How can this be done?

Enter “Environment Probes”. A fairly common technique in computer graphics is the use of environment probes to capture and sample shading information in an area surrounding an object. Usually, these are used for reflections and lighting, allowing objects to blend between multiple static pre-baked reflections quickly rather than re-rendering a reflection at runtime. This same concept could be made to work with arbitrary volumetric data, rather than just lighting, and would cover many of the requirements of the atmosphere system!

So, let’s say that a designer can place “atmosphere probes” in the game world. Huzzah, all is well, but how can that data actually be used practically? Not only do we need to propagate values between probes, but characters need to be able to sample their environment for the current atmosphere values at their position, where there may or may not be a probe! Choosing just the nearest probe will introduce noticeable “seams” between areas, and still doesn’t easily give us the adjacency data we need to propagate values from one probe to the next!

lightprobestestscene-sourceselected

“Light Probes” in the Unity game engine. An artist can place probes around the environment (shown as yellow spheres), and have the engine pre-calculate lighting information at each sample.

Let’s look at the Unity game engine for inspiration. One of their newer rendering features is “Light Probe Groups”, which is used for lighting objects as described above. Their mechanism is actually quite clever. They build a Delaunay tetrahedralization of hand-placed probes, resulting in a mesh defining a series of tetrahedral volumes. These volumes can then be used to sample the probes at each of the four vertices, and interpolate the lighting data for the volume between them! In theory, this doesn’t have to just be for light. By simply generalizing the concept, we could theoretically place probes for any volumetric data!

 

Let’s Get Graphic!

I spent the majority of the time building a triangulation framework based on Bowyer-Watson point insertion. Essentially, we iteratively add in vertices one at a time, and check whether the mesh is still a valid Delaunay triangulation with each insertion. If any triangle fails to meet those constraints after the new vertex is inserted, it’s removed from the mesh, and rebuilt. This algorithm is quite simple conceptually, and works relatively quickly, making it a great choice for this system. Once this was working, it was quite simple to flesh it out in the third dimension.

Atmosphere Probes - Minimal Case.png

A simple Delaunay tetrahedralization of a series of “Atmosphere Probes”.

So now what? So far we have a volumetric mesh defined across a series of probe objects. What can we do with this?

Each probe has an attached “Atmosphere Probe” component which allows it to store properties about the air at that location. Pressure, oxygen saturation, temperature, you name it. This is nice in itself, but the mesh also gives us a huge amount of local information. For starters, it gives us a clear idea of which atmosphere probes are connected, and the distance between them. A few times every second, the atmosphere system will look at every edge in the graph and calculate the pressure difference between the two vertices it connects. Using the pressure difference, it will propagate atmosphere properties along that edge. We essentially treat each probe as a cell connected to its neighbors by edges, and design a fluid-dynamics simulation at a variable resolution. This means that the air at eye-level can be simulated accurately and used for all sorts of cool visual effects, while the simulation around the player’s ankles can be kept extremely coarse to avoid wasting precious iterations. By iterating through edges, we partially avoid the combinatorial explosion that would result from comparing every unique pair of graph vertices, and we can ensure that no cells will be “skipped over” when calculating flow.

 

Interpolation – Pretending To Know What We Don’t.

Now, how do we actually sample this data?! The probes are nice, but what if the player is standing near them, rather than on them? We want to smoothly interpolate data between these probes, so that we can sample the mesh volume at arbitrary locations. Here, we can dust off our old 2D friend, barycentric coordinates. Normally, we humans like to think in cartesian coordinates. We define a set of orthogonal directions as “Up”, “Forward”, and “Right”, and then express everything relative to those directions. “In front, and a little to the right of me…” but coordinate systems don’t always need to be this way! In theory, we could describe a location using any basis.

bary2

An example of a barycentric coordinate system. Each triplet shows the coordinates of that point within the triangle.

Barycentric coordinate systems define points relative to the positions of the vertices of any arbitrary simplex. So for a triangle, one could say “80% of vertex 1, 26% of vertex 2, and 53% of vertex 3”.  Conveniently, these coordinates are also normalized, meaning that a point exactly at vertex 1 will be expressed as (1,0,0). We can therefore use these coordinates for interpolation between these vertices by performing a weighted sum of the values of all the vertices of the simplex, using their corresponding component of the coordinate vector of the sample point!

So, the value of the point at the center of the diagram would be equal to

x = 0.33M + 0.33L + 0.33K

or, the average of the values of each vertex!

By calculating the barycentric coordinates of the sample point within each tetrahedron, we can determine how to average the values of each corner to find the value of that point! For our application, by knowing which tetrahedron the player is in, we can simply find the coordinates of the player in barycentric space, and do a fancy average to determine the exact atmospheric properties at his or her position! By clamping and re-normalizing coordinates, this system will also handle extrapolation, meaning that, even if the player exits the volume of the graph, the sampled properties will still be fairly accurate!

Wait… you just said “by knowing which tetrahedron the player is in…” How do we do that? Well, we can use our mesh from before to calculate even more useful information! We can determine adjacency between tetrahedra by checking if they share any faces. If two tetrahedra share three vertices, we know they are adjacent along the face formed by those three vertices… wait, it gets better… remember we had barycentric coordinates for our sample point anyway. Barycentric coordinates are normalized, and “facing inward”, so if any of our coordinates are negative, we know that the sample point must be contained within the adjacent tetrahedron opposite the vertex for which the coordinate is negative.

We essentially get to know if our sample point is in another tetrahedron for “free”, and by doing some preprocessing, we can tell exactly WHICH tetrahedron that point is within for “free”.

In the final solution, the player maintains a “current tetrahedron” reference. Whenever the player’s coordinates within that tetrahedron go negative, we update that reference to be the tetrahedron opposite the vertex with the negative coordinates. As long as the player moves smoothly and doesn’t teleport (which isn’t possible in the game I was writing this for), this reference will always be correct, and the sampler will always be aware of the tetrahedron containing the player. If the player does teleport, it will only take a few frames for the current tetrahedron reference to “walk” its way through the graph and correct itself! I also implemented some graph bounding volume checks,  so I can even create multiple separate atmosphere graphs, and have the player seamlessly walk between them!

 

Concavity!

The last step was ensuring that I could actually design levels the way I wanted. I quickly found that I was unable to properly design concave rooms! The tetrahedralization would build edges through walls, allowing airflow between separate rooms that should be blocked off from one-another. I didn’t want to do any geometric collision detection because that would quickly become more of a hassle, and fine-tuning doorways and staircases to allow air to flow through them is not something I wanted to bother with. Instead, I implemented “Subtraction Volumes”. Essentially a way for a level designer to hint to the graph system that a given space is impassible. Once the atmosphere graph is constructed, a post-pass runs through the tetrahedron data and removes all tetrahedra which intersect a subtraction volume. By placing them around the level, the designer can essentially cut out chunks of the graph where they see fit.

subtraction-volumes

Notice in the first image there are edges spanning vertices on either side of what should be a wall. After sphere and box subtraction volumes are added, these edges are removed.

 

Looking Forward!

And that’s about it! Throwing that together, along with a simple custom editor in the Unity engine, I now have a great tool for representing volumetric data! In the future, I can generalize the system to represent other things, such as temperature or light-levels, and by saving the data used to calculate sample propagation, I can also determine the velocity of the air at any point for drawing cool particle effects or wind sound effects! For now, the system is finished, but who knows, maybe I’ll add more to it in the future 🙂

Advertisements

Object-Oriented Programming and Unity – Part 2

Recently, I’ve read complaints from a lot of Unity developers about how the engine doesn’t provide adequate support for object-oriented programming and design, with even very experienced developers running into this issue! In my opinion, this problem doesn’t really exist, and I feel as though most of the issues developers are facing stems from some fundamental misconceptions about how the engine is designed, so I’d like to take a moment to try and shed some light on the subject.

This is part 2 of a multi-part post. If you haven’t read part 1, I recommend you read it here.


Inheritance ≠ Object Oriented Programming.

OOP is a programming paradigm designed to make the design and use of a system more modular, and more intuitive to a developer. By grouping related data into objects, it can be treated as a unified collection, rather than a set of scattered elements, and can be added and removed from an architecture in a generic, and nonintrusive way.

One of the key concepts behind this is inheritance, allowing us to define “subclasses” of a class in order to extend its functionality. You can think of subclasses as a specific implementation of a more generic “parent” class, like how dogs and cats were both specific forms of animals in the previous inheritance example.

Inheritance is a large portion of traditional object-oriented programming, but the two are NOT synonymous. Object-oriented programming is merely a concept. The principles behind the Object-Oriented paradigm are equally valid with or without formal class inheritance, and can even be expressed in traditionally “non object-oriented” languages, such as C!

So why is Unity often criticized as being non-OO?

The Unity game engine maintains very tight control over its inheritance hierarchies. Developers are not allowed to create their own subclasses of many of the core components, and for good reason! Take “Colliders” for example. Colliders define the shape of an object for the physics system so that it can quickly and efficiently simulate physical interactions in the game world. Simulating physics is incredibly expensive, and as a result many shortcuts have been taken to ensure that your game runs as smoothly as possible. In order to minimize the workload, the physics system, (in Unity’s case, PhysX by NVidia), has been optimized to only process collisions on a set number of primitive shapes. If the developer were to add a new, non-standard shape, the PhysX would have no idea how to handle it. In order to prevent this, the kind folks at Unity have made Collider a sealed class, which can’t be extended.

Wait, then what can we modify?

Let’s look at the component hierarchy in Unity.

unity component hierarchy fixed

Yep, that’s it. The only portion of the Unity component hierarchy you are allowed to modify is “MonoBehaviour”.

GameObjects contain a set of attached “Behaviours”, commonly referred to as Components (while it is confusing within the context of the class hierarchy, it makes more sense when considering the exposed portions of the ECS architecture). Each of these defines a set of data and functions required by the constructed entity, and are operated on by Systems which are hidden from the developer. Each System is responsible manipulating a small subset of behaviours, for instance the physics System operates on Rigidbody and Collider components. With this in mind, how can developers create their own scripts and behaviors?

The Unity team had to come up with a solution that allowed all built-in components to be pre-compiled and manipulated without exposing any of the underlying architecture. Developers also couldn’t be allowed to create their own Systems, as they would need to make significant changes to the engine itself in order to incorporate their code into their application. Clearly, a generic System needed to be designed to allow runtime execution of unknown code. This is exactly what a MonoBehaviour does. MonoBehaviours are behaviours containing tiny Mono executables compiled while the editor is running. Much like the physics System, a MonoBehaviour System is managed by the editor, and is responsible for updating every MonoBehaviour in the game as it runs, periodically calling functions accessible to the scripting interface, such as “Start”, and “Update”. When a developer writes a script, it’s compiled to a MonoBehaviour, and is then operated on just like any other component! By adding a new System, and exposing a scripting interface, developers are now able to create nearly anything they want, without requiring any changes to the engine code, and still running with the efficiency of a compiled language, brilliant! (Keep in mind that the actual editor implementation is most likely more complex than this, however I feel that this cursory explanation is enough to effectively utilize the engine.)

Well, that’s all well and good… but what if some of my behaviours need to inherit from others?

Inheritance hierarchies work just fine within the context of MonoBehaviours! If we really needed to, we could make our own components, and have them inherit from one another, as long as the root class inherits from MonoBehaviour. This can be useful in some situations, for instance if we had a set of scripts which were dependent on another, we could provide all necessary functionality in a base class, and then override it for more specific purposes in a subclass. In this example, our MovementScript may depend on a control script in order to query input. We can subclass a generic control script in order to create more specialized inputs, or even simple AI, without changing our MovementScript.

Unity Monobehaviour Inheritance

The more experienced among you may recognize that, for this problem, perhaps implementing an interface would provide a more elegant solution than subclassing our control script. Well, we can do that too!

public interface MyInterface {}
public class MyScript : MonoBehaviour, MyInterface {}

There’s nothing special about MonoBehaviours. They’re just a very clever implementation of existing programming techniques!

MonoBehaviours sound really cool, but I have data I don’t want attached to a GameObject!

Well, then don’t use a MonoBehaviour! MonoBehaviors exist to allow developers to attach their scripts to GameObjects as a component, but not all of our code needs to inherit from it! If we need a class to represent some data, we can just define a class in a source file like you would in any traditional development environment.

using UnityEngine;

public class MyData {
    const int kConstant = 10;

    private int foo = 5;
    public int bar = 10;

    public Vector3 fooBar = new Vector3( 1, 2, 3 );
}

Now that this class is defined, we can use it anywhere we want, including in other classes, and our MonoBehaviours!

using UnityEngine;

public class MyMonoBehaviour : MonoBehaviour {

    private MyData data;

    void Start () {
        data = new MyData();

        data.fooBar = new Vector3( -1, -2, -3 );
    }
}

Also keep in mind that the entirety of the .NET framework (Version 2.0 at the time of this article) is accessible at any time. You can serialize your objects to JSON files, send them to a web-server, and forward the response through a socket if you need to. Just because Unity doesn’t implement a some feature, doesn’t mean it can’t be done within the engine.

 


This post demonstrates a few examples of how data can be handled outside of the MonoBehaviour system. This post is continued in Part 3, where we will recap a few points, and conclude this article.

PART 3 =>

Object-Oriented Programming and Unity – Part 1

Recently, I’ve read complaints from a lot of Unity developers about how the engine doesn’t provide adequate support for object-oriented programming and design, with even very experienced developers running into this issue! In my opinion, this problem doesn’t really exist, and I feel as though most of the issues developers are facing stems from some fundamental misconceptions about how the engine is designed, so I’d like to take a moment to try and shed some light on the subject.


Unity Engine Architecture, and Composition vs. Inheritance.

The Unity game engine represents the “physical” world of your program using an Entity Component System architecture. Each “object”, be it a character, a weapon, or a piece of the environment, is represented by an entity (referred to as GameObjects in the Unity engine). These entities do nothing on their own, but act as containers into which many components are placed. Each component represents a functional unit, and dictates a specific subset of the behavior of our object. Lastly, Systems act as a higher-level control system, which act on entities to update the state of their components. ECS has become increasingly popular in the game development world, as it provides some key advantages over more traditional architectures.

  1. Components are completely reusable, even across objects with dramatically different behaviors.
  2. Components provide near infinite extensibility, allowing new behaviors to be added to the game without touching any of the existing code.
  3. Components can be added and removed at run-time, allowing for the behavior of objects to change while the application is running, without any significant effort.

The entity component architecture embodies the principle of composition over inheritance, a relatively new programming paradigm which favors the structure and composition of an object over a hierarchy of inheritance. This is especially helpful when building a large application like a game, which requires many things to share large amounts of very similar code, while still being different in sometimes hundreds of ways.

Let’s look at an example.

Imagine we have a client who wants us to write a game about animals! Let’s represent a dog, and a cat in our code. The immediately intuitive solution would be to make a superclass called “Animal”, to contain the commonalities of both cats and dogs.

Animal_inheritance_corrected

That’s fantastic! Look, we just saved having to duplicate all of the code required to give our animal ears, legs, and a tail by using inheritance! This works really well until your client asks you to add a squid. Ok! Let’s add it to our animal class! Unfortunately, squids don’t have ears, or really much of a tail. They’ve also got 10 limbs, so our class hierarchy will have to change a bit. Let’s add another superclass, this time separating cats and dogs into their own group.

Animal_inheritance_2_corrected

Ok, there we go. Now the things shared across all animals can be separated out, and our dog and cat can still share legs, a tail, and ears! Our client liked the squid so much, he wants us to put in other ocean animals too! He asked us to put in a fish! Well, both fish and squid swim and have fins, so it would make sense to put them together… but fish also have a tail, and right now, a tail is defined as a part of mammals!

Animal_inheritance_3_corrected

Oh no! Suddenly, our hierarchy doesn’t look too good! While it makes the most sense to put animals into groups based on their defining characteristics, sometimes characteristics will be shared across multiple different subtrees, and we can’t inherit them from a parent!

Composition to the rescue!

Rather than defining our animals as a hierarchy of increasingly specific features, we can define them as individuals, composed of independent component parts.

Animal_composition

Notice that we still don’t have to duplicate any of our code for shared features! Attributes like legs are still shared between dogs, cats, and squids, but we don’t have to worry about where fish fit into the picture! This also means that we can add any animal component we want, without even touching unrelated animals! If we wanted to add a “teeth” component, we could attach it to dogs, cats, and (some) fish to provide new functionality, and wouldn’t even need to open the file for squids!

This model also allows us to add components at run-time to change functionality. Let’s say we have a robot. This robot normally attacks the player on sight, and does generally evil things. It’s pretty complicated too! The robot can move around the game, use a weapon, open doors, and more! What happens when our player hacks this robot character to be a good-guy? We could make a second type of robot, which can do everything the evil robot can, OR we can remove the “robot_AI_evil” component, and replace it with “robot_AI_good”. With the AI component replaced, our robot can help us and still do everything the evil robot could. If it’s well designed, it could even display more complex behavior, and use abilities it typically would use against the player to help defend against other robots!

Know that inheritance isn’t a bad thing, in fact we to use it to define our body part components, but understand that in some situations, other paradigms may be more useful!


This post provides a cursory look at the Unity engine’s general world representation, as well as a cursory look at some of the potential benefits of the “composition over inheritance” principle.
This post is continued in Part 2, where we will look at MonoBehaviours, and their role in the Unity engine.

PART 2 =>