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

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

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

Проблем

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

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

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

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

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

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

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

Идеята

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

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

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

MAP = """
################
#......#.......#
#......#.......#
#......#.......#
#......#.......#
#..............#
################
""".strip()




DIRECTIONS = [(0, -1), (1, 0), (0, 1), (-1, 0)]




def distances(level, start_x, start_y):
    # Вълната: колко стъпки е всяка клетка от старта.
    dist = [[-1] * level.width for _ in range(level.height)]
    dist[start_y][start_x] = 0
    queue = [Step(start_x, start_y)]
    head = 0
    while head < len(queue):
        cell = queue[head]
        head += 1
        for dx, dy in DIRECTIONS:
            next_x = cell.x + dx
            next_y = cell.y + dy
            if not level.walkable(next_x, next_y) or dist[next_y][next_x] != -1:
                continue
            dist[next_y][next_x] = dist[cell.y][cell.x] + 1
            queue.append(Step(next_x, next_y))
    return dist
level = Level(MAP)
dist = distances(level, ENEMY_X, ENEMY_Y)
print("Вълната от врага (a = 10, b = 11, ...):")
print_wave(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 е @dataclass(frozen=True) с x и y. Не ползваме list.pop(0): вадене от началото на списък мести всички останали елементи, затова вместо него се върви с индекс head.

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

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

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

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

Идеята

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

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

def find_path(level, start_x, start_y, goal_x, goal_y):
    came_from = [-1] * (level.width * level.height)
    start = start_y * level.width + start_x
    came_from[start] = start
    queue = [start]
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        x = current % level.width
        y = current // level.width
        if current != start and x == goal_x and y == goal_y:
            path = []
            index = current
            while index != start:
                path.append(Step(index % level.width, index // level.width))
                index = came_from[index]
            path.reverse()
            return path
        for dx, dy in DIRECTIONS:
            next_x = x + dx
            next_y = y + dy
            if not level.walkable(next_x, next_y):
                continue
            next_index = next_y * level.width + next_x
            if came_from[next_index] != -1:
                continue
            came_from[next_index] = current
            queue.append(next_index)
    return None




def distance(ax, ay, bx, by):
    return abs(ax - bx) + abs(ay - by)
level = Level(MAP)
path = find_path(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)
print(f"врагът ({ENEMY_X}, {ENEMY_Y}), героят ({HERO_X}, {HERO_Y}): по права линия {distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)}, по пътя {len(path)}")
dist = distances(level, ENEMY_X, ENEMY_Y)
print("Вълната от врага (a = 10, b = 11, ...):")
print_wave(level, dist)
print("Пътят до героя (*):")
print_path(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 по права линия. Стената не пречи на алгоритъма, защото вълната просто не влиза в нея.

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

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

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

Цената е ниска. Нивото на играта е 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).

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




def enemy_turn(level, enemy, hero_x, hero_y, turn, hidden):
    # Врагът „вижда“ героя, ако пътят до него е кратък (в играта: линия на погледа от урока за картата).
    path = find_path(level, enemy.x, enemy.y, hero_x, hero_y)
    path_length = NONE if path is None else len(path)
    sees = not hidden and path_length <= SIGHT
    if enemy.state == "sleep":
        if sees and path_length <= WAKE:
            enemy.state = "chase"
        return
    if enemy.state == "wander":
        if sees:
            enemy.state = "chase"
            enemy.lost = 0
            return
        # Броди по ред на посоките (в играта се хвърля зарче).
        dx, dy = DIRECTIONS[turn % 4]
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if level.walkable(next_x, next_y) and not (next_x == hero_x and next_y == hero_y):
            enemy.x = next_x
            enemy.y = next_y
        return
    if enemy.state == "chase":
        if enemy.life * 4 < enemy.max_life:
            enemy.state = "flee"
            return
        if not sees:
            enemy.lost += 1
            if enemy.lost > LOST:
                enemy.state = "wander"
                return
        else:
            enemy.lost = 0
        if path_length <= 1:
            return
        if path_length <= FAR:
            enemy.x = path[0].x
            enemy.y = path[0].y
        return
    # Бяга: стъпката, която най-много го отдалечава от героя.
    best_x = enemy.x
    best_y = enemy.y
    best_distance = distance(enemy.x, enemy.y, hero_x, hero_y)
    for dx, dy in DIRECTIONS:
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if not level.walkable(next_x, next_y) or (next_x == hero_x and next_y == hero_y):
            continue
        away = distance(next_x, next_y, hero_x, hero_y)
        if away > best_distance:
            best_distance = away
            best_x = next_x
            best_y = next_y
    enemy.x = best_x
    enemy.y = best_y

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

level = Level(MAP)
enemy = Enemy(ENEMY_X, ENEMY_Y, "sleep", ENEMY_LIFE)
for index, (hero_x, hero_y, hit, hidden) in enumerate(SCRIPT):
    enemy.life = max(0, enemy.life - hit)
    before = enemy.state
    enemy_turn(level, enemy, hero_x, hero_y, index + 1, hidden)
    path = find_path(level, enemy.x, enemy.y, hero_x, hero_y)
    length = NONE if path is None else len(path)
    state = before if before == enemy.state else before + " → " + enemy.state
    print(f"ход {index + 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 и гоблинът се събужда. Тогава се вижда търсенето: вълната тръгва от гоблина и заобикаля стената през процепа, докато стигне героя. После гоблинът върви, губи героя, пак го забелязва и накрая бяга.

def find_path(level, start_x, start_y, goal_x, goal_y):
    came_from = [-1] * (level.width * level.height)
    start = start_y * level.width + start_x
    came_from[start] = start
    queue = [start]
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        x = current % level.width
        y = current // level.width
        if current != start and x == goal_x and y == goal_y:
            path = []
            index = current
            while index != start:
                path.append(Step(index % level.width, index // level.width))
                index = came_from[index]
            path.reverse()
            return path
        for dx, dy in DIRECTIONS:
            next_x = x + dx
            next_y = y + dy
            if not level.walkable(next_x, next_y):
                continue
            next_index = next_y * level.width + next_x
            if came_from[next_index] != -1:
                continue
            came_from[next_index] = current
            queue.append(next_index)
    return None




def enemy_turn(level, enemy, hero_x, hero_y, turn, hidden):
    # Врагът „вижда“ героя, ако пътят до него е кратък (в играта: линия на погледа от урока за картата).
    path = find_path(level, enemy.x, enemy.y, hero_x, hero_y)
    path_length = NONE if path is None else len(path)
    sees = not hidden and path_length <= SIGHT
    if enemy.state == "sleep":
        if sees and path_length <= WAKE:
            enemy.state = "chase"
        return
    if enemy.state == "wander":
        if sees:
            enemy.state = "chase"
            enemy.lost = 0
            return
        # Броди по ред на посоките (в играта се хвърля зарче).
        dx, dy = DIRECTIONS[turn % 4]
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if level.walkable(next_x, next_y) and not (next_x == hero_x and next_y == hero_y):
            enemy.x = next_x
            enemy.y = next_y
        return
    if enemy.state == "chase":
        if enemy.life * 4 < enemy.max_life:
            enemy.state = "flee"
            return
        if not sees:
            enemy.lost += 1
            if enemy.lost > LOST:
                enemy.state = "wander"
                return
        else:
            enemy.lost = 0
        if path_length <= 1:
            return
        if path_length <= FAR:
            enemy.x = path[0].x
            enemy.y = path[0].y
        return
    # Бяга: стъпката, която най-много го отдалечава от героя.
    best_x = enemy.x
    best_y = enemy.y
    best_distance = distance(enemy.x, enemy.y, hero_x, hero_y)
    for dx, dy in DIRECTIONS:
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if not level.walkable(next_x, next_y) or (next_x == hero_x and next_y == hero_y):
            continue
        away = distance(next_x, next_y, hero_x, hero_y)
        if away > best_distance:
            best_distance = away
            best_x = next_x
            best_y = next_y
    enemy.x = best_x
    enemy.y = best_y
Стъпка по стъпка, с думи
  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 — коя е целта:

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




# is_passable(x, y) и is_goal(x, y) са функции; връща пътя без началото или None.
def find_path(level, start_x, start_y, is_passable, is_goal):
    came_from = [-1] * (level.width * level.height)
    start_index = start_y * level.width + start_x
    came_from[start_index] = start_index
    queue = [start_index]
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        x = current % level.width
        y = current // level.width
        if current != start_index and is_goal(x, y):
            path = []
            index = current
            while index != start_index:
                path.append(SimpleNamespace(x=index % level.width, y=index // level.width))
                index = came_from[index]
            path.reverse()
            return path
        for direction in DIRECTIONS:
            next_x = x + direction[0]
            next_y = y + direction[1]
            if not level.in_bounds(next_x, next_y):
                continue
            next_index = next_y * level.width + next_x
            if came_from[next_index] != -1:
                continue
            if not is_passable(next_x, next_y) and not is_goal(next_x, next_y):
                continue
            came_from[next_index] = current
            queue.append(next_index)
    return None




def distance(ax, ay, bx, by):
    return abs(ax - bx) + abs(ay - by)

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

# Изкуственият интелект на картата е краен автомат: спи → броди → гони → бяга при малко живот.
# Пазачът стои на пост (guard), докато не види героя.
def enemy_sees_hero(level, enemy, hero):
    if distance(enemy.x, enemy.y, hero.x, hero.y) > 8:
        return False
    return line_of_sight(level, enemy.x, enemy.y, hero.x, hero.y)




def can_enemy_step(game, level, x, y):
    if not level.is_walkable(x, y):
        return False
    if level.enemy_at(x, y) is not None or level.npc_at(x, y) is not None:
        return False
    return not (game.hero.x == x and game.hero.y == y)




def move_enemy(game, level, enemy, x, y):
    if enemy.has_effect('bleed'):
        level.add_blood(enemy.x, enemy.y)
    enemy.x = x
    enemy.y = y




def enemy_turn_on_map(game, level, enemy):
    hero = game.hero
    rng = game.rng
    sees = enemy_sees_hero(level, enemy, hero)
    hero_sees_it = level.visible[enemy.y][enemy.x]
    if enemy.calm > 0:
        enemy.calm -= 1
    if enemy.state == 'sleep':
        if sees and distance(enemy.x, enemy.y, hero.x, hero.y) <= 5 and rng.chance(50):
            enemy.state = 'chase'
            if hero_sees_it:
                game.say(t('ai.wakes', {'name': enemy.name}))
        return
    if enemy.state == 'guard':
        if sees and 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 and enemy.calm == 0:
            enemy.state = 'chase'
            enemy.lost_turns = 0
            if hero_sees_it:
                game.say(t('ai.notices', {'name': enemy.name}))
            return
        roll = rng.next_int(5)
        if roll < 4:
            next_x = enemy.x + DIRECTIONS[roll][0]
            next_y = enemy.y + DIRECTIONS[roll][1]
            if can_enemy_step(game, level, next_x, next_y):
                move_enemy(game, level, enemy, next_x, next_y)
        return
    if enemy.state == 'chase':
        if enemy.kind.special != 'warden' and enemy.is_heavily_wounded():
            enemy.state = 'flee'
            if hero_sees_it:
                game.say(t('ai.flees', {'name': enemy.name}))
            return
        if not sees:
            enemy.lost_turns += 1
            if enemy.lost_turns > 5:
                enemy.state = 'wander'
                return
        else:
            enemy.lost_turns = 0
        if distance(enemy.x, enemy.y, hero.x, hero.y) <= 1:
            return
        path = find_path(level, enemy.x, enemy.y,
                         lambda x, y: can_enemy_step(game, level, x, y),
                         lambda x, y: x == hero.x and y == hero.y)
        if path is not None and len(path) > 1 and len(path) <= 20:
            move_enemy(game, level, enemy, path[0].x, path[0].y)
        return
    # flee: стъпка, която отдалечава най-много от героя
    best_x = enemy.x
    best_y = enemy.y
    best_distance = distance(enemy.x, enemy.y, hero.x, hero.y)
    for direction in DIRECTIONS:
        next_x = enemy.x + direction[0]
        next_y = enemy.y + direction[1]
        if not can_enemy_step(game, level, next_x, next_y):
            continue
        away = distance(next_x, next_y, hero.x, hero.y)
        if away > best_distance:
            best_distance = away
            best_x = next_x
            best_y = next_y
    if best_x != enemy.x or best_y != enemy.y:
        move_enemy(game, level, enemy, best_x, best_y)

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

  • 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:
    def __init__(self, attack):
        self.best = attack
        self.best_score = 40
        self.trace = attack + " 40"


    def consider(self, score, action):
        self.trace += ", " + action + " " + str(score)
        if score > self.best_score:
            self.best = action
            self.best_score = score




def percent(a, b):
    return a * 100 // b




def choose_enemy_action(hero, hero_poisoned, allies, heal_wait, spit_wait):
    chooser = Chooser("удар " + hero.name)
    weakest = None
    for ally in allies:
        if percent(ally.hp, ally.max_hp) < 50 and (weakest is None or percent(ally.hp, ally.max_hp) < percent(weakest.hp, weakest.max_hp)):
            weakest = ally
    if weakest is not None and heal_wait == 0:
        chooser.consider(80, "лекува " + weakest.name)
    if spit_wait == 0 and not hero_poisoned:
        chooser.consider(60, "плюе " + hero.name)
    return chooser




def weakest_of(enemies):
    weakest = None
    for enemy in enemies:
        if weakest is None or enemy.hp < weakest.hp:
            weakest = enemy
    return weakest




def choose_hero_action(hero, has_potion, enemies):
    chooser = Chooser("удар " + weakest_of(enemies).name)
    if percent(hero.hp, hero.max_hp) < 35 and has_potion:
        chooser.consider(90, "отвара")
    return chooser




def show(chooser):
    print(chooser.trace + " → " + chooser.best)

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

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


show(choose_enemy_action(hero, False, [wounded_rat, goblin], 0, 0))
show(choose_enemy_action(hero, False, [wounded_rat, goblin], 2, 0))
show(choose_enemy_action(hero, True, [rat, goblin], 0, 0))
show(choose_enemy_action(hero, False, [wounded_rat, wounded_goblin], 0, 3))
show(choose_hero_action(hero, True, [wounded_rat, goblin, cultist]))
show(choose_hero_action(hurt_hero, True, [wounded_rat, 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:
    def __init__(self, attack):
        self.best = attack
        self.best_score = 40
        self.trace = attack + " 40"

    def consider(self, score, action):
        self.trace += ", " + action + " " + str(score)
        if score  self.best_score:
            self.best = action
            self.best_score = score

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

# В боя изкуственият интелект оценява всяко възможно действие с число (полезност) и избира
# най-полезното: лекува се при малко живот, ползва умение, когато е готово, иначе удря.
def choose_enemy_action(battle, enemy):
    hero = battle.hero
    best = AttackAction(enemy, hero)
    best_score = 40


    def consider(score, action):
        nonlocal best, best_score
        if score > best_score:
            best = action
            best_score = score


    special = enemy.kind.special
    if special == 'shaman':
        weakest = None
        for ally in battle.alive_enemies():
            if percent(ally.hp, ally.max_hp()) < 50 and (weakest is None or percent(ally.hp, ally.max_hp()) < percent(weakest.hp, weakest.max_hp())):
                weakest = ally
        if weakest is not None and enemy.cooldown_of('heal') == 0:
            consider(80, SpecialAction(enemy, 'heal', weakest))
        if enemy.cooldown_of('shaman') == 0 and not hero.has_effect('poison'):
            consider(60, SpecialAction(enemy, 'spit', hero))
    elif special == 'firebolt' and enemy.cooldown_of('firebolt') == 0:
        consider(65, SpecialAction(enemy, 'firebolt', hero))
    elif special == 'rend' and enemy.cooldown_of('rend') == 0 and not hero.has_effect('bleed'):
        consider(55, SpecialAction(enemy, 'rend', hero))
    elif special == 'slam' and enemy.cooldown_of('slam') == 0:
        consider(60, SpecialAction(enemy, 'slam', hero))
    elif special == 'warden':
        if enemy.phase == 1 and enemy.hp * 2 < enemy.max_hp():
            consider(100, SpecialAction(enemy, 'summon', hero))
        elif enemy.cooldown_of('warden') == 0:
            consider(60, SpecialAction(enemy, 'slam', hero))
    return best




def usable_skills(hero):
    result = []
    for skill_id in hero.skills:
        skill = SKILLS[skill_id]
        if hero.mana >= skill.mana and hero.cooldown_of(skill.id) == 0:
            result.append(skill)
    return result




def weakest_enemy(battle):
    weakest = None
    for enemy in battle.alive_enemies():
        if weakest is None or enemy.hp < weakest.hp:
            weakest = enemy
    return weakest




# Героят на автопилот (симулацията): същата оценка на полезността.
def choose_hero_action(battle):
    hero = battle.hero
    target = weakest_enemy(battle)
    best = AttackAction(hero, target)
    best_score = 40


    def consider(score, action):
        nonlocal best, best_score
        if score > best_score:
            best = action
            best_score = score


    life_share = percent(hero.hp, hero.max_hp())
    if life_share < 35 and hero.inventory.count('potion_heal') > 0:
        consider(90, ItemAction(hero, 'potion_heal'))
    if (hero.has_effect('poison') or hero.has_effect('bleed')) and life_share < 50 and hero.inventory.count('antidote') > 0:
        consider(70, ItemAction(hero, 'antidote'))
    many = len(battle.alive_enemies()) >= 2
    for skill in usable_skills(hero):
        score = 0
        if skill.kind == 'heal':
            score = 75 if life_share < 50 else 0
        elif skill.kind == 'buff':
            score = 0 if hero.has_effect(skill.effect) else 50
        elif skill.kind == 'debuff':
            score = 55 if many else 45
        elif skill.target == 'all':
            score = 65 if many else 52
        else:
            score = 55
        consider(score, SkillAction(hero, skill, target))
    return best

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

Пробвай

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

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

TINY = """
#######
#.#...#
#...#.#
#######
""".strip()
level = Level(TINY)
print_wave(level, distances(level, 1, 1))
Отговор

Пробвай

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

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

level = Level(MAP)
path = find_path(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)
print(f"врагът ({ENEMY_X}, {ENEMY_Y}), героят ({HERO_X}, {HERO_Y}): по права линия {distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)}, по пътя {len(path)}")
print("Пътят до героя (*):")
print_path(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-ия ход):

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 за достъпно обучение по програмиране ·