Contact Home

Archive for May, 2014

Procedurally Generated Trees with Space Colonization Algorithm in XNA C#

Posted on: May 23rd, 2014 by admin 7 Comments
I discovered a very interesting algorithm called “Space Colonization Algorithm”, which is described in a paper found here:

http://algorithmicbotany.org/papers/colonization.egwnp2007.html

With this algorithm, it is possible to create some pretty lifelike trees. With L-Systems, you can get some interesting looking trees, which typically start from the root, and generates branches based on a set of rules. The Space Colonization algorithm takes a different approach to the problem. Instead you first create the leaves, which serve as attraction points for the branches. Over each iteration, the branches grow closer and closer towards the leaves. In this manner, you end up having tree branches that appear to have grown towards some light source.

I decided to write the algorithm in C#. The following is an example of a tree that was generated using this algorithm:

Tree Generator Example 1 The algorithm works as follows:

  1. Define an area for the crown of the tree. In our examples, we are using Rectangles, but any shape can be used. In fact, very interesting trees can be created by using various shapes.
  2. Populate the defined area with attraction points (I call these leaves).
  3. Create the trunk of the tree, by adding Branches below the defined area. Keep growing branches upwards until the MaxDistance between a Leaf and a Branch is reached. This MaxDistance is a parameter that defines how far a Leaf can be to attract a Branch. A Branch is not affected by Leaves that are further away than MaxDistance.
  4. At this point, your tree would look something like this, and is now ready to grow:
    Tree Generator Example 2
  5. Process the Leaves, by comparing it to all the Branches. Calculate the direction and distance from the Leaf to the Branch. If the distance is smaller than MinDistance, we remove the Leaf for it has been reached. If the distance is greater than MaxDistance, we ignore it, since it is too far. Otherwise, we check if the Branch is the closest Branch to this Leaf. Each Leaf can only affect 1 Branch at a time.
  6. Once the closest Branch is determined, we increment the GrowCount of that Branch, and add the direction of the Leaf to the GrowDirection of the Branch. If multiple Leaves attract a branch, then the GrowDirection will be an average of all of the Leaf directions.
  7. Now loop through the Branches, and process any Branch with a GrowCount > 0. Divide the GrowDirection by the GrowCount, to get the average direction, then create a new branch with this GrowDirection, linking it to the Branch being processed as its parent. Then reset the GrowCount and GrowDirection of the parent Branch.
  8. Repeat from step 4 until there are no Leaves left, or no more Branches are growing.

To help visualize what is happening during each iteration, have a look at the following image:
Tree Generator Example 3
The green squares are Leaves. The brown Branches are Branches that were grown in previous iterations. The black lines indicate each Leaf’s attraction to its nearest Branches (that are in range). The orange lines indicate the Branches that will grow in this iteration based on those attraction points.

The orange Branches will grow with respect to the original parent Branch GrowDirection, adding the attraction points average direction to this value.

Onto the code. See the bottom of the page for a download of a sample project for Visual Studio.

Leaf class:
public class Leaf
{        
    public Vector2 Position { get; set; }
    public Branch ClosestBranch { get; set; }

    public Leaf(Vector2 position)
    {
        Position = position;
    }
}
Branch class:
public class Branch
{
    public Branch Parent { get; private set; }
    public Vector2 GrowDirection { get; set; }
    public Vector2 OriginalGrowDirection { get; set; }
    public int GrowCount { get; set; }
    public Vector2 Position { get; private set; }

    public Branch(Branch parent, Vector2 position, Vector2 growDirection)
    {
        Parent = parent;
        Position = position;
        GrowDirection = growDirection;
        OriginalGrowDirection = growDirection;
    }

    public void Reset()
    {
        GrowCount = 0;
        GrowDirection = OriginalGrowDirection;
    }
}
Tree class:
public class Tree
{
    bool DoneGrowing = false;
   
    Vector2 Position = Vector2.Zero;

    int LeafCount = 400;
    int TreeWidth = 80;    
    int TreeHeight = 150;   
    int TrunkHeight = 40;
    int MinDistance = 2;
    int MaxDistance = 15;
    int BranchLength = 2;

    Branch Root;
    List<Leaf> Leaves;
    Dictionary<Vector2, Branch> Branches;

    Rectangle Crown;

    public Tree(Vector2 position)
    {
        Position = position;
        GenerateCrown();
        GenerateTrunk();
    }

    private void GenerateCrown()
    {
        Crown = new Rectangle((int)Position.X - TreeWidth / 2, (int)Position.Y - TreeHeight - TrunkHeight, TreeWidth, TreeHeight);
        Leaves = new List<Leaf>();
        
        //randomly place leaves within our rectangle
        for (int i = 0; i < LeafCount; i++)
        {
            Vector2 location = new Vector2(Random.Next(Crown.Left, Crown.Right + 1), Random.Next(Crown.Top, Crown.Bottom + 1));
            Leaf leaf = new Leaf(location);
            Leaves.Add(leaf);
        }
    }
    
    private void GenerateTrunk()
    {
        Branches = new Dictionary<Vector2, Branch>();

        Root = new Branch(null, Position, new Vector2(0, -1));
        Branches.Add(Root.Position, Root);

        Branch current = new Branch(Root, new Vector2(Position.X, Position.Y - BranchLength), new Vector2(0, -1));
        Branches.Add(current.Position, current);

        //Keep growing trunk upwards until we reach a leaf       
        while ((Root.Position - current.Position).Length() < TrunkHeight)
        {
            Branch trunk = new Branch(current, new Vector2(current.Position.X, current.Position.Y - BranchLength), new Vector2(0, -1));
            Branches.Add(trunk.Position, trunk);
            current = trunk;                
        }         
    }

    public void Grow()
    {
        if (DoneGrowing) return;

        //If no leaves left, we are done
        if (Leaves.Count == 0) { 
            DoneGrowing = true; 
            return; 
        }

        //process the leaves
        for (int i = 0; i < Leaves.Count; i++)
        {
            bool leafRemoved = false;

            Leaves[i].ClosestBranch = null;
            Vector2 direction = Vector2.Zero;

            //Find the nearest branch for this leaf
            foreach (Branch b in Branches.Values)
            {
                direction = Leaves[i].Position - b.Position;                       //direction to branch from leaf
                float distance = (float)Math.Round(direction.Length());            //distance to branch from leaf
                direction.Normalize();

                if (distance <= MinDistance)            //Min leaf distance reached, we remove it
                {
                    Leaves.Remove(Leaves[i]);                        
                    i--;
                    leafRemoved = true;
                    break;
                }
                else if (distance <= MaxDistance)       //branch in range, determine if it is the nearest
                {
                    if (Leaves[i].ClosestBranch == null)
                        Leaves[i].ClosestBranch = b;
                    else if ((Leaves[i].Position - Leaves[i].ClosestBranch.Position).Length() > distance)
                        Leaves[i].ClosestBranch = b;
                }
            }

            //if the leaf was removed, skip
            if (!leafRemoved)
            {
                //Set the grow parameters on all the closest branches that are in range
                if (Leaves[i].ClosestBranch != null)
                {
                    Vector2 dir = Leaves[i].Position - Leaves[i].ClosestBranch.Position;
                    dir.Normalize();
                    Leaves[i].ClosestBranch.GrowDirection += dir;       //add to grow direction of branch
                    Leaves[i].ClosestBranch.GrowCount++;
                }
            }
        }

        //Generate the new branches
        HashSet<Branch> newBranches = new HashSet<Branch>();
        foreach (Branch b in Branches.Values)
        {
            if (b.GrowCount > 0)    //if at least one leaf is affecting the branch
            {
                Vector2 avgDirection = b.GrowDirection / b.GrowCount;
                avgDirection.Normalize();

                Branch newBranch = new Branch(b, b.Position + avgDirection * BranchLength, avgDirection);

                newBranches.Add(newBranch);
                b.Reset();
            }
        }

        //Add the new branches to the tree
        bool BranchAdded = false;
        foreach (Branch b in newBranches)
        {
            //Check if branch already exists.  These cases seem to happen when leaf is in specific areas
            Branch existing;
            if (!Branches.TryGetValue(b.Position, out existing))
            {
                Branches.Add(b.Position, b);
                BranchAdded = true;
            }
        }

        //if no branches were added - we are done
        //this handles issues where leaves equal out each other, making branches grow without ever reaching the leaf
        if (!BranchAdded) 
            DoneGrowing = true;
    }
}
With further improvements and refinements, you can make the tree form any shape you want: Tree Generator Example 4 Rendering some leaves: Tree Generator Example 5 Here is a gif to demonstrate what is possible with this method:
Tree Growing Gif

Cycling through the 4 seasons:
Season Cycle Gif

The demo project can be downloaded here. I have omitted the polygon code for the sake of simplicity, the trees are set to be Rectangles only.

http://www.jgallant.com/files/TreeGenerator.zip

Feel free to contact me if you have any questions or comments.

References used:
http://algorithmicbotany.org/papers/colonization.egwnp2007.html
http://procworld.blogspot.ca/2011/02/space-colonization.html
http://www.sea-of-memes.com/LetsCode26/LetsCode26.html