5. Autolayout- The tech tree draws itself and its lines automatically. This was needed because the tech tree will be different every time, so it must be able to lay itself out programmatically. The good news for modders is that they can add techs to their hearts content and they will be automatically added to the tree right where they belong.I thought that was really cool, and decided to look into how to do such things.
After some literature research, I found this paper out of AT&T Bell Labs By Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo.
The algorithm looked fairly straightforward so I decided to see if I could implement it first in Excel 2007 (VBA) and then in Civilization IV (Python or C++ depending upon which level I ran the algorithm).
Here is how the tool works:
- Reads in the Technology Data from a spreadsheet
- Processes the Technology Data to add missing Parent-Children links (Data originally contains only Children-Parent links)
- Does a DFS search from every root node and calculates an affinity between each root based on how many nodes they share.
- Orders the Root nodes based on their affinities, so that roots which share many nodes are placed together
- Runs most of the Vertex Ordering part of Gansner's Algorithm (Heuristic Based)
- Determines X and Y coordinates for each technology based on its rank and vertex order.
Limitations:
- I have not yet finished generalizing the code. I think that if you try it right now on a tree that is deeper than 9 ranks, you'll get an out of bounds error.
- It's not as fast as it could be, there are some inefficiencies I already have in my mind to target. For now it takes about 2 seconds to generate and draw the placement.
- It requires Excel 2007 and Macros enabled, you trust me right?
 |
| The Final Result Download AutoPlace and Route Tool |
