So what have I been upto?

It’s been a long time since my last post… and boy, has it been a journey. I’ve had my ups and down in life and work, but 2012 is over and the new year beckons. During the last month of 2012, I met some really influential people, made some new friends, caught up with old friends, and overall had a good time. It’s great to see the game development scene emerging in India.

Meanwhile however, my own personal projects and coding skills have taken a beating. I decided to fine tune my skills and start off low level, building my own memory manager. It’s based on Paul Laska’s implementation,  which although dated, is pretty good for simple games, or indie games where speed and ease of implementation often need to be balanced. Also, I’ve taken ideas from 3D Game Engine Design as well as the unbelievably informative Doug Lea’s malloc description

The project is hosted on github at the MMM project page, which makes it free and open source. So go check it out. MMM stands for Megamind Memory Manager, and has no discernable resemblance to the movie :) (It does have the noble need to take over control of the entire memory of the system)

The next few post will detail a few of implementation details of the manager.

Also, note that although this project is still in it’s nascent stages and is experimental in nature, and feedback is absolutely essential. So if you feel like shouting out or yelling at me, feel free to do so :) I’m always open to suggestions.

Memoization in C++

The class of Dynamic Programming problems are very interesting. These problems all boil down to a class of optimization problems. Such problems are characterized by the distinctive reduction in their design. This reduction can lead to smaller sub-problems that are solved and the results bubbled up. In essence, dynamic programming problems are solved bottom-up, since the results of the sub-problems drive those above them.

The problem with such a technique lies in the fact that every solution requires you to solve every sub-problem to obtain an optimal solution. Memoization provides a simple and largely effective solution to alleviate this problem by storing results to these overlapping sub-problems for future use. Let’s look at an example using the evergreen fibonacci series:

Inside the guts of Memoization

The naive solution to recursive fibonacci series is :

int fib (int n)
{
    if( n <=1 )    return 1;
    else           return fib ( n-1 ) + fib ( n-2 );
}

Let’s look at what happens when we run it for a couple of values :

fib (5) ; // = fib(4)  + fib(3)
          // = (fib(3) + fib(2)) + (fib(2) + fib(1))
          // = ( (fib(2) + fib(1)) + (fib(1) + fib(0)) ) + 
          //               ( (fib(1) + fib(0)) + fib(1))
          // = ( ( (fib(1) + fib(0)) + fib(1)) + 
          //               (fib(1) + fib(0)) ) + ( (fib(1) + fib(0)) + fib(1))
          // 7 '+' operators.

fib (6) ; // 6 overlapping subproblems, 
          // results in '+' operator being run 11 times, 
          // extrapolating from above.

But we already calculated fib (5), didn’t we? And since

fib (6) = fib (5) + fib(4);
and
fib (5) = fib(4) + fib(3);

We’ve already calculated fib (4) too. So fib (6) needs to just add the 2 values, resulting in just a single ‘+’ operation.

To use this information in our solution, let’s use a global map that stores intermediate solutions. (we can use hash_maps for faster un-ordered  access when the TR1 specification and C++0x is standardized)

std::map<int, int> fibHash;

int memoized_fib (int n)
{
    std::map<int, int>::iterator fibIter = fibHash.find(n);
    if( fibIter != fibHash.end() ) return *fibIter;

    int fib_val;
    if( n <=1 )    fib_val = 1;
    else           fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );
  
    fibHash[ n ] = fib_val;
    return fib_val;
}

This is a fairly one off solution, and requires modifications for using with multiple functions… but with C++0x we can do fully automatic memoization as described here : http://cpptruths.blogspot.in/2012/01/general-purpose-automatic-memoization.html

Coming up : my feeble attempt at auto-memoization in the current version of C++.

 

Building endless terrain in Unity3D

[EDIT] Find the updated location for Helix Toolkit’s DoubleKeyDictionary.cs here..

[EDIT] Finally, the new, independent script is up here

The first thing we needed in ‘Songlines’ was to create a realistic open world environment is to have no boundaries, where the player can move freely and fly in any direction as far as he wanted, and one thing we noticed very quickly was the terrain in Unity was created as a tile, and each tile is described by a width, height, length, and the most important attribute for us, as we’ll see later, ‘heightmap resolution’. The details of these attributes is described in the Unity – Using Terrains

We start off by placing a single Unity terrain tile, as shown here:

Single Terrain Tile

The parameters to choose for the tile of your terrain depend on a number of factors, including:

1. How high can the player go? If the player can fly really high above the terrain, he can probably notice the edge of the world, or the end of all the tiles. In such a case, we may need to drop additional tiles so the horizon stays invisible, or we use a tile really large. The higher you go, the lower your chances with a super-tile, so i’d suggest stick to a conservative value and drop tiles when required.

2. How fast does the player move across the tile? So this is more of a question of game mechanic. Does the player fly or walk across the terrain? If he walks/runs, how fast does he do that?

3. How far do you anticipate the player would go before he stops, or, you know, gets bored? This is where we had a problem in our game, we found that players, in the tests, would continue to fly endlessly in a straight line, and this meant, virtually endless terrains are a must. In this case, we needed frequent checks to ensure the player doesn’t lose track of where he’s going, or he doesn’t reach the end of the world.

4. Do you need additional functionality in the terrain? Do you need dynamic terrain deformation? Do you need to add details or prefabs at runtime in the game. If the answer to any of these questions is yes, stick to a lower resolution for optimal performance.

The attributes I use for our terrain is :

Terrain Settings

Designing a Terrain Manager

A terrain manager must:

1. Keep track of all terrain tiles currently in the scene.

2. Track the current player position and view vector.

3. Based on the field of vision and the parameters calculated in (2), decide if a terrain tile needs to be placed.

 

Part 1 – Keeping track of all terrain tiles in the scene.

In order to keep track of the terrain tiles placed in the scene, I need a list. A list of all terrains, but this must be easily accessible. The key to such a list is the 2-dimensional index of the terrain tile. Since each tile is evenly sized, it’s easy to calculate the 2D index.

Tile Indices

Now, we need an efficient way of indexing this list. That’s where DoubleKeyDictionary from Helix Toolkit comes to the rescue. It provides a 2 keyed dictionary by creating two dictionaries internally. An understandable overhead for such an essential functionality.

We then create a terrainList to contain all Terrain objects using 2 integer keys (x and y indices) of the terrain tile in question.

private DoubleKeyDictionary<int, int, Terrain> terrainList = 
                         new DoubleKeyDictionary<int, int, Terrain>();

Part 2 – Track the current player position and view vector

Player position = transform.position;
View Vector = Camera.mainCamera.transform.forward;

In order to calculate what tiles need to be placed, we can iterate over the view vector and sample at a couple of locations forward. Also, in order to compensate for the fov, we can transform the view vector 45 degrees to the left and 45 degrees to the right and sample over those vectors too, as shown below.

Part 3 – Decide if a terrain needs to be placed 

First, we sample the terrain under the first of the vectors, under the player, and forward 500 units.

GetTerrainUnder(transform.position + Camera.mainCamera.transform.forward 
                * 500.0f);
GetTerrainUnder(transform.position + (Camera.mainCamera.transform.forward
                + Camera.mainCamera.transform.right) * m * 500.0f);
GetTerrainUnder(transform.position + (Camera.mainCamera.transform.forward
                - Camera.mainCamera.transform.right) * m * 500.0f);

Given the position to sample at, we can transform that to an index by :

index x = Mathf.FloorToInt((x - terrainOriginPosition.x) 
                           / Terrain.activeTerrain.terrainData.size.x)
index y = Mathf.FloorToInt((z - terrainOriginPosition.z ) 
                           / Terrain.activeTerrain.terrainData.size.z )

where terrainOriginPosition is set at the start of the script to the position of the initial tile.

terrainOriginPosition = Terrain.activeTerrain.transform.position;

We then check the list if the terrain exists:

terrainList.ContainsKey(x, y)

and if it doesn’t exist, we can drop another tile:

TerrainData tData = new TerrainData();
tGameObject = Terrain.CreateTerrainGameObject(tData);
tGameObject.transform.position = piecePosition;

where

piecePosition = terrainOriginPosition 
                 + new Vector3(x * tileDimensions.x, 
                               0, 
                               y * tileDimensions.y);

and

Vector2 tileDimensions = 
    new Vector2((Terrain.activeTerrain.terrainData.heightmapWidth - 1) 
                * Terrain.activeTerrain.terrainData.heightmapScale.z,
                (Terrain.activeTerrain.terrainData.heightmapHeight - 1) 
                * Terrain.activeTerrain.terrainData.heightmapScale.x);

Set Neighbors to Match LOD

Once we drop the new tiles, we must set the neighbors on all the surrounding terrain tiles to ensure LODs match up.

public void SetTerrainNeighborsFor(Vector2 tID)
{
  if (GetTerrainAt(tID))
    GetTerrainAt(tID).SetNeighbors(GetTerrainAt(tID + new Vector2(-1, 0)),
                                 GetTerrainAt(tID + new Vector2(0, 1)),
                                 GetTerrainAt(tID + new Vector2(1, 0)),
                                 GetTerrainAt(tID + new Vector2(0, -1)));
}

Conclusions

That’s it. All other settings are optional. For more information, attached is a copy of the completed script. Just add it to the Player object and watch the tiles unfold.

<<TerrainManager>>

Also, and example unitypackage (zipped for wordpress love) here

In the next post I’ll talk about how we can set up dynamic terrain deformation in Unity…

Python to the rescue

I ran into an interesting problem today. My web server runs Apache on linux and some of my legacy links were encoded in Unicode. I had to fix all the unicode characters so the filenames aren’t in unicode. I had to first find all the files that were in unicode. After a lot of googling, I found this python script, at http://superuser.com/questions/237533/find-files-with-non-ascii-characters-in-filenames-in-windows-xp that helped me.

 

import sys, os

def main(argv):
    if len(argv) != 2:
        raise Exception('Syntax: FindUnicodeFiles.py ')

    startdir = argv[1]
    if not os.path.isdir(startdir):
        raise Exception('"%s" is not a directory' % startdir)

    for r in recurse_breadth_first(startdir, is_unicode_filename):
        print(r)

def recurse_breadth_first(dirpath, test_func):
    namesandpaths = [(f, os.path.join(dirpath, f)) for f in os.listdir(dirpath)]

    for (name, path) in namesandpaths:
        if test_func(name):
            yield path

    for (_, path) in namesandpaths:
        if os.path.isdir(path):
            for r in recurse_breadth_first(path, test_func):
                yield r

def is_unicode_filename(filename):
    return any(ord(c) >= 0x7F for c in filename)

if __name__ == '__main__':
    main(sys.argv)

Deferred Renderer – Official stupidest mistake

Every programmer goes through this at some point where they need to step back, whack their forehead and realize how stupid they’ve been. So I’ve been fighting with my lightMap because it wouldn’t render the right info, and after 2 hours I see that my vertex shader has

output.TexCoord = input.TexCoord = halfPixel;

instead of a

output.TexCoord = input.TexCoord - halfPixel;

Learning something new everyday!