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

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

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

Проблем

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

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

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

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

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

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

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

Идеята

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

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

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

static final String MAP = """
    ################
    #......#.......#
    #......#.......#
    #......#.......#
    #......#.......#
    #..............#
    ################""";


static final int[][] DIRECTIONS = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };


// Вълната: колко стъпки е всяка клетка от старта.
static int[][] distances(Level level, int startX, int startY) {
    int[][] dist = new int[level.height][level.width];
    for (int[] row : dist) Arrays.fill(row, -1);
    dist[startY][startX] = 0;
    List<Step> queue = new ArrayList<>(List.of(new Step(startX, startY)));
    int head = 0;
    while (head < queue.size()) {
        Step cell = queue.get(head);
        head++;
        for (int[] direction : DIRECTIONS) {
            int nextX = cell.x() + direction[0];
            int nextY = cell.y() + direction[1];
            if (!level.walkable(nextX, nextY) || dist[nextY][nextX] != -1) continue;
            dist[nextY][nextX] = dist[cell.y()][cell.x()] + 1;
            queue.add(new Step(nextX, nextY));
        }
    }
    return dist;
}
Level level = new Level(MAP);
int[][] dist = distances(level, ENEMY_X, ENEMY_Y);
System.out.println("Вълната от врага (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: числото е истинското разстояние по пода.

Step е запис (record) с x и y. Опашката е List<Step>, а индексът head сочи следващата клетка за вадене: нищо не се трие от списъка, затова не се мести нищо.

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

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

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

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

Идеята

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

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

static List<Step> findPath(Level level, int startX, int startY, int goalX, int goalY) {
    int[] cameFrom = new int[level.width * level.height];
    Arrays.fill(cameFrom, -1);
    int start = startY * level.width + startX;
    cameFrom[start] = start;
    List<Integer> queue = new ArrayList<>(List.of(start));
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        int x = current % level.width;
        int y = current / level.width;
        if (current != start && x == goalX && y == goalY) {
            List<Step> path = new ArrayList<>();
            int index = current;
            while (index != start) {
                path.add(new Step(index % level.width, index / level.width));
                index = cameFrom[index];
            }
            Collections.reverse(path);
            return path;
        }
        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (!level.walkable(nextX, nextY)) continue;
            int next = nextY * level.width + nextX;
            if (cameFrom[next] != -1) continue;
            cameFrom[next] = current;
            queue.add(next);
        }
    }
    return null;
}


static int distance(int ax, int ay, int bx, int by) {
    return Math.abs(ax - bx) + Math.abs(ay - by);
}
Level level = new Level(MAP);
List<Step> path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
System.out.println("врагът (" + ENEMY_X + ", " + ENEMY_Y + "), героят (" + HERO_X + ", " + HERO_Y + "): по права линия "
        + distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", по пътя " + path.size());
int[][] dist = distances(level, ENEMY_X, ENEMY_Y);
System.out.println("Вълната от врага (a = 10, b = 11, ...):");
printWave(level, dist);
System.out.println("Пътят до героя (*):");
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).

static final int SIGHT = 8;
static final int WAKE = 5;
static final int LOST = 3;
static final int FAR = 20;
static final int NONE = 99;
static final int ENEMY_LIFE = 16;


// Врагът „вижда“ героя, ако пътят до него е кратък (в играта: линия на погледа от урока за картата).
static void enemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, boolean hidden) {
    List<Step> path = findPath(level, enemy.x, enemy.y, heroX, heroY);
    int pathLength = path == null ? NONE : path.size();
    boolean sees = !hidden && pathLength <= SIGHT;
    if (enemy.state.equals("sleep")) {
        if (sees && pathLength <= WAKE) enemy.state = "chase";
        return;
    }
    if (enemy.state.equals("wander")) {
        if (sees) {
            enemy.state = "chase";
            enemy.lost = 0;
            return;
        }
        // Броди по ред на посоките (в играта се хвърля зарче).
        int[] direction = DIRECTIONS[turn % 4];
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (level.walkable(nextX, nextY) && !(nextX == heroX && nextY == heroY)) {
            enemy.x = nextX;
            enemy.y = nextY;
        }
        return;
    }
    if (enemy.state.equals("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.get(0).x();
            enemy.y = path.get(0).y();
        }
        return;
    }
    // Бяга: стъпката, която най-много го отдалечава от героя.
    int bestX = enemy.x;
    int bestY = enemy.y;
    int bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
    for (int[] direction : DIRECTIONS) {
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (!level.walkable(nextX, nextY) || (nextX == heroX && nextY == heroY)) continue;
        int away = distance(nextX, nextY, heroX, heroY);
        if (away > bestDistance) {
            bestDistance = away;
            bestX = nextX;
            bestY = nextY;
        }
    }
    enemy.x = bestX;
    enemy.y = bestY;
}

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

Level level = new Level(MAP);
Enemy enemy = new Enemy(ENEMY_X, ENEMY_Y, "sleep", ENEMY_LIFE);
for (int i = 0; i < SCRIPT.length; i++) {
    Turn turn = SCRIPT[i];
    enemy.life = Math.max(0, enemy.life - turn.hit());
    String before = enemy.state;
    enemyTurn(level, enemy, turn.heroX(), turn.heroY(), i + 1, turn.hidden());
    List<Step> path = findPath(level, enemy.x, enemy.y, turn.heroX(), turn.heroY());
    int length = path == null ? NONE : path.size();
    String state = before.equals(enemy.state) ? before : before + " → " + enemy.state;
    System.out.println("ход " + (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 и гоблинът се събужда. Тогава се вижда търсенето: вълната тръгва от гоблина и заобикаля стената през процепа, докато стигне героя. После гоблинът върви, губи героя, пак го забелязва и накрая бяга.

static List<Step> findPath(Level level, int startX, int startY, int goalX, int goalY) {
    int[] cameFrom = new int[level.width * level.height];
    Arrays.fill(cameFrom, -1);
    int start = startY * level.width + startX;
    cameFrom[start] = start;
    List<Integer> queue = new ArrayList<>(List.of(start));
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        int x = current % level.width;
        int y = current / level.width;
        if (current != start && x == goalX && y == goalY) {
            List<Step> path = new ArrayList<>();
            int index = current;
            while (index != start) {
                path.add(new Step(index % level.width, index / level.width));
                index = cameFrom[index];
            }
            Collections.reverse(path);
            return path;
        }
        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (!level.walkable(nextX, nextY)) continue;
            int next = nextY * level.width + nextX;
            if (cameFrom[next] != -1) continue;
            cameFrom[next] = current;
            queue.add(next);
        }
    }
    return null;
}


// Врагът „вижда“ героя, ако пътят до него е кратък (в играта: линия на погледа от урока за картата).
static void enemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, boolean hidden) {
    List<Step> path = findPath(level, enemy.x, enemy.y, heroX, heroY);
    int pathLength = path == null ? NONE : path.size();
    boolean sees = !hidden && pathLength <= SIGHT;
    if (enemy.state.equals("sleep")) {
        if (sees && pathLength <= WAKE) enemy.state = "chase";
        return;
    }
    if (enemy.state.equals("wander")) {
        if (sees) {
            enemy.state = "chase";
            enemy.lost = 0;
            return;
        }
        // Броди по ред на посоките (в играта се хвърля зарче).
        int[] direction = DIRECTIONS[turn % 4];
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (level.walkable(nextX, nextY) && !(nextX == heroX && nextY == heroY)) {
            enemy.x = nextX;
            enemy.y = nextY;
        }
        return;
    }
    if (enemy.state.equals("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.get(0).x();
            enemy.y = path.get(0).y();
        }
        return;
    }
    // Бяга: стъпката, която най-много го отдалечава от героя.
    int bestX = enemy.x;
    int bestY = enemy.y;
    int bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
    for (int[] direction : DIRECTIONS) {
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (!level.walkable(nextX, nextY) || (nextX == heroX && nextY == heroY)) continue;
        int 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 — коя е целта:

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


// Проверка за клетка: isPassable(x, y) и isGoal(x, y).
interface CellTest {
    boolean test(int x, int y);
}


static class Step {
    int x;
    int y;


    Step(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


// isPassable(x, y) и isGoal(x, y) са функции; връща пътя без началото или null.
static List<Step> findPath(Level level, int startX, int startY, CellTest isPassable, CellTest isGoal) {
    int[] cameFrom = new int[level.width * level.height];
    java.util.Arrays.fill(cameFrom, -1);
    int startIndex = startY * level.width + startX;
    cameFrom[startIndex] = startIndex;
    List<Integer> queue = new ArrayList<>(List.of(startIndex));
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        int x = current % level.width;
        int y = current / level.width;
        if (current != startIndex && isGoal.test(x, y)) {
            List<Step> path = new ArrayList<>();
            int index = current;
            while (index != startIndex) {
                path.add(new Step(index % level.width, index / level.width));
                index = cameFrom[index];
            }
            java.util.Collections.reverse(path);
            return path;
        }
        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (!level.inBounds(nextX, nextY)) continue;
            int nextIndex = nextY * level.width + nextX;
            if (cameFrom[nextIndex] != -1) continue;
            if (!isPassable.test(nextX, nextY) && !isGoal.test(nextX, nextY)) continue;
            cameFrom[nextIndex] = current;
            queue.add(nextIndex);
        }
    }
    return null;
}


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

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

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


static boolean canEnemyStep(Game game, Level level, int x, int 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);
}


static void moveEnemy(Game game, Level level, Enemy enemy, int x, int y) {
    if (enemy.hasEffect("bleed")) level.addBlood(enemy.x, enemy.y);
    enemy.x = x;
    enemy.y = y;
}


static void enemyTurnOnMap(Game game, Level level, Enemy enemy) {
    Hero hero = game.hero;
    Random rng = game.rng;
    boolean sees = enemySeesHero(level, enemy, hero);
    boolean heroSeesIt = level.visible[enemy.y][enemy.x];
    if (enemy.calm > 0) enemy.calm -= 1;
    if (enemy.state.equals("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.equals("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.equals("wander")) {
        if (sees && enemy.calm == 0) {
            enemy.state = "chase";
            enemy.lostTurns = 0;
            if (heroSeesIt) game.say(t("ai.notices", "name", enemy.name));
            return;
        }
        int roll = rng.nextInt(5);
        if (roll < 4) {
            int nextX = enemy.x + DIRECTIONS[roll][0];
            int nextY = enemy.y + DIRECTIONS[roll][1];
            if (canEnemyStep(game, level, nextX, nextY)) moveEnemy(game, level, enemy, nextX, nextY);
        }
        return;
    }
    if (enemy.state.equals("chase")) {
        if (!enemy.kind.special.equals("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;
        List<Step> 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.size() > 1 && path.size() <= 20) moveEnemy(game, level, enemy, path.get(0).x, path.get(0).y);
        return;
    }
    // flee: стъпка, която отдалечава най-много от героя
    int bestX = enemy.x;
    int bestY = enemy.y;
    int bestDistance = distance(enemy.x, enemy.y, hero.x, hero.y);
    for (int[] direction : DIRECTIONS) {
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (!canEnemyStep(game, level, nextX, nextY)) continue;
        int 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 {
    String best;
    int bestScore = 40;
    String trace;


    Chooser(String attack) {
        best = attack;
        trace = attack + " 40";
    }


    void consider(int score, String action) {
        trace += ", " + action + " " + score;
        if (score > bestScore) {
            best = action;
            bestScore = score;
        }
    }
}


static int percent(int a, int b) {
    return a * 100 / b;
}


static Chooser chooseEnemyAction(Fighter hero, boolean heroPoisoned, List<Fighter> allies, int healWait, int spitWait) {
    Chooser chooser = new Chooser("удар " + hero.name());
    Fighter weakest = null;
    for (Fighter ally : 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;
}


static Fighter weakestOf(List<Fighter> enemies) {
    Fighter weakest = null;
    for (Fighter enemy : enemies) {
        if (weakest == null || enemy.hp() < weakest.hp()) weakest = enemy;
    }
    return weakest;
}


static Chooser chooseHeroAction(Fighter hero, boolean hasPotion, List<Fighter> enemies) {
    Chooser chooser = new Chooser("удар " + weakestOf(enemies).name());
    if (percent(hero.hp(), hero.maxHp()) < 35 && hasPotion) chooser.consider(90, "отвара");
    return chooser;
}


static void show(Chooser chooser) {
    System.out.println(chooser.trace + " → " + chooser.best);
}

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

Fighter hero = new Fighter("Ива", 30, 40);
Fighter hurtHero = new Fighter("Ива", 10, 40);
Fighter woundedRat = new Fighter("плъх", 3, 9);
Fighter rat = new Fighter("плъх", 9, 9);
Fighter goblin = new Fighter("гоблин", 16, 16);
Fighter woundedGoblin = new Fighter("гоблин", 6, 16);
Fighter cultist = new Fighter("култист", 3, 20);


show(chooseEnemyAction(hero, false, List.of(woundedRat, goblin), 0, 0));
show(chooseEnemyAction(hero, false, List.of(woundedRat, goblin), 2, 0));
show(chooseEnemyAction(hero, true, List.of(rat, goblin), 0, 0));
show(chooseEnemyAction(hero, false, List.of(woundedRat, woundedGoblin), 0, 3));
show(chooseHeroAction(hero, true, List.of(woundedRat, goblin, cultist)));
show(chooseHeroAction(hurtHero, true, List.of(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 {
    String best;
    int bestScore = 40;
    String trace;

    Chooser(String attack) {
        best = attack;
        trace = attack + " 40";
    }

    void consider(int score, String action) {
        trace += ", " + action + " " + score;
        if (score  bestScore) {
            best = action;
            bestScore = score;
        }
    }
}

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

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


// Най-полезното действие досега. consider(score, action) го сменя, ако новото е по-полезно.
// (Ламбда в Java не може да променя локални променливи, затова изборът е в малък обект.)
static class BestAction {
    BattleAction best;
    int bestScore;


    BestAction(BattleAction best, int bestScore) {
        this.best = best;
        this.bestScore = bestScore;
    }


    void consider(int score, BattleAction action) {
        if (score > this.bestScore) {
            this.best = action;
            this.bestScore = score;
        }
    }
}


static BattleAction chooseEnemyAction(Battle battle, Enemy enemy) {
    Hero hero = battle.hero;
    BestAction choice = new BestAction(new AttackAction(enemy, hero), 40);
    String special = enemy.kind.special;
    if (special.equals("shaman")) {
        Enemy weakest = null;
        for (Enemy ally : 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) choice.consider(80, new SpecialAction(enemy, "heal", weakest));
        if (enemy.cooldownOf("shaman") == 0 && !hero.hasEffect("poison")) choice.consider(60, new SpecialAction(enemy, "spit", hero));
    } else if (special.equals("firebolt") && enemy.cooldownOf("firebolt") == 0) {
        choice.consider(65, new SpecialAction(enemy, "firebolt", hero));
    } else if (special.equals("rend") && enemy.cooldownOf("rend") == 0 && !hero.hasEffect("bleed")) {
        choice.consider(55, new SpecialAction(enemy, "rend", hero));
    } else if (special.equals("slam") && enemy.cooldownOf("slam") == 0) {
        choice.consider(60, new SpecialAction(enemy, "slam", hero));
    } else if (special.equals("warden")) {
        if (enemy.phase == 1 && enemy.hp * 2 < enemy.maxHp()) choice.consider(100, new SpecialAction(enemy, "summon", hero));
        else if (enemy.cooldownOf("warden") == 0) choice.consider(60, new SpecialAction(enemy, "slam", hero));
    }
    return choice.best;
}


static List<Skill> usableSkills(Hero hero) {
    List<Skill> result = new ArrayList<>();
    for (String skillId : hero.skills) {
        Skill skill = SKILLS.get(skillId);
        if (hero.mana >= skill.mana && hero.cooldownOf(skill.id) == 0) result.add(skill);
    }
    return result;
}


static Enemy weakestEnemy(Battle battle) {
    Enemy weakest = null;
    for (Enemy enemy : battle.aliveEnemies()) {
        if (weakest == null || enemy.hp < weakest.hp) weakest = enemy;
    }
    return weakest;
}


// Героят на автопилот (симулацията): същата оценка на полезността.
static BattleAction chooseHeroAction(Battle battle) {
    Hero hero = battle.hero;
    Enemy target = weakestEnemy(battle);
    BestAction choice = new BestAction(new AttackAction(hero, target), 40);
    int lifeShare = percent(hero.hp, hero.maxHp());
    if (lifeShare < 35 && hero.inventory.count("potion_heal") > 0) choice.consider(90, new ItemAction(hero, "potion_heal"));
    if ((hero.hasEffect("poison") || hero.hasEffect("bleed")) && lifeShare < 50 && hero.inventory.count("antidote") > 0) {
        choice.consider(70, new ItemAction(hero, "antidote"));
    }
    boolean many = battle.aliveEnemies().size() >= 2;
    for (Skill skill : usableSkills(hero)) {
        int score = 0;
        if (skill.kind.equals("heal")) score = lifeShare < 50 ? 75 : 0;
        else if (skill.kind.equals("buff")) score = hero.hasEffect(skill.effect) ? 0 : 50;
        else if (skill.kind.equals("debuff")) score = many ? 55 : 45;
        else if (skill.target.equals("all")) score = many ? 65 : 52;
        else score = 55;
        choice.consider(score, new SkillAction(hero, skill, target));
    }
    return choice.best;
}

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

Пробвай

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

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

static final String TINY = """
    #######
    #.#...#
    #...#.#
    #######""";
Level level = new Level(TINY);
printWave(level, distances(level, 1, 1));
Отговор

Пробвай

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

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

Level level = new Level(MAP);
List<Step> path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
System.out.println("врагът (" + ENEMY_X + ", " + ENEMY_Y + "), героят (" + HERO_X + ", " + HERO_Y + "): по права линия "
        + distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", по пътя " + path.size());
System.out.println("Пътят до героя (*):");
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-ия ход):

static final Turn[] SCRIPT = {
    new Turn(3, 5, 0, false),
    new Turn(4, 5, 0, false),
    new Turn(4, 5, 0, false),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(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 за достъпно обучение по програмиране ·