Procedural Content Generation Part I: Generic Asset Factory

Introduction

Procedural generation is a technique in gaming to create dynamic content through algorithms and mathematics. There are many approaches to procedural generation, I will take you through a few techniques I have developed throughout the course of this article series. In the first chapter, we will create a generic factory pattern for loading and managing in game assets. We will compose these assets into scenes and then examine different approaches to procedurally create them at runtime in subsequent chapters.

• Procedural Content Generation Part I: Generic Asset Factory
• Procedural Content Generation Part II: Loading Chunks and Tiles
• Procedural Content Generation Part III: Noise Algorithms
• Procedural Content Generation Part IV: An Agent Based Approach
• Example Code: Azmyth GitHub Repository

Background

I have been interested in procedural content generation for many years. I have experimented with several different concepts and approaches with varying degrees of success. I do this as a hobby and I want to share some of my experience with the community. A lot of my work is based on techniques by Ken Perlin. Ken Perlin developed the Perlin Noise algorithm in 1982 for the movie Tron. He later won an academy award for his work. I also like games such as Minecraft and enjoy the procedurally generated voxel environment. My goal is to combine different approaches together to create a flexible toolbox for procedural generation in C#.

Overview

We are going to start by creating a generic asset management system that can be used to create and store 2D assets. The first step is to create a core of interfaces that will be the base of our generic type system. Once we have the interfaces setup, we can go about creating a specific implementation to produce content of our choice.

I am going to start by creating a 2D tiling system that can create terrain dynamically. To render a decent looking map, we may need to load and track many assets. This system will allow us to manage the lifecycle of the procedurally generated assets. We will cover Agents and the IAgent interface in a later chapter. To keep it simple, we are just going to render this work to the console for now. It will be easy to extend this design to other platforms like GDI+, XNA, MonoGame, or other gaming platforms!

Scenes

The first step is to create a scene interface. A scene is a collection of game assets arranged spatially in either 2D or 3D space. We will start with 2D and then explore ways to extend this to 3D in subsequent chapters. The IScene interface will be responsible for storing and managing the lifecycle of in game assets.

// The Scene interface.
public interface IScene
{
    // Registers an Asset of type T with the Abstract Factory.
    IScene RegisterAsset<T>()
        where T : class, IAsset;
 
    // Registers Loaders of type T2 for type T1. Implements the Abstract Factory for type T1.
    IScene RegisterLoader<T1, T2>()
        where T1 : class, IAsset
        where T2 : class, ILoader;

     // Gets a list of IAssets of type T.
     List<IAsset> GetAssets<T>() where T : class, IAsset;
 
     // Queries a list of IAssets of type T within a boundary.
     List<IAsset> QueryAssets<T>(RectangleF bounds) where T : class, IAsset;

     // Loads an Asset of type T at location (X, Y)
     T LoadAsset<T>(IAsset parent, int x, int y) where T : class, IAsset;

     // Unloads an Asset and calls Dispose.
     void UnloadAsset(IAsset asset);
}

This interface creates a simple generic factory pattern to manage multiple types based on IAsset. It also allows you to query assets stored within the scene and load and unload assets as needed. We'll cover a concrete implementation in another section.

Assets

Assets are the building blocks of our game environment. Assets are basically containers for storing data to represent different aspects our game world. These could be tiles for a map, items, npcs, or even more advanced concepts like audio zones and loading areas. I'm not going to cover all of these ideas in this series. As we progress, you will hopefully recognize the flexibility of this system to manage many different types of content. We will implement the IAsset interface as follows:

// The IAsset interface, requires implementation of IDisposable.
public interface IAsset : IDisposable
{
    // Referene to the containing Scene object.
    IScene Scene { get; }
  
    // A Referene a Parent Asset if one exists.
    IAsset Parent { get; }

    // A boolean indicator for disposed status.
    bool Disposed { get; }

    // A rectangle that represents the Assets location in the Scene.
    RectangleF Bounds { get; }

    // An Event for the QuadTree Implementation used in this example.
    event EventHandler BoundsChanged;

    // An Update function updating assets in a game loop.
    void Update(TimeSpan elapsed);
}

As you can see, it's a fairly simple implementation that sets up a relationship between the asset and a scene. You'll also notice we have a reference to a parent object. This allows for more advanced compositing of assets into simple structures. The asset implements IDisposable and has an indicator for disposed status - this works with the IDisposable interface. The location of the asset is retrieved through the Bounds property, the implementation of this QuadTree uses floats but we are just going to convert these to integers later for our tiling system. An update function is also provided for updates in a game loop.

Loaders

Loaders represent the implementation of the factory pattern for each type of IAsset registered with the scene. We'll create an interface so that we can provide a custom implementation for each type registered. This allows for a lot of flexibility in procedural generation techniques as you'll see later. We're going to implement a procedural loader for our example, but loaders can easily be implemented to load for other mediums, like the filesystem, or a database.

public interface ILoader
{
    IAsset LoadAsset(IScene scene, IAsset parent, int x, int y);
}

The ILoader interface in this case only has one method, LoadAsset. The LoadAsset function takes the containing scene, a parent asset(if any), an X and Y position in our 2D coordinate system and an optional parameter. We could implement LoadAsset overloads that would take a file name or database ID.

Agents

Agents will be addressed in a later part of this series. I will mention them briefly here so you can have a better idea of the overall design. Agents will allow us to do customized procedural generation tasks that don't necessarily use volumetric filling algorithms like Perlin Noise. Agents work more like a finite state automata and can modify assets with a simple set of rules.

Creating a Scene

Now that the core interfaces are setup, we can create an implementation. I created a new class called Scene that inherits IScene. I chose to use a QuadTree to store assets for this project but it is possible to use other data structures like an array, octree, or whatever suits your needs.

public class Scene : IScene
{
    ...
}

Next, we'll need to define each function specified by the interface. We'll start with registering asset types and then move on to loaders.

Registering Assets

First, create a List<Type> to store asset types registered with the Scene, we'll also need a Dictionary with the asset types as keys to store a QuadTree for each asset type registered. Then to register asset types, we will create a generic method that takes a type T which must be a class that inherits from IAsset. We'll use the type defined by T to create a new entry in a list of asset types managed by the scene. I return the this reference to create a fluent interface, you'll see how this works when we call these functions later.

// List of types registered with Scene.
private List<Type> m_assetTypes = new List<Type>();

// List of QuadTrees to store assets of different types.
private Dictionary<Type, QuadTree<IAsset>> m_assets = new Dictionary<Type, QuadTree<IAsset>>();

...

// Register Asset.
public IScene RegisterAsset<T>() where T : class, IAsset
{
    // Convert Generic T to Type.
    Type assetType = typeof(T);

    // Throw an exception if this type is already registered.
    if (m_assetTypes.Contains(assetType))
    {
       throw new Exception(assetType.Name + " already registered.");
    }

    // Register Asset Type with the Scene.
    m_assetTypes.Add(assetType);

    // Create a new QuadTree to store loaded assets of type T.
    m_assets.Add(assetType, new QuadTree<IAsset>(new Size(100, 100), 1));

    // Return this for fluent interface.
    return this;
}

Registering Loaders

When we register a loader, we're going to instantiate a single instance and store in a dictionary indexed by the asset type. We'll later use this object to create instances of our assets. To create an instance of the loader, we'll use reflection, we can call Activator.CreateInstance<T2> to create a new instance.

...

// Dictionary of Registered Loaders.
private Dictionary<Type, ILoader> m_assetLoaders = new Dictionary<Type, ILoader>();

...

// Register ILoader of type T2 where T1 is an IAsset
public IScene RegisterLoader<T1, T2>() where T1 : class, IAsset where T2 : class, ILoader
{
    // Convert generics to types.
    Type assetType = typeof(T1);
    Type loaderType = typeof(T2);

    // Throw an Exception if T1 has not been registered.
    if (!m_assetTypes.Contains(assetType))
    {
         throw new Exception("Unable to register loader without registered asset.");
    }

    // Ensure a single instance of the Loader is created.
    if (!m_assetLoaders.ContainsKey(assetType))
    {
        // Use Reflection to create an instance of loader T2.
        m_assetLoaders.Add(assetType, Activator.CreateInstance<T2>());
    }

    // Return this for fluent interface.
    return this;
}

Assets & Loaders

To load an asset, we need to create an asset and a loader class that inherit from IAsset and ILoader respectively. In this example, we're just going to create a two generic assets each with a loader to demonstrate how the abstract factory pattern will work. When we get to the second chapter, we will see some more advanced uses of this pattern when we load chunks and tiles.

Asset Types

I'm just going to create two new asset types. Asset1 and Asset2, both of which will inherit from IAsset. Both types will have the same implementation but I am also going to add a Name property to each which will return "Asset1" and "Asset2" for our demo.

// Asset1 concrete implementation of IAsset.

public class Asset1 : IAsset
{
    public IScene Scene { get; private set; }
    public IAsset Parent { get; private set; }
    public RectangleF Bounds { get; private set; }
    public bool Disposed { get; private set; }
    public event EventHandler BoundsChanged; 

    public string Name
    {
        get
        {
            return "Asset1";
        }
    }

    public Asset1(IScene scene, IAsset parent, int x, int y)
    {
        Scene = scene;
        Parent = parent;
        Bounds = new RectangleF(x, y, 1, 1);
    }

    public void Update(TimeSpan elapsed)
    {
        // Perform any asset specific logic.
    }

    public void Dispose() 
    {
        if(!Disposed)
        {
            // Perform any Cleanup here.

            Disposed = true;
        }
    }
}

Next, the Asset2 class will have a slightly different implementation, just copy the Asset1 class and change Asset1 to Asset2. Typically, your asset types will have different properties than just a name, but for this demo, we're just going to keep it simple.

Loader Types

Creating a loader is pretty simple, in this example, we're just going to instantiate our new Asset types. We'll need a different loader for each Asset type. This will allow us to use custom loading logic for each type. This could mean loading assets from a file, database, or by using a procedural approach as you'll see later.

// Asset1 Loader class.
public class Asset1Loader : ILoader
{
    public IAsset LoadAsset(IScene scene, IAsset parent, int x, int y)
    {
        // Create a new asset using a constructor
        Asset1 asset = new Asset1(scene, parent, x, y);

        // Perform additional loading logic here.

        // Return the loaded asset.
        return asset;
    }
}

// Asset2 Loader class.
public class Asset2Loader : ILoader 
{ 
    public IAsset LoadAsset(IScene scene, IAsset parent, int x, int y)
    {
        // Create a new asset using a constructor
        Asset2 asset = new Asset2(scene, parent, x, y);

        // Perform additional loading logic here.

        // Return the loaded asset.
        return asset;
    } 
}

In our example loaders, we just have a few lines of code, here we are just instantiating a new instance using the constructor. We would perform additional loading logic here where necessary.

Registering & Loading

Now that we have a basic scene and some example assets with loaders, we're ready to put them together so we can move on the loading assets into the scene. We're going to create a console application that loads and queries the new asset types. Start by creating a simple main function that registers our new assets as follows.

Registering

static void Main(string[] args) 
{
    // Create a new Scene instance.
    Scene scene = new Scene();
    
    // Use fluent interface to Register Asset1 and it's Loader.
    Scene.RegisterAsset<Asset1>()
         .RegisterLoader<Asset1, Asset1Loader>();

    // Use fluent interface to Register Asset2 and it's Loader.
    Scene.RegisterAsset<Asset2>()
         .RegisterLoader<Asset2, Asset2Loader();

    ...
}

Here, we are using the fluent interface defined by the register functions created in the Scene. We pass the types for the assets and loaders as generic parameters to our registration functions.

Loading

Next, we need to add a function that will call our new loaders and store the assets created in the scene. We already have a function defined in our IScene interface called LoadAsset<T>(). We will create the LoadAsset function in the Scene class as follows:

public Scene : IScene 
{
    ...

    // Loads an Asset of type T at location (X, Y) 
    public T LoadAsset<T>(IAsset parent, int x, int y) where T : class, IAsset
    {
        IAsset asset = null;
        Type assetType = typeof(T);

        // Make sure the asset type has been registered with the scene.
        if(!m_assetTypes.Contains(assetType))
        {
            throw new Exception(assetType.Name + " has not been registered.");
        }

        // Make sure a loader has been registered for the asset type.
        if(!m_assetLoaders.ContainsKey(assetType))
        {
            throw new Exception("No loader registered for " + assetType.Name + ".");
        }

        // Call LoadAsset with registered asset loader.
        asset = m_assetLoaders[assetType].LoadAsset(this, parent, x, y);

        // Store the new asset in our scene.
        m_assets[assetType].Insert(asset);

        return asset;
    }    

    ...
}

Unloading

We can also add an unload function that will allow us to remove assets from the scene. I have defined it as follows in the Scene class.

public Scene : IScene
{
    ...

    // Unloads an asset and calls it's dispose method.
    public void UnloadAsset(IAsset asset)
    {
        // Check if asset is contained in the Scene.
        if(m_assets.Contains(asset))
        {
            // Remove the asset from our QuadTree.
            m_assets.Remove(asset);

            // Call the Dispose function defined for the Asset.
            asset.Dispose();
        }
    }

    ...
}

Our scene can now create instances of generic assets and store them in it's internal storage, in this case it's our QuadTree. It's pretty simple to use our new functions. We can update our main function to load and unload an asset like below:

static void Main(string[] args)
{   
    // Create a new Scene instance. 
    Scene scene = new Scene();

    // Use fluent interface to Register Asset1 and it's Loader.   
    scene.RegisterAsset<Asset1>()
         .RegisterLoader<Asset1, Asset1Loader>();   

    // Use fluent interface to Register Asset2 and it's Loader.   
    scene.RegisterAsset<Asset2>()
         .RegisterLoader<Asset2, Asset2Loader();   

    // Create a new asset at (0, 0) with no parent.    
​​​​​​    Asset1 asset1 = scene.LoadAsset<Asset1>(null, 0, 0);​

    // Create a new asset at (1, 1) with asset1 as a parent.
    Asset2 asset2 = scene.LoadAsset<Asset2>(asset1, 1, 1);

    // Perform additional steps with assets
    Console.Print("{0} ({1}, {2})", asset1.Name, asset1.Bounds.X, asset1.Bounds.Y);
    Console.Print("{0} ({1}, {2})", asset2.Name, asset2.Bounds.X, asset2.Bounds.Y);

    // Unload asset2.
    scene.UnloadAsset(asset2);

    ... 
}

Querying Assets

We have a way to store assets but in the demo, we're just using the assets returned by the LoadAsset function directly. This approach isn't very useful for managing many assets at once. In our Scene implementation, we setup a dictionary of QuadTrees for each type registered. You will also recall that we stored the asset loaded in LoadAsset in the QuadTree dictionary.

Quad Trees

Quote: https://en.wikipedia.org/wiki/Quadtree

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. A similar partitioning is also known as a Q-tree. All forms of quadtrees share some common features:

• They decompose space into adaptable cells
• Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits
• The tree directory follows the spatial decomposition of the quadtree.

I'm not going to go into details how QuadTrees work but as you can see from the quote above, they store objects in rectangular cells, which makes it perfect for storing 2D data. I'm using a slightly modified QuadTree from here. It is possible to use other data structures and could be extended to 3D using an octree. The IScene interface has two methods defined for querying assets. GetAssets<T> returns a list of each asset loaded into the scene of type T without regard for location. While QueryAssets<T> takes a rectangle parameter and returns a list of assets contained within.

Query Assets

The QueryAssets requires a generic parameter of type T and takes a RectangleF boundary to query in our QuadTree. The QuadTree has a QuadTree.Query method, we just need to verify that the asset type is registered with the factory. QuadTree.Query returns a List containing all assets contained within the boundary.

public List<IAsset> QueryAssets<T>(RectangleF bounds) where T : class, IAsset
{
    List<IAsset> assets = new List<IAsset>();

    // Verify Asset type is registered.
    if (!m_assets.ContainsKey(typeof(T)))
    {
        throw new Exception("Asset Type not registered.");
    }
    
    // Query assets of type T within bounds.
    assets = m_assets[typeof(T)].Query(bounds);

    return assets;
}

Get Assets

The GetAssets function takes a generic parameter of type T, and returns a list of assets. The QuadTree I'm using has a way to query the data in the nodes directly without using a rectangle. I just loop through each node and add them to the list returned by the function.

public List<IAsset> GetAssets<T>() where T : class, IAsset 
{
    List<IAsset> assets = new List<IAsset>();
    
     // Loop through each QuadTree node.
    foreach(QuadTree<IAsset>.QuadNode node in m_assets[typeof(T)].GetAllNodes()) 
    {
        // Add the objects contained in the node to the list.
        assets.AddRange(node.Objects);
    }

    return assets;
}

Finishing Up

In the Main function, we can query the assets based on a rectangle instead of using the references returned by LoadAsset directly. We can load several assets in different parts of the QuadTree and then query a subset of them. In this example, we're just printing the returned assets and then unloading them.

static void Main(string[] args) 
{   
    // Create a new Scene instance.   
    Scene scene = new Scene();   

    // Use fluent interface to Register Asset1 and it's Loader.   
    scene.RegisterAsset<Asset1>()   
         .RegisterLoader<Asset1, Asset1Loader>();   

    // Load a few assets into the scene. 
    scene.LoadAsset<Asset1>(null, 0, 0);   
    scene.LoadAsset<Asset1>(null, 5, 5);
    scene.LoadAsset<Asset1>(null, 10, 10);
    scene.LoadAsset<Asset1>(null, 15, 15);

    // Query a rectangle of 10 by 10
    var assets = scene.QueryAssets<Asset1>(new RectangleF(0, 0, 10, 10));

    // Print the assets returned and then unload them.
    foreach(Asset1 asset in assets)
    {
        Console.Print("{0} ({1}, {2})", asset.Name, asset.Bounds.X, asset.Bounds.Y); 
        
        // Unload the asset.
        scene.UnloadAsset(asset);  
    }    

    ...
}

We will see the following output when running the program:

Asset1 (0, 0)
Asset1 (50, 50)
Asset1 (100, 100)

A visual representation of the data loaded and selected looks like the following image:

That's it! In the next tutorial, we will look into loading larger amounts of assets and organizing them into manageable units. The final result will be a 2D tiling system that we will be able to create procedurally generated maps with. Stay tuned for: Procedural Terrain Generation Part II: Loading Chunks and Tiles

History

• 23^rd August, 2016 - Article posted