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.
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.
public interface IScene
{
IScene RegisterAsset<T>()
where T : class, IAsset;
IScene RegisterLoader<T1, T2>()
where T1 : class, IAsset
where T2 : class, ILoader;
List<IAsset> GetAssets<T>() where T : class, IAsset;
List<IAsset> QueryAssets<T>(RectangleF bounds) where T : class, IAsset;
T LoadAsset<T>(IAsset parent, int x, int y) where T : class, IAsset;
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:
public interface IAsset : IDisposable
{
IScene Scene { get; }
IAsset Parent { get; }
bool Disposed { get; }
RectangleF Bounds { get; }
event EventHandler BoundsChanged;
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.
private List<Type> m_assetTypes = new List<Type>();
private Dictionary<Type, QuadTree<IAsset>> m_assets = new Dictionary<Type, QuadTree<IAsset>>();
...
public IScene RegisterAsset<T>() where T : class, IAsset
{
Type assetType = typeof(T);
if (m_assetTypes.Contains(assetType))
{
throw new Exception(assetType.Name + " already registered.");
}
m_assetTypes.Add(assetType);
m_assets.Add(assetType, new QuadTree<IAsset>(new Size(100, 100), 1));
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.
...
private Dictionary<Type, ILoader> m_assetLoaders = new Dictionary<Type, ILoader>();
...
public IScene RegisterLoader<T1, T2>() where T1 : class, IAsset where T2 : class, ILoader
{
Type assetType = typeof(T1);
Type loaderType = typeof(T2);
if (!m_assetTypes.Contains(assetType))
{
throw new Exception("Unable to register loader without registered asset.");
}
if (!m_assetLoaders.ContainsKey(assetType))
{
m_assetLoaders.Add(assetType, Activator.CreateInstance<T2>());
}
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.
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)
{
}
public void Dispose()
{
if(!Disposed)
{
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.
public class Asset1Loader : ILoader
{
public IAsset LoadAsset(IScene scene, IAsset parent, int x, int y)
{
Asset1 asset = new Asset1(scene, parent, x, y);
return asset;
}
}
public class Asset2Loader : ILoader
{
public IAsset LoadAsset(IScene scene, IAsset parent, int x, int y)
{
Asset2 asset = new Asset2(scene, parent, x, y);
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)
{
Scene scene = new Scene();
Scene.RegisterAsset<Asset1>()
.RegisterLoader<Asset1, Asset1Loader>();
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
{
...
public T LoadAsset<T>(IAsset parent, int x, int y) where T : class, IAsset
{
IAsset asset = null;
Type assetType = typeof(T);
if(!m_assetTypes.Contains(assetType))
{
throw new Exception(assetType.Name + " has not been registered.");
}
if(!m_assetLoaders.ContainsKey(assetType))
{
throw new Exception("No loader registered for " + assetType.Name + ".");
}
asset = m_assetLoaders[assetType].LoadAsset(this, parent, x, y);
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
{
...
public void UnloadAsset(IAsset asset)
{
if(m_assets.Contains(asset))
{
m_assets.Remove(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)
{
Scene scene = new Scene();
scene.RegisterAsset<Asset1>()
.RegisterLoader<Asset1, Asset1Loader>();
scene.RegisterAsset<Asset2>()
.RegisterLoader<Asset2, Asset2Loader();
Asset1 asset1 = scene.LoadAsset<Asset1>(null, 0, 0);
Asset2 asset2 = scene.LoadAsset<Asset2>(asset1, 1, 1);
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);
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>();
if (!m_assets.ContainsKey(typeof(T)))
{
throw new Exception("Asset Type not registered.");
}
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>();
foreach(QuadTree<IAsset>.QuadNode node in m_assets[typeof(T)].GetAllNodes())
{
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)
{
Scene scene = new Scene();
scene.RegisterAsset<Asset1>()
.RegisterLoader<Asset1, Asset1Loader>();
scene.LoadAsset<Asset1>(null, 0, 0);
scene.LoadAsset<Asset1>(null, 5, 5);
scene.LoadAsset<Asset1>(null, 10, 10);
scene.LoadAsset<Asset1>(null, 15, 15);
var assets = scene.QueryAssets<Asset1>(new RectangleF(0, 0, 10, 10));
foreach(Asset1 asset in assets)
{
Console.Print("{0} ({1}, {2})", asset.Name, asset.Bounds.X, asset.Bounds.Y);
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
- 23rd August, 2016 - Article posted
