Игра как набор задач: от механики к спецификации

Если ты умеешь превращать «хочу, чтобы было умно» в вход, выход и критерий, листай до «Теперь сам».

Как думаешь, какая это задача

В диздоке игры - дизайн-документе, где описаны правила и механики, - написано: «отряд должен ходить к цели умно». Какой алгоритм курса это реализует - поиск в ширину, Дейкстра или что-то третье?

Ответь себе до чтения. Сама фраза ответа не содержит. «Умно» может значить «за меньшее число ходов» - тогда это поиск в ширину по клеткам. Может значить «быстрее по времени», если лес проходится втрое дольше луга, - тогда это Дейкстра с ценой клетки. Может значить «незаметно для врага» - и тогда ценой становится число клеток, которые видит противник, а это уже другая карта весов. Три толкования - три задачи, и выбирает между ними не программист, а тот, кто придумал игру. Работа программиста - задать вопрос.

На что это похоже

Смета на ремонт квартиры. «Сделать красиво» не превращается в работу, пока не разложено по комнатам: в ванной плитка, столько-то метров, такой-то клей; в кухне - розетки, столько-то точек. Каждая строка сметы - отдельная задача со своим мастером, сроком и ценой, и ошибка в одной не ломает остальные. Игра - та же квартира: механики - комнаты, и у каждой своя спецификация.

Механизм: мир «Архипелага» и его модули

Весь раздел строит одну игру - пошаговую песочницу «Архипелаг». Мир - карта 128 × 128 клеток: вода, луг (цена хода 1), лес (3), горы (непроходимы). До восьми игроков, у каждого до 25 отрядов. Отряды добывают сырьё, мастерские делают из него вещи по рецептам, на рынке товары меняют по курсам, между игроками есть чат, игру можно сохранить, а сообщество пишет моды - маленькие скрипты, которые сервер выполняет каждый ход. Сервер считает ход за 100 мс.

Каждая механика переводится в задачу курса:

Порядок работы над каждой строкой - из раздела 26: спецификация, бюджет, маленький пример с перебором, быстрое решение, проверка. Следующие уроки главы делают это для всей таблицы сразу: бюджет хода, структуры данных под частые операции, что нужно доказать, а что проверить.

Правило

Механика игры становится задачей, когда записаны вход, вид ответа, критерий «лучше», размер и края. Одна фраза диздока часто прячет несколько задач - выбери толкование явно и запиши его, прежде чем выбирать алгоритм.

Разбор: «отряд идёт к цели»

Спецификация. Вход - карта цен клеток, старт, цель. Вид ответа - сам путь, а не его длина: отряду нужно знать, куда шагнуть. «Лучше» - два толкования, их и сравним. Края: цель совпадает со стартом - путь из одной клетки, ход не нужен; цель в воде или недостижима - ответ пустой путь, а не ошибка. Размер: 16 384 клетки, до 200 отрядов.

# карта 5 × 6: цена входа в клетку (1 - луг, 3 - лес), 0 - вода
karta = [
    [1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 3, 1],
    [1, 3, 3, 1, 3, 1],
    [1, 0, 1, 1, 0, 1],
    [1, 1, 1, 0, 0, 1],
]
STROK = 5
STOLB = 6

def imya(k):
    # клетка как на доске: столбец буквой, строка цифрой - "c2"
    return "abcdef"[k[1]] + str(k[0])

def sosedi(k):
    out = []
    for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        r = k[0] + d[0]
        c = k[1] + d[1]
        if 0 <= r < STROK and 0 <= c < STOLB and karta[r][c] > 0:
            out.append([r, c])
    return out

def put(start, cel, cena):
    # Дейкстра за V²: карта маленькая. cena(k) - цена входа в клетку k
    dist = {}
    otkuda = {}
    kletka = {}
    gotovo = set()
    dist[imya(start)] = 0
    kletka[imya(start)] = start
    while True:
        v = ""
        for k in dist:
            if k not in gotovo and (v == "" or dist[k] < dist[v]):
                v = k
        if v == "" or v == imya(cel):
            break
        gotovo.add(v)
        for s in sosedi(kletka[v]):
            nd = dist[v] + cena(s)
            if imya(s) not in dist or nd < dist[imya(s)]:
                dist[imya(s)] = nd
                otkuda[imya(s)] = v
                kletka[imya(s)] = s
    if imya(cel) not in dist:
        return []                      # цель недостижима: пустой путь
    marshrut = [imya(cel)]
    while marshrut[0] != imya(start):
        marshrut = [otkuda[marshrut[0]]] + marshrut
    return marshrut

def po_kletkam(k):
    return 1

def po_vremeni(k):
    return karta[k[0]][k[1]]

def vremya(marshrut):
    t = 0
    for i in range(1, len(marshrut)):
        t = t + karta[int(marshrut[i][1])]["abcdef".find(marshrut[i][0])]
    return t

for zadacha in [["меньше клеток: ", po_kletkam],
                ["меньше времени:", po_vremeni]]:
    m = put([2, 0], [2, 5], zadacha[1])
    print(zadacha[0], len(m) - 1, "ходов,", vremya(m), "времени |",
          " ".join(m))
print("цель в воде:   ", put([2, 0], [1, 2], po_vremeni))

меньше клеток:  5 ходов, 11 времени | a2 b2 c2 d2 e2 f2
меньше времени: 9 ходов, 9 времени | a2 a1 a0 b0 c0 d0 e0 f0 f1 f2
цель в воде:    []

Один алгоритм, одна карта, два ответа. По клеткам выгоднее идти напрямик через лес - пять ходов, но 11 единиц времени. По времени выгоднее обойти лес по лугу - девять ходов, но 9 единиц. Ни один ответ не ошибка, ошибка - выбрать критерий молча. Цель в воде дала пустой путь: этот край записан в спецификации, и отряд, получив пустой путь, просто стоит, а не падает.

Разбор: «выгодный обмен на рынке»

Рынок меняет товары по курсам. Игроки ищут круг обмена, который возвращает больше, чем было: отдать рыбу, получить зерно, за зерно доски и так далее, пока не вернёшься к рыбе. Круг выгоден, если произведение курсов больше единицы. Переберём все простые круги на четырёх товарах.

import math

tovary = ["рыба", "зерно", "доски", "камень"]
# kurs[a][b] - сколько товара b дают за единицу товара a; 0 - не меняют
kurs = [
    [0, 3, 0, 0.5],
    [0.3, 0, 0.45, 0],
    [0, 2, 0, 0.8],
    [0.97, 0, 1.2, 0],
]

def krugi(put, out):
    # все простые круги, начинающиеся в товаре put[0] с меньшим номером
    a = put[len(put) - 1]
    for b in range(len(tovary)):
        if kurs[a][b] == 0:
            continue
        if b == put[0] and len(put) >= 2:
            out.append(put + [b])
        elif b > put[0] and b not in put:   # круг - с меньшего номера
            krugi(put + [b], out)

vse = []
for s in range(len(tovary)):
    krugi([s], vse)
for k in vse:
    proizv = 1
    summa = 0
    for i in range(len(k) - 1):
        proizv = proizv * kurs[k[i]][k[i + 1]]
        summa = summa - math.log(kurs[k[i]][k[i + 1]])
    nazvaniya = []
    for t in k:
        nazvaniya.append(tovary[t])
    print(" -> ".join(nazvaniya))
    print("    произведение", round(proizv, 3), "| сумма -log",
          round(summa, 3))

рыба -> зерно -> рыба
    произведение 0.9 | сумма -log 0.105
рыба -> зерно -> доски -> камень -> рыба
    произведение 1.048 | сумма -log -0.047
рыба -> камень -> рыба
    произведение 0.485 | сумма -log 0.724
рыба -> камень -> доски -> зерно -> рыба
    произведение 0.36 | сумма -log 1.022
зерно -> доски -> зерно
    произведение 0.9 | сумма -log 0.105
доски -> камень -> доски
    произведение 0.96 | сумма -log 0.041

Выгоден один круг: рыба - зерно - доски - камень - рыба, плюс 4,8% за оборот. Это дыра в экономике: игрок крутит круг, пока не станет богаче всех. Перебор кругов растёт факториально, поэтому на сотне товаров он не годится - и здесь работает переформулировка. math.log - натуральный логарифм; основание для нас неважно, важны два его свойства. Логарифм произведения равен сумме логарифмов, и логарифм больше нуля ровно у чисел больше единицы. Значит, «произведение курсов больше 1» - то же, что «сумма −log курса меньше 0». Если весом ребра взять −log курса, выгодный круг - это отрицательный цикл, а его находит Беллман - Форд из раздела 11 за V · E. Вывод это и показывает: у единственного выгодного круга сумма −0.047, у остальных - больше нуля. Граница правила: переформулировка верна, только пока обмен идёт без комиссии и округления. Комиссия в 1% за сделку - тоже множитель, её вносят в курс до логарифма.

Что ломается без этого

Код раньше спецификации. Поиск пути написан «по клеткам», а дизайнер ждал «по времени» - отряды лезут через лес, и это выглядит как ошибка ИИ, хотя алгоритм верен.

Пропущенный край. Цель в воде, а функция пути бросает исключение: сервер падает на ходу одного игрока.

Экономика с дырой. Курсы на рынке подобраны вручную, выгодный круг никто не искал - через неделю у одного игрока весь камень мира.

Зачем это в работе

Диздок игры, ТЗ заказчика, тикет «сделать подсказки умнее» - всё это просьбы, а не спецификации. Таблица «механика → задача → вид ответа → раздел» за час превращает документ в список тикетов, где у каждого понятно, как проверить готовность. А строка «нельзя решить - лимит» заранее снимает спор о невозможном.

Теперь сам

1. Механика «туман войны»: отряд видит клетки, до которых прямая линия не пересекает гору. Какая это задача, какой вид ответа?
2. Механика «игрок видит своё место в рейтинге среди 10 000 игроков после каждой партии». Что выбрать: сортировать всех после каждой партии или что-то другое?
3. Курсы обмена: рыба → зерно 2, зерно → рыба 0,6. Выгоден ли круг? Чему равна сумма −log?