Programming

Summer 2019 Project Round-Up

It’s been a few months since I’ve updated this site, and this is because I’ve been busy preparing to start a new job overseas! That’s right, I’m moving to Prague tomorrow. I’m very excited, and expect to be even more busy for the next few months as I get settled in a new city and undergo the work on-ramping process.

As such, I thought now would be a good time to show off some of the projects and experiments that I have been working on in my spare time.

The project I’ve spent the most time on is a portal rendering system. This is an off-shoot from my time working on Liminal. For Liminal, we used the render texture method to implement our portals. This is the most common approach. For those unfamiliar with it, it uses extra cameras to capture an image of the view out of the other side of a portal, then draws that image onto the near-surface of the portal.

Render-texture portals are great for most applications, but they have some performance limitations, Each portal in view requires you to render at least one additional camera. This isn’t too bad if you are only rendering one or two portals, but the rendering costs can rise steeply when you start rendering portals “nested“ within other portals. Furthermore, this approach can also require you to disable your engine’s occlusion culling, which can be another big efficiency hit.

The alternative approach that I’ve been playing with instead makes use of a rendering feature called the stencil buffer. The stencil buffer allows shaders to mask areas of the screen, such that later shader passes can be made to behave differently on pixels inside or outside of masked areas. My system works by simply rendering copies of the rooms seen through portals. These duplicate objects are rendered with a special shader that is configured to duplicate the lighting on the original objects, but also makes them invisible unless rendered in an area of the screen covered by the correct mask. The shaders on the portal planes write to the stencil buffer, masking objects behind them on the nearside of the portal but revealing the objects and nested portals keyed to the appropriate mask layer.

This approach has the advantage that performance mostly scales in a linear fashion as portals are nested, since each nested portal more or less adds a set of copied objects to the scene. The same limitations apply as would to simply adding a lot of conventional objects to the scene. In the example video I have the maximum nesting limit turned down to four, but I’ve found that I can easily run it at 50 or 100 without a detectable dip in frame rate.

There is still a lot to do. Besides various performance optimizations, I still need to add support for dynamic objects and dynamic lighting, improve the realism of my shaders, and support for per-portal skyboxes, and implement a system to allow flicker-less camera transitions through portals.

Besides this portal system, I’ve experimented in two other areas. One is procedural generation of organic tile sets. You can see an example image in the banner’s on this site. I will try to produce better images in the future. The second project was a short game jam where I messed around with Wang tiles. I didn’t really have a game at the end of it, but I did get the tiling system operational and had some success with some visual style experiments.

It may be a while before I have time to work on these projects again, but I learned a lot from each of them and certainly plan to do more with them when I have the opportunity.

Fun with 4D Meshes

   Over summer break I wrote a fun bit of code in Unity. It's a component for displaying a three dimensional mesh representation of a four-dimensional shape.

   How did I go about doing this? The first thing I needed to do was create a data structure for describing a “4D Mesh.” The key thing to understand about meshes, of any dimensionality, is that they describe shells, not actual shapes. A 3D mesh is a collection of 2D faces arranged in 3D space. Similarly, my 4D mesh asset is simply a collection of 3D tetrahedrons arranged in 4D space. Its data structure works on exactly the same principles; an array of Vector4s describing vertices positioned in 4D space, and an array of integers describing tetrahedrons by referencing sequences of four vertices.

4DShape.gif

   The second piece of necessary script is a process for translating a cross-section of a 4D mesh into a 3D mesh that can be read by Unity’s mesh renderer component. To do this, I need need the two key elements of a 3D mesh: an array of verts, and an array of triangles. The 3D verts need to be calculated based on the viewer’s current w-position since they describe points along the edges that connect 4D verts. These verts are added to a list, and their indices are also stored in a two-dimensional array. This is so that when I translate the tetrahedrons into triangles, I can use the indices of two 4D verts in a tetrahedron to find the index of the 3D vert that represents the edge between them.

   I plan to post the code on Github eventually, once I’ve done a little more cleanup and optimization. Currently the script makes an effort to cull unused vertices from the mesh it outputs to the mesh renderer, but I suspect that it’s faster and less memory intensive to simply process all the verts since it saves me the trouble of reconstructing a 3D vert index list whenever the mesh needs to be updated. I’m also looking into Unity’s new job system since it could allow me to do much of the calculations on a separate processor.

   The biggest roadblock in the experiment right now is actually the difficulty of inputting the data for a 4D mesh. So far I’ve been doing it by hand. For the shape in the gif above, I needed to input 16 Vector4s (64 values), and 32 tetrahedrons (a sequence of 128 integers). Now that ProBuilder is available for free in Unity 2018, I’m thinking about writing an extension that would allow me to better model and visualize a 4D shape.

A Bit of Bitmask Evangelism

   Friend, have you heard the good word about bitmasks? I’ve found them to be an extremely useful tool, one that I’ve used several times to make my code far more readable and efficient.

   First, let me give a (relatively) vernacular explanation of bitmasks. Computers store data as sequences of ones and zeroes. Normally these sequences are interpreted as binary representations of numbers, numbers that can then be interpreted as other things like text or enumerated types.

   A bitmask is simply a variable that is thought of as an array of booleans instead of a binary number. Bitmasks are useful for describing a subsets of sets. A good example of this is the layer system used by Unity and other game engines. Each layer is associated with a power of two, which means that each layer corresponds to its own bit in the sequence: Layer_A = 1, Layer_B = 2, Layer_C = 4, Layer_D = 8, and so on…

   I’ve linked a more indepth explanation of bitmasks and bitwise operations here. A good post about writing enumerations as bitmasks in Unity is here and below I’ve pasted the code for a custom property drawer for Unity that applies the built-in Layermask drawer to your own mask enumerations.

//Remember to place this class in a folder named Editor
using UnityEngine;
using UnityEditor;
[CustomPropertyDrawer(typeof(MaskFieldAttribute))]
public class MaskFieldDrawer : PropertyDrawer {
    public override void OnGUI(Rect _position, SerializedProperty _property, GUIContent _label)
    {
        EditorGUI.showMixedValue = _property.hasMultipleDifferentValues; //This was a safety line suggested in the forum for multi-object editing scenarios.
        _property.intValue = EditorGUI.MaskField( _position, _label, _property.intValue, _property.enumNames );
    }
}

Custom Property Drawer

//Remember to place this class in a folder named Editor using UnityEngine; using UnityEditor; [CustomPropertyDrawer(typeof(MaskFieldAttribute))] public class MaskFieldDrawer : PropertyDrawer { public override void OnGUI(Rect _position, SerializedProperty _property, GUIContent _label) { EditorGUI.showMixedValue = _property.hasMultipleDifferentValues;//This was a safety line suggested in the forum for multi-object editing scenarios. _property.intValue = EditorGUI.MaskField( _position, _label, _property.intValue, _property.enumNames ); } }

   Bitmasks have made my life easier on multiple occasions. I used them to write my own tag masks for unit behavior logic in Orbit Project. Tablecraft’s code was very quick and dirty, but now that it has become a larger project this semester, I’ve suggested to the new programming team that they ditch my messy loops-within-loops and use bitmasks to compare sets of element cubes.

   The example I really want to talk about is the puzzle-agnostic state-graph builder I wrote for my tech design final last semester. The project really warrants its own post, but I’ll describe it briefly here. The graph builder receives a puzzle class object (all puzzle classes adhere to the same interface). Using the initial state of the puzzle as its starting state, the builder gives the puzzle class a state and asks for all the states that lead from that state. In this way the builder performs a breadth-first search of the puzzle’s state graph. The plan is to eventually write tools that can use this information to assess the properties and overall quality of a puzzle.

   Where do the bitmasks come in? Not in the builder itself. Bitmasks came up because I chose a mobile puzzler named Kami 2 as my test subject. In Kami, the player uses a “paintbucket” mechanic to deconstruct a pattern of colored patches. The goal is to paint the canvas all one color in the minimum number of moves.

   Each given state of a Kami puzzle consists of a set of colored areas, with each area being adjacent to some of the other areas. When a player fills in an area, it combines with adjacent areas of the same color to become a super area.

   Bitmasks made this logic extraordinarily easy. Each initial color patch in the puzzle is given a layer in the bitmask, as well as a mask listing all the other patches that border it. When two areas merge, I simply use a bitwise OR operation to combine both their area mask and their adjacency mask. To check if two areas are adjacent, I use a bitwise AND to check for overlap between the area mask of one patch and the adjacency mask of another.

   Because the same super area can show up many different puzzle states, I ended memoizing area-to-adjacency relationships by storing them in a dictionary (int bitmasks serve as their own hashcode). These little optimizations add up, because even a simple Kami puzzle can have tens-of-thousands of states.