Levels, dialogs and quests

In short: Experience is counted from a table, and new levels and skills are handed out one at a time; combat and the map only publish events to a bus, while quests subscribe and are state machines; a dialog is a tree in which conditions hide the answers that do not apply.

Problem

The wolf that does not know there is a quest

So far the hero has killed enemies and that was all. Now the game wants something more to happen: killing the wolf leader should close a quest, killing the Warden should give the victory, entering the second level should move another quest forward, and experience should raise the level. The simplest way is to write it down where the enemy dies:

void onEnemyKilled(Enemy enemy) {
    hero.xp += enemy.xp;
    // Combat knows every part of the game that cares when an enemy dies.
    quests.enemyKilled(enemy);
    achievements.enemyKilled(enemy);
    // A new listener: one more line here and one more change in combat.
    stats.kills++;
}

Here combat knows about quests, achievements and statistics. A new quest is a new line in combat, and combat already has many reasons to change. Worse: every new listener is added in someone else's code, and every forgotten link is a quest that never finishes.

The fix is to turn the direction of knowledge around. Combat says in one place "the enemy died" and does not care who listens. Whoever wants to know signs up (subscribes). That is an event bus. The lesson builds five things, in the order the game uses them: experience and levels (a curve as a table), a skill tree, an event bus, a quest as a state machine and a dialog as a tree with conditions.

This is the same place once there is a bus. Combat publishes one line and that is all:

void onEnemyKilled(Enemy enemy) {
    hero.xp += enemy.xp;
    bus.publish(new GameEvent("EnemyKilled", enemy.kind, 0));
}

The idea

Experience and levels: the curve is a table

How much experience does each level need? A formula (say 100 × level²) is smooth, but it is awkward for tuning a game: you want to say "level 3 comes after about six enemies", not to calculate. So the curve is a table: XP_TABLE[n] is the total experience at which level n is reached. Past the end of the table the curve continues with 150 more per level, so the game does not crash at level 11.

The hero has xp and level. On every kill xp grows, and pendingLevels says how many levels are waiting: how many of the next thresholds the experience has already reached. The new level is a separate step (raiseLevel): more life. The program kills seven enemies from the game, each with its own experience (rat 5, goblin 9, ... the Warden 150), and prints every new level:

class Hero {
    int level = 1;
    int xp = 0;
    int maxHp = 48;
}

record Kill(String name, int xp) {}

// XP_TABLE[n] is the total experience at which level n is reached.
static final int[] XP_TABLE = {0, 0, 20, 55, 105, 170, 250, 345, 455, 580, 720};

static int xpForLevel(int level) {
    if (level < XP_TABLE.length) return XP_TABLE[level];
    // Past the end of the table the curve goes on with 150 per level.
    return XP_TABLE[XP_TABLE.length - 1] + (level - XP_TABLE.length + 1) * 150;
}

// How many levels are waiting: does the experience reach the next thresholds.
static int pendingLevels(int xp, int level) {
    int levels = 0;
    while (xp >= xpForLevel(level + levels + 1)) levels++;
    return levels;
}

static void raiseLevel(Hero hero) {
    hero.level += 1;
    hero.maxHp += 9;
}

static final List<Kill> KILLS = List.of(new Kill("rat", 5), new Kill("goblin", 9), new Kill("shaman", 12), new Kill("wolf", 14), new Kill("cultist", 20), new Kill("golem", 32), new Kill("Warden", 150));

Hero hero = new Hero();
for (Kill kill : KILLS) {
    hero.xp += kill.xp();
    System.out.println(kill.name() + " +" + kill.xp() + ": xp " + hero.xp);
    int raise = pendingLevels(hero.xp, hero.level);
    for (int i = 0; i < raise; i++) {
        int before = hero.maxHp;
        raiseLevel(hero);
        System.out.println("  level " + hero.level + ": life " + before + " -> " + hero.maxHp);
    }
}
for (int level = 10; level <= 12; level++) {
    System.out.println("level " + level + ": xp " + xpForLevel(level));
}

Output

rat +5: xp 5
goblin +9: xp 14
shaman +12: xp 26
  level 2: life 48 -> 57
wolf +14: xp 40
cultist +20: xp 60
  level 3: life 57 -> 66
golem +32: xp 92
Warden +150: xp 242
  level 4: life 66 -> 75
  level 5: life 75 -> 84
level 10: xp 720
level 11: xp 870
level 12: xp 1020

The Warden (+150) gives two levels at once, 4 and 5. That is why pendingLevels is a loop and not a comparison: one big blow can jump over a threshold. The last three lines show the tail of the table: level 10 is in it (720), while 11 and 12 come from the + 150 per level (870, 1020).

// XP_TABLE[n] is the total experience at which level n is reached.
static final int[] XP_TABLE = {0, 0, 20, 55, 105, 170, 250, 345, 455, 580, 720};

static int xpForLevel(int level) {
    if (level < XP_TABLE.length) return XP_TABLE[level];
    // Past the end of the table the curve goes on with 150 per level.
    return XP_TABLE[XP_TABLE.length - 1] + (level - XP_TABLE.length + 1) * 150;
}

// How many levels are waiting: does the experience reach the next thresholds.
static int pendingLevels(int xp, int level) {
    int levels = 0;
    while (xp  xpForLevel(level + levels + 1)) levels++;
    return levels;
}

Check

More precisely, if you are curious

Why a table and not a formula? The table is data: a slower pace, a new level or another mode is another table, not other code. The canon keeps it as numbers separated by | (0|0|20|55|105|170|250|345|455|580|720) and reads it at start-up together with the items and the enemies. The first two zeros are for levels 0 and 1: the hero starts at level 1.

The curve is tuned with the simulation from the last lesson: thousands of games are run and you look at which level the hero reaches against which enemy.

The idea

The skill tree: two paths of three steps

At every new level the player chooses: a stat (+8 life, +1 strength, +1 agility, +1 defense) or a new skill. The skills of one class form a tree with two branches of three steps. The rule is short: a skill is available if it is not learned yet and is either step 1, or the step one lower in the same branch is learned.

record Skill(String id, int branch, int tier) {}

static final List<Skill> SKILLS = List.of(
    new Skill("rage", 1, 1),
    new Skill("whirlwind", 1, 2),
    new Skill("bloodlust", 1, 3),
    new Skill("war_cry", 2, 1),
    new Skill("iron_skin", 2, 2),
    new Skill("second_wind", 2, 3));
static final String[] ORDER = {"rage", "war_cry", "whirlwind", "iron_skin", "bloodlust", "second_wind"};

static List<String> learnable(List<Skill> skills, List<String> known) {
    List<String> result = new ArrayList<>();
    for (Skill skill : skills) {
        if (known.contains(skill.id())) continue;
        boolean ready = skill.tier() == 1;
        for (Skill other : skills) {
            if (known.contains(other.id()) && other.branch() == skill.branch() && other.tier() == skill.tier() - 1) ready = true;
        }
        if (ready) result.add(skill.id());
    }
    return result;
}

static String show(List<String> list) {
    return list.isEmpty() ? "-" : String.join(", ", list);
}

The program learns the barbarian's skills in a given order and after each one prints what is available. An empty list is -.

List<String> known = new ArrayList<>();
System.out.println("start -> " + show(learnable(SKILLS, known)));
for (String id : ORDER) {
    known.add(id);
    System.out.println(id + " -> " + show(learnable(SKILLS, known)));
}

Output

start -> rage, war_cry
rage -> whirlwind, war_cry
war_cry -> whirlwind, iron_skin
whirlwind -> bloodlust, iron_skin
iron_skin -> bloodlust, second_wind
bloodlust -> second_wind
second_wind -> -

At the start only the two starting skills are available: rage and war_cry. Learning rage opens whirlwind, but bloodlust still waits (it needs whirlwind), and the branch of war_cry does not change. At the end second_wind -> -: the tree is used up and only the stats are left in the level-up choice.

The idea

An event bus: whoever publishes does not know who listens

The bus is the simplest thing: a dictionary from an event type to a list of functions. subscribe(type, handler) puts a function in the list for that type. publish(event) calls all the functions in the list for the event's type. Nothing else.

An event is a small record: a type and some data. Here it is type, id (the enemy, the item or the dialog) and depth (the level). Examples are EnemyKilled (an enemy died), TileEntered (the hero entered a level), DialogChoice (an answer was chosen) and ItemPicked (an item was picked up).

record GameEvent(String type, String id, int depth) {
    String label() {
        return id.isEmpty() ? String.valueOf(depth) : id;
    }
}

class EventBus {
    private final Map<String, List<Consumer<GameEvent>>> handlers = new HashMap<>();

    void subscribe(String type, Consumer<GameEvent> handler) {
        handlers.computeIfAbsent(type, k -> new ArrayList<>()).add(handler);
    }

    void publish(GameEvent event) {
        if (!handlers.containsKey(event.type())) return;
        // A copy of the list: a listener may subscribe or unsubscribe while publishing.
        for (Consumer<GameEvent> handler : new ArrayList<>(handlers.get(event.type()))) handler.accept(event);
    }
}

The first program puts two listeners on EnemyKilled (a log and the kill counter) and one on TileEntered. Nobody listens to ItemPicked, and the bus simply does nothing.

EventBus bus = new EventBus();
Stats stats = new Stats();
bus.subscribe("EnemyKilled", e -> log(e));
bus.subscribe("TileEntered", e -> log(e));
bus.subscribe("EnemyKilled", e -> {
    stats.kills++;
    System.out.println("kills: " + stats.kills);
});

fire(bus, new GameEvent("EnemyKilled", "rat", 0));
fire(bus, new GameEvent("TileEntered", "", 2));
fire(bus, new GameEvent("EnemyKilled", "wolf", 0));
fire(bus, new GameEvent("ItemPicked", "ore", 0));

Output

> EnemyKilled rat
log: EnemyKilled rat
kills: 1
> TileEntered 2
log: TileEntered 2
> EnemyKilled wolf
log: EnemyKilled wolf
kills: 2
> ItemPicked ore

Every line with > is a publish, and the lines under it are the listeners that answered, in the order they subscribed. After EnemyKilled rat both answer, after TileEntered 2 only the log, and ItemPicked ore wakes nobody. The code that publishes did not change a line when the listeners appeared.

More precisely, if you are curious

This pattern is called Observer or publish/subscribe. In the UI world it is addEventListener, on servers it is message queues. The game uses the simplest form: everything in one thread, the listeners called at once, one after another. So a listener that does something heavy slows down the whole turn. The listeners are called in the order they subscribed, but you should not rely on that (in the canon no listener depends on another).

publish walks a copy of the list. A quest that starts another quest may subscribe to the same type during publishing; without the copy this throws an exception in Java and C#, and in JavaScript the new listener would be called in the same publish.

The idea

A quest is a state machine

A quest has a state: inactive (not given yet), active (with stage 1, 2, 3), done (completed) and rewarded (the reward is taken). The transitions are not made by the player but by events. So the quest subscribes by itself to the ones that move it and keeps all its logic in one place.

From	To	When
inactive	active, stage 1	the elder gives the quest (the start action of the dialog)
active, stage 1	stage 2	TileEntered with depth 2
active, stage below 3	stage 3	DialogChoice miner:warden
active	done	EnemyKilled warden
done	rewarded	the dialog runs the reward action

The base Quest is the common part: a title, a list of goals by stage and three methods that change the state and write to the player. MinersQuest ("The missing miners") is a subclass that only subscribes:

class Quest {
    final String id;
    final String title;
    final String[] goals;
    final String doneGoal;
    String state = "inactive";
    int stage = 0;

    Quest(String id, String title, String[] goals, String doneGoal) {
        this.id = id;
        this.title = title;
        this.goals = goals;
        this.doneGoal = doneGoal;
    }

    String goal() {
        if (state.equals("done")) return doneGoal;
        return goals[stage - 1];
    }

    void start() {
        state = "active";
        stage = 1;
        System.out.println("New quest: " + title + ".");
    }

    void advance(int newStage) {
        stage = newStage;
        System.out.println(title + ": " + goal());
    }

    void complete() {
        state = "done";
        System.out.println("Quest complete: " + title + "!");
    }
}

class MinersQuest extends Quest {
    MinersQuest() {
        super("miners", "The missing miners", new String[] {"Go down into the mine and look for the miners.", "Someone is alive on the second level. Find them.", "Defeat the Warden of the Depths on the third level."}, "The Warden is defeated. Greyford is saved.");
    }

    void subscribe(EventBus bus) {
        bus.subscribe("TileEntered", e -> {
            if (state.equals("active") && stage == 1 && e.depth() == 2) advance(2);
        });
        bus.subscribe("DialogChoice", e -> {
            if (state.equals("active") && stage < 3 && e.id().equals("miner:warden")) advance(3);
        });
        bus.subscribe("EnemyKilled", e -> {
            if (state.equals("active") && e.id().equals("warden")) complete();
        });
    }
}

Every listener starts with state == "active": the bus does not know the state of the quest, so the question is the quest's own. The second condition (stage == 1, stage < 3, id == ...) says which event exactly drives exactly this transition. The base deliberately has no subscribe; in the canon it exists as an empty method, so that the game can walk through all quests and call subscribe on each.

The scenario has eight steps, four of which the quest ignores. The elder gives the quest on the third step, and the steps are exactly the ones the scene below shows.

EventBus bus = new EventBus();
MinersQuest quest = new MinersQuest();
quest.subscribe(bus);

fire(bus, new GameEvent("EnemyKilled", "rat", 0));
fire(bus, new GameEvent("TileEntered", "", 2));
System.out.println("> the elder gives the quest");
quest.start();
fire(bus, new GameEvent("TileEntered", "", 1));
fire(bus, new GameEvent("TileEntered", "", 2));
fire(bus, new GameEvent("DialogChoice", "miner:warden", 0));
fire(bus, new GameEvent("TileEntered", "", 2));
fire(bus, new GameEvent("EnemyKilled", "warden", 0));

Output

> EnemyKilled rat
> TileEntered 2
> the elder gives the quest
New quest: The missing miners.
> TileEntered 1
> TileEntered 2
The missing miners: Someone is alive on the second level. Find them.
> DialogChoice miner:warden
The missing miners: Defeat the Warden of the Depths on the third level.
> TileEntered 2
> EnemyKilled warden
Quest complete: The missing miners!

See it

Events travel to the quest

At the top is the path of the quest with a ball that sits on its state. Every event is a tile: it rises to the bus, goes to the quest, and the quest either moves forward or twitches and says "ignored". You can see which four of the eight events move nothing, and why: the quest has not started yet, the level is different, and for one of them the stage has already been passed.

class EventBus {
    private final Map<String, List<Consumer<GameEvent>>> handlers = new HashMap<>();

    void subscribe(String type, Consumer<GameEvent> handler) {
        handlers.computeIfAbsent(type, k -> new ArrayList<>()).add(handler);
    }

    void publish(GameEvent event) {
        if (!handlers.containsKey(event.type())) return;
        // A copy of the list: a listener may subscribe or unsubscribe while publishing.
        for (Consumer<GameEvent> handler : new ArrayList<>(handlers.get(event.type()))) handler.accept(event);
    }
}

class Quest {
    final String id;
    final String title;
    final String[] goals;
    final String doneGoal;
    String state = "inactive";
    int stage = 0;

    Quest(String id, String title, String[] goals, String doneGoal) {
        this.id = id;
        this.title = title;
        this.goals = goals;
        this.doneGoal = doneGoal;
    }

    String goal() {
        if (state.equals("done")) return doneGoal;
        return goals[stage - 1];
    }

    void start() {
        state = "active";
        stage = 1;
        System.out.println("New quest: " + title + ".");
    }

    void advance(int newStage) {
        stage = newStage;
        System.out.println(title + ": " + goal());
    }

    void complete() {
        state = "done";
        System.out.println("Quest complete: " + title + "!");
    }
}

class MinersQuest extends Quest {
    MinersQuest() {
        super("miners", "The missing miners", new String[] {"Go down into the mine and look for the miners.", "Someone is alive on the second level. Find them.", "Defeat the Warden of the Depths on the third level."}, "The Warden is defeated. Greyford is saved.");
    }

    void subscribe(EventBus bus) {
        bus.subscribe("TileEntered", e -> {
            if (state.equals("active") && stage == 1 && e.depth() == 2) advance(2);
        });
        bus.subscribe("DialogChoice", e -> {
            if (state.equals("active") && stage < 3 && e.id().equals("miner:warden")) advance(3);
        });
        bus.subscribe("EnemyKilled", e -> {
            if (state.equals("active") && e.id().equals("warden")) complete();
        });
    }
}

Step by step, in words

1. The game publishes events to the bus, and the bus calls everyone subscribed to that type. At the top is the quest “The missing miners”: it has not started yet. The ball sits on “inactive”.
2. A rat dies (EnemyKilled rat). The quest is subscribed to EnemyKilled, the bus calls it, but the listener asks: is the quest active, and is the enemy the Warden? No: nothing happens. Combat does not know anyone is listening.
3. The hero goes down to the second level (TileEntered 2). The depth is right, but the quest is still inactive (state is not "active"), so again nothing. Events arrive when the game says, not when the quest is ready.
4. The elder gives the quest: start() makes it active, stage 1. The ball moves to “stage 1”. This is not an event from the bus but an action of the dialog.
5. The hero enters level 1 (TileEntered 1). The quest is active and on stage 1, but it wants level 2: depth is 1, so the condition fails. A new event of the same type is not progress.
6. Second level (TileEntered 2): active, stage 1 and depth 2. The listener calls advance(2): the ball moves to “stage 2” and the game writes “The missing miners: Someone is alive on the second level. Find them.”.
7. The hero talks to the miner and picks “What is down there?”: the dialog publishes DialogChoice miner:warden. The quest is on stage 2 (below 3) and the id matches: advance(3). The ball is on “stage 3”.
8. The hero goes to level 2 again (TileEntered 2). depth == 2 is true, but the stage is already 3, not 1: the stage == 1 check stops the event. Without it the quest would slip back to stage 2.
9. The Warden dies (EnemyKilled warden). The quest is active and the id is "warden": complete(). The ball is on “done”. Combat only said “the enemy died”; who listens is none of its business.

The code next to the scene is the bus, the quest base and the MinersQuest subclass from the program. At every step the lines that are working at that moment light up.

The scene shows only the quest "The missing miners". Experience and the dialog are in the programs above and below, not in the scene.

The idea

A dialog is a tree with conditions

A conversation is a tree: a node (node) has a line and several answers (option), and every answer leads to a next node (or to end, which closes it). If that is all, the dialog is the same for every player. But Vela should not offer the silver quest if it is already taken, and should not take ore the hero does not have. So an answer has a condition and actions:

• condition (condition): flag:name, item:item:count, quest:quest:state, with a ! in front for negation. Several conditions are separated by commas and all must hold (a logical "and"). - means "always".
• actions (actions): flag, start, complete, reward, give, take. They run in order when the answer is chosen.

Conditions and actions are short text in the form kind:argument:argument, because dialogs are data: they can live in a file, not in the code. visibleOptions shows only the answers whose condition is true, and choose runs the actions of the chosen one.

record Option(String text, String next, String condition, String actions) {}

record Node(String text, List<Option> options) {}

class Game {
    static final Map<String, String> NAMES = Map.of("ore", "ore", "silver_sword", "silver sword", "potion_heal", "healing potion");

    final Set<String> flags = new HashSet<>();
    final Map<String, Integer> items = new HashMap<>();
    final Map<String, Quest> quests = new HashMap<>();

    Game(Quest... list) {
        for (Quest quest : list) quests.put(quest.id, quest);
    }

    Quest quest(String id) {
        return quests.get(id);
    }

    int count(String id) {
        return items.getOrDefault(id, 0);
    }

    String label(String id, int n) {
        return NAMES.get(id) + " x" + n;
    }

    void give(String id, int n) {
        items.merge(id, n, Integer::sum);
        System.out.println("You receive: " + label(id, n) + ".");
    }

    void take(String id, int n) {
        items.merge(id, -n, Integer::sum);
        System.out.println("You hand over: " + label(id, n) + ".");
    }
}

static String[] splitList(String text) {
    return text.equals("-") ? new String[0] : text.split(",");
}

static boolean checkCondition(Game game, String condition) {
    for (String part : splitList(condition)) {
        boolean negate = part.startsWith("!");
        String[] p = (negate ? part.substring(1) : part).split(":");
        boolean ok;
        if (p[0].equals("flag")) ok = game.flags.contains(p[1]);
        else if (p[0].equals("item")) ok = game.count(p[1]) >= Integer.parseInt(p[2]);
        else if (p[0].equals("quest")) ok = game.quest(p[1]).state.equals(p[2]);
        else throw new IllegalArgumentException("unknown condition: " + part);
        if (negate) ok = !ok;
        if (!ok) return false;
    }
    return true;
}

static void runActions(Game game, String actions) {
    for (String part : splitList(actions)) {
        String[] p = part.split(":");
        if (p[0].equals("flag")) {
            game.flags.add(p[1]);
        } else if (p[0].equals("start")) {
            game.quest(p[1]).start();
        } else if (p[0].equals("complete")) {
            game.quest(p[1]).complete();
        } else if (p[0].equals("reward")) {
            Quest quest = game.quest(p[1]);
            quest.state = "rewarded";
            System.out.println("Reward for " + quest.title + ".");
        } else if (p[0].equals("give")) {
            game.give(p[1], Integer.parseInt(p[2]));
        } else if (p[0].equals("take")) {
            game.take(p[1], Integer.parseInt(p[2]));
        } else {
            throw new IllegalArgumentException("unknown action: " + part);
        }
    }
}

static List<Option> visibleOptions(Game game, Node node) {
    List<Option> result = new ArrayList<>();
    for (Option option : node.options()) {
        if (option.condition().equals("-") || checkCondition(game, option.condition())) result.add(option);
    }
    return result;
}

static void show(String speaker, Game game, Node node) {
    System.out.println(speaker + ": " + node.text());
    List<Option> options = visibleOptions(game, node);
    for (int i = 0; i < options.size(); i++) System.out.println("  " + (i + 1) + ") " + options.get(i).text());
}

static String choose(Game game, Node node, int number) {
    Option option = visibleOptions(game, node).get(number - 1);
    System.out.println("> " + number);
    runActions(game, option.actions());
    return option.next();
}

The data are the two dialogs from the game: Vela the smith (items and a quest) and Dobri the miner (a one-time gift with a flag).

static final Map<String, Node> SMITH = Map.of(
    "start", new Node("My forge is cold without silver. Bring me three pieces of ore and I will forge you a sword.", List.of(
        new Option("I will look for ore.", "deal", "quest:silver:inactive", "start:silver"),
        new Option("Here is the ore.", "done", "quest:silver:active,item:ore:3", "take:ore:3,complete:silver,reward:silver,give:silver_sword:1"),
        new Option("Goodbye.", "end", "-", "-"))),
    "deal", new Node("The ore is on the second level. The ore golems carry it inside them.", List.of(
        new Option("Fine.", "end", "-", "-"))),
    "done", new Node("A silver sword. Its edge never dulls.", List.of(
        new Option("Thank you.", "end", "-", "-"))));

static final Map<String, Node> MINER = Map.of(
    "start", new Node("A living soul! The others ran up... I was trapped down here.", List.of(
        new Option("What is down there?", "warden", "quest:miners:active,!flag:miner_told", "flag:miner_told,give:potion_heal:1"),
        new Option("Stay here, I will come back.", "end", "-", "-"))),
    "warden", new Node("The Warden of the Depths. A stone guardian woken by our picks. When it cracks, it calls the dead to help. Take my potion.", List.of(
        new Option("I will stop it.", "end", "-", "-"))));

Game game = new Game(new Quest("silver", "Silver for the smith", new String[] {"Collect three pieces of silver ore.", "Bring the ore to Vela the smith."}, "The smith has her silver."), new Quest("miners", "The missing miners", new String[] {"Go down into the mine and look for the miners.", "Someone is alive on the second level. Find them.", "Defeat the Warden of the Depths on the third level."}, "The Warden is defeated. Greyford is saved."));
Node start = SMITH.get("start");
show("Vela", game, start);
String next = choose(game, start, 1);
show("Vela", game, SMITH.get(next));
game.give("ore", 3);
show("Vela", game, start);
next = choose(game, start, 1);
show("Vela", game, SMITH.get(next));
game.quest("miners").start();
Node minerStart = MINER.get("start");
show("Dobri", game, minerStart);
next = choose(game, minerStart, 1);
show("Dobri", game, MINER.get(next));
show("Dobri", game, minerStart);

Output

Vela: My forge is cold without silver. Bring me three pieces of ore and I will forge you a sword.
  1) I will look for ore.
  2) Goodbye.
> 1
New quest: Silver for the smith.
Vela: The ore is on the second level. The ore golems carry it inside them.
  1) Fine.
You receive: ore x3.
Vela: My forge is cold without silver. Bring me three pieces of ore and I will forge you a sword.
  1) Here is the ore.
  2) Goodbye.
> 1
You hand over: ore x3.
Quest complete: Silver for the smith!
Reward for Silver for the smith.
You receive: silver sword x1.
Vela: A silver sword. Its edge never dulls.
  1) Thank you.
New quest: The missing miners.
Dobri: A living soul! The others ran up... I was trapped down here.
  1) What is down there?
  2) Stay here, I will come back.
> 1
You receive: healing potion x1.
Dobri: The Warden of the Depths. A stone guardian woken by our picks. When it cracks, it calls the dead to help. Take my potion.
  1) I will stop it.
Dobri: A living soul! The others ran up... I was trapped down here.
  1) Stay here, I will come back.

Watch how Vela's answers change for the same node start: on the first visit there are two (deal and "Goodbye"), because done needs the quest and ore. After the hero brings three ore she no longer offers deal (the quest is active) but offers done. The actions of done take the ore, close the quest, give the reward and the silver sword. With Dobri the answer "What is down there?" disappears as soon as the flag miner_told is set: the gift is one-time.

The idea

In the game: experience, skills and the bus

Here are the real excerpts from the canon. First, the levels and the tree (xp-levelup). Besides our xpForLevel and pendingLevels there is learnableSkills (only the skills of the hero's class, from the hero's list), levelUpChoices (four stats and the available skills) and applyLevelChoice:

// The level curve is a table: XP_TABLE[n] is the XP that reaches level n.
static int xpForLevel(int level) {
    if (level < XP_TABLE.size()) return XP_TABLE.get(level);
    return XP_TABLE.get(XP_TABLE.size() - 1) + (level - XP_TABLE.size() + 1) * 150;
}

static int pendingLevels(Hero hero) {
    int levels = 0;
    while (hero.xp >= xpForLevel(hero.level + levels + 1)) levels++;
    return levels;
}

// The new level by itself: more life and mana, full health.
static void raiseLevel(Hero hero) {
    HeroClass heroClass = hero.heroClass();
    hero.level += 1;
    hero.base.put("maxHp", hero.base.get("maxHp") + heroClass.hpPerLevel);
    hero.base.put("maxMana", hero.base.get("maxMana") + heroClass.manaPerLevel);
    hero.hp = hero.maxHp();
    hero.mana = hero.maxMana();
}

// The skill tree: two branches of three steps. A step can be learned if the one before it is learned.
static List<String> learnableSkills(Hero hero) {
    List<String> result = new ArrayList<>();
    for (Skill skill : SKILLS.values()) {
        if (!skill.classId.equals(hero.classId) || hero.skills.indexOf(skill.id) >= 0) continue;
        boolean ready = skill.tier == 1;
        for (String known : hero.skills) {
            Skill other = SKILLS.get(known);
            if (other.branch == skill.branch && other.tier == skill.tier - 1) ready = true;
        }
        if (ready) result.add(skill.id);
    }
    return result;
}

// The choice at a new level: a stat (stat and amount) or a skill (stat is the skill's id).
static class LevelChoice {
    String kind;
    String stat;
    int amount;

    LevelChoice(String kind, String stat, int amount) {
        this.kind = kind;
        this.stat = stat;
        this.amount = amount;
    }
}

// The choices at a new level: a stat or a new skill.
static List<LevelChoice> levelUpChoices(Hero hero) {
    List<LevelChoice> choices = new ArrayList<>(List.of(
        new LevelChoice("stat", "maxHp", 8),
        new LevelChoice("stat", "strength", 1),
        new LevelChoice("stat", "agility", 1),
        new LevelChoice("stat", "defense", 1)
    ));
    for (String skillId : learnableSkills(hero)) choices.add(new LevelChoice("skill", skillId, 0));
    return choices;
}

static void applyLevelChoice(Hero hero, LevelChoice choice) {
    if (choice.kind.equals("skill")) {
        hero.skills.add(choice.stat);
    } else {
        hero.base.put(choice.stat, hero.base.get(choice.stat) + choice.amount);
        if (choice.stat.equals("maxHp")) hero.hp = hero.maxHp();
    }
}

The differences from our program are few:

• raiseLevel in the game adds mana too and restores full health; we only touch maximum life.
• The level is not given in gainXp. enemyKilled (besides the gold and the corpse) raises hero.xp and publishes an event, and queueLevelUps puts a LevelUpScreen on the stack (the lesson about screens): the player chooses a stat or a skill and only then do raiseLevel and applyLevelChoice change the hero. There is one screen per level, not one dialog for all of them.
• The stats change in base (the lesson about entities), not in the hero itself.

And the bus is the same as ours:

// The event bus: the publisher does not know who listens. Quests subscribe and track their own
// progress, and the combat system only says "the enemy died".
static class GameEvent {
    String type;
    int depth = 0;
    int x = 0;
    int y = 0;
    char decor = ' ';
    String marker = "";
    String itemId = "";
    int count = 0;
    String kindId = "";
    String dialogId = "";
    String nodeId = "";

    GameEvent(String type) {
        this.type = type;
    }

    static GameEvent tileEntered(int depth, int x, int y, char decor, String marker) {
        GameEvent event = new GameEvent("TileEntered");
        event.depth = depth;
        event.x = x;
        event.y = y;
        event.decor = decor;
        event.marker = marker;
        return event;
    }

    static GameEvent itemPicked(String itemId, int count) {
        GameEvent event = new GameEvent("ItemPicked");
        event.itemId = itemId;
        event.count = count;
        return event;
    }

    static GameEvent enemyKilled(String kindId) {
        GameEvent event = new GameEvent("EnemyKilled");
        event.kindId = kindId;
        return event;
    }

    static GameEvent dialogChoice(String dialogId, String nodeId) {
        GameEvent event = new GameEvent("DialogChoice");
        event.dialogId = dialogId;
        event.nodeId = nodeId;
        return event;
    }
}

static class EventBus {
    Map<String, List<Consumer<GameEvent>>> handlers = new LinkedHashMap<>();

    void subscribe(String type, Consumer<GameEvent> handler) {
        if (!this.handlers.containsKey(type)) this.handlers.put(type, new ArrayList<>());
        this.handlers.get(type).add(handler);
    }

    void publish(GameEvent event) {
        if (!this.handlers.containsKey(event.type)) return;
        for (Consumer<GameEvent> handler : new ArrayList<>(this.handlers.get(event.type))) handler.accept(event);
    }
}

The events in the game are free-form objects ({ type: 'EnemyKilled', kindId: … }), with different fields for each type: kindId, itemId, dialogId with nodeId, depth, decor, marker. In Java, C# and Python each shape is a separate record. We tied everything to type, id and depth, so that one type fits all four languages.

The idea

In the game: quests and dialogs

Here are the real quests. The base Quest uses keys to the texts (t('quest.' + id + '.title')) so that the game can be translated; MissingMinersQuest is ours, and the other two show what else a state machine can do:

// A quest is a small state machine: inactive → active (stages) → done → rewarded. It subscribes
// by itself to the events that move it forward.
static class Quest {
    String id;
    String state;
    int stage;

    Quest(String id) {
        this.id = id;
        this.state = "inactive";
        this.stage = 0;
    }

    String title() {
        return t("quest." + this.id + ".title");
    }

    String goal() {
        if (this.state.equals("done")) return t("quest." + this.id + ".done");
        if (this.state.equals("rewarded")) return t("quest.rewarded");
        return t("quest." + this.id + ".stage" + this.stage);
    }

    void start(Game game) {
        this.state = "active";
        this.stage = 1;
        game.say(t("quest.started", "title", this.title()));
    }

    void advance(Game game, int stage) {
        this.stage = stage;
        game.say(t("quest.updated", "title", this.title(), "goal", this.goal()));
    }

    void complete(Game game) {
        this.state = "done";
        game.say(t("quest.completed", "title", this.title()));
    }

    void subscribe(EventBus bus, Game game) {}
}

static class MissingMinersQuest extends Quest {
    MissingMinersQuest() {
        super("miners");
    }

    @Override
    void subscribe(EventBus bus, Game game) {
        bus.subscribe("TileEntered", (event) -> {
            if (this.state.equals("active") && this.stage == 1 && event.depth == 2) this.advance(game, 2);
        });
        bus.subscribe("DialogChoice", (event) -> {
            if (this.state.equals("active") && this.stage < 3 && event.dialogId.equals("miner") && event.nodeId.equals("warden")) this.advance(game, 3);
        });
        bus.subscribe("EnemyKilled", (event) -> {
            if (this.state.equals("active") && event.kindId.equals("warden")) this.complete(game);
        });
    }
}

static class BloodTrailQuest extends Quest {
    BloodTrailQuest() {
        super("blood");
    }

    @Override
    void start(Game game) {
        super.start(game);
        if (game.hasFlag("leader_dead")) this.complete(game);
    }

    @Override
    void subscribe(EventBus bus, Game game) {
        bus.subscribe("TileEntered", (event) -> {
            if (!this.state.equals("active") || event.depth != 1) return;
            if (this.stage == 1 && event.decor == ',') this.advance(game, 2);
            if (this.stage < 3 && event.marker.equals("lair")) this.advance(game, 3);
        });
        bus.subscribe("EnemyKilled", (event) -> {
            if (!event.kindId.equals("wolf_leader")) return;
            game.setFlag("leader_dead");
            if (this.state.equals("active")) this.complete(game);
        });
    }
}

static class SilverQuest extends Quest {
    SilverQuest() {
        super("silver");
    }

    @Override
    void start(Game game) {
        super.start(game);
        this.check(game);
    }

    void check(Game game) {
        if (this.state.equals("active") && this.stage == 1 && game.hero.inventory.count("ore") >= 3) this.advance(game, 2);
    }

    @Override
    void subscribe(EventBus bus, Game game) {
        bus.subscribe("ItemPicked", (event) -> {
            if (event.itemId.equals("ore")) this.check(game);
        });
    }
}

static List<Quest> createQuests() {
    return new ArrayList<>(List.of(new MissingMinersQuest(), new BloodTrailQuest(), new SilverQuest()));
}

• A quest that starts after its condition. BloodTrailQuest.start and SilverQuest.start check at once whether the condition is already true: the wolf leader may already be dead, or the ore already in the backpack, before the quest is taken. That way the quest does not stay on stage 1 forever. Our MinersQuest does not do this, because the Warden does not die before the talk with the elder.
• Stages with more than one source. BloodTrailQuest listens to TileEntered in two ways: for a blood trail (decor) and for the den (marker). The events do not have to be coordinated: the listener asks about its own state and answers.
• Reaching the victory. The Warden is not only EnemyKilled: the game sets victory in enemyKilled, and the quest moves on the same event. The quest "The missing miners" has no reward: the victory shows the victory screen.

The dialog in the canon is what we built, and a little more: the actions include gold and xp (the hunter's reward), and the conditions include gold: (enough gold):

// A dialog is a tree with conditions: choices whose conditions are not met are not shown.
static boolean checkCondition(Game game, String condition) {
    for (String part : splitList(condition)) {
        boolean negate = part.charAt(0) == '!';
        List<String> pieces = split(negate ? part.substring(1) : part, ":");
        boolean ok = false;
        if (pieces.get(0).equals("flag")) ok = game.hasFlag(pieces.get(1));
        else if (pieces.get(0).equals("item")) ok = game.hero.inventory.count(pieces.get(1)) >= toInt(pieces.get(2));
        else if (pieces.get(0).equals("gold")) ok = game.hero.gold >= toInt(pieces.get(1));
        else if (pieces.get(0).equals("quest")) ok = game.quest(pieces.get(1)).state.equals(pieces.get(2));
        else throw new RuntimeException("unknown condition: " + part);
        if (negate) ok = !ok;
        if (!ok) return false;
    }
    return true;
}

static void runActions(Game game, String actions) {
    for (String part : splitList(actions)) {
        List<String> pieces = split(part, ":");
        if (pieces.get(0).equals("flag")) {
            game.setFlag(pieces.get(1));
        } else if (pieces.get(0).equals("start")) {
            game.quest(pieces.get(1)).start(game);
        } else if (pieces.get(0).equals("complete")) {
            game.quest(pieces.get(1)).complete(game);
        } else if (pieces.get(0).equals("reward")) {
            game.quest(pieces.get(1)).state = "rewarded";
            game.say(t("quest.rewardedSay", "title", game.quest(pieces.get(1)).title()));
        } else if (pieces.get(0).equals("give")) {
            game.giveItem(pieces.get(1), toInt(pieces.get(2)));
        } else if (pieces.get(0).equals("take")) {
            game.hero.inventory.remove(pieces.get(1), toInt(pieces.get(2)));
            game.say(t("item.given", "item", itemLabel(pieces.get(1), toInt(pieces.get(2)))));
        } else if (pieces.get(0).equals("gold")) {
            game.hero.gold += toInt(pieces.get(1));
            game.say(t("item.gold", "amount", pieces.get(1)));
        } else if (pieces.get(0).equals("xp")) {
            game.gainXp(toInt(pieces.get(1)));
        } else {
            throw new RuntimeException("unknown action: " + part);
        }
    }
}

static List<DialogOption> visibleOptions(Game game, DialogNode node) {
    List<DialogOption> result = new ArrayList<>();
    for (DialogOption option : node.options) {
        if (option.condition.equals("-") || checkCondition(game, option.condition)) result.add(option);
    }
    return result;
}

DialogScreen (the screen on the stack) calls visibleOptions, and when the player picks an answer it runs runActions and publishes DialogChoice with the next node. So the dialog and the quest do not know each other: the talk with the miner moves the quest only because the dialog published and the quest listened.

Try it

Predict the output

Three calculations of pendingLevels with the table from the lesson. What does the program print?

// XP_TABLE[n] is the total experience at which level n is reached.
static final int[] XP_TABLE = {0, 0, 20, 55, 105, 170, 250, 345, 455, 580, 720};

static int xpForLevel(int level) {
    if (level < XP_TABLE.length) return XP_TABLE[level];
    // Past the end of the table the curve goes on with 150 per level.
    return XP_TABLE[XP_TABLE.length - 1] + (level - XP_TABLE.length + 1) * 150;
}

// How many levels are waiting: does the experience reach the next thresholds.
static int pendingLevels(int xp, int level) {
    int levels = 0;
    while (xp >= xpForLevel(level + levels + 1)) levels++;
    return levels;
}

System.out.println(pendingLevels(130, 1));
System.out.println(pendingLevels(104, 3));
System.out.println(pendingLevels(55, 1));

Answer

4
1
3

3
0
1

3
0
2

Check

Try it

Find the bug

A colleague removed one check in MinersQuest and now the quest goes backwards. The hero has already talked to the miner (stage 3) and goes down to the second level again:

EventBus bus = new EventBus();
MinersQuest quest = new MinersQuest();
quest.subscribe(bus);

fire(bus, new GameEvent("EnemyKilled", "rat", 0));
fire(bus, new GameEvent("TileEntered", "", 2));
System.out.println("> the elder gives the quest");
quest.start();
fire(bus, new GameEvent("TileEntered", "", 1));
fire(bus, new GameEvent("TileEntered", "", 2));
fire(bus, new GameEvent("DialogChoice", "miner:warden", 0));
fire(bus, new GameEvent("TileEntered", "", 2));
fire(bus, new GameEvent("EnemyKilled", "warden", 0));

Output

> EnemyKilled rat
> TileEntered 2
> the elder gives the quest
New quest: The missing miners.
> TileEntered 1
> TileEntered 2
The missing miners: Someone is alive on the second level. Find them.
> DialogChoice miner:warden
The missing miners: Defeat the Warden of the Depths on the third level.
> TileEntered 2
The missing miners: Someone is alive on the second level. Find them.
> EnemyKilled warden
Quest complete: The missing miners!

At the end of the output, after the third TileEntered 2 (the hero has already talked to the miner), the goal is again "Someone is alive on the second level", although the hero already knows about the Warden. Which line causes this?

Pick the line with the bug.

1class MinersQuest extends Quest {2 MinersQuest() {3 super("miners", "The missing miners", new String[] {"Go down into the mine and look for the miners.", "Someone is alive on the second level. Find them.", "Defeat the Warden of the Depths on the third level."}, "The Warden is defeated. Greyford is saved.");4 }56 void subscribe(EventBus bus) {7 bus.subscribe("TileEntered", e -> {8 if (state.equals("active") && e.depth() == 2) advance(2);9 });10 bus.subscribe("DialogChoice", e -> {11 if (state.equals("active") && stage < 3 && e.id().equals("miner:warden")) advance(3);12 });13 bus.subscribe("EnemyKilled", e -> {14 if (state.equals("active") && e.id().equals("warden")) complete();15 });16 }17}

Check

More precisely

More precisely: listener order, exceptions and determinism

Synchronous. publish returns when all the listeners have finished. Everything is in one thread, so a listener that publishes a new event fires it inside the first one (nested publishing). If quest A listens to EnemyKilled and publishes QuestDone, and quest B listens to QuestDone, B is called before the first publish ends. Limit the depth: an endless loop of events is the hardest bug of buses.

Listener order. The order of subscription is deliberately predictable (a list, not a set): the game must give the same result for the same seed in all four languages. But if listeners depend on the order, the design is wrong: two listeners that need each other should be one.

An exception in a listener. Here it interrupts publish, and the listeners after it are not called. In a single-player game that is acceptable (better to see the error); in a server you wrap it in try.

Unsubscribing. Our bus has no unsubscribe. A quest that is done stays subscribed and asks state == "active" every time; that is cheap. Where listeners are many or short-lived (elements on a screen), without unsubscribing "dangling" listeners and memory that is never returned are left behind.

The machine grows. Five states with two transitions each are ten if lines. When a quest branches (choose a side, fail after a time, check three goals in any order), the state is no longer a single value. Then every goal is its own small machine, and the quest is "done" when all of them are. The canon deliberately stops before that.

A dialog as data. Our format is a string kind:arg:arg. An advantage: the dialog can be in a file and changed without new code. A cost: a mistake in a name (quets:silver:active) is caught only at run time (unknown condition), not at compile time. That is why checkCondition and runActions throw for an unknown kind instead of quietly skipping it.

Exercise

Three wolves

Solve the task in your editor. Start from the program for the quest.

The quest "Three wolves". Write WolfQuest (a subclass of Quest) with one goal, "Kill three wolves": the quest counts the wolves killed and moves to done at the third. It listens only to EnemyKilled; it counts only wolves (id is "wolf") and only while it is active. For every wolf killed that is not the last, it writes the goal with the counter, for example "Kill three wolves (1/3)" (override goal()), by calling advance(1). At the third it calls complete(). Events before start() and after done do not count.

The base Quest, EventBus and fire are the same as in the program for the quest. Here is the scenario:

EventBus bus = new EventBus();
WolfQuest quest = new WolfQuest();
quest.subscribe(bus);

fire(bus, new GameEvent("EnemyKilled", "wolf", 0));
System.out.println("> start");
quest.start();
fire(bus, new GameEvent("EnemyKilled", "rat", 0));
fire(bus, new GameEvent("EnemyKilled", "wolf", 0));
fire(bus, new GameEvent("EnemyKilled", "wolf", 0));
fire(bus, new GameEvent("EnemyKilled", "wolf", 0));
fire(bus, new GameEvent("EnemyKilled", "wolf", 0));

The output is:

Output

> EnemyKilled wolf
> start
New quest: Three wolves.
> EnemyKilled rat
> EnemyKilled wolf
Three wolves: Kill three wolves (1/3)
> EnemyKilled wolf
Three wolves: Kill three wolves (2/3)
> EnemyKilled wolf
Quest complete: Three wolves!
> EnemyKilled wolf

More tasks

• Reward. Add a method reward() to Quest that goes from done to rewarded and writes the reward. Then make an answer in the hunter's dialog with the condition quest:wolves:done and the action reward:wolves.
• Two quests at once. Subscribe both MinersQuest and WolfQuest to the same bus and write a scenario in which one EnemyKilled moves both. Why is one publish enough?
• Unsubscribing. Add unsubscribe(type, handler) to the bus. What do you have to do in publish so that a listener can unsubscribe during publishing?
• The skill tree. Add a third class with two branches in which the second step needs two learned steps (one from each branch). What does this change in learnable?

Test

Check yourself

1. The hero is on level 3 with 92 xp. They kill the Warden (+150) and the xp becomes 242. The threshold for level 4 is 105, for level 5 it is 170, for level 6 it is 250. How many levels are waiting, and how does the player get them?

One: the level is the highest one the xp reaches, but it is given only once per killTwo (4 and 5): 242 reaches 105 and 170 but not 250. The levels are handed out one at a time, each with its own choiceThree: 242 is more than 105 + 170

2. A barbarian has learned "Rage" (rage, branch 1, step 1) and "War cry" (war_cry, branch 2, step 1). Which skills can the next level offer?

All the remaining four: the learned ones open everythingwhirlwind and iron_skin: step 2 of each of the two branches. bloodlust and second_wind wait until step 2 of their branch is learnedOnly whirlwind: a branch is chosen once and for all

3. Why does publish in the bus walk a copy of the list of listeners (slice, list(...), new ArrayList<>(...)) and not the list itself?

That way every listener gets its own copy of the eventThe copy is faster than the originalA listener may subscribe (or unsubscribe) while the event is being published; if the list changes while it is walked, the loop breaks or calls the new listener in the same publish

4. The quest is on stage 3. A TileEntered with depth 2 arrives (the hero goes down to the second level again). What does the listener that raises the stage to 2 do, and why?

Throws an exception: an event out of order is an errorMoves the quest back to stage 2: that is how the last visited level is keptNothing: its check has stage === 1, and the stage is 3. Events arrive in any order, and the listener has to ask in which state the quest is

5. An answer in the dialog has the condition quest:silver:active,item:ore:3. The hero has taken the quest but has only 2 ore. What does the player see?

It is shown and choosing it takes 2 oreIt is shown but cannot be chosenThe answer is not shown: the conditions are joined with "and" and the second one is false

Check

Start the lesson over

Related lessons

• Builds on: Lists · HashMap and HashSet · Lambdas · record, switch and patterns
• Tasks on this topic: Chronicles of Arcanum