Zum Inhalt
wannacode

Der Technologiebaum

Kurz gesagt: Technologien sind Knoten, und Voraussetzungen sind Pfeile zu ihnen: ein gerichteter Graph ohne Zyklen. Eine Technologie ist frei, wenn alle ihre Voraussetzungen bekannt sind; die topologische Reihenfolge ordnet alles so, dass jede nach ihren Voraussetzungen kommt, und ein Zyklus macht das unmöglich.

Problem

Zwölf Technologien bis zum Sternentor

In Epic Cosmos ist der Sieg durch Wissenschaft die Technologie Sternentor. Sie lässt sich nicht von null erforschen: Sie braucht Schlachtschiffe und Handelsrouten, die Schlachtschiffe brauchen Plasmakanonen und Nanopanzerung, und diese brauchen Kernfusion und mehr. Der Spieler stellt drei Fragen:

  1. Was kann ich jetzt erforschen? Nicht alles: Eine Technologie ist gesperrt, bis alle ihre Voraussetzungen bekannt sind.
  2. In welcher Reihenfolge erreiche ich das Ziel? Und wie viel Forschung kostet der Weg.
  3. Kann die Tabelle falsch sein? Wenn zwei Technologien aufeinander warten, kann nichts anfangen.

Hier ist der Bildschirm tech aus dem Spiel (aus dem Durchlauf, an dem das Spiel geprüft wird). + ist bekannt, > wird gerade erforscht, * kann erforscht werden, . ist gesperrt; die letzte Zeile zählt den Weg bis zum Sternentor:

Runde 24/150  Terranisches Reich (A)                   Punkte 93
M25+16 G173+30 C0+16 U47+3  Forschung +10
Forscht: Orbitalfestungen 13/42
Technologien (+ bekannt, > jetzt, * möglich, . gesperrt)
+  1 drill    Tiefbohrung             17  -
+  2 weapons1 Laser                   21  -
+  3 hulls1   Leichte Panzerung       21  -
+  4 lab2     Quantenlabore           35  drill
*  5 fusion   Kernfusion              49  lab2,weapons1
*  6 torpedo  Torpedos                31  weapons1
*  7 cruiser  Kreuzerrümpfe           31  hulls1
*  8 trade    Handelsrouten           35  drill
>  9 fortress Orbitalfestungen        42  hulls1,drill
. 10 weapons2 Plasmakanonen           71  fusion,torpedo
. 11 hulls2   Nanopanzerung           71  fusion,cruiser
. 12 dread    Schlachtschiffe        107  weapons2,hulls2
. 13 stargate Sternentor             249  dread,trade
Bis zum Sternentor: 8 Technologien, 644 Forschung, gespart 13.
Spalten: Nummer, Name, Preis, Voraussetzungen.

Die Lektion baut diese drei Antworten mit kleinen Programmen über dieselbe Tabelle und zeigt am Ende dasselbe im Spiel. Dass die Daten eine Texttabelle sind und kein Code, zeigt die Lektion über die Wesen in Arkanum; hier zählt, was die Tabelle als Struktur ist.

Die Idee

Eine Tabelle mit Voraussetzungen

Eine Technologie ist eine Zeile einer Tabelle: eine Nummer, ein Name, ein Preis in Forschungspunkten und Voraussetzungen, eine Liste anderer Nummern. Das Spiel hält die Tabelle als Text und liest sie beim Start, also ist eine neue Technologie eine neue Zeile, kein neuer Code. Hier ist dieselbe Tabelle, wie die Programme der Lektion sie laden (das Spiel hat mehr Spalten: die Namen in den anderen Sprachen, den Effekt und seinen Wert):

# id|Name|Preis|Voraussetzungen
drill|Tiefbohrung|17|-
weapons1|Laser|21|-
hulls1|Leichte Panzerung|21|-
lab2|Quantenlabore|35|drill
fusion|Kernfusion|49|lab2,weapons1
torpedo|Torpedos|31|weapons1
cruiser|Kreuzerrümpfe|31|hulls1
trade|Handelsrouten|35|drill
fortress|Orbitalfestungen|42|hulls1,drill
weapons2|Plasmakanonen|71|fusion,torpedo
hulls2|Nanopanzerung|71|fusion,cruiser
dread|Schlachtschiffe|107|weapons2,hulls2
stargate|Sternentor|249|dread,trade

Drei der dreizehn (drill, weapons1, hulls1) haben keine Voraussetzungen (-), und stargate braucht zwei. Zeilen mit # sind Notizen. Eine Zeile wird zu einem Objekt:

class Tech
{
    public string Id;
    public string Name;
    public int Cost;
    public List<string> Prereqs;


    public Tech(string id, string name, int cost, List<string> prereqs)
    {
        Id = id;
        Name = name;
        Cost = cost;
        Prereqs = prereqs;
    }
}


static Dictionary<string, Tech> Load(string text)
{
    var techs = new Dictionary<string, Tech>();
    foreach (string line in text.Split('\n'))
    {
        if (line.Trim() == "" || line.StartsWith("#")) continue;
        string[] c = line.Split('|');
        var prereqs = c[3] == "-" ? new List<string>() : new List<string>(c[3].Split(','));
        techs[c[0]] = new Tech(c[0], c[1], int.Parse(c[2]), prereqs);
    }
    return techs;
}

load geht die Zeilen durch, überspringt die leeren und die Notizen, schneidet bei | und hält die Technologien in der Reihenfolge der Tabelle. Die Reihenfolge zählt: Deshalb ist die Sammlung geordnet (LinkedHashMap in Java, Dictionary in C#, dict in Python, Map in JavaScript), damit die Programme in den vier Sprachen dasselbe ausgeben.

Dictionary liefert die Einträge in der Praxis in der Einfügereihenfolge, solange nichts daraus entfernt wird. Der Kanon verlässt sich nicht darauf und hält die Schlüssel in einer Liste (die Klasse OrderedMap); hier ist es für das Beispiel kurz.

Die Idee

Ein Graph ohne Zyklen

Zeichne jede Technologie als Knoten und jede Voraussetzung als Pfeil von der Voraussetzung zur Technologie: drill → lab2, lab2 → fusion. Die Tabelle wird zu einem gerichteten Graphen: Die Pfeile haben eine Richtung. Unserer hat 13 Knoten und 16 Pfeile.

Der Technologiegraph hat noch eine Eigenschaft: Er hat keinen Zyklus. Folgst du den Pfeilen, kommst du nie dorthin zurück, wo du gestartet bist. Ein solcher Graph heißt gerichteter azyklischer Graph (DAG, directed acyclic graph) und ist genau die Form von „erst das, dann jenes“: Aufgaben mit Abhängigkeiten, die Module eines Projekts, der Fähigkeitenbaum in einem RPG.

Ein Zyklus ist gegenseitiges Warten. Sagen wir, optics braucht lasers, lasers brauchen radar, radar braucht optics:

# id|Name|Preis|Voraussetzungen
optics|Optik|10|lasers
lasers|Laser|10|radar
radar|Radar|10|optics

Keine der drei kann die erste sein: Jede wartet auf eine andere. Das Spiel darf mit so einer Tabelle nicht starten, also prüft es zweimal. Erst beim Laden: Jede Voraussetzung muss eine Technologie sein, die es gibt.

foreach (Tech tech in TECHS.Values())
{
    foreach (string need in tech.Prereqs)
    {
        if (!TECHS.Has(need)) throw new Exception("techs: unknown prerequisite " + need);
    }
}

Dann in main, bevor das Spiel beginnt: Kommt die topologische Reihenfolge (die nächsten Karten) nicht heraus, hat der Baum einen Zyklus.

if (TopoOrder() == null) throw new Exception("the tech tree has a cycle");

Die Idee

Was jetzt erforschbar ist

Der Spieler kennt einige Technologien. Eine Technologie ist frei, wenn sie noch nicht bekannt ist und alle ihre Voraussetzungen bekannt sind. Der Code sagt dasselbe mit einer Schleife und einer frühen Rückgabe:

static bool Knows(List<string> known, string techId)
{
    return known.Contains(techId);
}


static bool CanResearch(List<string> known, Tech tech)
{
    if (Knows(known, tech.Id)) return false;
    foreach (string need in tech.Prereqs)
    {
        if (!Knows(known, need)) return false;
    }
    return true;
}


static List<Tech> AvailableTechs(Dictionary<string, Tech> techs, List<string> known)
{
    var list = new List<Tech>();
    foreach (Tech tech in techs.Values)
    {
        if (CanResearch(known, tech)) list.Add(tech);
    }
    return list;
}

canResearch gibt false zurück, sobald es eine unbekannte Voraussetzung sieht, und wenn es das Ende der Schleife erreicht, true. Eine Technologie ohne Voraussetzungen hat eine leere Schleife, also ist sie von Anfang an frei. availableTechs fragt für jede Technologie der Tabelle. Das Programm erforscht drill, weapons1 und lab2 nacheinander und gibt nach jedem Schritt aus, was sich öffnet:

var techs = Load(TABLE);
var known = new List<string>();
foreach (string learn in new[] { "", "drill", "weapons1", "lab2" })
{
    if (learn != "") known.Add(learn);
    Console.WriteLine("Bekannt: " + Show(known));
    Console.WriteLine("Erforschbar: " + Show(IdsOf(AvailableTechs(techs, known))));
}
Ausgabe
Bekannt: -
Erforschbar: drill, weapons1, hulls1
Bekannt: drill
Erforschbar: weapons1, hulls1, lab2, trade
Bekannt: drill, weapons1
Erforschbar: hulls1, lab2, torpedo, trade
Bekannt: drill, weapons1, lab2
Erforschbar: hulls1, fusion, torpedo, trade

Beachte, dass fusion erst am Ende erscheint: Sie braucht lab2 und weapons1. Und drill verschwindet aus der Liste, sobald sie bekannt ist, weil canResearch damit beginnt zu prüfen, ob du sie schon kennst.

static bool CanResearch(List<string> known, Tech tech)
{
    if (Knows(known, tech.Id)) return false;
    foreach (string need in tech.Prereqs)
    {
        if (!Knows(known, need)) return ;
    }
    return true;
}

Hier sind dieselben Funktionen aus dem Spiel. Das Wissen ist die Liste empire.techs, kein eigenes Argument, und alles andere ist gleich:

// Die Technologien sind ein gerichteter Graph ohne Zyklen: eine Kante von der Voraussetzung zur Technologie. Das Wissen des
// Reiches ist eine Liste von Nummern; „was jetzt erforscht werden kann“ sind die unbekannten, deren Voraussetzungen
// alle schon bekannt sind.
public static bool Knows(Empire empire, string techId)
{
    return empire.Techs.IndexOf(techId) >= 0;
}


public static bool CanResearch(Empire empire, Tech tech)
{
    if (Knows(empire, tech.Id)) return false;
    foreach (string need in tech.Prereqs)
    {
        if (!Knows(empire, need)) return false;
    }
    return true;
}


public static List<Tech> AvailableTechs(Empire empire)
{
    List<Tech> list = new List<Tech>();
    foreach (Tech tech in TECHS.Values())
    {
        if (CanResearch(empire, tech)) list.Add(tech);
    }
    return list;
}
Genauer, für Neugierige

Die fertigen Funktionen dort arbeiten auf zwei Ebenen: canResearch antwortet für eine Technologie, availableTechs sammelt die Antworten für alle. So dient dasselbe canResearch dem startResearch (kann die Forschung beginnen) und der künstlichen Intelligenz, die unter den freien wählt (die Lektion über die Rivalen).

Die Idee

Topologische Reihenfolge

Welche Forschungsreihenfolge ist erlaubt? Eine, in der jede Technologie nach ihren Voraussetzungen kommt. Sie heißt topologische Reihenfolge, und jeder Graph ohne Zyklen hat mindestens eine. Der Algorithmus ist einfach: Solange es nicht eingeordnete gibt, nimm die erste Technologie, deren Voraussetzungen alle schon eingeordnet sind, gib ihr die nächste Nummer und fang von vorn an.

static List<string>? TopoOrder(Dictionary<string, Tech> techs)
{
    var placed = new List<string>();
    var done = new HashSet<string>();
    while (placed.Count < techs.Count)
    {
        Tech? pick = null;
        foreach (Tech tech in techs.Values)
        {
            if (done.Contains(tech.Id)) continue;
            bool ready = true;
            foreach (string need in tech.Prereqs)
            {
                if (!done.Contains(need)) ready = false;
            }
            if (ready)
            {
                pick = tech;
                break;
            }
        }
        if (pick == null) return null; // Zyklus: keine bereite Technologie
        placed.Add(pick.Id);
        done.Add(pick.Id);
    }
    return placed;
}

Gibt es in einem Schritt keine solche Technologie, und es gibt noch nicht eingeordnete, dann warten sie aufeinander: Die Funktion gibt null zurück. So ist derselbe Algorithmus auch eine Prüfung auf Zyklen.

Das Programm legt die Tabelle verkehrt herum hin (stargate steht vorn), um zu zeigen, dass die Reihenfolge nicht von ihr kommt, und probiert dann die Tabelle mit dem Zyklus:

var techs = Load(REVERSED); // die Tabelle steht verkehrt herum, aber die Reihenfolge hängt nicht von ihr ab
List<string> order = TopoOrder(techs)!;
for (int i = 0; i < order.Count; i++)
{
    Console.WriteLine((i + 1) + " " + order[i]);
}


if (TopoOrder(Load(CYCLE)) == null) Console.WriteLine("Zyklus: Keine Technologie hat alle Voraussetzungen bereit.");
Ausgabe
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
Zyklus: Keine Technologie hat alle Voraussetzungen bereit.

Zuerst kommt hulls1: Alle davor warten auf etwas. Dann cruiser, weil hulls1 schon eingeordnet ist. Jeder Pfeil im Baum zeigt von einer kleineren zu einer größeren Nummer, und die Tabelle mit dem Zyklus gibt null zurück. Sind mehrere bereit, gewinnt die erste in der Tabelle, also ist die Reihenfolge überall gleich. Das ist auch die Regel im Spiel:

// Topologische Ordnung (Kahn): eine Technologie kommt heraus, wenn alle ihre Voraussetzungen herausgekommen sind. Bei
// mehreren bereiten gewinnt die mit der kleineren Nummer in der Tabelle, darum ist die Reihenfolge überall gleich.
public static List<string>? TopoOrder()
{
    List<string> placed = new List<string>();
    HashSet<string> done = new HashSet<string>();
    int total = TECHS.Count;
    while (placed.Count < total)
    {
        Tech? pick = null;
        foreach (Tech tech in TECHS.Values())
        {
            if (done.Contains(tech.Id)) continue;
            bool ready = true;
            foreach (string need in tech.Prereqs)
            {
                if (!done.Contains(need)) ready = false;
            }
            if (ready)
            {
                pick = tech;
                break;
            }
        }
        // Ein Zyklus: Keine Technologie hat ihre Voraussetzungen erfüllt.
        if (pick == null) return null;
        placed.Add(pick.Id);
        done.Add(pick.Id);
    }
    return placed;
}

Die Idee

Ein Plan bis zum Ziel

Der Spieler wählt ein Ziel, etwa stargate, und will eine Liste: was noch erforscht werden muss und in welcher Reihenfolge. Zwei Schritte.

  1. Was gebraucht wird. Wir beginnen beim Ziel und gehen mit einem Stapel rückwärts an den Pfeilen entlang: eine Technologie herausnehmen, und wenn sie nicht bekannt ist, in need eintragen und ihre Voraussetzungen auf den Stapel legen. Bekannte werden übersprungen, also wird der schon erforschte Teil nicht noch einmal bezahlt.
  2. In welcher Reihenfolge. need ist eine Menge, ohne Reihenfolge. Die Reihenfolge kommt von der topologischen: Wir gehen durch topoOrder und behalten nur die nötigen.
static List<string> PlanTo(Dictionary<string, Tech> techs, List<string> known, string targetId)
{
    var need = new HashSet<string>();
    var stack = new List<string> { targetId };
    while (stack.Count > 0)
    {
        string id = stack[stack.Count - 1];
        stack.RemoveAt(stack.Count - 1);
        if (need.Contains(id) || Knows(known, id)) continue;
        need.Add(id);
        foreach (string pre in techs[id].Prereqs) stack.Add(pre);
    }
    var plan = new List<string>();
    foreach (string id in TopoOrder(techs)!)
    {
        if (need.Contains(id)) plan.Add(id);
    }
    return plan;
}


static int PlanCost(Dictionary<string, Tech> techs, List<string> plan)
{
    int sum = 0;
    foreach (string id in plan) sum += techs[id].Cost;
    return sum;
}

Das Programm plant den Weg zum Sternentor ohne Wissen und dann mit bekannten drill, weapons1, hulls1 und lab2:

var techs = Load(TABLE);
var starts = new List<List<string>> { new List<string>(), new List<string> { "drill", "weapons1", "hulls1", "lab2" } };
foreach (List<string> known in starts)
{
    List<string> plan = PlanTo(techs, known, "stargate");
    Console.WriteLine("Bekannt: " + Show(known));
    Console.WriteLine("Plan: " + Show(plan));
    Console.WriteLine(plan.Count + " Technologien, " + PlanCost(techs, plan) + " Forschung");
}
Ausgabe
Bekannt: -
Plan: drill, weapons1, hulls1, lab2, fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
12 Technologien, 738 Forschung
Bekannt: drill, weapons1, hulls1, lab2
Plan: fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
8 Technologien, 644 Forschung

Der Plan ohne Wissen hat 12 Technologien, nicht 13: fortress braucht auf dem Weg niemand. Die Summe 738 ist das, was der Bildschirm am Anfang der Lektion als „Bis zum Sternentor“ zeigt, und mit vier bekannten bleiben 8 Technologien für 644. Im Kanon ist es genauso:

// Alles, was noch erforscht werden muss, um das Ziel zu erreichen, in topologischer Reihenfolge.
public static List<string> PlanTo(Empire empire, string targetId)
{
    HashSet<string> need = new HashSet<string>();
    List<string> stack = new List<string> { targetId };
    while (stack.Count > 0)
    {
        string id = stack[stack.Count - 1];
        stack.RemoveAt(stack.Count - 1);
        if (need.Contains(id) || Knows(empire, id)) continue;
        need.Add(id);
        foreach (string pre in TECHS.Get(id).Prereqs) stack.Add(pre);
    }
    List<string> plan = new List<string>();
    foreach (string id in TopoOrder()!)
    {
        if (need.Contains(id)) plan.Add(id);
    }
    return plan;
}


public static int PlanCost(List<string> plan)
{
    int sum = 0;
    foreach (string id in plan) sum += TECHS.Get(id).Cost;
    return sum;
}

Sieh es dir an

Der Baum in Bewegung

Die Szene geht durch die drei Antworten: was sich nach jeder erforschten Technologie öffnet, die Reihenfolge für die verkehrte Tabelle und den Gang rückwärts vom Sternentor. Achte auf die Farbe der Rahmen (grün ist frei, blau ist bekannt, orange ist nötig) und auf die Nummern der Plaketten:

static List<string> PlanTo(Dictionary<string, Tech> techs, List<string> known, string targetId)
{
    var need = new HashSet<string>();
    var stack = new List<string> { targetId };
    while (stack.Count > 0)
    {
        string id = stack[stack.Count - 1];
        stack.RemoveAt(stack.Count - 1);
        if (need.Contains(id) || Knows(known, id)) continue;
        need.Add(id);
        foreach (string pre in techs[id].Prereqs) stack.Add(pre);
    }
    var plan = new List<string>();
    foreach (string id in TopoOrder(techs)!)
    {
        if (need.Contains(id)) plan.Add(id);
    }
    return plan;
}
Schritt für Schritt, in Worten
  1. Dreizehn Technologien. Ein Pfeil geht von der Voraussetzung zur Technologie: lab2 braucht drill, fusion braucht lab2 und weapons1. Die Zahl unter dem Namen ist der Preis.
  2. Nichts ist erforscht. drill, weapons1 und hulls1 haben keine Voraussetzungen: Die Schleife findet keine unbekannte, und canResearch gibt true zurück. Nur sie sind frei (grün).
  3. Du erforschst drill (blau). Jetzt brauchen lab2 und trade nur drill und sind frei. fortress braucht auch hulls1 und wartet. drill steht nicht mehr in der Liste: Sie ist schon bekannt.
  4. Du erforschst weapons1: torpedo wird freigeschaltet. fusion braucht lab2 und weapons1: weapons1 ist bekannt, lab2 noch nicht, deshalb gibt die Schleife dort false zurück.
  5. Du erforschst lab2: Jetzt hat fusion beide Voraussetzungen und ist frei. Eine fehlende Voraussetzung hält eine Technologie gesperrt, alle bereiten öffnen sie.
  6. Eine andere Frage: In welcher Reihenfolge erforschen wir alles? Die Tabelle steht verkehrt herum (stargate steht vorn), aber die Reihenfolge kommt nicht von ihr. topoOrder geht die Tabelle durch und nimmt die erste Technologie, deren Voraussetzungen alle eingeordnet sind.
  7. stargate, dread und die anderen davor warten auf Voraussetzungen. Die erste bereite ist hulls1 (ohne Voraussetzungen): Sie bekommt die Nummer 1.
  8. Nach jeder Nummer beginnt die Suche von vorn: Jetzt ist cruiser bereit, weil hulls1 schon eingeordnet ist. Eingeordnete werden übersprungen.
  9. Als Letzte kommt stargate mit Nummer 13: Sie wartete auf dread und trade. Jeder Pfeil zeigt von einer kleineren zu einer größeren Nummer: Das ist die topologische Reihenfolge. Ist in einem Schritt keine Technologie bereit, gibt es einen Zyklus, und die Funktion gibt null zurück.
  10. Ein Plan bis stargate. Wir beginnen beim Ziel und gehen mit einem Stapel rückwärts an den Pfeilen entlang: Technologie herausnehmen, ihre Voraussetzungen hineinlegen. Alles Erreichte kommt in need (orange).
  11. fortress wurde nie erreicht: Keine Technologie auf dem Weg zu stargate braucht sie. Sie kommt nicht in den Plan. Bekannte werden übersprungen, also wird Erforschtes nicht noch einmal bezahlt.
  12. Der Gang sagt nur, was gebraucht wird. Die Reihenfolge kommt von der topologischen: planTo geht durch topoOrder und behält die nötigen. So hat der Plan 12 Technologien in einer Reihenfolge, in der jede nach ihren Voraussetzungen kommt.
  13. 12 Technologien, 738 Forschung: die Summe der Preise. fortress (42) wird nicht gebraucht. Dieselbe Zahl zeigt das Spiel auf dem Bildschirm tech als „Bis zum Sternentor“.

Der Graph ist in allen drei Teilen derselbe. Nur die Frage an ihn ändert sich: was ist frei (ein Blick nach vorn von den bekannten), in welcher Reihenfolge (alles ordnen) und wie weit (ein Blick zurück vom Ziel).

Probier es aus

Sage die Ausgabe voraus

Eine kleine Tabelle: sensors hat keine Voraussetzungen, engines und shields brauchen sensors, warp braucht beide, beacon braucht warp. Bekannt sind sensors und engines. Was gibt das Programm aus?

const string SMALL = """
# id|Name|Preis|Voraussetzungen
sensors|Sensoren|10|-
engines|Triebwerke|12|sensors
shields|Schilde|12|sensors
warp|Warp|20|engines,shields
beacon|Bake|25|warp
""";


var techs = Load(SMALL);
var known = new List<string> { "sensors", "engines" };
Console.WriteLine(Show(IdsOf(AvailableTechs(techs, known))));
Antwort

Probier es aus

Finde den Fehler

Ein Kollege hat canResearch kopiert und in der Prüfung der Voraussetzungen den falschen Namen eingesetzt. Hier steht, was das Programm ausgibt, wenn nur drill bekannt ist; wäre es richtig, stünden hier auch lab2 und trade:

static bool CanResearch(List<string> known, Tech tech)
{
    if (Knows(known, tech.Id)) return false;
    foreach (string need in tech.Prereqs)
    {
        if (!Knows(known, tech.Id)) return false;
    }
    return true;
}


var techs = Load(TABLE);
var known = new List<string> { "drill" };
Console.WriteLine("Bekannt: " + Show(known));
Console.WriteLine("Erforschbar: " + Show(IdsOf(AvailableTechs(techs, known))));
Ausgabe
Bekannt: drill
Erforschbar: weapons1, hulls1

Welche Zeile ist schuld?

Wähle die Zeile mit dem Fehler.

Genauer

Was dieses System offenlässt

Der Baum im Spiel hat wenige Regeln, und hinter ihnen stehen Entscheidungen.

Alle Voraussetzungen, nicht „eine von“. canResearch gibt bei der ersten unbekannten false zurück. Manche Spiele erlauben „dies oder das“: Dann ist eine Voraussetzung eine Gruppe, und die Technologie öffnet sich, wenn eine der Gruppen erfüllt ist. Das ist ein anderer Graph (mit zwei Arten von Pfeilen), keine andere Funktion.

Die Reihenfolge bei Gleichstand gehört zur Regel. Viele Technologien können gleichzeitig bereit sein, und jede Anordnung ist richtig. Der Kanon nimmt die erste in der Tabelle, damit in allen Sprachen und bei jedem Lauf dieselbe Reihenfolge herauskommt. Hinge die Reihenfolge von der Einfügereihenfolge einer Hash-Tabelle ab, könnten Programme in zwei Sprachen voneinander abweichen.

Der topologische Algorithmus hier ist der einfachste, nicht der schnellste. topoOrder geht für jede Nummer die Tabelle von vorn durch: Bei n Technologien sind das etwa n² Prüfungen. Bei dreizehn ist das nichts. Bei Tausenden (Paketabhängigkeiten) nimmt man den Algorithmus von Kahn mit einem Zähler wartender Voraussetzungen für jede Technologie und einer Warteschlange der bereiten: O(V + E). Das ist die Lektion über topologisches Sortieren, und das Durchlaufen eines Graphen mit einem Stapel steht in der DFS-Lektion.

Der Effekt einer Technologie ist eine eigene Arbeit. Hier ist eine Technologie nur ein Knoten mit einem Preis. Was sie gibt (mehr Ertrag, Angriff, ein neues Schiff), steht in anderen Spalten der Tabelle, und techMods summiert die Effekte aller bekannten; welches Schiff was braucht, steht in der Lektion über die Flotten.

Der Zyklus wird beim Start gefangen, nicht während des Spiels. Die Tabelle ist Teil des Codes des Spiels, keine Eingabe des Spielers. Also ist die Prüfung ein Aufruf von topoOrder in main. Käme die Tabelle von einem Nutzer (ein Mod), wäre dieselbe Prüfung eine Fehlermeldung an ihn, kein Absturz des Spiels.

Übung

Ein Plan für eine gegebene Tabelle

Löse das in deinem Editor.

Ein Plan für eine gegebene Tabelle. Das Programm liest drei Dinge von der Eingabe: in der ersten Zeile das Ziel, in der zweiten die bekannten Technologien, durch Kommas getrennt (oder -, wenn es keine gibt), und in jeder folgenden Zeile eine Technologie in der Form id Preis Voraussetzungen (die Voraussetzungen durch Kommas getrennt, - für keine). Die Tabelle steht in topologischer Reihenfolge, aber das Programm darf sich nicht darauf verlassen. Es gibt den Plan aus (nur die nötigen nicht eingeordneten Technologien in topologischer Reihenfolge) und die Summe der Preise.

Mit der Eingabe warp | sensors | sensors 10 - | engines 12 sensors | shields 12 sensors | warp 20 engines,shields | beacon 25 warp (je eine pro Zeile) lautet die Ausgabe:

Ausgabe
Plan: engines, shields, warp
Preis: 44

Achtung: sensors ist bekannt, also steht sie nicht im Plan und wird nicht bezahlt; warp ist das Ziel und kommt im Plan zuletzt.

Weitere Aufgaben

  • Ein Zyklus in der Tabelle. Gib eine Tabelle, in der a b braucht und b a. Was macht planTo mit einem topoOrder, das null zurückgibt? Bring das Programm dazu, zu sagen, dass es einen Zyklus gibt, statt abzustürzen.
  • Eine unbekannte Voraussetzung. Füge eine Zeile mit einer Voraussetzung hinzu, die nicht in der Tabelle steht. Fange sie beim Laden, wie es loadData tut.
  • Was schaltet diese frei? Schreibe unlocks(techs, id), das die Technologien zurückgibt, die id als Voraussetzung brauchen. Das ist ein Gang vorwärts entlang der Pfeile.
  • Der billigste erste Zug. Wähle unter den freien Technologien die mit dem niedrigsten Preis. Was passiert, wenn zwei gleich viel kosten?

Test

Teste dich

1. Warum darf die Technologietabelle keinen Zyklus haben, zum Beispiel optics braucht lasers, lasers braucht radar, radar braucht optics?
2. fusion braucht lab2 und weapons1. Bekannt sind drill und weapons1. Kann fusion erforscht werden?
3. Im Programm topo steht die Tabelle verkehrt herum (stargate steht vorn). Warum gibt topoOrder trotzdem eine richtige Reihenfolge?
4. Warum kommt fortress nicht in den Plan bis stargate?
5. topoOrder hat null zurückgegeben. Was heißt das für die Tabelle?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·