Drawing a Tech Tree

Java 2D
#1

Hi, guys!

I’m developing a game that is going to have a tech tree (like Civilization, for example);

So, I began to search how to draw and discovered that this is quite tricky. A tech tree is actually a directed acyclic graph. So, we have to draw a graph. I found tons of academic material, but most of them grows in complexity, since they try to optimize the code (in terms of Big O).

So, I would like to know if anyone knows a working algorithm that is not tooooooooo complex to implement. For now, I don’t need to be optimized.

Thanks!

#2

If your tech tree won’t change during gameplay, you may find it easier to just layout the graph beforehand, either manually or using some external software. One option would be to use GraphViz and exporting the layout in their plain text format. Then, convert it to a custom format or write an importer for your game to layout your tech tree.

As you probably discovered, laying out DAGs to minimize edge crossings is NP-hard. Some methods I found from a quick Google search that may be useful are Suigyama Drawing (this might be good since it structures nodes into layers) and Topological sorting. You may also find this paper useful: https://www.graphviz.org/Documentation/TSE93.pdf

#3

Hi, Longarmx,

thanks for your answer. It never occourred to me to simply draw it beforhand, lol.

Actually, I still don’t know how it will be. It will not exactly dynamic, but if it’s too big, may be I could use just some “cuts”, but I think it will be less work with the image.

These algorithms are really annoying.

Thanks again!