Creating a Tech Tree

The next task for Attack of the Gelatinous Blob for me was to create a research tech tree. This would allow the player to upgrade units and unlock other ones. It seemed simple enough: each research item had one or more children, I would simply draw the tree of children and be done. Turns out it isn’t so easy. First off, you want the tree to look good. You don’t want overlaps or large gaps, and you definitely don’t want it to waste too much space on the small realestate of of the screen.

TreeGraphView-Figure7

It became apparent pretty quickly that is was a difficult problem and that someone must have solved it by now. And of course they have! I won’t go into detail about the algorithm here, the page describes it well enough; code and everything.

What I will talk about is how I implemented it. Or more specifically, how I found an open source Java implementation.

 

Welcome to Tree Layout by abego

The Java open source community saves the day again. This library is compact, easy to use, and saved me at least a day implementing my own version. It has the very flexible New BSD License and doesn’t force you to change your data structures in order to use it. Your code stays intact and unmolested by a 3rd party library.

So how do you use it?

First, download the jar file and add it to your class path.

Next you need to give it a means to find children of a particular node, and those children’s parent. This is done by implementing the TreeForTreeLayout interface, however there is a convenience class already there for you called AbstractTreeForTreeLayout and with it you only have to implement two methods:

public MyNodeClass getParent(MyNodeClass n);
public List<MyNodeClass> getChildrenList(MyNodeClassn);

My research objects each know what children they have, and who their parent is. So it was really easy to implement. If you don’t already have a tree structure for your objects, TreeLayout provides ones for you.

With the tree structure complete, and TreeLayout now knows how to access nodes and their relationship with each other, it is time to configure how the tree will look. In particular how large each node will be. Not all nodes have to be the same size, and quite often with a tech tree in a game they won’t be.

treeLayout-example

To achieve this customization you create one more class that implements the NodeExtentProvider interface. This interface has two simple methods:

public double getWidth(MyNodeClass tn);
public double getHeight(MyNodeClass tn);

 For my research nodes the layout size was simple: they have a fixed size. So for each one I just returned 70 (representing 70 pixels).

Finally, you have to configure the gaps between the rows and the nodes, what way you want the tree to face, and node alignment. You can use the DefaultConfiguration class to do this. The direction of the tree is quite important for your layout, and TreeLayout will provide you with 4 options:

treeLayout-directions

Here is what my code for building the tree looked like in the end:

private TreeLayout buildTree(GuiUnitResearchComponent a) {
        ResearchGraphTree tree = new ResearchGraphTree(a, es);
        ResearchNodeExtentProvider extentProvider = new ResearchNodeExtentProvider();
        Configuration config = new DefaultConfiguration(50, 10, Configuration.Location.Bottom, Configuration.AlignmentInLevel.TowardsRoot);
        TreeLayout layout = new TreeLayout(tree, extentProvider, config);
        return layout;
    }

With that code there we have a tree that is built, balanced, and usable. So what do we do next?

Draw Your Tree

With the tree built, you now need to draw your actual elements on the screen. It is first a good idea to confirm what your tree looks like by using the TreeLayout.dumpTree() method. This allows you to verify the parent-child relationships. Next you will want to get the bounds of every node in the tree, as well as the overall bounds of the whole tree.

layout.dumpTree(System.out);
Rectangle wholeTreeBounds = layout.getBounds().getBounds();
Map<GuiUnitResearchComponent,Rectangle2D> nodeBounds = layout.getNodeBounds();

That code is pretty self explanatory. What I end up with in the end there is a map of each node and where it should be positioned. The Rectangle2D class is very convenient with its center (x,y), minX/Y, maxX/Y values and this makes drawing the research boxes a cinch.

The harder part was drawing the lines in between each node. Not an impossible task: find the center point of the parent node and draw a line directly from it to the center of each child node. Or do what I did and instead of using direct lines, use a right-angle stepped line system (there is probably a real name for that). Here is a picture of my end result:

tree-ss

So there you have it. A pretty, balanced, tech tree that took no effort at all to build. I highly recommend you use TreeLayout if you are using Java, and if you aren’t using Java, take a look at the code and port it over. It will be worth it.

 

Ahh! My Groovy Script is Slow

Attack of the Gelatinous Blob uses Groovy scripts for all entities, level configuration, and pretty much most game features. It provides an easy and forgiving way to implement features and reuse them. I’ve also built the game so you can change a script for an entity while the game is running and see the changes in the entity immediately. This has been hugely beneficial.

But that is not what this post is about. This post is about performance when it comes to Groovy scripts and in particular, when loading and compiling them.

I started the investigation into script loading times when I noticed the levels for AotGB were taking longer to load than expected. Especially when many of the same entity were loaded, the time would grow linearly when it shouldn’t have since jMonkeyEngine’s asset manager caches models: once you load it, a clone is returned very quickly. The time to load a level with roughly 400 objects and 600k triangles, texture maps no larger than 1024×1024 took around 17 seconds. This was much too slow to be tolerable.

I had a suspicion that the slowdown was in the Groovy scripts. But just to make sure (as any good programmer should do) I ran the profiler to pin down the time-sink. Sure enough, it was the scripts.

To load the scripts I was doing a little caching: the script files themselves were loaded and cached off of the disk so they could be retrieved from memory quickly. However the compiled script was not being cached. The profiler pointed right to this spot: compile times. These were quite slow and were being repeated for the same script over and over again. That had to change.

I had see the Groovy Script Engine before: an embedded script manager that comes bundled with Groovy. It handles caching for you and checks if a file has changed, and will re-compile the script for you if it has. Great! This exactly what I want. So I slotted it in and ran some loading tests.

Loading times went from 17 seconds to 40 seconds! What happened there? I double-checked if it was running and configured correctly, it was. Some google searching quickly revealed the problem with the Groovy Script Engine, as can be found in this (http://groovy.329449.n5.nabble.com/GroovyScriptEngine-maximizing-performance-td339751.html) discussion. The issue is that it tries to make sure all dependencies are always up to date and that the files haven’t changed.

The script file checking is nice, but I do not really need it since it is only used during development and I enter the script through the groovy console whenever I change it. So that feature can go. All I really want is the pre-compiled script.

The solution I took for this was to just cache it myself. A simple HashMap of the script name and the compiled class.

private Map<String,Script> scriptCache = new HashMap<String,Script>();
...
Script script = getScript(codeKey.getName());
if (script == null) {
    Class<Script> clazz = (Class<Script>) parseClass();
    script = clazz.newInstance();
    cacheScript(codeKey.getName(), script);
}

script.setBinding(binding);
return script.run();

I implemented this and tested it. Load times went from 17 seconds for no caching and 40 seconds using Groovy Script Engine down to 7 seconds! Okay that is much better. The load times are reasonable now.

groovyPerf-chart

There are some things you can do to speed up the Groovy Script Engine, however my solution only took a couple minutes to implement and test, and it will be extremely easy to maintain. So I think I will be sticking with it.

 


			

The Entity System

If you missed my post about Entity Systems on IndieDB, don’t fear! I am posting it here for your reading enjoyment:

An Entity System (ES) is another way of managing all of your entities in a game, specifically how to organize their attributes (speed, damage, hit points, goopiness, etc…). Attack of the Gelatinous Blob uses an ES and in this post I will go into detail how an ES works and the benefits of using one.

What it Replaces

Commonly games will use a hierarchy of Actor classes, where each subclass adds new attributes to that entity/actor. Picture a top-level parent class called Actor, it has some basic attributes such as health, movementSpeed, and attackDamage. Then there is a subclass of actor called Human, where it adds to the attributes: jumpHeight, carriesWeapon, and carryWeight. Now lets say there is another subclass of Actor called Tank; it adds the attributes: armor, and carriesWeapon. Both the Human and Tank can carry weapons, and thus can both attack.

Next we create a child of Human called Blob. We want to subclass Human so we get the carriesWeapon and carryWeight attributes. But a Blob cannot jump! Ug, ok so we can have each class include a check of canJump(), no biggy. Next we add a 4th actor called ArmoredRobot. It has armor, carries a weapon, and can jump. So it could subclass Tank, but it can also carry weight and jump; should it subclass Human then? Either Human or Tank will work, but we have to copy attributes across to the other class. Not ideal as we now have two places where the jumpheight attribute lives.

blog-es-objDiagram1

The really messy part comes when you are accessing these attributes. Suddenly to see if something can jump we need to know if it is either a Human, or an ArmoredRobot(that subclasses Tank), and then get its jumpHeight. Imagine if there were more types of robots, some that couldn’t jump or had some other attributes. Suddenly whenever we want to use these attributes we have to perform lots of checks and object casting and always have to be aware of the entire Actor class tree; when all we care about is if it can jump!

ES Overview

Entities Systems solve this problem elegantly by removing this object hierarchy.
An entity system is broken into 3 parts: The entity, the components, and the systems.

  • An entity is just an ID (AotGB uses integers). Each entity has a unique ID, similar to a primary key in a database table.
  • Components are the actual attributes that an entity can have: hit points, armor value…
  • Systems use the components, and only the components their care about, to do the actual work.

The easiest way to see this is a concrete example:
First we create an entity, it is given ID# 234. That’s all it is! Just a number and absolutely nothing else.
Next we give it a component: a HealthComponent. The HealthComponent has two values: maxHP and currentHP.
Lets give it another component: a MovableComponent. It has two values as well: moveSpeed and turnSpeed.
Finally lets give it an AttackComponent. This has attackRange, attackDamage, and attackSpeed.

blog-es-objDiagram2

Okay, now that entity can move, has hit points, and can attack. Time to send it into the real world and cause trouble.

Systems

The parts of the game that interact with Components are called Systems. A game can have many systems; AotGB has around 30 of them.
One such system is the CombatSystem, the most fun of all the systems.
It runs once every frame, checks if an entity can attack, and if so it will perform that attack, deal damage, and check if the other entity died.

The first part in its update loop is to get all of the entities it cares about, specifically entities with a HealthComponent and an AttackComponent. It queries them like this

java code:
List<entityIDs> = es.getAllEntitiesWithComponents(AttackComponent.class, HealthComponent.class);
 // ‘es’ is the entity sys

 

With this simple query we get all the entities that we care about, and no extra baggage of other attributes, no class casting or instance checks. Super easy, clean, and in one line!
In reality the AttackComponent has a cooldown time, and a counter, so it can track if it is time to attack again. The CombatSystem looks at these values and will attack if the cooldown time has reached zero, like this:

java code:
if (playerAttackComponent.getCoolDownTime <= 0) {
    // time to attack the enemy
    float enemyHealth = enemyHealthComponent.getCurrentHP() - 
                          playerAttackComponent.getAttackDamage()
    if (enemyHealth <= 0) {
        enemyHealthComponent.setAlive(false)
        // play some sound
        // give the player some points
    }
 }

Not all systems run every frame from the game’s main update loop, as the combat system does. Some just run occasionally or are triggered to run. So what is the classification of a system? Anything that uses Components. Usually asking the ES for a bunch of entities with specific components it cares about.

Throw Out That OOP Mentality

The hardest part about ES is throwing Object Oriented Programming out of your head. At least for the entities and Components.
You do not want to subclass a component. For example with the AttackComponent you do not want a PunchComponent that subclasses it. If you do that, then you are back to checking in the systems “if this is a regular AttackComponent, or a punch this time?” You want to have a separate component, called PunchComponent, that does not subclass. You can then have a punch system that deals with it.
This can cause a little bit of duplication of code, but you can use some good design to make sure you aren’t duplicating too much.
It takes practice, and I had to rewrite the ES twice because I didn’t get OOP out of my head when making the first components.

The Back-End

Storing the components is fairly easy. I use a Hash map, but others use database tables. If you picture it stored in database tables then each Componet type (say, all AttackComponents) are stored in the AttackComponentTable:

blog-es-chart

Every entity with an AttackComponent has a row in the table. For example entity 98 has a damage of 7, a range of 2, speed of 0.5, and a cooldown time of 5.74
Performing the lookups is very fast because you can index any of the columns you wish, and you only have to query against only those entities with that particular component, not every single entity out there.

How I Have Found it so Far

  • ES makes your game very modular. If there is a bug with combat not working as intended, then it is restricted to only the CombatSystem class. This has saved my skin so many times and I rarely have a multi-hour long debugging session anymore; I always know where to look because of the modularity.
  • -Modability is super easy with components. A mod can just be a system that updates every frame, checks for a HealthComponent and a BlobComponent, and gives those blobs extra hit points every frame, thus regenerating them. None of the other systems have to care about this new system so the risk of breaking things is small. I’ve also set up AotGB so you can easily add and remove systems. If there is a level where there is no combat (just sneaking around and collecting items instead) I only have to remove or disable the combat system. No side effects; combat just doesn’t happen. And all of this with just one line of code!
  • It does take some practice to get used to ES, especially to not think about OOP as you are building the components. It can also be a little too much for a tiny game; if you don’t have an existing ES to plug in and use. I wouldn’t recommend it to beginners.

So When Should I Use One?

  • If you have a nasty Actor hierarchy.
  • If your combat (for example) code is in many places.
  • if you are doing a lot of class casting or type checking: “is this a jumping orc or a swimming orc”.
  • If you are doing networking. (I won’t get into this here, but in another post)
  • If you are making an MMO. (I won’t talk about this either here)

Conclusion

Well I hope you are a little inspired now to try making an ES or do some more reading. The benefits are many and there are very few downsides, so give it a shot!

Further reading

T-machine.org
Paulgestwicki.blogspot.ca
jMonkeyEngine ES thread

Time for a blog

The character limit on Twitter just isn’t enough any more. There’s lots I want to share and I need a new space for that. So, here it is, my new blog.

First off, a little bit about who I am.

I’m a software developer with around 10 years of professional experience. Most of my jobs are related to GIS, but throughout my career I have been working on games, game engines, mods. No major titles, just dabbling here and there, learning as I go.

One of my larger contributions to the gaming community is my work on jMonkeyEngine 3. I am one of the core developers and created its terrain system.

I am also the creator of an RTS game called Attack of the Gelatinous Blob. It is currently in development is has become my passion. It’s an ambitious project, but incredibly fun to work on.

What can you expect to see on this blog? Anything related to game development that I feel is worth sharing. I will describe techniques and technologies I use, and I will share the development progress of AotGB.

So stay tuned, and follow me on twitter: @sploreg @AotGB for frequent, small, updates.

ss-townUnderFire