Keeping Track: Trello for Game Development

If you haven't heard of Trello, it's a free service which provides what boils down to a fancy to-do list.
In Trello, you have different categories. By default, these are To Do, Doing, and Done. You can also add your own categories.
To each category, you can add Cards. These are individual items, like say "Fix the sink" or "Buy milk". You can also move cards between categories (you might move a card from To Do to Doing, and then later from there to Done).
Trello also has a handy collaboration feature - multiple people can work on the same to-do list (or "Board" as Trello calls it).
As it turns out, despite being designed as a generic to-do list, Trello doubles as a fantastic project management tool.
You can create an "organization" in Trello, to which you invite other people, and then create a board private to that organization. You add as many categories as you need, and then use cards to keep track of tasks that need to be done on the project.
For instance, in my current project I have 5 categories: To Do, Bugs, Fixing, Doing, and Done. To-Do is for new features that need to be implemented, Bugs is for problems that need to be resolved, Fixing is for bugs which have been resolved, Doing is for features which need to be implemented, and Done is for any tasks which have been completed.
Even though I'm working alone (for now), I've found it immensely useful for staying focused and on track. Many times in the past have I tried working purely from memory, and I can say it almost never works. Keeping a list of things to do means I'm never sitting there trying to figure out what to work on next (and meanwhile losing the drive to work on the project). I add stuff to the To-Do list any time I think of something, move the next task to Doing, knock it out, move it to Done and immediately pick my next task.

Could I have done this with sticky-notes or a notepad? Sure, definitely. But Trello is arguably more convenient and paper-friendly ;)

Just Write A Game

When developing a game you're passionate about, sometimes you turn into a perfectionist. Hours of googling are sunk into researching shiny bits of tech that don't really matter. There comes a time when you need to quit obsessing and just write a game.

Just this last week, I became utterly obsessed with the thought of huge-scale worlds. ArmA of course was a big inspiration, supporting absolutely gigantic maps of 50km or even 100km, far eclipsing the size of games like Skyrim. This is made possible because ArmA is based on a military simulation engine, which was designed for accuracy and huge scale and uses double-precision to represent coordinates. I don't get this luxury out of the box in Unity, but I wanted it so badly I sunk hours and even days of research into fighting Unity to get what I wanted. Floating point origin, terrain streaming, and even customized builds of third-party physics engines - nothing was out of the question to me.

I never even came close to completing my research and testing, and haven't even come close to creating a semblance of a game with it.

I realized that I needed to put down Google, and actually write a goddamn game.

I mean, hell, 32-bit floats give me 10km away from origin. That comes out to a usable world space of 20km (from -10km to +10km on each axis, if the world is perfectly centered around origin) before precision issues kick in.

That's huge. It's nearly the size of Skyrim (actually 37km, but approximately a quarter is hidden behind invisible walls and artificial barriers). It's bigger than Chernarus from ArmA/DayZ, which as far as I know is 15km x 15km. For a mostly on-foot multiplayer survival game, that is massive.

Even if I could have enormous 50km maps, what would I fill it with? Big stretches of the map would end up barren, leading to a huge but boring world. Small, but interesting, worlds are better than huge, and boring, ones.

So I need to just stop worrying and start writing something productive.

The importance of custom-built solutions

It's only been somewhat recent that we've seen a massive surge in game development middleware. It used to be, not long ago, that games were entirely custom-built from the ground up. These days you can find an off-the-shelf product for nearly every task in game development, and you might even wonder where you would be without them.

But sometimes, you have a use-case so wierd, so uncommon, that there's just no product for you. You've tried everything, from the industry-tested AAA products to the backwaters-of-the-internet open source solutions, but nothing works.

And that's when you custom-build it.

I just recently encountered this while developing an open-world game project. The problem? How to make my AIs intelligently navigate a huge open world with pathfinding.

At first, as anyone would, I thought to myself, "There's such a HUGE number of pathfinding solutions for Unity. This should be a piece of cake!".

And that's where I was partially wrong. Yes, there's lots of them, but not a single one of them designed for even marginally big game worlds and also in my budget.

My first try was Unity's own pathfinding, basically a port of Recast. It failed right out of the gate, since it couldn't even export the scene data to be voxelized within a reasonable length of time.

My second try was Aron Granberg's pathfinding. I never had much luck with this one in the past, but I gave it another shot. Still no luck - it's grid generator seemed to have severe trouble generating a graph for such a large terrain.

Eventually I realized I needed something highly customized to my needs - something I wouldn't be able to solve with money. Time to break out the elbow grease and the thinking caps.

The problem here is that my world is designed a bit like Arma 2. There's a big 10km^2 island, upon which are various buildings which can be entered. Said buildings will NOT be separate zones, but luckily will be fairly simple (just a few rooms and hallways, not more than a couple stories, etc).

I figure I can divide this into separate graphs, which are somehow linked: A grid graph for my outdoor area, and a waypoint graph for my indoor areas. These will be linked with special navigation nodes (which I'll call "offmesh links" for lack of a better term).

My outdoor grid graph is simply generated based on the terrain's heightfield and "occluder boxes" (which I would use to punch holes in the terrain navigation grid). One really nice property of A* is that it does not explore much more than it needs to - so if my AIs are only chasing nearby opponents, even with a huge world there's still a fairly light workload on the pathfinder. I've also decided that I will not make the grid fine-grained enough to represent trees - it would take up a hell of a lot more memory than I would like, and I can just stick in some simple obstacle avoidance to navigate around trees. I've found a 512x512 grid represents my terrain quite nicely then, if I don't care about trees. I also added a cutoff to the pathfinder - if it explores more than 1000 nodes, it simply quits. This number is large enough that the AI can pathfind halfway across the map (I specifically tested this), but still small enough that if the AI tries reaching an unreachable island it will exit out long before it exhausts the search space.

One thing I needed was to make my pathfinding algorithm as generic as possible. To that end, I created interfaces for INode, IGraph, and ICostEstimator. A node has a position in the game world, a G and H cost (I don't really care about costs for traversing individual nodes, but that would be trivial to add), a graph it belongs to (entirely optional - for instance, offmesh links are technically INodes but do not belong to a graph), and neighboring nodes. A graph simply contains nodes and can locate the node nearest a particular point. A cost estimator estimates the H cost between a given node and the goal node (currently implemented are Manhattan and Euclidean).

Waypoint nodes have explicit neighbors - baked at design time by raycasting to waypoints in the same graph. Grid nodes, on the other hand, have implicit neighbors - these are calculated on the first request and cached for subsequent calls.

My waypoint graph also has a bounds property, which represents the extents of the graph. This is used in order to locate the nearest INode to a given world position - first all waypoint graphs in the scene are queried to check if their bounds contain the point. If one does contain the point, it is queried for the closest waypoint. The terrain grid is also queried for the closest point (which is found by quantizing the point and converting this to a 2D grid index). Whichever of the two points is closest is chosen.

This is used for two purposes - one, for pathfinding (first the start and end nodes are located, then pathfinding is performed), and two, for offmesh links.

Offmesh Links as mentioned before are a way to link my grid and waypoint graphs together. An offmesh link is a special type of node with exactly two neighbors. On startup, these neighbors are located by finding the nearest nodes to two points, and then the offmesh link is registered as a neighbor with both nodes (and therefore becomes a shared neighbor of both). By, for instance, placing one side of the offmesh link inside a building, and the other outside the building, the inside one will locate a waypoint, and the outside one will locate a grid cell. These two are then linked together via a shared neighbor. These nodes would be placed, for example, at the entrances of a building. The nice feature is that they don't care which type of nodes they link, so it's entirely possible to link two grid cells (for example, if there's a teleporter). If I wanted, I could also associated extra data with an offmesh link such as an enum of what type it is (for example, I could specify that a particular offmesh link is an elevator, which the AI would respond to by waiting for the elevator to arrive, getting in, waiting for the elevator to arrive at the appropriate floor, and getting out).

It took me two days to accomplish all of this, but it was well worth it. I added some extras as well, such as multithreaded pathfinding (all pathfinding work is offloaded onto a separate worker thread) with callbacks for when a path request is serviced. Pathfinding is reasonably fast, and agents can not only pathfind a fair around the world, but they can also pathfind in and out of buildings. None of this could be provided in a third-party solution, but was fairly quick to accomplish and fits my needs perfectly. It's also pluggable, which means I can reuse it in other projects and extend it (for instance, by adding navmesh support).

And that's why it's important to custom-build stuff - because when you're making a game that few others dare to attempt, you've got no choice but to build it yourself.

Large Streaming Terrain in Unity: An Adventure

Recently, I made a fair bit of progress towards a streaming terrain solution in Unity. This kind of system powers open-world games like Grand Theft Auto, Skyrim, Fallout, and more.
I wanted to share the process behind it, and current progress thus far.

Some of my work was initially based on the GIS talk from Unite. The idea is that I'll store terrain files to be loaded in the StreamingAssets folder. So far, I've got Heightmap files (RAW) and Splatmap files (PNG). Later on I'll probably figure out how to store detail densities, but that's enough for now. When a terrain tile is needed, I load both the Heightmap and Splatmap associated with the tile (by name, based on tile X and Y) and create a new Terrain object.

Just having a terrain isn't enough. I need scenery, of course. I decided on the condition that all scenery to be saved must be a prefab in a resources folder - this allows me to simply serialize the name of the object, and later I can load the object via Resources.Load.
Objects are stored in yet another file, in a custom binary format I call the World Tile Format, and files are stored as .WTFs. The obvious pun was probably the biggest driving factor in choosing the name.
My first attempts to save objects were unsuccessful. The files always came out empty - WTF indeed. Turned out to be a simple error - forgot to close a stream. After getting that sorted out, I could save and load objects for individual terrain tiles. I also drafted up a simple editor utility to let me do this - it allows me to load terrain tiles, and save WTF files (saves the list of objects within the bounds of each terrain tile).
The actual format is pretty simple.

The header consists of 10 bytes, and looks like this:
{
    MAGIC: three ASCII chars ('WTF')
    VERSION: one byte.
    OBJ_COUNT: four bytes (uint)
    TREE_COUNT: two bytes (ushort)
}

As you can see, I also decided that my WTF file should store trees for a terrain tile.

Following the header is a big dump of each object. Each one is 296 bytes and looks like this:
{
    OBJECT_ID: 256 ASCII chars
    POSITION_X/Y/Z: four bytes per (float)
    SCALE_X/Y/Z: four bytes per (float)
    ROTATION_X/Y/Z/W: four bytes per (float)
}
I may trim down OBJECT_ID later, depending on how I feel. Have yet to see a prefab with anywhere close to 256 characters in the name, but you never know.

And finally, a dump of all trees. Each tree is just 5 bytes and looks like this:
{
    TREE_IDX: one byte
    POSITION_X: two bytes (short)
    POSITION_Y: two bytes (short)
}
Each position field is divided by short.MaxValue on load to map to the range 0-1 (I wanted to use bytes, but given a terrain tile spanning 650 meters that gives me a resolution of several meters, whereas a short gives me a resolution of smaller than a meter, but is still half the size of a full float value).

And this brings me to the current state of the thing.
Currently trees are unused (they are loaded from disk into a TreeInstance array, but not applied to the terrain - doing this would be trivial, however). My TerrainManager loads a radius of terrain and object tiles around the camera. The radius of each is different, so that I can load a big portion of terrain to avoid popping, but reduce the object load radius (since objects popping in/out is less noticeable than terrain popping in/out, especially with smaller objects). I believe Skyrim does something similar.
The last piece of the puzzle missing is detail objects like grass and bushes. I have not yet decided how I will store these, I might figure out how to store them in splatmap-style images (four detail objects neatly maps to R, G, B, and A channels which could map to a density range).
I also have a fair bit of optimizing to do. Loading terrain by itself is pretty speedy, although loading objects causes a noticeable hitch in framerate. I expected to spend time optimizing, however - it's my first try at anything remotely like this.

Still don't know what to do with this if I finish it.

2014. Yay.

Been a fair bit since I posted. Don't have anything groundbreaking or particularly rant-ish to post today, so I'll just sum up how my transition from 2013 to 2014 went.

Unity Multiplayer Games is now officially published. Yay! If you haven't considered buying it, for shame! I'm just kidding. But seriously, go buy it.

In other book-related events, I received a copy of Masters of Doom for Christmas. I finished it in two days (it was very difficult to put down). It's an excellent read, and I highly recommend it.

Got a new Xbox 360 E as well, plus GTA 5. First game I've owned in the series (I was previously uninterested, until Rockstar announced GTA Online, and watching Achievement Hunter videos thoroughly converted me). I expect to be playing plenty of that.

I'm toying with the idea of rebooting an old game of mine, NecroPixels. It was originally an entry for a multiplayer games contest which one third place. That said, I've lost the original source code - which is fine, since it was buggy as hell to begin with. One idea is to shoot for DOOM-style graphics. It's just a thought for the moment.

I'm also making more forays into physically-based shading. I've been toying with simplified/modified cook-torrance. I say "modified" because the fresnel effect was way too strong for my taste (could have been the implementation, not sure). Don't know if I'm going to really finish it or not.

Sorry if the post feels disorganized and rambling. I just felt the need to post something so people know I'm not dead. Or abducted by aliens.