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

Врагове, които мислят

Накратко: Врагът на картата е краен автомат (спи, броди, гони, бяга), който гони по най-краткия път, намерен с търсене в ширина; в боя избира действието с най-висока оценка на полезността.

Проблем

Гоблинът, който се блъска в стената

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

Най-простото гонене е: „направи стъпката, която най-много те приближава до героя“. Ето гоблин (g) и герой (@) от двете страни на стена с процеп долу:

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

По права линия са 6 клетки, но стената е между тях. Простото гонене сравнява само разстоянието: гоблинът иска да отиде наляво, там е стена, и той стои залепен за нея. Ето къде спира:

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

Правата линия не знае за стените. Трябва път, който ги заобикаля, и най-краткият път на решетка се намира с търсене в ширина. Урокът първо го строи на малкото ниво 16 × 7 (процепът е долу), после слага над него краен автомат, който решава кога врагът ходи, и накрая показва втория мозък на играта: оценката на полезността в боя.

Идеята

Вълната: колко стъпки е всяка клетка

Представи си, че пуснеш камък във вода: кръгове се разширяват от мястото, където е паднал. Търсенето в ширина прави същото по решетката. Тръгва от гоблина: той е на разстояние 0. Съседите му са на 1. Съседите на съседите (още невиждани) са на 2. И така нататък, докато вълната не покрие всичко. Всяка клетка получава число: колко стъпки е от гоблина по пода, не по права линия.

Нужна е опашка: клетките, които вълната е достигнала, но още не е разгледала. От началото на опашката се вади най-старата клетка (затова вълната върви по ред), а нейните нови съседи отиват в края. Клетка, която вече има число, не се добавя втори път.

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


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


// Вълната: колко стъпки е всяка клетка от старта.
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("Вълната от врага (a = 10, b = 11, ...):");
printWave(level, dist);
Изход
Вълната от врага (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################

a е 10, b е 11 и така нататък. Гоблинът е на 0 (до стената, в лявия край на дясната стая), а стената е #. Вълната първо пълни дясната стая, после минава през процепа долу и чак тогава се качва в лявата. Героят на (2, 3) е на a, т.е. на 10 стъпки от гоблина, макар че по права линия е на 6: числото е истинското разстояние по пода.

Не ползваме shift(): вадене от началото на масив мести всички останали елементи, затова вместо него се върви с индекс head.

Проверката dist[nextY][nextX] != -1 е целият „вече беше“: клетката е получила число, значи е в опашката или е била в нея. Без нея вълната би се връщала назад и никога нямаше да свърши.

По-точно, за любопитните

Четирите посоки са в постоянен ред: горе, дясно, долу, ляво. Редът не променя разстоянията (те са еднакви при всеки ред), но променя кой от равните пътища ще се намери. В играта редът е постоянен точно за това: един и същ вход трябва да дава един и същ път на Java, C#, Python и JavaScript, иначе записът на боя и проверката със записаното минаване ще се разминават.

Тази вълна от разстояния се казва поле на разстоянията (distance field, Dijkstra map): едно търсене от героя дава число за всяка клетка, а всеки враг просто стъпва към съседа с по-малко число. При много врагове това е много по-евтино от търсене за всеки.

Идеята

Пътят: откъде е дошла всяка клетка

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

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("врагът (" + ENEMY_X + ", " + ENEMY_Y + "), героят (" + HERO_X + ", " + HERO_Y + "): по права линия " +
  distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", по пътя " + path.length);
const dist = distances(level, ENEMY_X, ENEMY_Y);
console.log("Вълната от врага (a = 10, b = 11, ...):");
printWave(level, dist);
console.log("Пътят до героя (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
Изход
врагът (8, 3), героят (2, 3): по права линия 6, по пътя 10
Вълната от врага (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################
Пътят до героя (*):
################
#......#.......#
#......#.......#
#.@****#g......#
#.....*#*......#
#.....***......#
################

Пътят (*) слиза през процепа, качва се покрай стената в лявата стая и върви наляво до героя: 10 стъпки срещу 6 по права линия. Стената не пречи на алгоритъма, защото вълната просто не влиза в нея.

Търсенето спира още щом извади целта от опашката: после не му трябва. Затова първата намерена цел е най-близката. И ако няма път (героят е зад стена без процеп), опашката свършва и функцията връща null.

По-точно, за любопитните

Първата стъпка на пътя е само една клетка, но врагът я прави и пита наново на следващия ход. Така той не може да „залепне“ за стар път: героят се е преместил, друг враг е заел клетката, вратата се е затворила.

Цената е ниска. Нивото на играта е 50 × 20, до около 1000 клетки, и дори да се обходят всичките, това са хиляди прости проверки на ход на враг.

Идеята

Краен автомат: спи, броди, гони, бяга

Кога врагът ползва пътя? Зависи от това, какъв е сега. Спящият не мърда. Скитникът се лута. Гонещият върви по пътя. Бягащият се отдалечава. Това е краен автомат: враг има състояние (низ: "sleep", "wander", "chase", "flee"), а всеки ход се казва „в това състояние, при това положение, какво правя и към кое състояние минавам“.

От Към Кога
sleep chase пътят до героя е най-много 5
wander chase враг „вижда“ героя: пътят е най-много 8
chase wander повече от 3 хода без поглед (lost > LOST)
chase flee живот × 4 < най-много живот (под една четвърт)

Програмата ползва същата карта и враг със 16 живот. „Вижда“ е опростено: враг вижда героя, ако пътят до него е най-много 8. В играта това е линия на погледа от урока за картата (до 8 клетки), а тук пътят дава същото без още един алгоритъм. Сценарият е в SCRIPT: героят се приближава, скрива се зад ъгъл (hidden), показва се пак и накрая го удрят (hit).

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


// Врагът „вижда“ героя, ако пътят до него е кратък (в играта: линия на погледа от урока за картата).
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;
    }
    // Броди по ред на посоките (в играта се хвърля зарче).
    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;
  }
  // Бяга: стъпката, която най-много го отдалечава от героя.
  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;
}

Всяко състояние е клон на едно if, който връща в края си: на един ход се случва точно едно нещо. Чете се отгоре надолу като таблицата. Броячът lost е паметта на автомата: без него врагът би забравял героя още при първото скриване.

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("ход " + (i + 1) + ": " + state + ", враг (" + enemy.x + ", " + enemy.y + "), път " + length + ", живот " + enemy.life);
});
Изход
ход 1: sleep, враг (8, 3), път 7, живот 16
ход 2: sleep, враг (8, 3), път 6, живот 16
ход 3: sleep → chase, враг (8, 3), път 5, живот 16
ход 4: chase, враг (8, 4), път 4, живот 16
ход 5: chase, враг (8, 5), път 3, живот 16
ход 6: chase, враг (7, 5), път 2, живот 16
ход 7: chase, враг (6, 5), път 1, живот 16
ход 8: chase → wander, враг (6, 5), път 1, живот 16
ход 9: wander, враг (7, 5), път 2, живот 16
ход 10: wander → chase, враг (7, 5), път 2, живот 16
ход 11: chase, враг (6, 5), път 1, живот 16
ход 12: chase → flee, враг (6, 5), път 1, живот 3
ход 13: flee, враг (7, 5), път 2, живот 3
ход 14: flee, враг (8, 5), път 3, живот 3
ход 15: flee, враг (9, 5), път 4, живот 3

Ход 3: пътят става 5 и sleep → chase. Ходове 4–7: гоблинът върви по пътя. На ход 8 lost надвишава 3 и той минава на wander; на ход 9 прави стъпка като скитник, а на ход 10 пак вижда героя. На ход 12 героят го удря и му отнема 13 от 16 живот: 3 × 4 = 12 < 16 и chase → flee. Бягането не ползва пътя: от четирите съседа взима този, който най-много го отдалечава (away > bestDistance).

По-точно, за любопитните

Защо низове, а не enum? Канонът ползва низове, защото състоянията се пишат в записа на играта (урокът за записа) и се четат от файл. Така нов вид враг с ново състояние не иска нов тип. Цената е, че грешка в името ("chaes") не се хваща при компилиране.

Автоматът е най-простият начин да се опише поведение, но расте: десет състояния с по пет прехода са петдесет реда, които трудно се четат. Тогава се минава на дърво на поведение (behavior tree) или на оценка на полезността, каквато има в боя по-долу.

Виж го

Гонене в действие

Ето същото по ходове. Гоблинът спи от другата страна на стената. Героят се приближава; пътят става 5 и гоблинът се събужда. Тогава се вижда търсенето: вълната тръгва от гоблина и заобикаля стената през процепа, докато стигне героя. После гоблинът върви, губи героя, пак го забелязва и накрая бяга.

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 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;
    }
    // Броди по ред на посоките (в играта се хвърля зарче).
    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;
  }
  // Бяга: стъпката, която най-много го отдалечава от героя.
  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;
}
Стъпка по стъпка, с думи
  1. Гоблинът спи на (8, 3). Героят е от другата страна на стената. На ход 2 пътят до него е 6, а събуждането иска най-много 5: гоблинът продължава да спи, макар че по права линия героят е на 4 клетки.
  2. Ход 3: героят е на (6, 4). По права линия е на 3 клетки, през стената, но пътят е 5 ≤ 5: sleep → chase.
  3. Търсене в ширина от гоблина: опашка, а от нея се вади най-старата клетка. Вълната се разлива по пода, клетка по клетка, и заобикаля стената през процепа. Вадят се 27 от 66 клетки, докато се стигне героя.
  4. Героят е намерен. От него се върви назад през cameFrom, клетка по клетка до гоблина, и пътят се обръща: 5 стъпки. Гоблинът ще направи първата.
  5. Всеки ход гоблинът пита наново и прави само първата стъпка от пътя: 4, 3, 2, 1 до героя. Ако героят се мръдне, пътят е друг.
  6. Героят се скрива зад ъгъла (бледото топче). Гоблинът още върви към него, но брои: след 3 хода без поглед (lost > 3) на ход 8 става chase → wander.
  7. Ход 9: гоблинът броди. Посоката е по ред (в играта се хвърля зарче) и стъпката е случайна за героя, не за гоблина.
  8. Ход 10: героят се показва, пътят е 2 ≤ 8: wander → chase. Гоблинът пак гони и стига до героя.
  9. Ход 12: ударът на героя оставя на гоблина 3 от 16 живот. Проверката е живот × 4 < най-много живот: 12 < 16, затова chase → flee.
  10. Бягането няма път и няма търсене: от четирите съседа се взима този, който най-много го отдалечава от героя (2, 3, 4 клетки).

Кодът до сцената е findPath и enemyTurn от програмата. На всяка стъпка светят редовете, които работят в този момент.

Идеята

В играта

Това, което построихме, е същото като в канона, само по-малко. Ето истинското търсене в ширина. Тя приема две функции вместо готова цел и готова карта на проходимостта: isPassable казва къде може да стъпи враг (не през други врагове и не през героя), а isGoal — коя е целта:

// Търсене в ширина: опашка от клетки, всяка помни откъде е дошла. Първата намерена цел е
// най-близката. Посоките са в постоянен ред (горе, дясно, долу, ляво), затова пътят е еднакъв
// на всеки език.
const DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]];


// isPassable(x, y) и isGoal(x, y) са функции; връща пътя без началото или 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);
}

А ето автомата на картата. Освен нашите състояния има guard (пазач на пост), calm (след като героят избяга от бой, враговете броди и 6 хода не го забелязват) и зарче за събуждането:

// Изкуственият интелект на картата е краен автомат: спи → броди → гони → бяга при малко живот.
// Пазачът стои на пост (guard), докато не види героя.
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: стъпка, която отдалечава най-много от героя
  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);
}

Разликите от нашата програма са малко, но важни:

  • enemySeesHero ползва линията на погледа (Bresenham от урока за картата), а не дължината на пътя. Затова враг може да те види през отворена врата, но не през стена.
  • Спящият се събужда с шанс 50% на ход (rng.chance(50)), а скитникът се мърда само в 4 от 5 хвърляния на зарче (rng.nextInt(5)). Зарчето е от генератора със семе на играта, затова играта остава повторяема.
  • lostTurns > 5, а не 3. Пътят се ограничава с path.length <= 20: по-далечен враг не гони.
  • Шефът (warden) не бяга, колкото и да е ранен.
  • Съобщенията (ai.wakes, ai.notices, ai.flees) се пишат само ако героят вижда врага: играта не издава повече, отколкото виждаш.

Идеята

В боя: оценка на полезността

На картата врагът има състояние. В боя няма къде да се върви: има избор между няколко действия и той трябва да е разумен. Автоматът тук би означавал по един ред за всяка двойка „положение — действие“. Вместо това всяко действие получава число: колко е полезно сега. Врагът взима най-голямото.

Правилото е кратко: удар по подразбиране е 40. Всяко друго възможно действие има своя оценка: лекуване на ранен приятел 80, плюнка 60. Ако оценката е по-голяма от най-добрата досега, действието я заменя.

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("удар " + 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, "лекува " + weakest.name);
  if (spitWait === 0 && !heroPoisoned) chooser.consider(60, "плюе " + 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("удар " + weakestOf(enemies).name);
  if (percent(hero.hp, hero.maxHp) < 35 && hasPotion) chooser.consider(90, "отвара");
  return chooser;
}


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

Програмата показва шест решения. Всеки ред е: разгледаните действия с оценките им, стрелка и избраното.

const hero = { name: "Ива", hp: 30, maxHp: 40 };
const hurtHero = { name: "Ива", hp: 10, maxHp: 40 };
const woundedRat = { name: "плъх", hp: 3, maxHp: 9 };
const rat = { name: "плъх", hp: 9, maxHp: 9 };
const goblin = { name: "гоблин", hp: 16, maxHp: 16 };
const woundedGoblin = { name: "гоблин", hp: 6, maxHp: 16 };
const cultist = { name: "култист", 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]));
Изход
удар Ива 40, лекува плъх 80, плюе Ива 60 → лекува плъх
удар Ива 40, плюе Ива 60 → плюе Ива
удар Ива 40 → удар Ива
удар Ива 40, лекува плъх 80 → лекува плъх
удар плъх 40 → удар плъх
удар плъх 40, отвара 90 → отвара

Първите четири са на шамана. С ранен плъх и готово лекуване той лекува (80 > 60 > 40). Ако лекуването чака (healWait е 2), плюе (60). Ако героят вече е отровен и никой приятел не е ранен, остава ударът (40). Четвъртият ред: ранени са и плъхът (33%), и гоблинът (37%); лекува се по-малкият процент, т.е. плъхът.

Последните два реда са на героя на автопилот (в симулацията на играта и при автоматичен бой). Той удря най-слабия: този с най-малко живот. Плъхът (3) и култистът (3) са равни и печели първият, защото < не сменя при равенство. При 25% живот (под 35%) и с отвара оценката на отварата (90) надвиша 40 и героят пие.

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;
    }
  }
}

Числата 80, 60, 40 не са закон. Те са настройка: ако шаманът лекува твърде често, играта става скучна, а ако рядко, невъзможна. Затова последният урок (цялата игра и балансът) пуска хиляда боя, за да се нагласят тези числа.

// В боя изкуственият интелект оценява всяко възможно действие с число (полезност) и избира
// най-полезното: лекува се при малко живот, ползва умение, когато е готово, иначе удря.
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;
}


// Героят на автопилот (симулацията): същата оценка на полезността.
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;
}

Канонът добавя повече: огнена стрела на култиста 65, раздиране 55 (само ако героят още не кърви), тежък удар 60 и шефът, който под половин живот призовава помощници с оценка 100. Но формата е същата: consider(оценка, действие). Действията са обекти от урока за умения и действия като команди: AttackAction, SkillAction и т.н. Затова враг, герой на автопилот и симулация избират по един и същи начин.

Пробвай

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

Малка карта с препятствие. Търсенето започва от (1, 1). Какво печата програмата?

const TINY = `
#######
#.#...#
#...#.#
#######`.trim();
const level = new Level(TINY);
printWave(level, distances(level, 1, 1));
Отговор

Пробвай

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

Колега промени търсенето и сега пътят до героя е по-дълъг:

const level = new Level(MAP);
const path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
console.log("врагът (" + ENEMY_X + ", " + ENEMY_Y + "), героят (" + HERO_X + ", " + HERO_Y + "): по права линия " +
  distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", по пътя " + path.length);
console.log("Пътят до героя (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
Изход
врагът (8, 3), героят (2, 3): по права линия 6, по пътя 12
Пътят до героя (*):
################
#......#.......#
#......#.......#
#*@....#g......#
#*.....#*......#
#********......#
################

Пътят е 12 стъпки вместо 10 и прави излишна обиколка. Кой ред взима клетките от грешния край?

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

По-точно

По-точно: A*, полета и слабите места

A*. Търсенето в ширина гледа във всички посоки еднакво, дори далеч от целта. A* му добавя подсказка: за всяка клетка смята f = g + h, където g са стъпките досега, а h е оценка колко остава (най-често разстоянието по права линия по осите). Вади се клетката с най-малко f, т.е. тази, която изглежда най-обещаваща. Нужна е приоритетна опашка вместо обикновена, а резултатът е същият най-къс път, стига h да не надценява. На нашата карта от гоблина до героя търсенето в ширина вади 59 клетки, A* — 25. В отворена стая, от (2, 2) до (6, 2), е 19 срещу 5. Числата са от модела на урока (A* не е на четирите езика тук). Канонът ползва търсене в ширина: нивата са 50 × 20, няма цени на движение, а A* струва приоритетна опашка и още код на четири езика. Ако плитката вода струва 2 (урокът за картата), BFS вече не е вярно и се минава на Dijkstra; ако нивата са големи и открити, на A*.

Полето вместо път. Едно търсене от героя дава число за всяка клетка (вълната от тази карта). Тогава всеки враг стъпва към съседа с най-малко число и не търси сам. При двадесет врагове това е едно търсене на ход вместо двадесет. Така правят много игри с орди. За бягане върви по обратното число: към най-голямото.

Бягането е глупаво. Нашият беглец взима стъпката, която най-много увеличава разстоянието. В сцената той побягва по долния ред, но в ъгъл остава без ход и стои: няма път, който да мисли напред. Умното бягане върви по полето на разстоянията (от героя), където цялото число се вижда наведнъж и ъгълът се избягва.

Автоматът расте с преходите. Всяко ново поведение е ново състояние и преходи към него и от него (виж упражнението: guard и home са две състояния с няколко прехода). Оценката на полезността расте по-леко: ново действие е ново consider, без преходи.

Оценката е грубо число. Тук оценките са 40, 60, 80, написани на ръка. По-добрите системи умножават няколко „съображения“ с криви (колко е ранен, колко е далеч, колко мана има) и оценките се менят плавно. Правилото остава същото: числото решава, а решението е повторяемо.

Упражнение

Пазачът, който се връща

Реши задачата в редактора си. Тръгни от програмата за автомата.

Пазач на пост. Промени автомата така, че враг да започва в състояние guard на мястото си. Пазачът стои и не броди. Когато пътят до героя е най-много 6, минава на chase. Гони по пътя; ако lost надхвърли 3, минава на home и се връща на поста си по най-краткия път (стъпка на ход), а когато стигне, пак е guard. Пазачът няма sleep, wander и flee. Героят не удря: няма hit.

Картата е същата, пазачът е на поста си (8, 3), а сценарият е този (героят, hit, hidden; героят е скрит от 4-ия до 12-ия ход):

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],
];

Изходът е:

Изход
ход 1: guard, враг (8, 3), път 7, живот 16
ход 2: guard → chase, враг (8, 3), път 6, живот 16
ход 3: chase, враг (8, 4), път 5, живот 16
ход 4: chase, враг (8, 5), път 4, живот 16
ход 5: chase, враг (7, 5), път 3, живот 16
ход 6: chase, враг (6, 5), път 2, живот 16
ход 7: chase → home, враг (6, 5), път 2, живот 16
ход 8: home, враг (7, 5), път 3, живот 16
ход 9: home, враг (8, 5), път 4, живот 16
ход 10: home, враг (8, 4), път 5, живот 16
ход 11: home → guard, враг (8, 3), път 6, живот 16
ход 12: guard, враг (8, 3), път 6, живот 16

Още задачи

  • Спокойствие. В канона след бягство от бой враговете минават на wander с calm = 6: докато calm е над 0, не забелязват героя. Добави брояч calm на врага, намаляван на ход.
  • Заобикаляне на друг враг. Дай на findPath списък със заети клетки (другите врагове) и ги прескачай като стени. Какво става, ако двама врагове гонят героя в тесен коридор?
  • Поле на разстоянията. Реши гонитбата без findPath: пусни distances от героя и нека врагът стъпва към съседа с най-малко число. Колко търсения на ход са това при пет врага и колко с findPath?

Тест

Провери се

1. Едно и също търсене на път взима клетките от началото на списъка (опашка) или от края му (стек). С опашка пътят до героя е 10 стъпки, със стек е 12. Защо?
2. Гоблинът спи, героят е от другата страна на стената на 4 клетки по права линия, а пътят около стената е 6. Прагът за събуждане е 5. Защо гоблинът не се събужда?
3. Гоблинът гони, а героят се скрива от погледа му. На кой ход без поглед гоблинът спира да гони и започва да броди (LOST = 3)?
4. В оценката на полезността врагът има удар (40) и още две действия с оценка 40 и 60. Кое избира и какво става, ако две действия имат равни най-високи оценки?
5. Защо гоблинът смята пътя наново на всеки ход, а не помни стария?

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