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.

 

5 thoughts on “Creating a Tech Tree

  1. Kevin Manuel says:

    Hey could you please email me the code on as to how you actually used the Tree layout thing to display your tree as i am a beginner and am having a problem understanding how to use the library.If it is possible for you to please provide me with more detailed instructions on how to use it, I would be much obliged.Thank you!

    • bowens says:

      Sure thing. Some of the classes in this test are proprietary and I cannot share them, but they aren’t really needed to get the tree to work, and contain no code to help format the tree.
      The GuiUnitResearchComponent class holds references to parents and children

      private static void test1() {
      EntitySystem es = new EntitySystem();
      EntityObject rootObj = new EntityObject(1, es);

      GuiUnitResearchComponent rootR = new GuiUnitResearchComponent(“root”);
      rootObj.addComponentToList(AvailableGuiUnitActionsComponent.class, rootR);
      rootObj.saveComponentChanges();

      GuiUnitResearchComponent scienceR = new GuiUnitResearchComponent(“science”);
      EntityObject scienceObj = rootR.addResearchChild(rootObj, scienceR);

      GuiUnitResearchComponent mathR = new GuiUnitResearchComponent(“math”);
      EntityObject mathObj = rootR.addResearchChild(rootObj, mathR);
      rootObj.saveComponentChanges();

      GuiUnitResearchComponent calculusR = new GuiUnitResearchComponent(“calculus”);
      EntityObject calculusObj = mathR.addResearchChild(mathObj, calculusR);

      GuiUnitResearchComponent linearAlgebraR = new GuiUnitResearchComponent(“Linear Algebra”);
      EntityObject linearAlgebraObj = mathR.addResearchChild(mathObj, linearAlgebraR);

      GuiUnitResearchComponent quaternionsR = new GuiUnitResearchComponent(“Quaternions”);
      EntityObject quaternionObj = linearAlgebraR.addResearchChild(linearAlgebraObj, quaternionsR);

      GuiUnitResearchComponent vectorsR = new GuiUnitResearchComponent(“Vectors”);
      EntityObject vectorsObj = linearAlgebraR.addResearchChild(linearAlgebraObj, vectorsR);

      GuiUnitResearchComponent statsR = new GuiUnitResearchComponent(“stats”);
      EntityObject statsObj = mathR.addResearchChild(mathObj, statsR);

      GuiUnitResearchComponent artR = new GuiUnitResearchComponent(“art”);
      EntityObject artObj = rootR.addResearchChild(rootObj, artR);

      rootObj.saveComponentChanges();

      ResearchGraphTree tree = new ResearchGraphTree(rootR, es);
      ResearchNodeExtentProvider extentProvider = new ResearchNodeExtentProvider();
      Configuration config = new DefaultConfiguration(10, 20);
      TreeLayout layout = new TreeLayout(tree, extentProvider, config);

      Map nodeBounds = layout.getNodeBounds();

      layout.dumpTree(System.out);

      for (final GuiUnitResearchComponent research : nodeBounds.keySet()) {
      final Rectangle.Double rect = (Rectangle.Double) nodeBounds.get(research);
      System.out.println(“rect: “+rect+ “, minY: “+rect.getMinY()+ “, maxY: “+rect.getMaxY()+ “, minX: “+rect.getMinX()+ “, maxX: “+rect.getMaxX());
      }
      }

      =============================

      /**
      * Parses the structure of the research tree using GuiUnitResearchComponents
      * @author bowens
      */
      public class ResearchGraphTree extends AbstractTreeForTreeLayout {
      private EntitySystem es;

      public ResearchGraphTree(GuiUnitResearchComponent root, EntitySystem es) {
      super(root);
      this.es = es;
      }

      @Override
      public GuiUnitResearchComponent getParent(GuiUnitResearchComponent n) {
      return es.getComponent(n.getParentId(), GuiUnitResearchComponent.class);
      }

      @Override
      public List getChildrenList(GuiUnitResearchComponent n) {
      List
      children = new ArrayList();
      Set restricted = TritiumMain.getApp().getGameCommands().getRestrictedResearch();
      for (int i : n.getResearchChildren()) {
      GuiUnitResearchComponent research = es.getComponent(i, GuiUnitResearchComponent.class);
      if ( !restricted.contains(research.getName()) )
      children.add(es.getComponent(i, GuiUnitResearchComponent.class));
      }
      return children;
      }

      }

      /**
      * Default bounds of the graphics for the research tree
      * @author bowens
      */
      public class ResearchNodeExtentProvider implements NodeExtentProvider {

      public double getWidth(GuiUnitResearchComponent n) {
      return 70;
      }

      public double getHeight(GuiUnitResearchComponent n) {
      return 70;
      }

      }

  2. Drawing Edges says:

    Hello there. I stumbled on your blog and was wondering how you managed to draw the edges in your game. Unlike you I am using the jung library. I like the 1-M link from parent to children though and think it makes the tree look smarter than 1-1 edges. I’m sure the same implementation could be used to override jungs edge renderer and was wondering if you could provide any assistance.

    • bowens says:

      Hey there. TreeLayout gives you rectangles for each node. Each rectangle has world coordinates so I just used their positions and drew the lines from that. I picked the middle of each rectangle tor draw the vertical lines. The vertical length was half the vertical distance between the nodes. Then I just drew a horizontal line from the left node to the right node. Hope that helps.

Leave a Reply

Your email address will not be published. Required fields are marked *


+ two = 11