Tuesday, July 26, 2011

An Autoplace & Route Tool for Civilization Style Tech Trees

A particular statement in this piece by Derek "Kael" Paxton about technology in Stardock's Elemental: War of Magic stood out:
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:

  1. Reads in the Technology Data from a spreadsheet
  2. Processes the Technology Data to add missing Parent-Children links (Data originally contains only Children-Parent links)
  3. Does a DFS search from every root node and calculates an affinity between each root based on how many nodes they share.
  4. Orders the Root nodes based on their affinities, so that roots which share many nodes are placed together
  5. Runs most of the Vertex Ordering part of Gansner's Algorithm (Heuristic Based)
  6. 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

A Cvilization IV Combat Calculator

Update (8/10/12): There was a bug in the calculator when calculating battles not at 100% health for both sides.  I've fixed it now.

Download Combat Calculator

In one of my PBEM Civilization games I needed to destroy one particular unit, but none of my units had good odds on it.  Since I outnumbered it 7:1, I decided to go ahead and attempt to mob it to death.  I had no idea what my odds were, but before combat began any one of my units did not get (in game calculator's) odds over 0.01%.  I ended up winning after 4 battles.

I was curious then, what my actual, group, odds were.

Looking online, there were no good current CIV IV combat calculators available, so I decided to build my own.  Working with some of the other fellows at Realms Beyond to understand how the combat system actually worked, I ended up with a decent calculator.

This calculator can be used to find the precise odds for 1:1 unit combats, or X:1 combats with many attackers and a single defender.  It is built on Excel 2007 and requires macros to be enabled.  You trust me don't you?

Limitations:

  • Does not properly calculate retreat Chances
  • Does not calculate defensive strikes (A Mechanic from FfH)
Multiple Attacker, Single Defender Tab

Single Attacker, Single Defender Tab