Zum Inhalt
wannacode

Gegner, die denken

Kurz gesagt: Ein Gegner auf der Karte ist ein endlicher Automat (schläft, wandert, jagt, flieht), der auf dem kürzesten Weg jagt, den die Breitensuche gefunden hat; im Kampf wählt er die Aktion mit dem höchsten Nutzenwert.

Problem

Der Goblin, der gegen die Wand läuft

Bisher standen die Gegner in der Mine dort, wo die Karte sie hingestellt hat. Wer das sieht, merkt sofort, dass das Spiel aus Pappe ist. Ein lebendiger Gegner muss drei Dinge können: entscheiden, was er tut (schlafen, wandern, jagen, fliehen), seinen Weg finden und im Kampf wählen.

Die einfachste Jagd lautet: „Mach den Schritt, der dich dem Helden am meisten nähert.“ Hier sind ein Goblin (g) und ein Held (@) auf beiden Seiten einer Wand mit einer Lücke unten:

################
#......#.......#
#......#.......#
#.@....#g......#
#......#.......#
#..............#
################

In gerader Linie sind es 6 Zellen, aber die Wand liegt dazwischen. Die einfache Jagd vergleicht nur die Entfernung: Der Goblin will nach links, dort ist eine Wand, und er bleibt an ihr kleben. Hier bleibt er stehen:

################
#......#.......#
#......#.......#
#.@....#g......#
#......#.......#
#..............#
################

Eine gerade Linie weiß nichts von Wänden. Wir brauchen einen Weg, der sie umgeht, und der kürzeste Weg auf einem Raster wird mit der Breitensuche gefunden. Die Lektion baut sie zuerst auf der kleinen Ebene 16 × 7 (die Lücke ist unten), setzt dann einen endlichen Automaten darüber, der entscheidet, wann der Gegner sich bewegt, und zeigt zuletzt das zweite Gehirn des Spiels: die Nutzenbewertung im Kampf.

Die Idee

Die Welle: Wie viele Schritte jede Zelle entfernt ist

Stell dir vor, du wirfst einen Stein ins Wasser: Von der Stelle, an der er gefallen ist, breiten sich Kreise aus. Die Breitensuche macht dasselbe über ein Raster. Sie beginnt beim Goblin: Er hat die Entfernung 0. Seine Nachbarn haben 1. Die Nachbarn der Nachbarn (noch nicht gesehen) haben 2. Und so weiter, bis die Welle alles bedeckt. Jede Zelle bekommt eine Zahl: wie viele Schritte sie vom Goblin über den Boden entfernt ist, nicht in gerader Linie.

Man braucht eine Warteschlange: die Zellen, die die Welle erreicht, aber noch nicht angeschaut hat. Vorne wird die älteste Zelle entnommen (deshalb geht die Welle der Reihe nach), und ihre neuen Nachbarn kommen hinten dazu. Eine Zelle, die schon eine Zahl hat, wird kein zweites Mal eingefügt.

const MAP = `
################
#......#.......#
#......#.......#
#......#.......#
#......#.......#
#..............#
################`.trim();


const DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]];


// Die Welle: wie viele Schritte jede Zelle vom Start entfernt ist.
function distances(level, startX, startY) {
  const dist = Array.from({ length: level.height }, () => new Array(level.width).fill(-1));
  dist[startY][startX] = 0;
  const queue = [{ x: startX, y: startY }];
  let head = 0;
  while (head < queue.length) {
    const cell = queue[head];
    head++;
    for (const [dx, dy] of DIRECTIONS) {
      const nextX = cell.x + dx;
      const nextY = cell.y + dy;
      if (!level.walkable(nextX, nextY) || dist[nextY][nextX] !== -1) continue;
      dist[nextY][nextX] = dist[cell.y][cell.x] + 1;
      queue.push({ x: nextX, y: nextY });
    }
  }
  return dist;
}
const level = new Level(MAP);
const dist = distances(level, ENEMY_X, ENEMY_Y);
console.log("Die Welle vom Feind aus (a = 10, b = 11, ...):");
printWave(level, dist);
Ausgabe
Die Welle vom Feind aus (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################

a ist 10, b ist 11 und so weiter. Der Goblin steht auf 0 (an der Wand, am linken Rand des rechten Raums), und die Wand ist #. Die Welle füllt zuerst den rechten Raum, geht dann durch die Lücke unten und steigt erst danach in den linken. Der Held auf (2, 3) steht auf a, also 10 Schritte vom Goblin entfernt, obwohl es in gerader Linie 6 sind: Die Zahl ist die wirkliche Entfernung über den Boden.

Wir benutzen nicht shift(): Das Entnehmen am Anfang eines Arrays verschiebt alle anderen Elemente, deshalb gehen wir stattdessen mit einem Index head voran.

Die Prüfung dist[nextY][nextX] != -1 ist das ganze „schon dagewesen“: Die Zelle hat eine Zahl, ist also in der Warteschlange oder war darin. Ohne diese Prüfung würde die Welle zurückfließen und nie enden.

Genauer, für Neugierige

Die vier Richtungen stehen in fester Reihenfolge: oben, rechts, unten, links. Die Reihenfolge ändert die Entfernungen nicht (sie sind bei jeder Reihenfolge gleich), aber sie ändert, welcher von mehreren gleich langen Wegen gefunden wird. Im Spiel ist die Reihenfolge genau deshalb fest: Dieselbe Eingabe muss in Java, C#, Python und JavaScript denselben Weg ergeben, sonst würden die Aufzeichnung eines Kampfes und die Prüfung gegen den aufgezeichneten Durchgang auseinanderlaufen.

Diese Welle von Entfernungen heißt distance field (auch Dijkstra map): Eine Suche vom Helden aus gibt für jede Zelle eine Zahl, und jeder Gegner geht einfach zum Nachbarn mit der kleineren Zahl. Bei vielen Gegnern ist das viel billiger als eine Suche für jeden.

Die Idee

Der Weg: Woher jede Zelle kam

Die Zahlen zeigen die Entfernung, aber der Gegner braucht die Schritte. Wir fügen eine Tabelle hinzu: Für jede Zelle merken wir uns, von welcher Zelle die Welle gekommen ist. Wenn die Welle das Ziel erreicht, gehen wir rückwärts: das Ziel, woher es kam, woher jene kam, und so weiter bis zum Start. So entsteht der Weg von hinten nach vorn, deshalb drehen wir ihn am Ende um.

function findPath(level, startX, startY, goalX, goalY) {
  const cameFrom = new Array(level.width * level.height).fill(-1);
  const start = startY * level.width + startX;
  cameFrom[start] = start;
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head++;
    const x = current % level.width;
    const y = Math.floor(current / level.width);
    if (current !== start && x === goalX && y === goalY) {
      const path = [];
      let index = current;
      while (index !== start) {
        path.push({ x: index % level.width, y: Math.floor(index / level.width) });
        index = cameFrom[index];
      }
      path.reverse();
      return path;
    }
    for (const [dx, dy] of DIRECTIONS) {
      const nextX = x + dx;
      const nextY = y + dy;
      if (!level.walkable(nextX, nextY)) continue;
      const next = nextY * level.width + nextX;
      if (cameFrom[next] !== -1) continue;
      cameFrom[next] = current;
      queue.push(next);
    }
  }
  return null;
}


function distance(ax, ay, bx, by) {
  return Math.abs(ax - bx) + Math.abs(ay - by);
}
const level = new Level(MAP);
const path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
console.log("der Feind (" + ENEMY_X + ", " + ENEMY_Y + "), der Held (" + HERO_X + ", " + HERO_Y + "): in gerader Linie " +
  distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", auf dem Weg " + path.length);
const dist = distances(level, ENEMY_X, ENEMY_Y);
console.log("Die Welle vom Feind aus (a = 10, b = 11, ...):");
printWave(level, dist);
console.log("Der Weg zum Helden (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
Ausgabe
der Feind (8, 3), der Held (2, 3): in gerader Linie 6, auf dem Weg 10
Die Welle vom Feind aus (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################
Der Weg zum Helden (*):
################
#......#.......#
#......#.......#
#.@****#g......#
#.....*#*......#
#.....***......#
################

Der Weg (*) geht durch die Lücke nach unten, steigt an der Wand entlang in den linken Raum und läuft nach links zum Helden: 10 Schritte gegenüber 6 in gerader Linie. Die Wand stört den Algorithmus nicht, denn die Welle betritt sie einfach nicht.

Die Suche endet, sobald sie das Ziel aus der Warteschlange nimmt: Danach braucht sie nichts mehr. Deshalb ist das erste gefundene Ziel das nächste. Und wenn es keinen Weg gibt (der Held steht hinter einer Wand ohne Lücke), geht die Warteschlange zu Ende, und die Funktion gibt null zurück.

Genauer, für Neugierige

Der erste Schritt des Weges ist nur eine Zelle, aber der Gegner macht ihn und fragt im nächsten Zug neu. So kann er an einem alten Weg nicht hängen bleiben: Der Held hat sich bewegt, ein anderer Gegner hat die Zelle besetzt, die Tür ist zugefallen.

Die Kosten sind gering. Die Ebene im Spiel ist 50 × 20, etwa 1000 Zellen, und selbst wenn alle besucht werden, sind das ein paar tausend einfache Prüfungen pro Gegner und Zug.

Die Idee

Ein endlicher Automat: schläft, wandert, jagt, flieht

Wann benutzt der Gegner den Weg? Das hängt davon ab, was er gerade ist. Ein Schläfer bewegt sich nicht. Ein Wanderer streift herum. Ein Jäger folgt dem Weg. Ein Fliehender entfernt sich. Das ist ein endlicher Automat: Ein Gegner hat einen Zustand (eine Zeichenkette: "sleep", "wander", "chase", "flee"), und in jedem Zug steht da: „in diesem Zustand, in dieser Lage, was tue ich und in welchen Zustand gehe ich über“.

Von Nach Wann
sleep chase der Weg zum Helden ist höchstens 5 lang
wander chase der Gegner „sieht“ den Helden: Der Weg ist höchstens 8 lang
chase wander mehr als 3 Züge ohne Sicht (lost > LOST)
chase flee Leben × 4 < maximales Leben (unter einem Viertel)

Das Programm benutzt dieselbe Karte und einen Gegner mit 16 Leben. „Sehen“ ist vereinfacht: Ein Gegner sieht den Helden, wenn der Weg zu ihm höchstens 8 lang ist. Im Spiel ist das eine Sichtlinie aus der Lektion über die Karte (bis zu 8 Zellen), und hier liefert der Weg dasselbe ohne einen weiteren Algorithmus. Der Ablauf steht in SCRIPT: Der Held nähert sich, duckt sich hinter eine Ecke (hidden), taucht wieder auf und wird zuletzt getroffen (hit).

const SIGHT = 8;
const WAKE = 5;
const LOST = 3;
const FAR = 20;
const NONE = 99;
const ENEMY_LIFE = 16;


// Der Feind „sieht“ den Helden, wenn der Weg zu ihm kurz ist (im Spiel: die Sichtlinie aus der Lektion über die Karte).
function enemyTurn(level, enemy, heroX, heroY, turn, hidden) {
  const path = findPath(level, enemy.x, enemy.y, heroX, heroY);
  const pathLength = path === null ? NONE : path.length;
  const sees = !hidden && pathLength <= SIGHT;
  if (enemy.state === "sleep") {
    if (sees && pathLength <= WAKE) enemy.state = "chase";
    return;
  }
  if (enemy.state === "wander") {
    if (sees) {
      enemy.state = "chase";
      enemy.lost = 0;
      return;
    }
    // Wandert in der Reihenfolge der Richtungen (das Spiel würfelt).
    const [dx, dy] = DIRECTIONS[turn % 4];
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (level.walkable(nextX, nextY) && !(nextX === heroX && nextY === heroY)) {
      enemy.x = nextX;
      enemy.y = nextY;
    }
    return;
  }
  if (enemy.state === "chase") {
    if (enemy.life * 4 < enemy.maxLife) {
      enemy.state = "flee";
      return;
    }
    if (!sees) {
      enemy.lost++;
      if (enemy.lost > LOST) {
        enemy.state = "wander";
        return;
      }
    } else {
      enemy.lost = 0;
    }
    if (pathLength <= 1) return;
    if (pathLength <= FAR) {
      enemy.x = path[0].x;
      enemy.y = path[0].y;
    }
    return;
  }
  // Flieht: der Schritt, der ihn am weitesten vom Helden entfernt.
  let bestX = enemy.x;
  let bestY = enemy.y;
  let bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
  for (const [dx, dy] of DIRECTIONS) {
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (!level.walkable(nextX, nextY) || (nextX === heroX && nextY === heroY)) continue;
    const away = distance(nextX, nextY, heroX, heroY);
    if (away > bestDistance) {
      bestDistance = away;
      bestX = nextX;
      bestY = nextY;
    }
  }
  enemy.x = bestX;
  enemy.y = bestY;
}

Jeder Zustand ist ein Zweig eines if, der an seinem Ende zurückkehrt: In einem Zug geschieht genau eine Sache. Es liest sich von oben nach unten wie die Tabelle. Der Zähler lost ist das Gedächtnis des Automaten: Ohne ihn würde der Gegner den Helden schon beim ersten Verschwinden vergessen.

const level = new Level(MAP);
const enemy = new Enemy(ENEMY_X, ENEMY_Y, "sleep", ENEMY_LIFE);
SCRIPT.forEach(([heroX, heroY, hit, hidden], i) => {
  enemy.life = Math.max(0, enemy.life - hit);
  const before = enemy.state;
  enemyTurn(level, enemy, heroX, heroY, i + 1, hidden);
  const path = findPath(level, enemy.x, enemy.y, heroX, heroY);
  const length = path === null ? NONE : path.length;
  const state = before === enemy.state ? before : before + " → " + enemy.state;
  console.log("Zug " + (i + 1) + ": " + state + ", Feind (" + enemy.x + ", " + enemy.y + "), Weg " + length + ", Leben " + enemy.life);
});
Ausgabe
Zug 1: sleep, Feind (8, 3), Weg 7, Leben 16
Zug 2: sleep, Feind (8, 3), Weg 6, Leben 16
Zug 3: sleep → chase, Feind (8, 3), Weg 5, Leben 16
Zug 4: chase, Feind (8, 4), Weg 4, Leben 16
Zug 5: chase, Feind (8, 5), Weg 3, Leben 16
Zug 6: chase, Feind (7, 5), Weg 2, Leben 16
Zug 7: chase, Feind (6, 5), Weg 1, Leben 16
Zug 8: chase → wander, Feind (6, 5), Weg 1, Leben 16
Zug 9: wander, Feind (7, 5), Weg 2, Leben 16
Zug 10: wander → chase, Feind (7, 5), Weg 2, Leben 16
Zug 11: chase, Feind (6, 5), Weg 1, Leben 16
Zug 12: chase → flee, Feind (6, 5), Weg 1, Leben 3
Zug 13: flee, Feind (7, 5), Weg 2, Leben 3
Zug 14: flee, Feind (8, 5), Weg 3, Leben 3
Zug 15: flee, Feind (9, 5), Weg 4, Leben 3

Zug 3: Der Weg wird 5 lang, und sleep → chase. Züge 4–7: Der Goblin geht den Weg entlang. In Zug 8 übersteigt lost die 3, und er geht zu wander über; in Zug 9 macht er einen Schritt wie ein Wanderer, und in Zug 10 sieht er den Helden wieder. In Zug 12 trifft ihn der Held und nimmt ihm 13 von 16 Leben: 3 × 4 = 12 < 16, und chase → flee. Das Fliehen benutzt den Weg nicht: Von den vier Nachbarn nimmt er den, der ihn am weitesten entfernt (away > bestDistance).

Genauer, für Neugierige

Warum Zeichenketten und kein enum? Der Kanon benutzt Zeichenketten, weil die Zustände in den Spielstand geschrieben und aus einer Datei gelesen werden. So braucht eine neue Gegnerart mit einem neuen Zustand keinen neuen Typ. Der Preis ist, dass ein Tippfehler im Namen ("chaes") beim Kompilieren nicht auffällt.

Ein Automat ist die einfachste Art, Verhalten zu beschreiben, aber er wächst: Zehn Zustände mit je fünf Übergängen sind fünfzig Zeilen, die schwer zu lesen sind. Dann geht man zu einem behavior tree über oder zur Nutzenbewertung, wie sie unten im Kampf vorkommt.

Sieh es dir an

Die Jagd in Aktion

Hier ist dasselbe Zug für Zug. Der Goblin schläft auf der anderen Seite der Wand. Der Held nähert sich; der Weg wird 5, und der Goblin wacht auf. Dann sieht man die Suche: Eine Welle geht vom Goblin aus und läuft durch die Lücke um die Wand herum, bis sie den Helden erreicht. Danach geht der Goblin los, verliert den Helden, bemerkt ihn wieder und flieht schließlich.

function findPath(level, startX, startY, goalX, goalY) {
  const cameFrom = new Array(level.width * level.height).fill(-1);
  const start = startY * level.width + startX;
  cameFrom[start] = start;
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head++;
    const x = current % level.width;
    const y = Math.floor(current / level.width);
    if (current !== start && x === goalX && y === goalY) {
      const path = [];
      let index = current;
      while (index !== start) {
        path.push({ x: index % level.width, y: Math.floor(index / level.width) });
        index = cameFrom[index];
      }
      path.reverse();
      return path;
    }
    for (const [dx, dy] of DIRECTIONS) {
      const nextX = x + dx;
      const nextY = y + dy;
      if (!level.walkable(nextX, nextY)) continue;
      const next = nextY * level.width + nextX;
      if (cameFrom[next] !== -1) continue;
      cameFrom[next] = current;
      queue.push(next);
    }
  }
  return null;
}


// Der Feind „sieht“ den Helden, wenn der Weg zu ihm kurz ist (im Spiel: die Sichtlinie aus der Lektion über die Karte).
function enemyTurn(level, enemy, heroX, heroY, turn, hidden) {
  const path = findPath(level, enemy.x, enemy.y, heroX, heroY);
  const pathLength = path === null ? NONE : path.length;
  const sees = !hidden && pathLength <= SIGHT;
  if (enemy.state === "sleep") {
    if (sees && pathLength <= WAKE) enemy.state = "chase";
    return;
  }
  if (enemy.state === "wander") {
    if (sees) {
      enemy.state = "chase";
      enemy.lost = 0;
      return;
    }
    // Wandert in der Reihenfolge der Richtungen (das Spiel würfelt).
    const [dx, dy] = DIRECTIONS[turn % 4];
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (level.walkable(nextX, nextY) && !(nextX === heroX && nextY === heroY)) {
      enemy.x = nextX;
      enemy.y = nextY;
    }
    return;
  }
  if (enemy.state === "chase") {
    if (enemy.life * 4 < enemy.maxLife) {
      enemy.state = "flee";
      return;
    }
    if (!sees) {
      enemy.lost++;
      if (enemy.lost > LOST) {
        enemy.state = "wander";
        return;
      }
    } else {
      enemy.lost = 0;
    }
    if (pathLength <= 1) return;
    if (pathLength <= FAR) {
      enemy.x = path[0].x;
      enemy.y = path[0].y;
    }
    return;
  }
  // Flieht: der Schritt, der ihn am weitesten vom Helden entfernt.
  let bestX = enemy.x;
  let bestY = enemy.y;
  let bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
  for (const [dx, dy] of DIRECTIONS) {
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (!level.walkable(nextX, nextY) || (nextX === heroX && nextY === heroY)) continue;
    const away = distance(nextX, nextY, heroX, heroY);
    if (away > bestDistance) {
      bestDistance = away;
      bestX = nextX;
      bestY = nextY;
    }
  }
  enemy.x = bestX;
  enemy.y = bestY;
}
Schritt für Schritt, in Worten
  1. Der Goblin schläft auf (8, 3). Der Held ist auf der anderen Seite der Wand. In Zug 2 ist der Weg zum Helden 6, und zum Aufwachen sind höchstens 5 nötig: Der Goblin schläft weiter, obwohl der Held in gerader Linie nur 4 Zellen entfernt ist.
  2. Zug 3: Der Held steht auf (6, 4). In gerader Linie, durch die Wand, sind es 3 Zellen, aber der Weg ist 5 ≤ 5: sleep → chase.
  3. Breitensuche vom Goblin aus: eine Warteschlange, aus der die älteste Zelle zuerst herauskommt. Die Welle breitet sich Zelle für Zelle über den Boden aus und läuft durch die Lücke um die Wand herum. 27 von 66 Zellen kommen aus der Warteschlange, bis der Held erreicht ist.
  4. Der Held ist gefunden. Vom Helden aus gehen wir über cameFrom Zelle für Zelle zurück zum Goblin und drehen den Weg um: 5 Schritte. Der Goblin macht den ersten.
  5. In jedem Zug fragt der Goblin neu und macht nur den ersten Schritt des Weges: 4, 3, 2, 1 bis zum Helden. Bewegt sich der Held, ist der Weg ein anderer.
  6. Der Held duckt sich hinter eine Ecke (die blasse Kugel). Der Goblin geht noch auf ihn zu, zählt aber mit: Nach 3 Zügen ohne Sicht (lost > 3) wird in Zug 8 aus chase → wander.
  7. Zug 9: Der Goblin wandert. Die Richtung kommt aus der Zugnummer (das Spiel würfelt), für den Helden wirkt der Schritt zufällig, nicht gezielt.
  8. Zug 10: Der Held taucht wieder auf, der Weg ist 2 ≤ 8: wander → chase. Der Goblin jagt wieder und erreicht den Helden.
  9. Zug 12: Der Schlag des Helden lässt dem Goblin 3 von 16 Leben. Der Test ist Leben × 4 < maximales Leben: 12 < 16, also chase → flee.
  10. Fliehen braucht keinen Weg und keine Suche: Von den vier Nachbarn nimmt er den, der ihn am weitesten vom Helden entfernt (2, 3, 4 Zellen).

Der Code neben der Szene ist findPath und enemyTurn aus dem Programm. In jedem Schritt leuchten die Zeilen auf, die gerade arbeiten.

Die Idee

Im Spiel

Was wir gebaut haben, ist dasselbe wie im Kanon, nur kleiner. Hier ist die echte Breitensuche. Sie nimmt zwei Funktionen statt eines fertigen Ziels und einer fertigen Karte des Begehbaren: isPassable sagt, wohin ein Gegner treten darf (nicht durch andere Gegner und nicht durch den Helden), und isGoal sagt, welche Zelle das Ziel ist:

// Breitensuche: eine Warteschlange von Feldern, jedes merkt sich, woher es kam. Das erste gefundene Ziel ist
// das nächste. Die Richtungen haben eine feste Reihenfolge (oben, rechts, unten, links), darum ist der Weg gleich
// in jeder Sprache.
const DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]];


// isPassable(x, y) und isGoal(x, y) sind Funktionen; liefert den Pfad ohne den Start oder null.
function findPath(level, startX, startY, isPassable, isGoal) {
  const cameFrom = new Array(level.width * level.height).fill(-1);
  const startIndex = startY * level.width + startX;
  cameFrom[startIndex] = startIndex;
  const queue = [startIndex];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head++;
    const x = current % level.width;
    const y = Math.floor(current / level.width);
    if (current !== startIndex && isGoal(x, y)) {
      const path = [];
      let index = current;
      while (index !== startIndex) {
        path.push({ x: index % level.width, y: Math.floor(index / level.width) });
        index = cameFrom[index];
      }
      path.reverse();
      return path;
    }
    for (const direction of DIRECTIONS) {
      const nextX = x + direction[0];
      const nextY = y + direction[1];
      if (!level.inBounds(nextX, nextY)) continue;
      const nextIndex = nextY * level.width + nextX;
      if (cameFrom[nextIndex] !== -1) continue;
      if (!isPassable(nextX, nextY) && !isGoal(nextX, nextY)) continue;
      cameFrom[nextIndex] = current;
      queue.push(nextIndex);
    }
  }
  return null;
}


function distance(ax, ay, bx, by) {
  return Math.abs(ax - bx) + Math.abs(ay - by);
}

Und hier ist der Automat auf der Karte. Außer unseren Zuständen gibt es guard (ein Wächter auf seinem Posten), calm (nachdem der Held aus einem Kampf geflohen ist, wandern die Gegner und bemerken ihn 6 Züge lang nicht) und einen Würfel fürs Aufwachen:

// Die Karten-KI ist eine Zustandsmaschine: schläft → streift umher → jagt → flieht bei wenig Leben.
// Der Wächter bleibt auf seinem Posten (guard), bis er den Helden sieht.
function enemySeesHero(level, enemy, hero) {
  if (distance(enemy.x, enemy.y, hero.x, hero.y) > 8) return false;
  return lineOfSight(level, enemy.x, enemy.y, hero.x, hero.y);
}


function canEnemyStep(game, level, x, y) {
  if (!level.isWalkable(x, y)) return false;
  if (level.enemyAt(x, y) !== null || level.npcAt(x, y) !== null) return false;
  return !(game.hero.x === x && game.hero.y === y);
}


function moveEnemy(game, level, enemy, x, y) {
  if (enemy.hasEffect('bleed')) level.addBlood(enemy.x, enemy.y);
  enemy.x = x;
  enemy.y = y;
}


function enemyTurnOnMap(game, level, enemy) {
  const hero = game.hero;
  const rng = game.rng;
  const sees = enemySeesHero(level, enemy, hero);
  const heroSeesIt = level.visible[enemy.y][enemy.x];
  if (enemy.calm > 0) enemy.calm -= 1;
  if (enemy.state === 'sleep') {
    if (sees && distance(enemy.x, enemy.y, hero.x, hero.y) <= 5 && rng.chance(50)) {
      enemy.state = 'chase';
      if (heroSeesIt) game.say(t('ai.wakes', { name: enemy.name }));
    }
    return;
  }
  if (enemy.state === 'guard') {
    if (sees && distance(enemy.x, enemy.y, hero.x, hero.y) <= 6) {
      enemy.state = 'chase';
      game.say(t('ai.guard', { name: enemy.name }));
    }
    return;
  }
  if (enemy.state === 'wander') {
    if (sees && enemy.calm === 0) {
      enemy.state = 'chase';
      enemy.lostTurns = 0;
      if (heroSeesIt) game.say(t('ai.notices', { name: enemy.name }));
      return;
    }
    const roll = rng.nextInt(5);
    if (roll < 4) {
      const nextX = enemy.x + DIRECTIONS[roll][0];
      const nextY = enemy.y + DIRECTIONS[roll][1];
      if (canEnemyStep(game, level, nextX, nextY)) moveEnemy(game, level, enemy, nextX, nextY);
    }
    return;
  }
  if (enemy.state === 'chase') {
    if (enemy.kind.special !== 'warden' && enemy.isHeavilyWounded()) {
      enemy.state = 'flee';
      if (heroSeesIt) game.say(t('ai.flees', { name: enemy.name }));
      return;
    }
    if (!sees) {
      enemy.lostTurns += 1;
      if (enemy.lostTurns > 5) {
        enemy.state = 'wander';
        return;
      }
    } else {
      enemy.lostTurns = 0;
    }
    if (distance(enemy.x, enemy.y, hero.x, hero.y) <= 1) return;
    const path = findPath(level, enemy.x, enemy.y,
      (x, y) => canEnemyStep(game, level, x, y),
      (x, y) => x === hero.x && y === hero.y);
    if (path !== null && path.length > 1 && path.length <= 20) moveEnemy(game, level, enemy, path[0].x, path[0].y);
    return;
  }
  // flee: der Schritt, der am weitesten vom Helden wegführt
  let bestX = enemy.x;
  let bestY = enemy.y;
  let bestDistance = distance(enemy.x, enemy.y, hero.x, hero.y);
  for (const direction of DIRECTIONS) {
    const nextX = enemy.x + direction[0];
    const nextY = enemy.y + direction[1];
    if (!canEnemyStep(game, level, nextX, nextY)) continue;
    const away = distance(nextX, nextY, hero.x, hero.y);
    if (away > bestDistance) {
      bestDistance = away;
      bestX = nextX;
      bestY = nextY;
    }
  }
  if (bestX !== enemy.x || bestY !== enemy.y) moveEnemy(game, level, enemy, bestX, bestY);
}

Die Unterschiede zu unserem Programm sind wenige, aber wichtig:

  • enemySeesHero benutzt die Sichtlinie (Bresenham aus der Lektion über die Karte), nicht die Länge eines Weges. Ein Gegner kann dich also durch eine offene Tür sehen, aber nicht durch eine Wand.
  • Ein Schläfer wacht mit 50 % Wahrscheinlichkeit pro Zug auf (rng.chance(50)), und ein Wanderer bewegt sich nur bei 4 von 5 Würfen (rng.nextInt(5)). Der Würfel kommt aus dem Generator des Spiels mit Seed, deshalb bleibt das Spiel wiederholbar.
  • lostTurns > 5, nicht 3. Der Weg ist mit path.length <= 20 begrenzt: Ein weiter entfernter Gegner jagt nicht.
  • Der Boss (warden) flieht nie, so verwundet er auch ist.
  • Die Meldungen (ai.wakes, ai.notices, ai.flees) werden nur geschrieben, wenn der Held den Gegner sieht: Das Spiel verrät nicht mehr, als du siehst.

Die Idee

Im Kampf: Nutzenbewertung

Auf der Karte hat ein Gegner einen Zustand. Im Kampf gibt es nichts zu laufen: Es gibt eine Wahl zwischen mehreren Aktionen, und sie muss vernünftig sein. Ein Automat würde hier eine Zeile für jedes Paar „Lage — Aktion“ bedeuten. Stattdessen bekommt jede Aktion eine Zahl: wie nützlich sie gerade ist. Der Gegner nimmt die größte.

Die Regel ist kurz: Der Standard ist ein Angriff mit 40. Jede andere mögliche Aktion hat ihren eigenen Wert: einen verwundeten Freund heilen 80, spucken 60. Ist ein Wert größer als der beste bisher, ersetzt die Aktion ihn.

class Chooser {
  constructor(attack) {
    this.best = attack;
    this.bestScore = 40;
    this.trace = attack + " 40";
  }


  consider(score, action) {
    this.trace += ", " + action + " " + score;
    if (score > this.bestScore) {
      this.best = action;
      this.bestScore = score;
    }
  }
}


function percent(a, b) {
  return Math.floor((a * 100) / b);
}


function chooseEnemyAction(hero, heroPoisoned, allies, healWait, spitWait) {
  const chooser = new Chooser("Angriff auf " + hero.name);
  let weakest = null;
  for (const ally of allies) {
    if (percent(ally.hp, ally.maxHp) < 50 && (weakest === null || percent(ally.hp, ally.maxHp) < percent(weakest.hp, weakest.maxHp))) {
      weakest = ally;
    }
  }
  if (weakest !== null && healWait === 0) chooser.consider(80, "heilt " + weakest.name);
  if (spitWait === 0 && !heroPoisoned) chooser.consider(60, "spuckt auf " + hero.name);
  return chooser;
}


function weakestOf(enemies) {
  let weakest = null;
  for (const enemy of enemies) {
    if (weakest === null || enemy.hp < weakest.hp) weakest = enemy;
  }
  return weakest;
}


function chooseHeroAction(hero, hasPotion, enemies) {
  const chooser = new Chooser("Angriff auf " + weakestOf(enemies).name);
  if (percent(hero.hp, hero.maxHp) < 35 && hasPotion) chooser.consider(90, "Trank");
  return chooser;
}


function show(chooser) {
  console.log(chooser.trace + " → " + chooser.best);
}

Das Programm zeigt sechs Entscheidungen. Jede Zeile ist: die betrachteten Aktionen mit ihren Werten, ein Pfeil und die gewählte.

const hero = { name: "Iva", hp: 30, maxHp: 40 };
const hurtHero = { name: "Iva", hp: 10, maxHp: 40 };
const woundedRat = { name: "Ratte", hp: 3, maxHp: 9 };
const rat = { name: "Ratte", hp: 9, maxHp: 9 };
const goblin = { name: "Goblin", hp: 16, maxHp: 16 };
const woundedGoblin = { name: "Goblin", hp: 6, maxHp: 16 };
const cultist = { name: "Kultist", hp: 3, maxHp: 20 };


show(chooseEnemyAction(hero, false, [woundedRat, goblin], 0, 0));
show(chooseEnemyAction(hero, false, [woundedRat, goblin], 2, 0));
show(chooseEnemyAction(hero, true, [rat, goblin], 0, 0));
show(chooseEnemyAction(hero, false, [woundedRat, woundedGoblin], 0, 3));
show(chooseHeroAction(hero, true, [woundedRat, goblin, cultist]));
show(chooseHeroAction(hurtHero, true, [woundedRat, goblin, cultist]));
Ausgabe
Angriff auf Iva 40, heilt Ratte 80, spuckt auf Iva 60 → heilt Ratte
Angriff auf Iva 40, spuckt auf Iva 60 → spuckt auf Iva
Angriff auf Iva 40 → Angriff auf Iva
Angriff auf Iva 40, heilt Ratte 80 → heilt Ratte
Angriff auf Ratte 40 → Angriff auf Ratte
Angriff auf Ratte 40, Trank 90 → Trank

Die ersten vier gehören dem Schamanen. Mit einer verwundeten Ratte und bereitem Heilen heilt er (80 > 60 > 40). Muss das Heilen warten (healWait ist 2), spuckt er (60). Ist der Held schon vergiftet und kein Freund verwundet, bleibt der Angriff (40). In der vierten Zeile sind sowohl die Ratte (33 %) als auch der Goblin (37 %) verwundet; der kleinere Prozentsatz wird geheilt, also die Ratte.

Die letzten beiden Zeilen gehören dem Helden auf Autopilot (in der Simulation des Spiels und im automatischen Kampf). Er schlägt den Schwächsten: den mit dem wenigsten Leben. Die Ratte (3) und der Kultist (3) sind gleich, und der erste gewinnt, weil < bei Gleichstand nicht ersetzt. Bei 25 % Leben (unter 35 %) und mit einem Trank übertrifft der Wert des Tranks (90) die 40, und der Held trinkt.

class Chooser {
  constructor(attack) {
    this.best = attack;
    this.bestScore = 40;
    this.trace = attack + " 40";
  }

  consider(score, action) {
    this.trace += ", " + action + " " + score;
    if (score  this.bestScore) {
      this.best = action;
      this.bestScore = score;
    }
  }
}

Die Zahlen 80, 60, 40 sind kein Gesetz. Sie sind eine Einstellung: Wenn der Schamane zu oft heilt, wird das Spiel langweilig, und wenn zu selten, unmöglich. Deshalb lässt die letzte Lektion (das ganze Spiel und die Balance) tausend Kämpfe laufen, um diese Zahlen einzustellen.

// Im Kampf bewertet die KI jede mögliche Aktion mit einer Zahl (Nutzen) und wählt
// die nützlichste: Sie heilt bei wenig Leben, nutzt eine Fähigkeit, wenn sie bereit ist, sonst greift sie an.
function chooseEnemyAction(battle, enemy) {
  const hero = battle.hero;
  let best = new AttackAction(enemy, hero);
  let bestScore = 40;
  const consider = (score, action) => {
    if (score > bestScore) {
      best = action;
      bestScore = score;
    }
  };
  const special = enemy.kind.special;
  if (special === 'shaman') {
    let weakest = null;
    for (const ally of battle.aliveEnemies()) {
      if (percent(ally.hp, ally.maxHp()) < 50 && (weakest === null || percent(ally.hp, ally.maxHp()) < percent(weakest.hp, weakest.maxHp()))) weakest = ally;
    }
    if (weakest !== null && enemy.cooldownOf('heal') === 0) consider(80, new SpecialAction(enemy, 'heal', weakest));
    if (enemy.cooldownOf('shaman') === 0 && !hero.hasEffect('poison')) consider(60, new SpecialAction(enemy, 'spit', hero));
  } else if (special === 'firebolt' && enemy.cooldownOf('firebolt') === 0) {
    consider(65, new SpecialAction(enemy, 'firebolt', hero));
  } else if (special === 'rend' && enemy.cooldownOf('rend') === 0 && !hero.hasEffect('bleed')) {
    consider(55, new SpecialAction(enemy, 'rend', hero));
  } else if (special === 'slam' && enemy.cooldownOf('slam') === 0) {
    consider(60, new SpecialAction(enemy, 'slam', hero));
  } else if (special === 'warden') {
    if (enemy.phase === 1 && enemy.hp * 2 < enemy.maxHp()) consider(100, new SpecialAction(enemy, 'summon', hero));
    else if (enemy.cooldownOf('warden') === 0) consider(60, new SpecialAction(enemy, 'slam', hero));
  }
  return best;
}


function usableSkills(hero) {
  const result = [];
  for (const skillId of hero.skills) {
    const skill = SKILLS.get(skillId);
    if (hero.mana >= skill.mana && hero.cooldownOf(skill.id) === 0) result.push(skill);
  }
  return result;
}


function weakestEnemy(battle) {
  let weakest = null;
  for (const enemy of battle.aliveEnemies()) {
    if (weakest === null || enemy.hp < weakest.hp) weakest = enemy;
  }
  return weakest;
}


// Der Held im Autopilot (die Simulation): dieselbe Nutzenbewertung.
function chooseHeroAction(battle) {
  const hero = battle.hero;
  const target = weakestEnemy(battle);
  let best = new AttackAction(hero, target);
  let bestScore = 40;
  const consider = (score, action) => {
    if (score > bestScore) {
      best = action;
      bestScore = score;
    }
  };
  const lifeShare = percent(hero.hp, hero.maxHp());
  if (lifeShare < 35 && hero.inventory.count('potion_heal') > 0) consider(90, new ItemAction(hero, 'potion_heal'));
  if ((hero.hasEffect('poison') || hero.hasEffect('bleed')) && lifeShare < 50 && hero.inventory.count('antidote') > 0) {
    consider(70, new ItemAction(hero, 'antidote'));
  }
  const many = battle.aliveEnemies().length >= 2;
  for (const skill of usableSkills(hero)) {
    let score = 0;
    if (skill.kind === 'heal') score = lifeShare < 50 ? 75 : 0;
    else if (skill.kind === 'buff') score = hero.hasEffect(skill.effect) ? 0 : 50;
    else if (skill.kind === 'debuff') score = many ? 55 : 45;
    else if (skill.target === 'all') score = many ? 65 : 52;
    else score = 55;
    consider(score, new SkillAction(hero, skill, target));
  }
  return best;
}

Der Kanon fügt mehr hinzu: den Feuerpfeil des Kultisten 65, Zerreißen 55 (nur wenn der Held noch nicht blutet), einen schweren Schlag 60 und den Boss, der unter halbem Leben Helfer mit dem Wert 100 herbeiruft. Aber die Form ist dieselbe: consider(Wert, Aktion). Die Aktionen sind Objekte aus der Lektion über Fähigkeiten und Aktionen als Befehle: AttackAction, SkillAction und so weiter. Deshalb wählen ein Gegner, ein Held auf Autopilot und eine Simulation auf dieselbe Weise.

Probier es aus

Sage die Ausgabe voraus

Eine kleine Karte mit einem Hindernis. Die Suche beginnt bei (1, 1). Was gibt das Programm aus?

const TINY = `
#######
#.#...#
#...#.#
#######`.trim();
const level = new Level(TINY);
printWave(level, distances(level, 1, 1));
Antwort

Probier es aus

Finde den Fehler

Ein Kollege hat die Suche verändert, und jetzt ist der Weg zum Helden länger:

const level = new Level(MAP);
const path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
console.log("der Feind (" + ENEMY_X + ", " + ENEMY_Y + "), der Held (" + HERO_X + ", " + HERO_Y + "): in gerader Linie " +
  distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", auf dem Weg " + path.length);
console.log("Der Weg zum Helden (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
Ausgabe
der Feind (8, 3), der Held (2, 3): in gerader Linie 6, auf dem Weg 12
Der Weg zum Helden (*):
################
#......#.......#
#......#.......#
#*@....#g......#
#*.....#*......#
#********......#
################

Der Weg ist 12 Schritte lang statt 10 und macht einen unnötigen Umweg. Welche Zeile nimmt die Zellen vom falschen Ende?

Wähle die Zeile mit dem Fehler.

Genauer

Genauer: A*, Felder und Schwachstellen

A*. Die Breitensuche schaut in alle Richtungen gleich, auch weit vom Ziel entfernt. A* fügt einen Hinweis hinzu: Für jede Zelle berechnet es f = g + h, wobei g die bisherigen Schritte sind und h eine Schätzung, wie viele noch bleiben (meist die Entfernung in gerader Linie entlang der Achsen). Es nimmt die Zelle mit dem kleinsten f, die also am vielversprechendsten aussieht. Man braucht eine Prioritätswarteschlange statt einer gewöhnlichen, und das Ergebnis ist derselbe kürzeste Weg, solange h nie überschätzt. Auf unserer Karte vom Goblin zum Helden nimmt die Breitensuche 59 Zellen aus der Warteschlange, A* nimmt 25. In einem offenen Raum, von (2, 2) nach (6, 2), sind es 19 gegenüber 5. Die Zahlen stammen aus dem Modell der Lektion (A* gibt es hier nicht in allen vier Sprachen). Der Kanon benutzt die Breitensuche: Die Ebenen sind 50 × 20, es gibt keine Bewegungskosten, und A* kostet eine Prioritätswarteschlange und mehr Code in vier Sprachen. Wenn flaches Wasser 2 kostet (die Lektion über die Karte), stimmt die Breitensuche nicht mehr, und man geht zu Dijkstra über; bei großen, offenen Ebenen zu A*.

Ein Feld statt eines Weges. Eine Suche vom Helden aus gibt für jede Zelle eine Zahl (die Welle dieser Karte). Dann geht jeder Gegner zum Nachbarn mit der kleinsten Zahl und sucht nicht selbst. Bei zwanzig Gegnern ist das eine Suche pro Zug statt zwanzig. Viele Spiele mit Horden machen es so. Zum Fliehen geht man andersherum: zur größten Zahl.

Fliehen ist dumm. Unser Flüchtling nimmt den Schritt, der die Entfernung am meisten vergrößert. In der Szene läuft er die untere Reihe entlang, aber in einer Ecke hat er keinen Zug mehr und bleibt stehen: Es gibt keinen Weg, der vorausdenkt. Kluges Fliehen folgt dem Entfernungsfeld (vom Helden aus), in dem das ganze Bild auf einmal sichtbar ist und die Ecke vermieden wird.

Ein Automat wächst mit seinen Übergängen. Jedes neue Verhalten ist ein neuer Zustand und Übergänge hinein und heraus (siehe die Aufgabe: guard und home sind zwei Zustände mit mehreren Übergängen). Die Nutzenbewertung wächst sanfter: Eine neue Aktion ist ein neues consider, ohne Übergänge.

Ein Wert ist eine grobe Zahl. Hier sind die Werte 40, 60, 80, von Hand geschrieben. Bessere Systeme multiplizieren mehrere „Erwägungen“ mit Kurven (wie verwundet er ist, wie weit weg, wie viel Mana er hat), und die Werte ändern sich fließend. Die Regel bleibt dieselbe: Die Zahl entscheidet, und die Entscheidung ist wiederholbar.

Übung

Der Wächter, der zurückgeht

Löse die Aufgabe in deinem Editor. Fang mit dem Programm des Automaten an.

Ein Wächter auf seinem Posten. Ändere den Automaten so, dass ein Gegner an seinem Platz im Zustand guard beginnt. Der Wächter steht und wandert nicht. Ist der Weg zum Helden höchstens 6 lang, geht er zu chase über. Er jagt auf dem Weg; wenn lost über 3 steigt, geht er zu home über und kehrt auf dem kürzesten Weg zu seinem Posten zurück (ein Schritt pro Zug), und wenn er ankommt, ist er wieder guard. Der Wächter hat kein sleep, wander und flee. Der Held schlägt nicht zu: Es gibt kein hit.

Die Karte ist dieselbe, der Wächter steht auf seinem Posten (8, 3), und der Ablauf ist dieser (Held, hit, hidden; der Held ist von Zug 4 bis Zug 12 verborgen):

const SCRIPT = [
  [3, 5, 0, false],
  [4, 5, 0, false],
  [4, 5, 0, false],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
];

Die Ausgabe ist:

Ausgabe
Zug 1: guard, Feind (8, 3), Weg 7, Leben 16
Zug 2: guard → chase, Feind (8, 3), Weg 6, Leben 16
Zug 3: chase, Feind (8, 4), Weg 5, Leben 16
Zug 4: chase, Feind (8, 5), Weg 4, Leben 16
Zug 5: chase, Feind (7, 5), Weg 3, Leben 16
Zug 6: chase, Feind (6, 5), Weg 2, Leben 16
Zug 7: chase → home, Feind (6, 5), Weg 2, Leben 16
Zug 8: home, Feind (7, 5), Weg 3, Leben 16
Zug 9: home, Feind (8, 5), Weg 4, Leben 16
Zug 10: home, Feind (8, 4), Weg 5, Leben 16
Zug 11: home → guard, Feind (8, 3), Weg 6, Leben 16
Zug 12: guard, Feind (8, 3), Weg 6, Leben 16

Weitere Aufgaben

  • Ruhe. Im Kanon wechseln die Gegner nach einer Flucht aus einem Kampf zu wander mit calm = 6: Solange calm über 0 ist, bemerken sie den Helden nicht. Füge dem Gegner einen Zähler calm hinzu, der in jedem Zug verringert wird.
  • Um einen anderen Gegner herumgehen. Gib findPath eine Liste besetzter Zellen (die anderen Gegner) und behandle sie wie Wände. Was passiert, wenn zwei Gegner den Helden in einem engen Gang jagen?
  • Ein Entfernungsfeld. Löse die Jagd ohne findPath: Lass distances vom Helden aus laufen, und der Gegner geht zum Nachbarn mit der kleinsten Zahl. Wie viele Suchen pro Zug sind das bei fünf Gegnern, und wie viele mit findPath?

Test

Teste dich

1. Dieselbe Wegsuche nimmt Zellen vom Anfang der Liste (eine Warteschlange) oder von ihrem Ende (ein Stapel). Mit einer Warteschlange ist der Weg zum Helden 10 Schritte lang, mit einem Stapel 12. Warum?
2. Der Goblin schläft, der Held ist auf der anderen Seite der Wand, in gerader Linie 4 Zellen entfernt, und der Weg um die Wand ist 6 lang. Die Schwelle zum Aufwachen ist 5. Warum wacht der Goblin nicht auf?
3. Der Goblin jagt, und der Held verschwindet aus seiner Sicht. In welchem Zug ohne Sicht hört der Goblin auf zu jagen und fängt an zu wandern (LOST = 3)?
4. Bei der Nutzenbewertung hat der Gegner einen Angriff (40) und zwei weitere Aktionen mit 40 und 60. Welche wählt er, und was passiert, wenn zwei Aktionen den gleichen höchsten Wert haben?
5. Warum berechnet der Goblin den Weg in jedem Zug neu, statt sich den alten zu merken?

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