Към съдържанието
wannacode

Дървото на технологиите

Накратко: Технологиите са възли, а предпоставките са стрелки към тях: ориентиран граф без цикли. Технология е свободна, когато всичките ѝ предпоставки са известни; топологичният ред подрежда всичко така, че всяка е след предпоставките си, а цикълът го прави невъзможен.

Проблем

Дванайсет технологии до Звездната врата

В Epic Cosmos победата по наука е технологията Звездна врата. Тя не се проучва от нулата: иска Дредноути и Търговски пътища, Дредноутите искат плазмени оръдия и наноброня, а те искат термоядрен синтез и още. Играчът си задава три въпроса:

  1. Какво мога да проучвам сега? Не всичко: технология е заключена, докато не са известни всичките ѝ предпоставки.
  2. В какъв ред да стигна до целта? И колко наука ще струва пътят.
  3. Може ли таблицата да е сгрешена? Ако две технологии се чакат взаимно, нищо не може да започне.

Ето екран tech от играта (от минаването, с което се проверява играта). + е известна, > се проучва сега, * може да се проучи, . е заключена; последният ред смята пътя до Звездната врата:

Ход 24/150  Земна империя (A)                           точки 93
M25+16 G173+30 C0+16 U47+3  наука +10
Проучава: Орбитални крепости 13/42
Технологии по ред (+ има, > сега, * може, . заключена)
+  1 drill    Дълбок добив            17  -
+  2 weapons1 Лазери                  21  -
+  3 hulls1   Леки брони              21  -
+  4 lab2     Квантови лаборатории    35  drill
*  5 fusion   Термоядрен синтез       49  lab2,weapons1
*  6 torpedo  Торпеда                 31  weapons1
*  7 cruiser  Крайцерски корпуси      31  hulls1
*  8 trade    Търговски пътища        35  drill
>  9 fortress Орбитални крепости      42  hulls1,drill
. 10 weapons2 Плазмени оръдия         71  fusion,torpedo
. 11 hulls2   Наноброня               71  fusion,cruiser
. 12 dread    Дредноути              107  weapons2,hulls2
. 13 stargate Звездна врата          249  dread,trade
До Звездната врата: 8 технологии, 644 наука, натрупана 13.
Колони: номер, име, цена, предпоставки.

Урокът строи тези три отговора с малки програми върху същата таблица, а накрая показва същото в играта. Че данните са таблица от текст, а не код, е показано в урока за съществата в Арканум; тук важното е какво е таблицата като структура.

Идеята

Таблица с предпоставки

Технологията е ред в таблица: номер, име, цена в точки наука и предпоставки, списък от други номера. Играта пази таблицата като текст и я чете при старт, затова нова технология е нов ред, не нов код. Ето същата таблица, както я зареждат програмите на урока (в играта има още колони: имената на другите езици, ефектът и стойността му):

# id|име|цена|предпоставки
drill|Дълбок добив|17|-
weapons1|Лазери|21|-
hulls1|Леки брони|21|-
lab2|Квантови лаборатории|35|drill
fusion|Термоядрен синтез|49|lab2,weapons1
torpedo|Торпеда|31|weapons1
cruiser|Крайцерски корпуси|31|hulls1
trade|Търговски пътища|35|drill
fortress|Орбитални крепости|42|hulls1,drill
weapons2|Плазмени оръдия|71|fusion,torpedo
hulls2|Наноброня|71|fusion,cruiser
dread|Дредноути|107|weapons2,hulls2
stargate|Звездна врата|249|dread,trade

Три от тринайсетте (drill, weapons1, hulls1) са без предпоставки (-), а stargate иска две. Редовете с # са бележка. Един ред става обект:

class Tech {
    final String id;
    final String name;
    final int cost;
    final List<String> prereqs;


    Tech(String id, String name, int cost, List<String> prereqs) {
        this.id = id;
        this.name = name;
        this.cost = cost;
        this.prereqs = prereqs;
    }
}


static Map<String, Tech> load(String text) {
    Map<String, Tech> techs = new LinkedHashMap<>();
    for (String line : text.split("\n")) {
        if (line.isBlank() || line.startsWith("#")) continue;
        String[] c = line.split("\\|");
        List<String> prereqs = c[3].equals("-") ? List.of() : List.of(c[3].split(","));
        techs.put(c[0], new Tech(c[0], c[1], Integer.parseInt(c[2]), prereqs));
    }
    return techs;
}

load минава през редовете, пропуска празните и бележките, реже на | и пази технологиите по реда на таблицата. Редът е важен: затова колекцията е подредена (LinkedHashMap в Java, Dictionary в C#, dict в Python, Map в JavaScript), за да печатат програмите на четирите езика едно и също.

Идеята

Граф без цикли

Нарисувай всяка технология като възел, а всяка предпоставка като стрелка от предпоставката към технологията: drill → lab2, lab2 → fusion. Таблицата става ориентиран граф: стрелките имат посока. В нашата са 13 възела и 16 стрелки.

Графът на технологиите има още едно свойство: няма цикъл. Ако тръгнеш по стрелките, никога не се връщаш там, откъдето си тръгнал. Такъв граф се казва ориентиран граф без цикли (на английски DAG, directed acyclic graph) и е точно формата на „първо това, после онова“: задачи със зависимости, модули на проект, дървото на уменията в RPG.

Цикълът е взаимно чакане. Нека оптиката иска лазери, лазерите искат радар, радарът иска оптика:

# id|име|цена|предпоставки
optics|Оптика|10|lasers
lasers|Лазери|10|radar
radar|Радар|10|optics

Никоя от трите не може да е първа: всяка чака друга. Играта не бива да стартира с такава таблица, затова проверява два пъти. Първо при зареждането: всяка предпоставка трябва да е технология, която съществува.

for (Tech tech : TECHS.values()) {
    for (String need : tech.prereqs) {
        if (!TECHS.containsKey(need)) throw new RuntimeException("techs: unknown prerequisite " + need);
    }
}

После в main, преди да започне играта: ако топологичният ред (следващите карти) не излиза, дървото има цикъл.

if (topoOrder() == null) throw new RuntimeException("the tech tree has a cycle");

Идеята

Какво може да се проучи сега

Играчът знае някои технологии. Технология е свободна, ако още не е известна и всичките ѝ предпоставки са известни. Кодът казва същото с един цикъл и ранно връщане:

static boolean knows(List<String> known, String techId) {
    return known.contains(techId);
}


static boolean canResearch(List<String> known, Tech tech) {
    if (knows(known, tech.id)) return false;
    for (String need : tech.prereqs) {
        if (!knows(known, need)) return false;
    }
    return true;
}


static List<Tech> availableTechs(Map<String, Tech> techs, List<String> known) {
    List<Tech> list = new ArrayList<>();
    for (Tech tech : techs.values()) {
        if (canResearch(known, tech)) list.add(tech);
    }
    return list;
}

canResearch връща false веднага щом види неизвестна предпоставка, а ако стигне до края на цикъла, true. Технология без предпоставки има празен цикъл, затова е свободна още в началото. availableTechs пита за всяка технология в таблицата. Програмата проучва drill, weapons1 и lab2 една по една и след всяка стъпка печата какво се отваря:

Map<String, Tech> techs = load(TABLE);
List<String> known = new ArrayList<>();
for (String learn : new String[] {"", "drill", "weapons1", "lab2"}) {
    if (!learn.isEmpty()) known.add(learn);
    System.out.println("Знаеш: " + show(known));
    System.out.println("Можеш да проучиш: " + show(idsOf(availableTechs(techs, known))));
}
Изход
Знаеш: -
Можеш да проучиш: drill, weapons1, hulls1
Знаеш: drill
Можеш да проучиш: weapons1, hulls1, lab2, trade
Знаеш: drill, weapons1
Можеш да проучиш: hulls1, lab2, torpedo, trade
Знаеш: drill, weapons1, lab2
Можеш да проучиш: hulls1, fusion, torpedo, trade

Забележи, че fusion се появява едва в края: иска и lab2, и weapons1. А drill изчезва от списъка веднага щом е известна, защото canResearch започва с проверката дали вече я знаеш.

static boolean canResearch(List<String> known, Tech tech) {
    if (knows(known, tech.id)) return false;
    for (String need : tech.prereqs) {
        if (!knows(known, need)) return ;
    }
    return true;
}

Ето същите функции от играта. Знанията са списъкът empire.techs, а не отделен аргумент, и всичко е същото:

// Технологиите са ориентиран граф без цикли: ребро от предпоставката към технологията. Знанията на
// империята са списък с номера; „какво може да се проучи сега“ са неизвестните, на които всички
// предпоставки вече са известни.
static boolean knows(Empire empire, String techId) {
    return empire.techs.indexOf(techId) >= 0;
}


static boolean canResearch(Empire empire, Tech tech) {
    if (knows(empire, tech.id)) return false;
    for (String need : tech.prereqs) {
        if (!knows(empire, need)) return false;
    }
    return true;
}


static List<Tech> availableTechs(Empire empire) {
    List<Tech> list = new ArrayList<>();
    for (Tech tech : TECHS.values()) {
        if (canResearch(empire, tech)) list.add(tech);
    }
    return list;
}
По-точно, за любопитните

Готовите функции там са на два нива: canResearch отговаря за една технология, availableTechs събира отговорите за всички. Така същият canResearch служи на startResearch (проучването може ли да започне) и на изкуствения интелект, който избира измежду свободните (урока за съперниците).

Идеята

Топологичен ред

Кой ред на проучване е допустим? Такъв, в който всяка технология е след предпоставките си. Наричат го топологичен ред и за всеки граф без цикли има поне един. Алгоритъмът е прост: докато има неподредени, вземи първата технология, на която всичките предпоставки вече са подредени, дай ѝ следващия номер и започни отначало.

static List<String> topoOrder(Map<String, Tech> techs) {
    List<String> placed = new ArrayList<>();
    Set<String> done = new HashSet<>();
    while (placed.size() < techs.size()) {
        Tech pick = null;
        for (Tech tech : techs.values()) {
            if (done.contains(tech.id)) continue;
            boolean ready = true;
            for (String need : tech.prereqs) {
                if (!done.contains(need)) ready = false;
            }
            if (ready) {
                pick = tech;
                break;
            }
        }
        if (pick == null) return null; // цикъл: няма готова технология
        placed.add(pick.id);
        done.add(pick.id);
    }
    return placed;
}

Ако на някоя стъпка няма такава технология, а още има неподредени, значи те се чакат взаимно: функцията връща null. Така същият алгоритъм е и проверка за цикъл.

Програмата подрежда таблицата наобратно (stargate е първа), за да се види, че редът не идва от нея, и после опитва таблицата с цикъл:

Map<String, Tech> techs = load(REVERSED); // таблицата е наобратно, но редът не зависи от нея
List<String> order = topoOrder(techs);
for (int i = 0; i < order.size(); i++) {
    System.out.println((i + 1) + " " + order.get(i));
}


if (topoOrder(load(CYCLE)) == null) System.out.println("Цикъл: няма технология, на която всички предпоставки да са готови.");
Изход
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
Цикъл: няма технология, на която всички предпоставки да са готови.

Първа излиза hulls1: всички отпред чакат нещо. После cruiser, защото hulls1 вече е подредена. Всяка стрелка в дървото сочи от по-малък номер към по-голям, а таблицата с цикъл връща null. При няколко готови печели първата в таблицата, затова редът е един и същ навсякъде. Такова е и правилото в играта:

// Топологичен ред (Kahn): технология излиза, когато всичките ѝ предпоставки вече са излезли. При
// няколко готови печели тази с по-малък номер в таблицата, затова редът е един и същ навсякъде.
static List<String> topoOrder() {
    List<String> placed = new ArrayList<>();
    List<String> done = new ArrayList<>();
    int total = TECHS.size();
    while (placed.size() < total) {
        Tech pick = null;
        for (Tech tech : TECHS.values()) {
            if (done.contains(tech.id)) continue;
            boolean ready = true;
            for (String need : tech.prereqs) {
                if (!done.contains(need)) ready = false;
            }
            if (ready) {
                pick = tech;
                break;
            }
        }
        // Цикъл: няма технология с готови предпоставки.
        if (pick == null) return null;
        placed.add(pick.id);
        done.add(pick.id);
    }
    return placed;
}

Идеята

План до целта

Играчът избира цел, например stargate, и иска списък: какво още трябва да се проучи и в какъв ред. Две стъпки.

  1. Какво е нужно. Тръгваме от целта и вървим назад по стрелките със стек: вадим технология, а ако не е известна, я записваме в need и слагаме предпоставките ѝ в стека. Известните се прескачат, така че вече проучената част не се плаща пак.
  2. В какъв ред. need е множество, без ред. Редът идва от топологичния: минаваме през topoOrder и оставяме само нужните.
static List<String> planTo(Map<String, Tech> techs, List<String> known, String targetId) {
    Set<String> need = new HashSet<>();
    List<String> stack = new ArrayList<>();
    stack.add(targetId);
    while (stack.size() > 0) {
        String id = stack.remove(stack.size() - 1);
        if (need.contains(id) || knows(known, id)) continue;
        need.add(id);
        for (String pre : techs.get(id).prereqs) stack.add(pre);
    }
    List<String> plan = new ArrayList<>();
    for (String id : topoOrder(techs)) {
        if (need.contains(id)) plan.add(id);
    }
    return plan;
}


static int planCost(Map<String, Tech> techs, List<String> plan) {
    int sum = 0;
    for (String id : plan) sum += techs.get(id).cost;
    return sum;
}

Програмата планира пътя до Звездната врата при празно знание и после при известни drill, weapons1, hulls1 и lab2:

Map<String, Tech> techs = load(TABLE);
List<List<String>> starts = List.of(List.of(), List.of("drill", "weapons1", "hulls1", "lab2"));
for (List<String> known : starts) {
    List<String> plan = planTo(techs, known, "stargate");
    System.out.println("Знаеш: " + show(known));
    System.out.println("План: " + show(plan));
    System.out.println(plan.size() + " технологии, " + planCost(techs, plan) + " наука");
}
Изход
Знаеш: -
План: drill, weapons1, hulls1, lab2, fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
12 технологии, 738 наука
Знаеш: drill, weapons1, hulls1, lab2
План: fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
8 технологии, 644 наука

Планът без знания е 12 технологии, а не 13: fortress никой по пътя не иска. Сборът 738 е това, което екранът в началото на урока показва като „до Звездната врата“, а с четири известни остават 8 технологии за 644. Така е и в канона:

// Всичко, което още трябва да се проучи, за да стигнем до целта, в топологичен ред.
static List<String> planTo(Empire empire, String targetId) {
    List<String> need = new ArrayList<>();
    List<String> stack = new ArrayList<>();
    stack.add(targetId);
    while (stack.size() > 0) {
        String id = stack.remove(stack.size() - 1);
        if (need.contains(id) || knows(empire, id)) continue;
        need.add(id);
        for (String pre : TECHS.get(id).prereqs) stack.add(pre);
    }
    List<String> plan = new ArrayList<>();
    for (String id : topoOrder()) {
        if (need.contains(id)) plan.add(id);
    }
    return plan;
}


static int planCost(List<String> plan) {
    int sum = 0;
    for (String id : plan) sum += TECHS.get(id).cost;
    return sum;
}

Виж го

Дървото в движение

Сцената минава през трите отговора: какво се отваря след всяка проучена технология, редът за таблицата наобратно и обхождането назад от Звездната врата. Следи цвета на рамките (зелено е свободна, синьо е известна, оранжево е нужна) и номерата на значките:

static List<String> planTo(Map<String, Tech> techs, List<String> known, String targetId) {
    Set<String> need = new HashSet<>();
    List<String> stack = new ArrayList<>();
    stack.add(targetId);
    while (stack.size() > 0) {
        String id = stack.remove(stack.size() - 1);
        if (need.contains(id) || knows(known, id)) continue;
        need.add(id);
        for (String pre : techs.get(id).prereqs) stack.add(pre);
    }
    List<String> plan = new ArrayList<>();
    for (String id : topoOrder(techs)) {
        if (need.contains(id)) plan.add(id);
    }
    return plan;
}
Стъпка по стъпка, с думи
  1. Тринайсет технологии. Стрелката отива от предпоставката към технологията: lab2 иска drill, fusion иска lab2 и weapons1. Числото под името е цената.
  2. Нищо не е проучено. drill, weapons1 и hulls1 нямат предпоставки: цикълът не намира неизвестна и canResearch връща true. Само те са свободни (зелени).
  3. Проучваш drill (синя). Сега lab2 и trade искат само drill и са свободни. fortress иска още hulls1, затова чака. drill вече не е в списъка: вече е известна.
  4. Проучваш weapons1: torpedo се отключва. fusion иска и lab2, и weapons1: weapons1 вече е известна, lab2 още не, затова цикълът връща false още на нея.
  5. Проучваш lab2: сега fusion има и двете предпоставки и е свободна. Една липсваща предпоставка държи технологията заключена, всичките готови я отварят.
  6. Друг въпрос: в какъв ред да проучим всичко? Таблицата е наобратно (stargate е първа), но редът не идва от нея. topoOrder минава по таблицата и взема първата технология, на която всичките предпоставки са подредени.
  7. stargate, dread и другите отпред чакат предпоставки. Първата готова е hulls1 (без предпоставки): получава номер 1.
  8. След всеки номер търсенето започва отначало: сега cruiser е готова, защото hulls1 вече е подредена. Подредените се прескачат.
  9. Последна е stargate, номер 13: чакаше dread и trade. Всяка стрелка сочи от по-малък номер към по-голям: това е топологичният ред. Ако на някой ход няма готова технология, значи има цикъл и функцията връща null.
  10. План до stargate. Тръгваме от целта и вървим назад по стрелките със стек: вадим технология, слагаме предпоставките ѝ. Всяка достигната влиза в need (оранжево).
  11. fortress не е достигната: никоя технология по пътя до stargate не я иска. Тя не влиза в плана. Известните се прескачат, затова проучената част не се плаща пак.
  12. Обхождането казва само какво е нужно. Редът идва от топологичния: planTo минава през topoOrder и оставя нужните. Така планът има 12 технологии в ред, в който всяка е след предпоставките си.
  13. 12 технологии, 738 наука: сборът от цените. fortress (42) не е нужна. Същото число показва играта на екрана tech, като „до Звездната врата“.

Графът е същият във всичките три части. Променя се само въпросът към него: какво е свободно (поглед напред от известните), в какъв ред (подреждане на всичко) и докъде (поглед назад от целта).

Пробвай

Предвиди изхода

Малка таблица: sensors няма предпоставки, engines и shields искат sensors, warp иска и двете, beacon иска warp. Известни са sensors и engines. Какво печата програмата?

static final String SMALL = """
# id|име|цена|предпоставки
sensors|Сензори|10|-
engines|Двигатели|12|sensors
shields|Щитове|12|sensors
warp|Варп|20|engines,shields
beacon|Маяк|25|warp
""";


Map<String, Tech> techs = load(SMALL);
List<String> known = List.of("sensors", "engines");
System.out.println(show(idsOf(availableTechs(techs, known))));
Отговор

Пробвай

Намери грешката

Колега копира canResearch и в проверката на предпоставките сложи не това име. Ето какво печата програмата за известна само drill; ако е вярна, тук трябва да са и lab2, и trade:

static boolean canResearch(List<String> known, Tech tech) {
    if (knows(known, tech.id)) return false;
    for (String need : tech.prereqs) {
        if (!knows(known, tech.id)) return false;
    }
    return true;
}


Map<String, Tech> techs = load(TABLE);
List<String> known = List.of("drill");
System.out.println("Знаеш: " + show(known));
System.out.println("Можеш да проучиш: " + show(idsOf(availableTechs(techs, known))));
Изход
Знаеш: drill
Можеш да проучиш: weapons1, hulls1

Кой ред е виновен?

Избери реда с грешката.

По-точно

Какво не е в тази система

Дървото в играта има малко правила и зад тях стоят избори.

Всички предпоставки, не „някоя от“. canResearch връща false при първата неизвестна. Някои игри позволяват „или това, или онова“: тогава предпоставката е група, а технологията се отваря, когато една от групите е изпълнена. Това е друг граф (с две вида стрелки), а не друга функция.

Редът за равенство е част от правилото. Много технологии могат да са готови едновременно и всяка подредба е вярна. Канонът взема първата в таблицата, за да излиза един и същ ред на всички езици и при всяко пускане. Ако редът зависи от реда на вмъкване в хеш таблица, програмите на два езика могат да се различават.

Топологичният алгоритъм тук е най-простият, не най-бързият. topoOrder отначало обхожда таблицата при всеки номер: за n технологии това са около n² проверки. За тринайсет е нищо. За хиляди (зависимости на пакети) се ползва алгоритъмът на Kahn с брояч на чакащите предпоставки на всяка технология и опашка с готовите: O(V + E). Това е урокът за топологично сортиране, а обхождането на графа с стек е в урока за DFS.

Ефектът на технологията е отделна работа. Тук технологията е само възел с цена. Какво дава (повече добив, нападение, нов кораб) е в други колони на таблицата, а techMods събира ефектите на всички известни; кой кораб какво иска, е в урока за флотите.

Цикълът се хваща при старт, не по време на игра. Таблицата е част от кода на играта, а не вход на играча. Затова проверката е едно извикване на topoOrder в main. Ако таблицата идваше от потребител (мод), същата проверка би била съобщение за грешка към него, не пад на играта.

Упражнение

План по зададена таблица

Реши задачата в редактора си.

План по зададена таблица. Програмата чете от входа три неща: на първия ред целта, на втория известните технологии, разделени със запетая (или -, ако няма), а на всеки следващ ред по една технология във вида id цена предпоставки (предпоставките са разделени със запетая, - е без). Таблицата е в топологичен ред, но програмата не трябва да разчита на това. Печата плана (само нужните неподредени технологии в топологичен ред) и сбора на цените.

С вход warp | sensors | sensors 10 - | engines 12 sensors | shields 12 sensors | warp 20 engines,shields | beacon 25 warp (по един на ред) изходът е:

Изход
План: engines, shields, warp
Цена: 44

Внимавай: sensors е известна, затова не е в плана и не се плаща; warp е целта и влиза в плана последна.

Още задачи

  • Цикъл в таблицата. Подай таблица, в която a иска b, а b иска a. Какво прави planTo с topoOrder, която връща null? Накарай програмата да каже, че има цикъл, вместо да пада.
  • Непозната предпоставка. Добави ред с предпоставка, която я няма в таблицата. Хвани я при зареждането, както го прави loadData.
  • Кои технологии отключва тази? Напиши unlocks(techs, id), която връща технологиите, които иска id като предпоставка. Това е обхождане на стрелките напред.
  • Най-евтиният начален ход. От свободните технологии избери тази с най-малка цена. Какво се случва, ако две струват колкото?

Тест

Провери се

1. Защо таблицата с технологии не бива да има цикъл, например optics иска lasers, lasers иска radar, radar иска optics?
2. fusion иска lab2 и weapons1. Известни са drill и weapons1. Може ли да се проучи fusion?
3. В програмата topo таблицата е наобратно (stargate е първа). Защо topoOrder пак дава правилен ред?
4. Защо fortress не влиза в плана до stargate?
5. topoOrder върна null. Какво значи това за таблицата?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·