How to generate very complex tree structure in HTML

Question

In our game, we have a typical tech tree, which is currently edited by hand - very hard to maintain and error-prone: http://igmarauders.isotx.com/library/images/a/a3/Techtree-july26-2011-vehicles-resized.png

If at all possible, I'd like to generate this in an HTML form, but I have no idea where to start. Maybe people here have tackled similar problems and can point me in the right direction?

Some technical details:

• Every node is an entity, with a unique ID (number)
• Every entity has a list of prerequisites (other entities)
• The starting tech (on the left) is an array of entities
• Only entities that can be traced back to the starting tech show up in the map
• The research level (the columns along the top) are a property available for each entity
• Entities of the same types but different levels (e.g. Assault Archos LvL 1, Assault Archos LvL 2) are linked by a property from the higher level to the lower level (and the higher level always has the lower level as a prerequisite too)
• We can distinguish between Technology (upper part) and Vehicles (lower part) by the entity type, a per-entity property.
• The actual names are also a per-entity property, and not really important for the tree itself

Finally:

• You can ignore the differentiation between solid lines and dotted lines (I don't even know what the difference really is)
• The boxes that group vehicles together that are unlocked by one research project are nice to have, but not required

Thanks in advance. I have searched on Google, but all the "complex tree" examples I found were childishly simple compared to mine :)

edit: Here is some sample data, in a JSON format: http://pastebin.com/Fa3JcnRw

edit 2: Also, if it matters, we use PHP on the server side, but I'm open to alternatives - we could generate the static HTML in a build script for example.

Answer 1

There won't be an easy solution to this.

I would recommend looking into generating an SVG (standard vector graphics) file for this tree. SVG is basically an XML file that describes the various objects on a canvas, using coordinates, fills, gradients, etc. All modern browsers have built-in support for SVG files.

You can use PHP or pretty much any language to generate the XML code of the SVG file.

I've played with that a little bit and what I found very useful if you create some XML templates and then replace only the part that is varied from one element to another. Let me give you an example: on your diagram you have blue boxes with text in them. That could be a unit that you create the template XML for (you can use InkScape for that and then just look into the SVG file it creates). Then just substitute the coordinates and the text inside the XML code. "sprintf" in PHP is a great tool for that.

Using SVG has some great advantages: - Very small file size - Fully zoomable without loss of quality (because it is vector based and not pixel based). - Can be displayed as embedded object in a webpage.

It will take a while to write the code, no doubt about it, but it will produce a high quality result.

Answer 2

So, while I can't give you a working demo since I simply don't have the time to figure out all connections this is what I suggest;

What you want is actually a complex flowchart based on raw data from your system. To make it so that it creates the structure like your example is not possible. The connections that can be made are simply too complex to make with the limited data you provide...

However, making the html structure (a grid) which can contain all items and relations (lines), is possible.

The lines itself are easy enough here is a plugin which will allow you to make the actual connections with no less than 3 popular JS libraries (jQuery, Mootools, YUI3). From there you can build the required structures between the html nodes.

I would keep the nodes in a table, you can assign a default position in the 2d grid from there based on the level they have, but from there it will need some human input, possibly drag/drop system, which moves the nodes to different positions in the grid, do crud actions.

It's definitly possible, but a lot of work. The problem is that you're trying to do stuff that almost matches Visio functionality.

If you're not up to that task I suggest you take a different aproach visualising the relations. Something like @Jedidiah made is a good start.

If anyone else wishes to make something working with this plugin / idea I wish them good luck, I just don't have the time right now, sorry.

Answer 3

I've hacked together an alternative idea, you can see it at http://jsfiddle.net/jedidiah/sTj3E/4/embedded/result/

The idea is to just list all of the items at each level in columns, and then when you click on one of the items it highlights the techs that are required.

I think it would be a bit easier to get your head around than all the lines, thought it wouldn't give you the overview at a glance, you would have to click around.

edit: You can see the code here http://jsfiddle.net/jedidiah/sTj3E/4/ forgive the messiness, just a quick example to get the idea across.

Answer 4

If you can't adapt or extend something existing, you would surely need to use a canvas.

(Looks like you're in for a lot of work - but interesting one.)