Туман войны: что видит отряд

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

Как думаешь, видят ли они друг друга

Лучник A стоит в клетке [14, 10], лучник B - в [13, 12], между ними одна гора. Видимость считается прямой от стрелка к цели. Если A не видит B, обязательно ли и B не видит A?

Ответь себе до чтения. На плоскости отрезок от A до B - тот же, что от B до A, и ответ был бы «да». Но на клетках отрезок заменяется цепочкой клеток, и цепочка зависит от того, с какого конца её строить: где прямая проходит ровно между двумя клетками, выбор делает правило округления, а оно смотрит на направление. Поэтому A может смотреть через гору, а B - мимо неё.

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

Два человека за колонной в концертном зале. Один видит сцену краем глаза слева от колонны, другой со сцены его видит справа - тонкий край колонны оказывается «то в кадре, то нет», смотря откуда смотреть. На клетках этот край - целая клетка, и спорить о нём приходится правилом.

Механизм: прямая Брезенхема на целых числах

Нужно провести «прямую» из клетки (r₀, c₀) в (r₁, c₁). Пусть по столбцам расстояние больше: dc ≥ dr. Тогда прямая делает ровно dc шагов по столбцам, и иногда - шаг по строке. Когда? Когда настоящая прямая ушла от текущей строки больше чем на половину клетки. Можно считать это дробями, но дроби копят ошибку округления и на границе «ровно половина» ведут себя непредсказуемо - раздел 23 о точности как раз про это.

Прямая Брезенхема считает то же самое на целых числах. Ошибка oshibka - целое число, которое копит, насколько шаги по одной оси отстали от шагов по другой, всё умноженное на общий знаменатель, - так что половина клетки тоже целая. Начальное значение dc − dr; шаг по столбцу вычитает dr, шаг по строке прибавляет dc. Перед шагом считают e2 = 2 · oshibka и сравнивают с двумя порогами: e2 > −dr - пора шагнуть по столбцу, e2 < dc - по строке, а если верно оба - по диагонали. Пороги стоят ровно там, где настоящая прямая уходит от клетки на половину; равенство на пороге - та самая «ровно половина», и строгие сравнения решают её всегда в одну сторону. Никаких дробей и никакого округления - два сравнения на шаг.

Цена: прямая до клетки на расстоянии d - d клеток, и обзор радиуса R проверяет (2R + 1)² прямых длиной до R, то есть порядка R³ клеток. Точно: на расстоянии d по большей из осей лежит 8d клеток, и прямая до каждой - d клеток, всего 8 · (1² + 2² + … + R²) = 8R(R + 1)(2R + 1) / 6. При R = 6 это сотни, при двухстах отрядах - сотни тысяч: заметная, но посильная доля бюджета хода.

Правило

Видимость на клетках считают прямой Брезенхема: целочисленная ошибка решает шаг по короткой оси, без дробей и округления. Прямая от A к B и от B к A может пройти по разным клеткам - если игре нужна честная взаимная видимость, задай одно направление для пары, например от меньшего номера клетки к большему.

Разбор: обзор одного отряда

Карта 15 × 15, до 28 гор (случайная клетка может выпасть дважды), отряд в центре, радиус обзора 6 по большей из осей. Гора закрывает то, что за ней, но саму гору видно.

import random

N = 15
random.seed(9)
gora = set()
for i in range(28):
    gora.add(random.randint(0, N * N - 1))
OTRYAD = 7 * N + 7                        # отряд в центре
gora.discard(OTRYAD)
R = 6                                     # радиус обзора

def liniya(a, b):
    # клетки прямой Брезенхема от a до b на целых числах: шагаем по
    # длинной оси, а ошибка решает, когда шагнуть и по короткой
    r0 = a // N
    c0 = a % N
    r1 = b // N
    c1 = b % N
    dr = abs(r1 - r0)
    dc = abs(c1 - c0)
    sr = 1
    if r1 < r0:
        sr = -1
    sc = 1
    if c1 < c0:
        sc = -1
    oshibka = dc - dr
    kletki = []
    while r0 != r1 or c0 != c1:
        e2 = 2 * oshibka
        if e2 > -dr:
            oshibka = oshibka - dr
            c0 = c0 + sc
        if e2 < dc:
            oshibka = oshibka + dc
            r0 = r0 + sr
        kletki.append(r0 * N + c0)
    return kletki

def vidit(a, b):
    # видно, если на прямой МЕЖДУ a и b нет гор (сама b может быть горой)
    put = liniya(a, b)
    for i in range(len(put) - 1):
        if put[i] in gora:
            return False
    return True

proverok = 0
vidno = set()
for r in range(N):
    for c in range(N):
        k = r * N + c
        if max(abs(r - 7), abs(c - 7)) <= R:
            proverok = proverok + len(liniya(OTRYAD, k))
            if vidit(OTRYAD, k):
                vidno.add(k)
# квадрат обзора: @ отряд, . видно, ^ видна гора, ~ туман
for r in range(7 - R, 7 + R + 1):
    stroka = ""
    for c in range(7 - R, 7 + R + 1):
        k = r * N + c
        if k == OTRYAD:
            stroka = stroka + " @"
        elif k in gora and k in vidno:
            stroka = stroka + " ^"
        elif k in vidno:
            stroka = stroka + " ."
        else:
            stroka = stroka + " ~"
    print(stroka)
print("видно клеток:", len(vidno), "| клеток прямых проверено:",
      proverok)

 . . . ~ ~ ~ ~ ~ ~ ~ ~ . .
 ~ . . . ~ ~ ~ ~ ~ ^ . . ~
 ~ ^ . . ~ ~ ~ ~ ~ . . ~ ~
 ~ ~ ~ . . ~ ~ ~ . . ~ ~ ~
 ~ ~ ~ ~ . ~ ~ ~ . ^ ^ ~ .
 . . . ~ ^ . ^ . . . . . ~
 ~ ~ ^ . . . @ . . ^ ~ ~ ~
 . . . . . . . ^ . . . . ~
 . . . . . ^ . . ~ ~ . . .
 . . . ^ ~ ~ ^ . ~ ~ ~ ~ .
 . . ~ ~ ~ ~ ~ ^ . ~ ~ ~ ~
 . ~ . ~ ~ ~ ~ ~ . ~ ~ ~ ~
 ~ . ~ ~ ~ ~ ~ ~ ~ . ~ ~ ~
видно клеток: 83 | клеток прямых проверено: 728

Из 169 клеток квадрата видно 83, на это ушло 728 клеток прямых - в среднем четыре с небольшим на прямую. Программа строит каждую прямую дважды - для счётчика и для проверки; в игре её строят один раз. Тени за горами расходятся лучами, как и должно быть. Но кое-где за тенью мелькают одиночные видимые клетки: прямая на клетках проходит в «щель» между двумя горами, которая на плоскости была бы закрыта. Это свойство дискретной прямой, а не ошибка программы, и его надо либо принять, либо закрыть правилом - например, запретить прямой проходить по диагонали между двумя горами, стоящими углом, - и проверить такое правило тем же перебором пар.

Разбор: «я тебя вижу, а ты меня нет»

Сорок отрядов на той же карте. Для каждой пары в радиусе обзора сравниваем видимость в обе стороны.

import random

N = 15
random.seed(9)
gora = set()
for i in range(28):
    gora.add(random.randint(0, N * N - 1))
R = 6                                     # радиус обзора

def liniya(a, b):
    # клетки прямой Брезенхема от a до b на целых числах: шагаем по
    # длинной оси, а ошибка решает, когда шагнуть и по короткой
    r0 = a // N
    c0 = a % N
    r1 = b // N
    c1 = b % N
    dr = abs(r1 - r0)
    dc = abs(c1 - c0)
    sr = 1
    if r1 < r0:
        sr = -1
    sc = 1
    if c1 < c0:
        sc = -1
    oshibka = dc - dr
    kletki = []
    while r0 != r1 or c0 != c1:
        e2 = 2 * oshibka
        if e2 > -dr:
            oshibka = oshibka - dr
            c0 = c0 + sc
        if e2 < dc:
            oshibka = oshibka + dc
            r0 = r0 + sr
        kletki.append(r0 * N + c0)
    return kletki

def vidit(a, b):
    # видно, если на прямой МЕЖДУ a и b нет гор (сама b может быть горой)
    put = liniya(a, b)
    for i in range(len(put) - 1):
        if put[i] in gora:
            return False
    return True

def vidit_simm(a, b):
    # симметричное правило: прямую всегда ведут от меньшего номера
    # клетки к большему, поэтому «a видит b» и «b видит a» - одна
    # проверка
    if a < b:
        return vidit(a, b)
    return vidit(b, a)

random.seed(2)
otryady = []
while len(otryady) < 40:
    k = random.randint(0, N * N - 1)
    if k not in gora and k not in otryady:
        otryady.append(k)
par = 0
nesimm = 0
nesimm_ispr = 0
primer = []
for i in range(len(otryady)):
    for j in range(i + 1, len(otryady)):
        a = otryady[i]
        b = otryady[j]
        if max(abs(a // N - b // N), abs(a % N - b % N)) <= R:
            par = par + 1
            if vidit(a, b) != vidit(b, a):
                nesimm = nesimm + 1
                if len(primer) == 0:
                    primer = [a, b, vidit(a, b), vidit(b, a)]
            if vidit_simm(a, b) != vidit_simm(b, a):
                nesimm_ispr = nesimm_ispr + 1
print("пар в радиусе обзора:", par)
print("несимметричных по Брезенхему:", nesimm)
print("несимметричных по правилу «от меньшего номера»:", nesimm_ispr)
a = primer[0]
b = primer[1]
print("пример:", [a // N, a % N], "видит", [b // N, b % N], ":",
      primer[2],
      "| наоборот:", primer[3])
def pokazat(put):
    # клетки прямой как [строка, столбец]; ^ - гора
    out = []
    for k in put:
        t = "[" + str(k // N) + ", " + str(k % N) + "]"
        if k in gora:
            t = t + "^"
        out.append(t)
    return " ".join(out)

print("   прямая туда:   ", pokazat(liniya(a, b)))
print("   прямая обратно:", pokazat(liniya(b, a)))

пар в радиусе обзора: 374
несимметричных по Брезенхему: 36
несимметричных по правилу «от меньшего номера»: 0
пример: [14, 10] видит [13, 12] : False | наоборот: True
   прямая туда:    [14, 11]^ [13, 12]
   прямая обратно: [13, 11] [14, 10]

В 36 парах из 374 - почти каждой десятой - видимость несимметрична. Пример показывает почему: прямая из [14, 10] в [13, 12] шагает сначала по столбцу, в [14, 11], и упирается в гору; прямая обратно шагает сначала по строке, в [13, 11], и проходит свободно. Обе прямые - честные Брезенхема, просто ничья «половина клетки» разрешилась в разные стороны. Правило «от меньшего номера к большему» строит для пары одну и ту же прямую, и несимметричных пар стало 0. Граница правила: симметрия куплена произволом - теперь видимость зависит от нумерации клеток. Игре это обычно безразлично; если нет, берут прямую, симметричную по построению, или считают клетку видимой, если видна хоть одна из двух прямых.

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

Стрельба из невидимости. Лучник A стреляет по B, а B не видит A и не может ответить - игроки называют это читом, хотя это округление.

Дроби вместо целых. Прямая на числах с плавающей точкой иногда пропускает клетку на границе «ровно половина», и тень за горой мерцает от хода к ходу.

Обзор, который съел бюджет. Радиус обзора подняли с 6 до 20 - работа выросла в 31,5 раза: 22 960 клеток прямых против 728, и ход перестал укладываться.

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

Прямая Брезенхема рисует линии на экране, ведёт резец станка с ЧПУ шагами по осям и проходит луч по сетке вокселей. Несимметричность дискретных решений встречается шире: два узла сети по-разному округляют таймер и по-разному решают, кто кого видел последним. Лечится тем же - одним правилом для пары.

Теперь сам

1. Сколько клеток строит прямая Брезенхема из [0, 0] в [3, 7]? Сколько шагов по строкам она сделает?
2. Радиус обзора вырос с 6 до 12. Во сколько раз вырастет число клеток прямых на один отряд?
3. Почему правило «от меньшего номера к большему» делает видимость симметричной?