The technology tree

In short: Technologies are nodes and prerequisites are arrows into them: a directed graph without cycles. A technology is free when all its prerequisites are known; the topological order puts everything so that each comes after its prerequisites, and a cycle makes that impossible.

Problem

Twelve technologies to the Stargate

In Epic Cosmos the victory by science is the technology Stargate. It cannot be researched from zero: it needs Dreadnoughts and Trade routes, the Dreadnoughts need Plasma cannons and Nano armor, and those need Fusion power and more. The player asks three questions:

1. What can I research now? Not everything: a technology is locked until all its prerequisites are known.
2. In what order do I reach the goal? And how much science will the way cost.
3. Can the table be wrong? If two technologies wait for each other, nothing can start.

Here is the tech screen from the game (from the run the game is checked with). + is known, > is being researched now, * can be researched, . is locked; the last line counts the way to the Stargate:

Turn 24/150  Terran Empire (A)                          score 93
M25+16 G173+30 C0+16 U47+3  science +10
Researching: Orbital fortresses 13/42
Technologies in order (+ known, > now, * can, . locked)
+  1 drill    Deep drilling           17  -
+  2 weapons1 Lasers                  21  -
+  3 hulls1   Light armor             21  -
+  4 lab2     Quantum labs            35  drill
*  5 fusion   Fusion power            49  lab2,weapons1
*  6 torpedo  Torpedoes               31  weapons1
*  7 cruiser  Cruiser hulls           31  hulls1
*  8 trade    Trade routes            35  drill
>  9 fortress Orbital fortresses      42  hulls1,drill
. 10 weapons2 Plasma cannons          71  fusion,torpedo
. 11 hulls2   Nano armor              71  fusion,cruiser
. 12 dread    Dreadnoughts           107  weapons2,hulls2
. 13 stargate Stargate               249  dread,trade
To the Stargate: 8 technologies, 644 science, banked 13.
Columns: number, name, cost, prerequisites.

The lesson builds these three answers with small programs over the same table, and at the end shows the same in the game. That the data is a text table and not code is shown in the lesson on creatures in Arcanum; here what matters is what the table is as a structure.

The idea

A table of prerequisites

A technology is a row of a table: a number, a name, a cost in science points and prerequisites, a list of other numbers. The game keeps the table as text and reads it at start, so a new technology is a new row, not new code. Here is the same table as the programs of the lesson load it (the game has more columns: the names in the other languages, the effect and its value):

# id|name|cost|prerequisites
drill|Deep drilling|17|-
weapons1|Lasers|21|-
hulls1|Light armor|21|-
lab2|Quantum labs|35|drill
fusion|Fusion power|49|lab2,weapons1
torpedo|Torpedoes|31|weapons1
cruiser|Cruiser hulls|31|hulls1
trade|Trade routes|35|drill
fortress|Orbital fortresses|42|hulls1,drill
weapons2|Plasma cannons|71|fusion,torpedo
hulls2|Nano armor|71|fusion,cruiser
dread|Dreadnoughts|107|weapons2,hulls2
stargate|Stargate|249|dread,trade

Three of the thirteen (drill, weapons1, hulls1) have no prerequisites (-), and stargate needs two. Rows with # are notes. One row becomes an object:

class Tech:
    def __init__(self, id, name, cost, prereqs):
        self.id = id
        self.name = name
        self.cost = cost
        self.prereqs = prereqs


def load(text):
    techs = {}
    for line in text.split("\n"):
        if line.strip() == "" or line.startswith("#"):
            continue
        c = line.split("|")
        prereqs = [] if c[3] == "-" else c[3].split(",")
        techs[c[0]] = Tech(c[0], c[1], int(c[2]), prereqs)
    return techs

load goes through the lines, skips the empty ones and the notes, cuts at | and keeps the technologies in the order of the table. The order matters: that is why the collection is ordered (LinkedHashMap in Java, Dictionary in C#, dict in Python, Map in JavaScript), so that the programs in the four languages print the same.

dict in Python keeps insertion order by specification since version 3.7.

The idea

A graph without cycles

Draw every technology as a node and every prerequisite as an arrow from the prerequisite to the technology: drill → lab2, lab2 → fusion. The table becomes a directed graph: the arrows have a direction. Ours has 13 nodes and 16 arrows.

The technology graph has one more property: it has no cycle. If you follow the arrows, you never come back to where you started. Such a graph is called a directed acyclic graph (DAG) and it is exactly the shape of “first this, then that”: tasks with dependencies, the modules of a project, the skill tree in an RPG.

A cycle is waiting for each other. Say optics needs lasers, lasers need radar, radar needs optics:

# id|name|cost|prerequisites
optics|Optics|10|lasers
lasers|Lasers|10|radar
radar|Radar|10|optics

None of the three can be first: each waits for another. The game must not start with such a table, so it checks twice. First at loading: every prerequisite must be a technology that exists.

for tech in TECHS.values():
    for need in tech.prereqs:
        if need not in TECHS:
            raise RuntimeError('techs: unknown prerequisite ' + need)

Then in main, before the game starts: if the topological order (the next cards) does not come out, the tree has a cycle.

if topo_order() is None:
    raise RuntimeError('the tech tree has a cycle')

The idea

What can be researched now

The player knows some technologies. A technology is free if it is not known yet and all its prerequisites are known. The code says the same with one loop and an early return:

def knows(known, tech_id):
    return tech_id in known


def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return False
    return True


def available_techs(techs, known):
    result = []
    for tech in techs.values():
        if can_research(known, tech):
            result.append(tech)
    return result

canResearch returns false as soon as it sees an unknown prerequisite, and if it reaches the end of the loop, true. A technology without prerequisites has an empty loop, so it is free from the start. availableTechs asks about every technology in the table. The program researches drill, weapons1 and lab2 one by one and after each step prints what opens:

techs = load(TABLE)
known = []
for learn in ["", "drill", "weapons1", "lab2"]:
    if learn != "":
        known.append(learn)
    print("Known: " + show(known))
    print("Can research: " + show(ids_of(available_techs(techs, known))))

Output

Known: -
Can research: drill, weapons1, hulls1
Known: drill
Can research: weapons1, hulls1, lab2, trade
Known: drill, weapons1
Can research: hulls1, lab2, torpedo, trade
Known: drill, weapons1, lab2
Can research: hulls1, fusion, torpedo, trade

Notice that fusion appears only at the end: it needs both lab2 and weapons1. And drill disappears from the list as soon as it is known, because canResearch starts by checking whether you already know it.

def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return 
    return True

Check

Here are the same functions from the game. The knowledge is the list empire.techs, not a separate argument, and everything else is the same:

# The technologies are a directed graph without cycles: an edge from the prerequisite to the technology. The knowledge of the
# empire is a list of ids; "what can be researched now" are the unknown ones whose prerequisites are
# all known.
def knows(empire, tech_id):
    return tech_id in empire.techs


def can_research(empire, tech):
    if knows(empire, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(empire, need):
            return False
    return True


def available_techs(empire):
    result = []
    for tech in TECHS.values():
        if can_research(empire, tech):
            result.append(tech)
    return result

More precisely, if you are curious

The ready functions there work on two levels: canResearch answers for one technology, availableTechs collects the answers for all. So the same canResearch serves startResearch (can the research begin) and the artificial intelligence that chooses among the free ones (the lesson on the rivals).

The idea

Topological order

Which research order is allowed? One in which each technology comes after its prerequisites. It is called a topological order, and every graph without cycles has at least one. The algorithm is simple: while there are unplaced ones, take the first technology whose prerequisites are all placed already, give it the next number and start over.

def topo_order(techs):
    placed = []
    done = set()
    while len(placed) < len(techs):
        pick = None
        for tech in techs.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            return None  # cycle: no ready technology
        placed.append(pick.id)
        done.add(pick.id)
    return placed

If at some step there is no such technology and there are still unplaced ones, they wait for each other: the function returns null. So the same algorithm is also a check for a cycle.

The program puts the table in reverse (stargate comes first), to show that the order does not come from it, and then tries the table with a cycle:

techs = load(REVERSED)  # the table is reversed, but the order does not depend on it
order = topo_order(techs)
for i in range(len(order)):
    print(i + 1, order[i])

if topo_order(load(CYCLE)) is None:
    print("Cycle: no technology has all its prerequisites ready.")

Output

1 hulls1
2 cruiser
3 weapons1
4 torpedo
5 drill
6 fortress
7 trade
8 lab2
9 fusion
10 hulls2
11 weapons2
12 dread
13 stargate
Cycle: no technology has all its prerequisites ready.

First comes hulls1: all those in front wait for something. Then cruiser, because hulls1 is already placed. Every arrow in the tree points from a smaller number to a larger one, and the table with a cycle returns null. When several are ready, the first in the table wins, so the order is the same everywhere. That is the rule in the game too:

# Topological order (Kahn): a technology comes out when all its prerequisites have come out. When
# several are ready, the one with the smaller number in the table wins, so the order is the same everywhere.
def topo_order():
    placed = []
    done = set()
    total = len(TECHS)
    while len(placed) < total:
        pick = None
        for tech in TECHS.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            # A cycle: no technology has its prerequisites ready.
            return None
        placed.append(pick.id)
        done.add(pick.id)
    return placed

The idea

A plan to the goal

The player chooses a goal, say stargate, and wants a list: what still has to be researched, and in what order. Two steps.

1. What is needed. We start at the goal and walk backwards along the arrows with a stack: pop a technology, and if it is not known, record it in need and push its prerequisites onto the stack. Known ones are skipped, so the part already researched is not paid for again.
2. In what order. need is a set, without order. The order comes from the topological one: we go through topoOrder and keep only the needed ones.

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan


def plan_cost(techs, plan):
    total = 0
    for tech_id in plan:
        total += techs[tech_id].cost
    return total

The program plans the way to the Stargate with no knowledge and then with drill, weapons1, hulls1 and lab2 known:

techs = load(TABLE)
for known in [[], ["drill", "weapons1", "hulls1", "lab2"]]:
    plan = plan_to(techs, known, "stargate")
    print("Known: " + show(known))
    print("Plan: " + show(plan))
    print(str(len(plan)) + " technologies, " + str(plan_cost(techs, plan)) + " science")

Output

Known: -
Plan: drill, weapons1, hulls1, lab2, fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
12 technologies, 738 science
Known: drill, weapons1, hulls1, lab2
Plan: fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
8 technologies, 644 science

The plan with no knowledge is 12 technologies, not 13: nobody on the way needs fortress. The sum 738 is what the screen at the start of the lesson shows as “to the Stargate”, and with four known ones 8 technologies remain for 644. It is the same in the canon:

# Everything that still has to be researched to reach the goal, in topological order.
def plan_to(empire, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(empire, tech_id):
            continue
        need.add(tech_id)
        for pre in TECHS[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order():
        if tech_id in need:
            plan.append(tech_id)
    return plan


def plan_cost(plan):
    total = 0
    for tech_id in plan:
        total += TECHS[tech_id].cost
    return total

See it

The tree in motion

The scene goes through the three answers: what opens after each researched technology, the order for the reversed table and the walk backwards from the Stargate. Follow the color of the frames (green is free, blue is known, orange is needed) and the numbers of the badges:

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan

Step by step, in words

1. Thirteen technologies. An arrow goes from the prerequisite to the technology: lab2 needs drill, fusion needs lab2 and weapons1. The number under the name is the cost.
2. Nothing is researched. drill, weapons1 and hulls1 have no prerequisites: the loop finds no unknown one and canResearch returns true. Only they are free (green).
3. You research drill (blue). Now lab2 and trade need only drill and are free. fortress also needs hulls1, so it waits. drill is no longer in the list: it is already known.
4. You research weapons1: torpedo unlocks. fusion needs both lab2 and weapons1: weapons1 is known, lab2 is not yet, so the loop returns false at lab2.
5. You research lab2: now fusion has both prerequisites and is free. One missing prerequisite keeps a technology locked; all of them ready open it.
6. A different question: in what order do we research everything? The table is reversed (stargate comes first), but the order does not come from it. topoOrder walks the table and takes the first technology whose prerequisites are all placed.
7. stargate, dread and the others in front are waiting for prerequisites. The first ready one is hulls1 (no prerequisites): it gets number 1.
8. After every number the search starts over: now cruiser is ready, because hulls1 is already placed. Placed ones are skipped.
9. Last is stargate, number 13: it waited for dread and trade. Every arrow points from a smaller number to a larger one: that is the topological order. If at some step no technology is ready, there is a cycle and the function returns null.
10. A plan to stargate. We start at the goal and walk backwards along the arrows with a stack: pop a technology, push its prerequisites. Everything reached goes into need (orange).
11. fortress was never reached: no technology on the way to stargate needs it. It does not go into the plan. Known ones are skipped, so what is already researched is not paid for again.
12. The walk says only what is needed. The order comes from the topological one: planTo goes through topoOrder and keeps the needed ones. So the plan has 12 technologies in an order where each comes after its prerequisites.
13. 12 technologies, 738 science: the sum of the costs. fortress (42) is not needed. The game shows the same number on the tech screen as “to the Stargate”.

The graph is the same in all three parts. Only the question to it changes: what is free (a look forward from the known ones), in what order (arranging everything) and how far (a look back from the goal).

Try it

Predict the output

A small table: sensors has no prerequisites, engines and shields need sensors, warp needs both, beacon needs warp. sensors and engines are known. What does the program print?

SMALL = """
# id|name|cost|prerequisites
sensors|Sensors|10|-
engines|Engines|12|sensors
shields|Shields|12|sensors
warp|Warp|20|engines,shields
beacon|Beacon|25|warp
"""

techs = load(SMALL)
known = ["sensors", "engines"]
print(show(ids_of(available_techs(techs, known))))

Answer

shields

engines, shields

shields, warp

Check

Try it

Find the bug

A colleague copied canResearch and put the wrong name in the check of the prerequisites. Here is what the program prints with only drill known; if it were correct, lab2 and trade would be here too:

def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, tech.id):
            return False
    return True


techs = load(TABLE)
known = ["drill"]
print("Known: " + show(known))
print("Can research: " + show(ids_of(available_techs(techs, known))))

Output

Known: drill
Can research: weapons1, hulls1

Which line is to blame?

Pick the line with the bug.

1def can_research(known, tech):2 if knows(known, tech.id):3 return False4 for need in tech.prereqs:5 if not knows(known, tech.id):6 return False7 return True8910techs = load(TABLE)11known = ["drill"]12print("Known: " + show(known))13print("Can research: " + show(ids_of(available_techs(techs, known))))

Check

More precisely

What this system leaves out

The tree in the game has few rules, and behind them stand choices.

All prerequisites, not “any of”. canResearch returns false at the first unknown one. Some games allow “this or that”: then a prerequisite is a group, and the technology opens when one of the groups is fulfilled. That is another graph (with two kinds of arrows), not another function.

The order for a tie is part of the rule. Many technologies can be ready at once, and every arrangement is correct. The canon takes the first in the table, so that the same order comes out in all languages and on every run. If the order depended on the insertion order of a hash table, programs in two languages could differ.

The topological algorithm here is the simplest, not the fastest. topoOrder walks the table from the start for every number: for n technologies that is about n² checks. For thirteen it is nothing. For thousands (package dependencies) the algorithm of Kahn is used, with a counter of waiting prerequisites for every technology and a queue of the ready ones: O(V + E). That is the lesson on topological sorting, and walking a graph with a stack is in the DFS lesson.

The effect of a technology is separate work. Here a technology is only a node with a cost. What it gives (more output, attack, a new ship) is in other columns of the table, and techMods sums the effects of all known ones; which ship needs what is in the lesson on fleets.

The cycle is caught at start, not during the game. The table is part of the code of the game, not an input of the player. So the check is one call of topoOrder in main. If the table came from a user (a mod), the same check would be an error message to them, not a crash of the game.

Exercise

A plan for a given table

Solve this in your editor.

A plan for a given table. The program reads three things from the input: on the first line the goal, on the second the known technologies separated by commas (or - if there are none), and on every following line one technology in the form id cost prerequisites (the prerequisites separated by commas, - for none). The table is in a topological order, but the program must not rely on that. It prints the plan (only the needed unplaced technologies in a topological order) and the sum of the costs.

With the input warp | sensors | sensors 10 - | engines 12 sensors | shields 12 sensors | warp 20 engines,shields | beacon 25 warp (one per line) the output is:

Output

Plan: engines, shields, warp
Cost: 44

Be careful: sensors is known, so it is not in the plan and is not paid for; warp is the goal and comes last in the plan.

More tasks

• A cycle in the table. Give a table in which a needs b and b needs a. What does planTo do with a topoOrder that returns null? Make the program say there is a cycle instead of crashing.
• An unknown prerequisite. Add a row with a prerequisite that is not in the table. Catch it at loading, the way loadData does.
• What does this one unlock? Write unlocks(techs, id), which returns the technologies that need id as a prerequisite. That is walking the arrows forward.
• The cheapest first move. From the free technologies pick the one with the lowest cost. What happens if two cost the same?

Test

Check yourself

1. Why must the technology table have no cycle, for example optics needs lasers, lasers needs radar, radar needs optics?

Because a technology can need at most one prerequisiteEach of the three waits for another one of them, so none can be first and none ever becomes “free”. The game checks this at start and does not run with such a tableBecause a cycle makes the table slower to read

2. fusion needs lab2 and weapons1. drill and weapons1 are known. Can fusion be researched?

Yes: weapons1 is known, and one prerequisite is enoughYes: drill leads to lab2No: lab2 is not known yet, and all prerequisites are required

3. In the program topo the table is reversed (stargate comes first). Why does topoOrder still give a correct order?

It does not: a correct order exists only if the table is already sortedIt does not follow the order of the table, it takes the first technology whose prerequisites are all placed already, and starts over. The table only decides which one wins when several are readyIt first sorts the table by cost

4. Why does fortress not go into the plan to stargate?

Because it has two prerequisitesBecause it is the cheapest technologyNo technology on the paths back from stargate needs it: it is a leaf the walk never reaches

5. topoOrder returned null. What does that mean for the table?

Some technology needs a prerequisite that does not existThe table is emptyThere is a cycle: at some step no unplaced technology has all its prerequisites placed

Check

Start the lesson over

Related lessons

• Builds on: What all objects share: class attributes · Strings · Lists: append, remove and sort · dict and set
• Tasks on this topic: Epic Cosmos: the empire