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

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

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

Проблем

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

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

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

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

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

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

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

Идеята

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

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

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

const string MAP = """
    ################
    #......#.......#
    #......#.......#
    #......#.......#
    #......#.......#
    #..............#
    ################
    """;


// Вълната: колко стъпки е всяка клетка от старта.
static int[][] Distances(Level level, int startX, int startY)
{
    var dist = new int[level.Height][];
    for (int y = 0; y < level.Height; y++)
    {
        dist[y] = new int[level.Width];
        Array.Fill(dist[y], -1);
    }
    dist[startY][startX] = 0;
    var queue = new List<Step> { new Step(startX, startY) };
    int head = 0;
    while (head < queue.Count)
    {
        Step cell = queue[head];
        head++;
        foreach (int[] direction in Level.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;
}
var level = new Level(MAP);
int[][] dist = Distances(level, ENEMY_X, ENEMY_Y);
Console.WriteLine("Вълната от врага (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). Масивът с четирите посоки е в Level: функциите под програмата са локални и не виждат променливите на Main, а полето на класа се вижда отвсякъде.

Проверката 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)
{
    var cameFrom = new int[level.Width * level.Height];
    Array.Fill(cameFrom, -1);
    int start = startY * level.Width + startX;
    cameFrom[start] = start;
    var queue = new List<int> { start };
    int head = 0;
    while (head < queue.Count)
    {
        int current = queue[head];
        head++;
        int x = current % level.Width;
        int y = current / level.Width;
        if (current != start && x == goalX && y == goalY)
        {
            var path = new List<Step>();
            int index = current;
            while (index != start)
            {
                path.Add(new Step(index % level.Width, index / level.Width));
                index = cameFrom[index];
            }
            path.Reverse();
            return path;
        }
        foreach (int[] direction in Level.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);
}
var level = new Level(MAP);
List<Step> path = FindPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)!;
Console.WriteLine($"врагът ({ENEMY_X}, {ENEMY_Y}), героят ({HERO_X}, {HERO_Y}): по права линия {Distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)}, по пътя {path.Count}");
int[][] dist = Distances(level, ENEMY_X, ENEMY_Y);
Console.WriteLine("Вълната от врага (a = 10, b = 11, ...):");
PrintWave(level, dist);
Console.WriteLine("Пътят до героя (*):");
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 int SIGHT = 8;
const int WAKE = 5;
const int LOST = 3;
const int FAR = 20;
const int NONE = 99;
const int ENEMY_LIFE = 16;


// Врагът „вижда“ героя, ако пътят до него е кратък (в играта: линия на погледа от урока за картата).
static void EnemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, bool hidden)
{
    List<Step>? path = FindPath(level, enemy.X, enemy.Y, heroX, heroY);
    int pathLength = path == null ? NONE : path.Count;
    bool 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;
        }
        // Броди по ред на посоките (в играта се хвърля зарче).
        int[] direction = Level.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 == "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;
    }
    // Бяга: стъпката, която най-много го отдалечава от героя.
    int bestX = enemy.X;
    int bestY = enemy.Y;
    int bestDistance = Distance(enemy.X, enemy.Y, heroX, heroY);
    foreach (int[] direction in Level.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 е паметта на автомата: без него врагът би забравял героя още при първото скриване.

var level = new Level(MAP);
var 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.Count;
    string state = before == enemy.State ? before : before + " → " + enemy.State;
    Console.WriteLine($"ход {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)
{
    var cameFrom = new int[level.Width * level.Height];
    Array.Fill(cameFrom, -1);
    int start = startY * level.Width + startX;
    cameFrom[start] = start;
    var queue = new List<int> { start };
    int head = 0;
    while (head < queue.Count)
    {
        int current = queue[head];
        head++;
        int x = current % level.Width;
        int y = current / level.Width;
        if (current != start && x == goalX && y == goalY)
        {
            var path = new List<Step>();
            int index = current;
            while (index != start)
            {
                path.Add(new Step(index % level.Width, index / level.Width));
                index = cameFrom[index];
            }
            path.Reverse();
            return path;
        }
        foreach (int[] direction in Level.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, bool hidden)
{
    List<Step>? path = FindPath(level, enemy.X, enemy.Y, heroX, heroY);
    int pathLength = path == null ? NONE : path.Count;
    bool 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;
        }
        // Броди по ред на посоките (в играта се хвърля зарче).
        int[] direction = Level.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 == "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;
    }
    // Бяга: стъпката, която най-много го отдалечава от героя.
    int bestX = enemy.X;
    int bestY = enemy.Y;
    int bestDistance = Distance(enemy.X, enemy.Y, heroX, heroY);
    foreach (int[] direction in Level.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 — коя е целта:

// Търсене в ширина: опашка от клетки, всяка помни откъде е дошла. Първата намерена цел е
// най-близката. Посоките са в постоянен ред (горе, дясно, долу, ляво), затова пътят е еднакъв
// на всеки език.
class Point
{
    public int X;
    public int Y;
}


static partial class Arcanum
{
    public static readonly int[][] DIRECTIONS = { new[] { 0, -1 }, new[] { 1, 0 }, new[] { 0, 1 }, new[] { -1, 0 } };


    // isPassable(x, y) и isGoal(x, y) са функции; връща пътя без началото или null.
    public static List<Point>? FindPath(Level level, int startX, int startY, Func<int, int, bool> isPassable, Func<int, int, bool> isGoal)
    {
        int[] cameFrom = new int[level.Width * level.Height];
        Array.Fill(cameFrom, -1);
        int startIndex = startY * level.Width + startX;
        cameFrom[startIndex] = startIndex;
        List<int> queue = new List<int> { startIndex };
        int head = 0;
        while (head < queue.Count)
        {
            int current = queue[head];
            head++;
            int x = current % level.Width;
            int y = current / level.Width;
            if (current != startIndex && isGoal(x, y))
            {
                List<Point> path = new List<Point>();
                int index = current;
                while (index != startIndex)
                {
                    path.Add(new Point { X = index % level.Width, Y = index / level.Width });
                    index = cameFrom[index];
                }
                path.Reverse();
                return path;
            }
            foreach (int[] direction in 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(nextX, nextY) && !isGoal(nextX, nextY)) continue;
                cameFrom[nextIndex] = current;
                queue.Add(nextIndex);
            }
        }
        return null;
    }


    public 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 partial class Arcanum
{
    public static bool 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);
    }


    public static bool 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);
    }


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


    public static void EnemyTurnOnMap(Game game, Level level, Enemy enemy)
    {
        Hero hero = game.Hero;
        Random rng = game.Rng;
        bool sees = EnemySeesHero(level, enemy, hero);
        bool 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;
            }
            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 == "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;
            List<Point>? 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.Count > 1 && path.Count <= 20) MoveEnemy(game, level, enemy, path[0].X, path[0].Y);
            return;
        }
        // flee: стъпка, която отдалечава най-много от героя
        int bestX = enemy.X;
        int bestY = enemy.Y;
        int bestDistance = Distance(enemy.X, enemy.Y, hero.X, hero.Y);
        foreach (int[] direction in 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
{
    public string Best;
    public int BestScore = 40;
    public string Trace;


    public Chooser(string attack)
    {
        Best = attack;
        Trace = attack + " 40";
    }


    public 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, bool heroPoisoned, List<Fighter> allies, int healWait, int spitWait)
{
    var chooser = new Chooser("удар " + hero.Name);
    Fighter? weakest = null;
    foreach (Fighter ally in 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;
    foreach (Fighter enemy in enemies)
    {
        if (weakest == null || enemy.Hp < weakest.Hp) weakest = enemy;
    }
    return weakest!;
}


static Chooser ChooseHeroAction(Fighter hero, bool hasPotion, List<Fighter> enemies)
{
    var chooser = new Chooser("удар " + WeakestOf(enemies).Name);
    if (Percent(hero.Hp, hero.MaxHp) < 35 && hasPotion) chooser.Consider(90, "отвара");
    return chooser;
}


static void Show(Chooser chooser)
{
    Console.WriteLine(chooser.Trace + " → " + chooser.Best);
}

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

var hero = new Fighter("Ива", 30, 40);
var hurtHero = new Fighter("Ива", 10, 40);
var woundedRat = new Fighter("плъх", 3, 9);
var rat = new Fighter("плъх", 9, 9);
var goblin = new Fighter("гоблин", 16, 16);
var woundedGoblin = new Fighter("гоблин", 6, 16);
var cultist = new Fighter("култист", 3, 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
{
    public string Best;
    public int BestScore = 40;
    public string Trace;

    public Chooser(string attack)
    {
        Best = attack;
        Trace = attack + " 40";
    }

    public void Consider(int score, string action)
    {
        Trace += ", " + action + " " + score;
        if (score  BestScore)
        {
            Best = action;
            BestScore = score;
        }
    }
}

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

// В боя изкуственият интелект оценява всяко възможно действие с число (полезност) и избира
// най-полезното: лекува се при малко живот, ползва умение, когато е готово, иначе удря.
static partial class Arcanum
{
    public static IBattleAction ChooseEnemyAction(Battle battle, Enemy enemy)
    {
        Hero hero = battle.Hero;
        IBattleAction best = new AttackAction(enemy, hero);
        int bestScore = 40;
        Action<int, IBattleAction> consider = (score, action) =>
        {
            if (score > bestScore)
            {
                best = action;
                bestScore = score;
            }
        };
        string special = enemy.Kind.Special;
        if (special == "shaman")
        {
            Enemy? weakest = null;
            foreach (Enemy ally in 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;
    }


    public static List<Skill> UsableSkills(Hero hero)
    {
        List<Skill> result = new List<Skill>();
        foreach (string skillId in hero.Skills)
        {
            Skill skill = SKILLS.Get(skillId);
            if (hero.Mana >= skill.Mana && hero.CooldownOf(skill.Id) == 0) result.Add(skill);
        }
        return result;
    }


    public static Enemy? WeakestEnemy(Battle battle)
    {
        Enemy? weakest = null;
        foreach (Enemy enemy in battle.AliveEnemies())
        {
            if (weakest == null || enemy.Hp < weakest.Hp) weakest = enemy;
        }
        return weakest;
    }


    // Героят на автопилот (симулацията): същата оценка на полезността.
    public static IBattleAction ChooseHeroAction(Battle battle)
    {
        Hero hero = battle.Hero;
        Enemy? target = WeakestEnemy(battle);
        IBattleAction best = new AttackAction(hero, target);
        int bestScore = 40;
        Action<int, IBattleAction> consider = (score, action) =>
        {
            if (score > bestScore)
            {
                best = action;
                bestScore = score;
            }
        };
        int 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"));
        }
        bool many = battle.AliveEnemies().Count >= 2;
        foreach (Skill skill in UsableSkills(hero))
        {
            int 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 string TINY = """
    #######
    #.#...#
    #...#.#
    #######
    """;
var level = new Level(TINY);
PrintWave(level, Distances(level, 1, 1));
Отговор

Пробвай

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

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

var level = new Level(MAP);
List<Step> path = FindPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)!;
Console.WriteLine($"врагът ({ENEMY_X}, {ENEMY_Y}), героят ({HERO_X}, {HERO_Y}): по права линия {Distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)}, по пътя {path.Count}");
Console.WriteLine("Пътят до героя (*):");
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-ия ход):

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