Technology Trees

[Sareln]

First, go read this piece by Kael on how his team is tackling technologies in Elemental: Fallen Enchantress.

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.

Hey, that's really cool.

One of the things I noticed when I was mucking around in the guts of FfH for my tech-heat-map coloring project last summer is that techs are assigned fixed positions in CIV, and that's in the XML. I played around with the idea of having the python screen dynamically reconstruct the tech tree every time you opened the tech advisor (just ignoring the XML values), but eventually moved on to other things (Paring). Now that I hear it's possible, I'm insanely curious as to how they did it. Here's the thing, I think that CIV is perfectly capable of supporting a dynamic tech tree in the python screen, it just needs a clever algorithm, and this is where this post comes in.

Given a technology's Name, Cost, Or_Prereqs and And_Prereqs, how would you find a set of X/Y coordinates for it? Any one else made curious by this?

[SevenSpirits]

Definitely interesting.

Ignoring cost/era considerations for the moment, I think you'd first start by determining each tech's minimum X position (given that you don't want arrows to go backwards). A tech's min X would be the max of the min X of all its or-prereqs plus one. Probably you want to add a rule that to determine the min X of a tech of era N, you also treat all techs of era N-2 as or-prereqs for it, or something similar.

Then perhaps you start at minX = 0 and minX = 1 and lay them out with random Y values. At this point you start rearranging them (swapping positions of same-X techs) trying to minimize the sum of the Y distances that the prereq lines have to travel. Maybe you also consider crossed prereq-lines as a negative quality. Then you add the next column and jiggle them some more, etc, fingers crossed.

It's awfully vague. I don't know if there are any simplifying assumptions we can make. (I only made the assumption that two techs can't lead to each other in a loop.) Things would be much easier for example if no tech had more than one or-prereq, and I can't tell if Elemental is doing that.

[zakalwe]

The absence of cycles does simplify the problem. What you've got is a directed acyclic graph (DAG), defined by the techs and their OR prerequisites, which you want to visualize. You can do that by doing a so-called "topological sort", which is a fairly straightforward recursive algorithm. The topological sort would assign a "depth" to each technology. (The min X that SevenSpirits is talking about). So that would determine the set of columns that the techs would need to be arranged into in order to avoid backward arrows.

As a special case, if a lot of techs end up in the same column, you might want to arbitrarily split it into two equal-sized but vertically staggered columns (to leave room for arrows to pass through), just to improve the visual presentation.

The next step would involve deciding how to order the techs within each column to minimize the number of arrow crossings. You could probably do this through an exhaustive search of all possible orderings, depending on the number of techs. If that turns out to be too time-consuming, you could perhaps use some kind of "genetic algorithm", which essentially boils down to making a bunch of random guesses and keeping the best ones. Again, I'm basically just repeating what SevenSpirits suggested using more fancy lingo.

[Sareln]

TopSort would probably do what we want. O(E+V) is as good as it gets when you talk about graphs anyways, so I'll take it. This gets us the Y coordinates of the techs (do need to add in extra handling to split the eras apart though. If you know the Eras of a technology, which we do, that's straightforward).

So we pay O(R+T) + O(E * T), where T is the number of technologies to be placed, E is the number of eras, and R is the total number of prereqs (both AND and OR).

For finding X, the best non-genetic I can come up with is: There are some number of starting techs (techs with no requirements), there should be relatively few of these. For each starting tech, do what is essentially a depth-first search of the tree, placing all of it's children to have either it's X value, or the largest_X value of it's sibling's children + 1. If the child has already been placed, then skip it.

Evaluate the final result for arrow crossings.

Do this operation for each possible permutation of the starting techs (which one you do first) and choose the one with the least number of arrow crossings.

We visit every node once, so that's O(T), but we do this S! times, where S is the number of "Starting Techs".

I should draw some pictures for this. Later.

So then, given a graph with X/Y's and dependencies, how do you check it for arrow crossings?

EDIT: A graph that has the properties we want (no edge overlap) is called a Planar Graph. Not all graphs are Planar, of course.

[novice]

TopSort would probably do what we want. O(E+V) is as good as it gets when you talk about graphs anyways, so I'll take it. This gets us the Y coordinates of the techs (do need to add in extra handling to split the eras apart though. If you know the Eras of a technology, which we do, that's straightforward).

So we pay O(R+T) + O(E * T), where T is the number of technologies to be placed, E is the number of eras, and R is the total number of prereqs (both AND and OR).

For finding X, the best non-genetic I can come up with is: There are some number of starting techs (techs with no requirements), there should be relatively few of these. For each starting tech, do what is essentially a depth-first search of the tree, placing all of it's children to have either it's X value, or the largest_X value of it's sibling's children + 1. If the child has already been placed, then skip it.

Evaluate the final result for arrow crossings.

Do this operation for each possible permutation of the starting techs (which one you do first) and choose the one with the least number of arrow crossings.

We visit every node once, so that's O(T), but we do this S! times, where S is the number of "Starting Techs".

I should draw some pictures for this. Later.

So then, given a graph with X/Y's and dependencies, how do you check it for arrow crossings?

Does the python code control the positioning of the arrows themselves, or does the game engine draw them based solely on the coordinates of the from and to techs?

[Sareln]

Does the python code control the positioning of the arrows themselves, or does the game engine draw them based solely on the coordinates of the from and to techs?

Python draws the arrows, near as I can tell.

[Sareln]

An interesting paper (PDF) on a related field.

What I've learned in the past several days:

1. This problem does not have an ideal algorithmic solution
   
2. There are a lot of different ways to do it "good enough"
   
3. Graph Visualization is it's own Subfield of Graph Theory
   
4. Running fast is hard, since algs tend to be multi-pass with several evaluation heuristics.
   

The take-away message being: it's doable, read more

[Sareln]

The graphing algorithm proposed in that paper has been implemented in an open-source tool called graphviz. I grabbed it and plugged in the Paring mod's tech tree with only the Or requirements as edges (since I don't need to draw the and requirements) and was rewarded with this:

Looks good enough to use don't you think?

[SevenSpirits]

Nice!

[Caustic Soda]

I'm not certain I understand what the point of having a dynamic tech tree would be for Civ or FFH. As I understand it, it's relevant for Elemental because it is semi-random what techs you can get, which isn't the case in Civ. Am I missing something here?