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:

function onEnemyKilled(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:

function onEnemyKilled(enemy) {
  hero.xp += enemy.xp;
  bus.publish(makeEvent("EnemyKilled", enemy.kind));
}

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 {
  constructor() {
    this.level = 1;
    this.xp = 0;
    this.maxHp = 48;
  }
}

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

function xpForLevel(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.
function pendingLevels(xp, level) {
  let levels = 0;
  while (xp >= xpForLevel(level + levels + 1)) levels++;
  return levels;
}

function raiseLevel(hero) {
  hero.level += 1;
  hero.maxHp += 9;
}

const KILLS = [{ name: "rat", xp: 5 }, { name: "goblin", xp: 9 }, { name: "shaman", xp: 12 }, { name: "wolf", xp: 14 }, { name: "cultist", xp: 20 }, { name: "golem", xp: 32 }, { name: "Warden", xp: 150 }];

const hero = new Hero();
for (const kill of KILLS) {
  hero.xp += kill.xp;
  console.log(kill.name + " +" + kill.xp + ": xp " + hero.xp);
  const raise = pendingLevels(hero.xp, hero.level);
  for (let i = 0; i < raise; i++) {
    const before = hero.maxHp;
    raiseLevel(hero);
    console.log("  level " + hero.level + ": life " + before + " -> " + hero.maxHp);
  }
}
for (let level = 10; level <= 12; level++) {
  console.log("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.
const XP_TABLE = [0, 0, 20, 55, 105, 170, 250, 345, 455, 580, 720];

function xpForLevel(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.
function pendingLevels(xp, level) {
  let 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.

const SKILLS = [
  { id: "rage", branch: 1, tier: 1 },
  { id: "whirlwind", branch: 1, tier: 2 },
  { id: "bloodlust", branch: 1, tier: 3 },
  { id: "war_cry", branch: 2, tier: 1 },
  { id: "iron_skin", branch: 2, tier: 2 },
  { id: "second_wind", branch: 2, tier: 3 },
];
const ORDER = ["rage", "war_cry", "whirlwind", "iron_skin", "bloodlust", "second_wind"];

function learnable(skills, known) {
  const result = [];
  for (const skill of skills) {
    if (known.includes(skill.id)) continue;
    let ready = skill.tier === 1;
    for (const other of skills) {
      if (known.includes(other.id) && other.branch === skill.branch && other.tier === skill.tier - 1) ready = true;
    }
    if (ready) result.push(skill.id);
  }
  return result;
}

function show(list) {
  return list.length === 0 ? "-" : list.join(", ");
}

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

const known = [];
console.log("start -> " + show(learnable(SKILLS, known)));
for (const id of ORDER) {
  known.push(id);
  console.log(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).

function makeEvent(type, id = "", depth = 0) {
  return { type, id, depth };
}

function label(event) {
  return event.id === "" ? String(event.depth) : event.id;
}

class EventBus {
  constructor() {
    this.handlers = new Map();
  }

  subscribe(type, handler) {
    if (!this.handlers.has(type)) this.handlers.set(type, []);
    this.handlers.get(type).push(handler);
  }

  publish(event) {
    if (!this.handlers.has(event.type)) return;
    // A copy of the list: a listener may subscribe or unsubscribe while publishing.
    for (const handler of this.handlers.get(event.type).slice()) handler(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.

const bus = new EventBus();
const stats = new Stats();
bus.subscribe("EnemyKilled", log);
bus.subscribe("TileEntered", log);
bus.subscribe("EnemyKilled", (event) => {
  stats.kills++;
  console.log("kills: " + stats.kills);
});

fire(bus, makeEvent("EnemyKilled", "rat"));
fire(bus, makeEvent("TileEntered", "", 2));
fire(bus, makeEvent("EnemyKilled", "wolf"));
fire(bus, makeEvent("ItemPicked", "ore"));

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 {
  constructor(id, title, goals, doneGoal) {
    this.id = id;
    this.title = title;
    this.goals = goals;
    this.doneGoal = doneGoal;
    this.state = "inactive";
    this.stage = 0;
  }

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

  start() {
    this.state = "active";
    this.stage = 1;
    console.log("New quest: " + this.title + ".");
  }

  advance(newStage) {
    this.stage = newStage;
    console.log(this.title + ": " + this.goal());
  }

  complete() {
    this.state = "done";
    console.log("Quest complete: " + this.title + "!");
  }
}

class MinersQuest extends Quest {
  constructor() {
    super("miners", "The missing miners", ["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.");
  }

  subscribe(bus) {
    bus.subscribe("TileEntered", (event) => {
      if (this.state === "active" && this.stage === 1 && event.depth === 2) this.advance(2);
    });
    bus.subscribe("DialogChoice", (event) => {
      if (this.state === "active" && this.stage < 3 && event.id === "miner:warden") this.advance(3);
    });
    bus.subscribe("EnemyKilled", (event) => {
      if (this.state === "active" && event.id === "warden") this.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.

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

fire(bus, makeEvent("EnemyKilled", "rat"));
fire(bus, makeEvent("TileEntered", "", 2));
console.log("> the elder gives the quest");
quest.start();
fire(bus, makeEvent("TileEntered", "", 1));
fire(bus, makeEvent("TileEntered", "", 2));
fire(bus, makeEvent("DialogChoice", "miner:warden"));
fire(bus, makeEvent("TileEntered", "", 2));
fire(bus, makeEvent("EnemyKilled", "warden"));

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 {
  constructor() {
    this.handlers = new Map();
  }

  subscribe(type, handler) {
    if (!this.handlers.has(type)) this.handlers.set(type, []);
    this.handlers.get(type).push(handler);
  }

  publish(event) {
    if (!this.handlers.has(event.type)) return;
    // A copy of the list: a listener may subscribe or unsubscribe while publishing.
    for (const handler of this.handlers.get(event.type).slice()) handler(event);
  }
}

class Quest {
  constructor(id, title, goals, doneGoal) {
    this.id = id;
    this.title = title;
    this.goals = goals;
    this.doneGoal = doneGoal;
    this.state = "inactive";
    this.stage = 0;
  }

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

  start() {
    this.state = "active";
    this.stage = 1;
    console.log("New quest: " + this.title + ".");
  }

  advance(newStage) {
    this.stage = newStage;
    console.log(this.title + ": " + this.goal());
  }

  complete() {
    this.state = "done";
    console.log("Quest complete: " + this.title + "!");
  }
}

class MinersQuest extends Quest {
  constructor() {
    super("miners", "The missing miners", ["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.");
  }

  subscribe(bus) {
    bus.subscribe("TileEntered", (event) => {
      if (this.state === "active" && this.stage === 1 && event.depth === 2) this.advance(2);
    });
    bus.subscribe("DialogChoice", (event) => {
      if (this.state === "active" && this.stage < 3 && event.id === "miner:warden") this.advance(3);
    });
    bus.subscribe("EnemyKilled", (event) => {
      if (this.state === "active" && event.id === "warden") this.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.

class Game {
  static NAMES = { ore: "ore", silver_sword: "silver sword", potion_heal: "healing potion" };

  constructor(...quests) {
    this.flags = new Set();
    this.items = new Map();
    this.quests = new Map(quests.map((quest) => [quest.id, quest]));
  }

  quest(id) {
    return this.quests.get(id);
  }

  count(id) {
    return this.items.get(id) ?? 0;
  }

  label(id, n) {
    return Game.NAMES[id] + " x" + n;
  }

  give(id, n) {
    this.items.set(id, this.count(id) + n);
    console.log("You receive: " + this.label(id, n) + ".");
  }

  take(id, n) {
    this.items.set(id, this.count(id) - n);
    console.log("You hand over: " + this.label(id, n) + ".");
  }
}

function splitList(text) {
  return text === "-" ? [] : text.split(",");
}

function checkCondition(game, condition) {
  for (const part of splitList(condition)) {
    const negate = part.startsWith("!");
    const p = (negate ? part.substring(1) : part).split(":");
    let ok;
    if (p[0] === "flag") ok = game.flags.has(p[1]);
    else if (p[0] === "item") ok = game.count(p[1]) >= Number(p[2]);
    else if (p[0] === "quest") ok = game.quest(p[1]).state === p[2];
    else throw new Error("unknown condition: " + part);
    if (negate) ok = !ok;
    if (!ok) return false;
  }
  return true;
}

function runActions(game, actions) {
  for (const part of splitList(actions)) {
    const p = part.split(":");
    if (p[0] === "flag") {
      game.flags.add(p[1]);
    } else if (p[0] === "start") {
      game.quest(p[1]).start();
    } else if (p[0] === "complete") {
      game.quest(p[1]).complete();
    } else if (p[0] === "reward") {
      const quest = game.quest(p[1]);
      quest.state = "rewarded";
      console.log("Reward for " + quest.title + ".");
    } else if (p[0] === "give") {
      game.give(p[1], Number(p[2]));
    } else if (p[0] === "take") {
      game.take(p[1], Number(p[2]));
    } else {
      throw new Error("unknown action: " + part);
    }
  }
}

function visibleOptions(game, node) {
  return node.options.filter((o) => o.condition === "-" || checkCondition(game, o.condition));
}

function show(speaker, game, node) {
  console.log(speaker + ": " + node.text);
  visibleOptions(game, node).forEach((option, i) => console.log("  " + (i + 1) + ") " + option.text));
}

function choose(game, node, number) {
  const option = visibleOptions(game, node)[number - 1];
  console.log("> " + 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).

const SMITH = {
  start: {
    text: "My forge is cold without silver. Bring me three pieces of ore and I will forge you a sword.",
    options: [
      { text: "I will look for ore.", next: "deal", condition: "quest:silver:inactive", actions: "start:silver" },
      { text: "Here is the ore.", next: "done", condition: "quest:silver:active,item:ore:3", actions: "take:ore:3,complete:silver,reward:silver,give:silver_sword:1" },
      { text: "Goodbye.", next: "end", condition: "-", actions: "-" },
    ],
  },
  deal: {
    text: "The ore is on the second level. The ore golems carry it inside them.",
    options: [
      { text: "Fine.", next: "end", condition: "-", actions: "-" },
    ],
  },
  done: {
    text: "A silver sword. Its edge never dulls.",
    options: [
      { text: "Thank you.", next: "end", condition: "-", actions: "-" },
    ],
  },
};

const MINER = {
  start: {
    text: "A living soul! The others ran up... I was trapped down here.",
    options: [
      { text: "What is down there?", next: "warden", condition: "quest:miners:active,!flag:miner_told", actions: "flag:miner_told,give:potion_heal:1" },
      { text: "Stay here, I will come back.", next: "end", condition: "-", actions: "-" },
    ],
  },
  warden: {
    text: "The Warden of the Depths. A stone guardian woken by our picks. When it cracks, it calls the dead to help. Take my potion.",
    options: [
      { text: "I will stop it.", next: "end", condition: "-", actions: "-" },
    ],
  },
};

const game = new Game(new Quest("silver", "Silver for the smith", ["Collect three pieces of silver ore.", "Bring the ore to Vela the smith."], "The smith has her silver."), new Quest("miners", "The missing miners", ["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."));
const start = SMITH.start;
show("Vela", game, start);
let next = choose(game, start, 1);
show("Vela", game, SMITH[next]);
game.give("ore", 3);
show("Vela", game, start);
next = choose(game, start, 1);
show("Vela", game, SMITH[next]);
game.quest("miners").start();
const minerStart = MINER.start;
show("Dobri", game, minerStart);
next = choose(game, minerStart, 1);
show("Dobri", game, MINER[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.
function xpForLevel(level) {
  if (level < XP_TABLE.length) return XP_TABLE[level];
  return XP_TABLE[XP_TABLE.length - 1] + (level - XP_TABLE.length + 1) * 150;
}

function pendingLevels(hero) {
  let levels = 0;
  while (hero.xp >= xpForLevel(hero.level + levels + 1)) levels++;
  return levels;
}

// The new level by itself: more life and mana, full health.
function raiseLevel(hero) {
  const heroClass = hero.heroClass();
  hero.level += 1;
  hero.base.set('maxHp', hero.base.get('maxHp') + heroClass.hpPerLevel);
  hero.base.set('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.
function learnableSkills(hero) {
  const result = [];
  for (const skill of SKILLS.values()) {
    if (skill.classId !== hero.classId || hero.skills.indexOf(skill.id) >= 0) continue;
    let ready = skill.tier === 1;
    for (const known of hero.skills) {
      const other = SKILLS.get(known);
      if (other.branch === skill.branch && other.tier === skill.tier - 1) ready = true;
    }
    if (ready) result.push(skill.id);
  }
  return result;
}

// The choices at a new level: a stat or a new skill.
function levelUpChoices(hero) {
  const choices = [
    { kind: 'stat', stat: 'maxHp', amount: 8 },
    { kind: 'stat', stat: 'strength', amount: 1 },
    { kind: 'stat', stat: 'agility', amount: 1 },
    { kind: 'stat', stat: 'defense', amount: 1 },
  ];
  for (const skillId of learnableSkills(hero)) choices.push({ kind: 'skill', stat: skillId, amount: 0 });
  return choices;
}

function applyLevelChoice(hero, choice) {
  if (choice.kind === 'skill') {
    hero.skills.push(choice.stat);
  } else {
    hero.base.set(choice.stat, hero.base.get(choice.stat) + choice.amount);
    if (choice.stat === '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".
class EventBus {
  constructor() {
    this.handlers = new Map();
  }

  subscribe(type, handler) {
    if (!this.handlers.has(type)) this.handlers.set(type, []);
    this.handlers.get(type).push(handler);
  }

  publish(event) {
    if (!this.handlers.has(event.type)) return;
    for (const handler of this.handlers.get(event.type).slice()) handler(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.
class Quest {
  constructor(id) {
    this.id = id;
    this.state = 'inactive';
    this.stage = 0;
  }

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

  goal() {
    if (this.state === 'done') return t('quest.' + this.id + '.done');
    if (this.state === 'rewarded') return t('quest.rewarded');
    return t('quest.' + this.id + '.stage' + this.stage);
  }

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

  advance(game, stage) {
    this.stage = stage;
    game.say(t('quest.updated', { title: this.title(), goal: this.goal() }));
  }

  complete(game) {
    this.state = 'done';
    game.say(t('quest.completed', { title: this.title() }));
  }

  subscribe(bus, game) {}
}

class MissingMinersQuest extends Quest {
  constructor() {
    super('miners');
  }

  subscribe(bus, game) {
    bus.subscribe('TileEntered', (event) => {
      if (this.state === 'active' && this.stage === 1 && event.depth === 2) this.advance(game, 2);
    });
    bus.subscribe('DialogChoice', (event) => {
      if (this.state === 'active' && this.stage < 3 && event.dialogId === 'miner' && event.nodeId === 'warden') this.advance(game, 3);
    });
    bus.subscribe('EnemyKilled', (event) => {
      if (this.state === 'active' && event.kindId === 'warden') this.complete(game);
    });
  }
}

class BloodTrailQuest extends Quest {
  constructor() {
    super('blood');
  }

  start(game) {
    super.start(game);
    if (game.hasFlag('leader_dead')) this.complete(game);
  }

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

class SilverQuest extends Quest {
  constructor() {
    super('silver');
  }

  start(game) {
    super.start(game);
    this.check(game);
  }

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

  subscribe(bus, game) {
    bus.subscribe('ItemPicked', (event) => {
      if (event.itemId === 'ore') this.check(game);
    });
  }
}

function createQuests() {
  return [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.
function checkCondition(game, condition) {
  for (const part of splitList(condition)) {
    const negate = part.charAt(0) === '!';
    const pieces = (negate ? part.substring(1) : part).split(':');
    let ok = false;
    if (pieces[0] === 'flag') ok = game.hasFlag(pieces[1]);
    else if (pieces[0] === 'item') ok = game.hero.inventory.count(pieces[1]) >= toInt(pieces[2]);
    else if (pieces[0] === 'gold') ok = game.hero.gold >= toInt(pieces[1]);
    else if (pieces[0] === 'quest') ok = game.quest(pieces[1]).state === pieces[2];
    else throw new Error('unknown condition: ' + part);
    if (negate) ok = !ok;
    if (!ok) return false;
  }
  return true;
}

function runActions(game, actions) {
  for (const part of splitList(actions)) {
    const pieces = part.split(':');
    if (pieces[0] === 'flag') {
      game.setFlag(pieces[1]);
    } else if (pieces[0] === 'start') {
      game.quest(pieces[1]).start(game);
    } else if (pieces[0] === 'complete') {
      game.quest(pieces[1]).complete(game);
    } else if (pieces[0] === 'reward') {
      game.quest(pieces[1]).state = 'rewarded';
      game.say(t('quest.rewardedSay', { title: game.quest(pieces[1]).title() }));
    } else if (pieces[0] === 'give') {
      game.giveItem(pieces[1], toInt(pieces[2]));
    } else if (pieces[0] === 'take') {
      game.hero.inventory.remove(pieces[1], toInt(pieces[2]));
      game.say(t('item.given', { item: itemLabel(pieces[1], toInt(pieces[2])) }));
    } else if (pieces[0] === 'gold') {
      game.hero.gold += toInt(pieces[1]);
      game.say(t('item.gold', { amount: pieces[1] }));
    } else if (pieces[0] === 'xp') {
      game.gainXp(toInt(pieces[1]));
    } else {
      throw new Error('unknown action: ' + part);
    }
  }
}

function visibleOptions(game, node) {
  const result = [];
  for (const option of node.options) {
    if (option.condition === '-' || checkCondition(game, option.condition)) result.push(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.
const XP_TABLE = [0, 0, 20, 55, 105, 170, 250, 345, 455, 580, 720];

function xpForLevel(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.
function pendingLevels(xp, level) {
  let levels = 0;
  while (xp >= xpForLevel(level + levels + 1)) levels++;
  return levels;
}

console.log(pendingLevels(130, 1));
console.log(pendingLevels(104, 3));
console.log(pendingLevels(55, 1));

Answer

3
0
2

3
0
1

4
1
3

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:

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

fire(bus, makeEvent("EnemyKilled", "rat"));
fire(bus, makeEvent("TileEntered", "", 2));
console.log("> the elder gives the quest");
quest.start();
fire(bus, makeEvent("TileEntered", "", 1));
fire(bus, makeEvent("TileEntered", "", 2));
fire(bus, makeEvent("DialogChoice", "miner:warden"));
fire(bus, makeEvent("TileEntered", "", 2));
fire(bus, makeEvent("EnemyKilled", "warden"));

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 constructor() {3 super("miners", "The missing miners", ["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 subscribe(bus) {7 bus.subscribe("TileEntered", (event) => {8 if (this.state === "active" && event.depth === 2) this.advance(2);9 });10 bus.subscribe("DialogChoice", (event) => {11 if (this.state === "active" && this.stage < 3 && event.id === "miner:warden") this.advance(3);12 });13 bus.subscribe("EnemyKilled", (event) => {14 if (this.state === "active" && event.id === "warden") this.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:

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

fire(bus, makeEvent("EnemyKilled", "wolf"));
console.log("> start");
quest.start();
fire(bus, makeEvent("EnemyKilled", "rat"));
fire(bus, makeEvent("EnemyKilled", "wolf"));
fire(bus, makeEvent("EnemyKilled", "wolf"));
fire(bus, makeEvent("EnemyKilled", "wolf"));
fire(bus, makeEvent("EnemyKilled", "wolf"));

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: Arrays: push, splice and sort · Map and Set · Arrow functions · Data, switch and destructuring
• Tasks on this topic: Chronicles of Arcanum