Картата и гледането

Накратко: Полето на видимост е множеството клетки, които героят вижда: до всяка клетка в обхвата се прекарва линия на Bresenham, стената я спира, а видяното веднъж остава на картата като мъгла.

Проблем

Шефът се вижда от входа

Първото ниво на мината е 50 × 20 клетки, а картата на екрана е 40 × 13. Цялото ниво не се събира. И да се събираше, не бива да се вижда цялото: ако от входа виждаш Пазача на дълбините и всеки сандък, няма какво да откриваш.

Затова играта показва само това, което героят вижда, и помни видяното. Ето първия кадър, когато героят слезе в мината (от минаването, с което се проверява играта):

###                                      Горната галерия
#@.....#                                 Ниво 1 от 3
#......+
 ......#                                 Наоколо:
 ......                                  никой
 ######







Ива, варварин ур.1  опит 0/20  злато 5
Ж [############] 48/48   М [########] 4/4
Нов куест: „Кървавата следа“.
Нов куест: „Сребро за ковачката“.
Ти си в „Горната галерия“, ниво 1.

Стаята и вратата се виждат. Коридорът и залата зад вратата ги няма, макар че са на пет-шест клетки. За този кадър трябват пет неща: карта от текст, движение със сблъсък, камера, поле на видимост и мъгла. Урокът ги строи едно по едно на малко ниво 16 × 7, а после показва същото място в играта.

Идеята

Нивото е текст

Нивото на урока е 16 × 7:

################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################

Всеки знак е клетка: # стена, . под, + затворена врата, ~ вода, > стълби надолу, @ героят. Кодът не знае каква е формата на нивото. Той чете текста. Ново ниво е нов текст, без нито ред нов код.

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

from dataclasses import dataclass


@dataclass(frozen=True)
class Tile:
    glyph: str
    name: str
    walkable: bool
    opaque: bool


TILES = [
    Tile("#", "стена", False, True),
    Tile(".", "под", True, False),
    Tile("+", "врата", False, True),
    Tile("'", "отворена врата", True, False),
    Tile("~", "вода", False, False),
    Tile(">", "стълби", True, False),
]


def tile_of(glyph):
    for tile in TILES:
        if tile.glyph == glyph:
            return tile
    raise ValueError("Непозната клетка: " + glyph)


class Level:
    def __init__(self, text):
        rows = text.split("\n")
        self.height = len(rows)
        self.width = len(rows[0])
        self.hero_x = 0
        self.hero_y = 0
        self.cells = []
        for y in range(self.height):
            row = []
            for x in range(self.width):
                glyph = rows[y][x]
                if glyph == "@":
                    self.hero_x = x
                    self.hero_y = y
                    glyph = "."
                row.append(tile_of(glyph))
            self.cells.append(row)

    def in_bounds(self, x, y):
        return 0 <= x < self.width and 0 <= y < self.height

    # Извън картата е стена: никой не излиза и никой не гледа навън.
    def at(self, x, y):
        return self.cells[y][x] if self.in_bounds(x, y) else TILES[0]

MAP = """
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
""".strip()

level = Level(MAP)
print(f"Нивото е {level.width} × {level.height}, героят е на ({level.hero_x}, {level.hero_y}).")
for tile in TILES:
    count = 0
    for row in level.cells:
        for cell in row:
            if cell is tile:
                count += 1
    if count == 0:
        continue
    walk = "да" if tile.walkable else "не"
    sight = "да" if tile.opaque else "не"
    print(f"{tile.glyph} {tile.name}: {count}, минава се: {walk}, спира погледа: {sight}")

Нивото е 16 × 7, героят е на (6, 3).
# стена: 46, минава се: не, спира погледа: да
. под: 60, минава се: да, спира погледа: не
+ врата: 1, минава се: не, спира погледа: да
~ вода: 4, минава се: не, спира погледа: не
> стълби: 1, минава се: да, спира погледа: не

at(x, y) връща стена за всичко извън картата. Така нито движението, нито гледането трябва да проверяват границите: никой не излиза от картата, защото навън е стена.

@dataclass(frozen=True) прави записа: полетата се дават в конструктора и не се сменят.

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

В решетката има 112 клетки, но плочките са само шест обекта. Всяка клетка пази препратка към една от тях, затова броенето по-горе сравнява с is. Когато вратата се отвори, клетката просто започва да сочи друга плочка. Това е шаблонът „споделени леки обекти“ (flyweight): общото (името, свойствата) е на едно място, а мястото на картата е в решетката.

В канона клетките са знаци, а свойствата са два малки метода: isWalkable и isOpaque. Идеята е същата, формата е по-проста, защото видовете са осем и свойствата са две. Ако добавиш още (цена на движение, шум, светлина), таблицата пак печели.

Идеята

Нивата в играта

Трите нива на мината са в един текст в кода на играта. Всяко започва с ред level|1|… (дълбочината и името на четирите езика), после идват редовете на картата, легендата и end. Ето първото ниво без заглавния ред:

##################################################
#<.....#............#........1.#..~~~~~.......2..#
#......+....r.......+......g...#..~~~~~..........#
#......#............#..........+..~~~~~..........#
#......#............#..........#.........,.......#
########.........r..############........,........#
########............############........,........#
##############.#########################,#########
##############.#########################.#########
##############.#########################,#########
###....#.3............#########.........,...######
###.4..?.........s....+..................,..######
###....#...g..........#########..........,..######
########..............###################+########
##############.###############........5555555....#
##......................######............,......#
##..................r...######..............,L...#
##.>....................######......w............#
##......7...............######.................6.#
##################################################
legend|1|item|potion_heal|1
legend|2|gold|25|0
legend|3|item|antidote|1
legend|4|item|ring_life|1
legend|5|marker|lair|0
legend|6|gold|30|0
legend|7|item|potion_heal|1
end

Освен плочките има още знаци. Буквите (r, g, s, L) са врагове от таблицата на враговете. Цифрите са от легендата под картата: предмет, злато, знак за куест. < е мястото, където героят слиза. ? е тайна врата, която изглежда като стена. , е кръв по пода.

# Картата е текст: редовете между „level|…“ и „legend|…“ са самата карта, легендата казва какво
# значи всяка цифра. Тук само се четат определенията; живото ниво се строи в build_level.
def load_maps():
    current = None
    for raw_line in MAPS_DATA.split('\n'):
        line = trim_spaces(raw_line)
        if len(line) == 0:
            continue
        if line.startswith('level|'):
            cells = line.split('|')
            current = SimpleNamespace(depth=to_int(cells[1]), bg=cells[2], en=cells[3], de=cells[4], es=cells[5], rows=[], legend={})
        elif line.startswith('legend|'):
            cells = line.split('|')
            current.legend[cells[1]] = SimpleNamespace(kind=cells[2], value=cells[3], amount=to_int(cells[4]))
        elif line == 'end':
            MAP_DEFS.append(current)
            current = None
        else:
            current.rows.append(line)

Четенето е на две стъпки. loadMaps само разделя текста на определения. Живото ниво се строи с buildLevel при нова игра (и при зареждане): буквите стават врагове, цифрите стават предмети, а под тях остава под. Затова в решетката на нивото няма гоблин. Съществата са отделен списък и се движат по картата, а картата стои.

Идеята

Ходът е молба

Най-простият ход е heroX += dx. С него героят минава през стени и излиза от картата. Ходът трябва да е молба: „искам да вляза там“. Клетката, в която иска да влезе, решава:

# Ходът е молба: клетката, в която искаш да влезеш, решава.
def step(level, dx, dy):
    x = level.hero_x + dx
    y = level.hero_y + dy
    target = level.at(x, y)
    if target.glyph == "+":
        level.cells[y][x] = tile_of("'")
        return "Вратата изскърцва и се отваря."
    if not target.walkable:
        return "Не минаваш: " + target.name + "."
    level.hero_x = x
    level.hero_y = y
    return ""

стена или вода: не, и казва защо;
затворена врата: отваря се (става '), но героят остава на мястото си. Отварянето е ходът;
всичко друго: героят влиза.

Програмата чете команди w a s d (горе, ляво, долу, дясно), по една на ред, и след всяка рисува нивото. Входът е d a w d d d:

level = Level(MAP)
for line in sys.stdin:
    command = line.strip()
    if len(command) != 1:
        continue
    direction = MOVES.find(command)
    if direction < 0:
        continue
    message = step(level, DX[direction], DY[direction])
    print("> " + command + ("  " + message if message else ""))
    print_level(level)

> d  Не минаваш: стена.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> a  Не минаваш: вода.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> w
################
#......#.......#
#.....@+.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d  Вратата изскърцва и се отваря.
################
#......#.......#
#.....@'.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......@.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......'@......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################

Първите два хода са в стена и във вода: героят стои. После тръгва нагоре, отваря вратата и минава.

В играта стъпката прави повече неща и редът им е важен:

# Стъпка на героя: бой, разговор, врата, тайник, стена или движение.
def step_hero(self, dx, dy):
    level = self.level()
    hero = self.hero
    x = hero.x + dx
    y = hero.y + dy
    enemy = level.enemy_at(x, y)
    if enemy is not None:
        self.start_battle(enemy)
        return 'stop'
    npc = level.npc_at(x, y)
    if npc is not None:
        self.stack.push(DialogScreen(self, npc.id))
        return 'stop'
    tile = level.tile(x, y)
    if tile == '+':
        level.tiles[y][x] = "'"
        self.say(t('map.door'))
        self.world_turn()
        return 'stop' if len(self.stack.changes) > 0 else 'acted'
    if tile == '?':
        level.tiles[y][x] = '+'
        self.say(t('map.secret'))
        self.world_turn()
        return 'stop' if len(self.stack.changes) > 0 else 'acted'
    if not level.is_walkable(x, y):
        self.say(t('map.water' if tile == '~' else 'map.wall'))
        return 'blocked'
    if hero.has_effect('bleed'):
        level.add_blood(hero.x, hero.y)
    hero.x = x
    hero.y = y
    self.bus.publish(SimpleNamespace(type='TileEntered', depth=self.depth, x=x, y=y, decor=level.decor[y][x], marker=level.markers[y][x]))
    here = level.items_at(x, y)
    if len(here) > 0:
        names = []
        for item in here:
            names.append(item_label(item.id, item.count))
        self.say(t('map.itemsHere', {'items': ', '.join(names)}))
    self.world_turn()
    return 'stop' if len(self.stack.changes) > 0 else 'moved'

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

Блъскането в стена връща blocked и не вика worldTurn: грешката на играча не струва ход и враговете не се приближават. Вратата струва ход.

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

Тук водата просто не пуска. В много игри плитката вода пуска, но бавно: всяка плочка има цена на движение (подът 1, плитката вода 2, блатото 3), и героят трупа енергия, докато стигне цената, като енергията в боя (урокът за бойната система). Тогава walkable става число вместо да/не. Търсенето на път също трябва да знае цените: тогава BFS не стига и трябва Dijkstra.

Идеята

Камерата

Нивото на играта е 50 × 20, а изгледът е 40 × 13. Камерата е светът, видян през прозорец: cameraX и cameraY са клетката от света, която е в горния ляв ъгъл на екрана. От тях двете посоки са едно събиране:

от света към екрана: screenX = x − cameraX;
от екрана към света: x = cameraX + screenX.

Камерата следва героя: героят е в средата, затова cameraX = heroX − VIEW_W / 2. Близо до ръба на картата това дава отрицателно число или изглед, който излиза от картата. Затова камерата се затяга (clamp) между 0 и width − VIEW_W. Там изгледът спира, а героят тръгва към ръба на екрана.

VIEW_W = 9
VIEW_H = 5


def clamp(value, low, high):
    if value < low:
        return low
    if value > high:
        return high
    return value


def print_view(level):
    camera_x = clamp(level.hero_x - VIEW_W // 2, 0, level.width - VIEW_W)
    camera_y = clamp(level.hero_y - VIEW_H // 2, 0, level.height - VIEW_H)
    print(f"герой ({level.hero_x}, {level.hero_y}), камера ({camera_x}, {camera_y}"
          f"), на екрана ({level.hero_x - camera_x}, {level.hero_y - camera_y})")
    for view_y in range(VIEW_H):
        row = ""
        for view_x in range(VIEW_W):
            x = camera_x + view_x
            y = camera_y + view_y
            row += "@" if x == level.hero_x and y == level.hero_y else level.at(x, y).glyph
        print(row)

Програмата ползва изглед 9 × 5 върху нивото 16 × 7 и печата изгледа след всяка отсечка от пътя на героя:

level = Level(MAP)
for leg in ["", "wdddd", "ddddd", "sss"]:
    for command in leg:
        direction = MOVES.find(command)
        step(level, DX[direction], DY[direction])
    print_view(level)

герой (6, 3), камера (2, 1), на екрана (4, 2)
.....#...
.....+...
..~~@#...
..~~.#...
.....#...
герой (9, 2), камера (5, 0), на екрана (4, 2)
#########
..#......
..'.@....
~.#....>.
~.#......
герой (14, 2), камера (7, 0), на екрана (7, 2)
#########
#.......#
'......@#
#....>..#
#.......#
герой (14, 5), камера (7, 2), на екрана (7, 3)
'.......#
#....>..#
#.......#
#......@#
#########

Първите два изгледа са центрирани: героят е на (4, 2) на екрана. В третия камерата е стигнала дясното ограничение 16 − 9 = 7 и спира, а героят продължава към ръба. В четвъртия камерата е спряла и отдолу.

VIEW_W // 2 е цяло деление: 9 // 2 = 4.

camera_x = clamp(level.hero_x - VIEW_W // 2, 0, )

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

Ако нивото е по-тясно от изгледа, width − VIEW_W е отрицателно, и според мястото на героя clamp връща 0 или отрицателно число: камерата скача или излиза отляво на картата. В канона това не се случва, защото и трите нива са 50 × 20, но в игра с малки стаи нивото се центрира в изгледа: cameraX = (width − VIEW_W) / 2.

Камерата, която се мести с всяка стъпка, кара целия екран да подскача. Много игри държат мъртва зона: камерата мърда едва когато героят излезе от правоъгълник в средата. В конзолата, ход по ход, това рядко трябва; в игра с плавно движение е задължително.

В играта е същото с 40 × 13. Ето кадър по-надолу в първото ниво: камерата е слязла, затова горните редове на нивото не се виждат:

########............############........ Горната галерия
       #............#          #........ Ниво 1 от 3
       #######.#####           #########
                                       # Наоколо:
                 ######       ########## никой
              ........#########.........
              ...%.%@.'.................
              ........#########.........
              ........#       ##########
               ########                .
                                     ...
                                    ....
                                    ....
Ива, варварин ур.2  опит 40/55  злато 30
Ж [############] 57/57   М [########] 5/5
Гоблин копиеносец те забелязва!
Победа! Опит от боя: 21.
Ива стига ниво 2: ново умение: Вихър (клон Ярост).

Идеята

Първият опит: радиус

Героят трябва да вижда около себе си. Първата идея е радиус: виждаш всяка клетка, която е по-близо от 6.

RADIUS = 6


def radius_only(level, visible, seen):
    origin_x = level.hero_x
    origin_y = level.hero_y
    for y in range(level.height):
        for x in range(level.width):
            visible[y][x] = False
    for y in range(origin_y - RADIUS, origin_y + RADIUS + 1):
        for x in range(origin_x - RADIUS, origin_x + RADIUS + 1):
            if not level.in_bounds(x, y):
                continue
            dx = x - origin_x
            dy = y - origin_y
            if dx * dx + dy * dy > RADIUS * RADIUS + RADIUS:
                continue
            visible[y][x] = True
            seen[y][x] = True

visible е „виждам сега“. seen е „виждал съм някога“ и се ползва по-късно за мъглата. Ето какво вижда героят от старта:

level = Level(MAP)
visible = [[False] * level.width for _ in range(level.height)]
seen = [[False] * level.width for _ in range(level.height)]
radius_only(level, visible, seen)
report(level, visible, seen)

герой (6, 3): виждаш 87, помниш 87
| ###########    |
|#......#.....   |
|#......+.....   |
|#...~~@#....>   |
|#...~~.#.....   |
|#......#.....   |
| ###########    |

Виждат се 87 клетки и сред тях стълбите (>) зад стената. Затворената врата не пречи. Радиусът знае колко е далеч клетката, но не и какво има между нея и героя. Това е шефът, който се вижда от входа.

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

Защо условието е dx² + dy² ≤ R² + R, а не ≤ R²? При ≤ R² от кръга стърчат четири самотни клетки: (R, 0), (0, R) и симетричните им. Добавката + R го закръгля: за цели числа dx² + dy² ≤ R² + R е същото като разстояние до центъра на клетката под R + ½, защото (R + ½)² = R² + R + ¼. Без корен квадратен и без дробни числа.

Идеята

Права линия: Bresenham

Една клетка се вижда, ако правата линия от героя до нея не минава през стена. На решетка правата линия е поредица от клетки, и трябва да решиш кои. Алгоритъмът на Bresenham го прави само с цели числа: събиране, изваждане и умножение по 2.

Идеята: тръгваш от началото и на всяка стъпка правиш крачка по x, по y или и по двете. Коя, казва error: колко се е отклонила линията от истинската права. Когато отклонението по едната ос стане голямо, правиш крачка по нея и го намаляваш.

def line(x0, y0, x1, y1):
    cells = []
    dx = abs(x1 - x0)
    dy = -abs(y1 - y0)
    step_x = 1 if x0 < x1 else -1
    step_y = 1 if y0 < y1 else -1
    error = dx + dy
    x = x0
    y = y0
    while True:
        cells.append((x, y))
        if x == x1 and y == y1:
            return cells
        doubled = 2 * error
        if doubled >= dy:
            error += dy
            x += step_x
        if doubled <= dx:
            error += dx
            y += step_y

Програмата чертае линията от A = (0, 0) до B = (8, 3), а после и обратно, от B до A:

there = line(0, 0, 8, 3)
back = line(8, 3, 0, 0)
print("A → B: " + format_cells(there))
print("B → A: " + format_cells(back))
picture = [["."] * 9 for _ in range(4)]
for x, y in there:
    picture[y][x] = "*"
picture[0][0] = "A"
picture[3][8] = "B"
for row in picture:
    print("".join(row))

A → B: 0,0 1,0 2,1 3,1 4,2 5,2 6,2 7,3 8,3
B → A: 8,3 7,3 6,2 5,2 4,1 3,1 2,1 1,0 0,0
A*.......
..**.....
....***..
.......*B

Двете посоки минават почти през същите клетки, но не съвсем: отиване минава през 4,2, а връщане през 4,1. На средата грешката е точно наравно, и алгоритъмът избира едната страна. Обратно изборът е другата. Запомни това: ще ни трябва в слабостите на метода.

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

Откъде е error = dx + dy (с dy отрицателно)? Правата през двата края е f(x, y) = 0, където f е линейна, а знакът на f казва от коя страна си. error е f, умножено така, че да е цяло число, в точката, която би била следващата. Проверките 2 · error ≥ dy и 2 · error ≤ dx питат дали крачката по x, съответно по y, приближава линията. Затова алгоритъмът върви и в осемте посоки и не дели никъде.

Джак Брезенхам го измисля в IBM през 1962 г. за плотер: машината мести писалката само с една стъпка, а деленето е скъпо. Днес деленето не е скъпо, но целите числа дават един и същ резултат на всеки компютър и всеки език, а това за нашата игра е задължително.

Виж го

Поле на видимост и мъгла

Сега двете се събират. За всяка клетка в радиуса тръгва линия на Bresenham. Линията проверява две неща на всяка крачка: стигнахме ли и стена ли е тук. Редът им е важен. Ако е стигнала целта, клетката се вижда, дори да е стена. Ако по пътя преди целта има стена, линията спира: клетката не се вижда.

RADIUS = 6


def line_of_sight(level, x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = -abs(y1 - y0)
    step_x = 1 if x0 < x1 else -1
    step_y = 1 if y0 < y1 else -1
    error = dx + dy
    x = x0
    y = y0
    while True:
        if x == x1 and y == y1:
            return True
        if (x != x0 or y != y0) and level.at(x, y).opaque:
            return False
        doubled = 2 * error
        if doubled >= dy:
            error += dy
            x += step_x
        if doubled <= dx:
            error += dx
            y += step_y


def compute_fov(level, visible, seen):
    origin_x = level.hero_x
    origin_y = level.hero_y
    for y in range(level.height):
        for x in range(level.width):
            visible[y][x] = False
    for y in range(origin_y - RADIUS, origin_y + RADIUS + 1):
        for x in range(origin_x - RADIUS, origin_x + RADIUS + 1):
            if not level.in_bounds(x, y):
                continue
            dx = x - origin_x
            dy = y - origin_y
            if dx * dx + dy * dy > RADIUS * RADIUS + RADIUS:
                continue
            if line_of_sight(level, origin_x, origin_y, x, y):
                visible[y][x] = True
                seen[y][x] = True

def line_of_sight(level, x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = -abs(y1 - y0)
    step_x = 1 if x0 < x1 else -1
    step_y = 1 if y0 < y1 else -1
    error = dx + dy
    x = x0
    y = y0
    while True:
        if x == x1 and y == y1:
            return True
        if (x != x0 or y != y0) and level.at(x, y).opaque:
            return False
        doubled = 2 * error
        if doubled >= dy:
            error += dy
            x += step_x
        if doubled <= dx:
            error += dx
            y += step_y


def compute_fov(level, visible, seen):
    origin_x = level.hero_x
    origin_y = level.hero_y
    for y in range(level.height):
        for x in range(level.width):
            visible[y][x] = False
    for y in range(origin_y - RADIUS, origin_y + RADIUS + 1):
        for x in range(origin_x - RADIUS, origin_x + RADIUS + 1):
            if not level.in_bounds(x, y):
                continue
            dx = x - origin_x
            dy = y - origin_y
            if dx * dx + dy * dy > RADIUS * RADIUS + RADIUS:
                continue
            if line_of_sight(level, origin_x, origin_y, x, y):
                visible[y][x] = True
                seen[y][x] = True

Стъпка по стъпка, с думи

Героят е на (6, 3). Полето се смята наново всеки ход и първо всяка клетка става невидима. Още нищо не е видяно: цялото ниво е непознато.
Кандидатите са клетките в радиус 6: dx² + dy² ≤ 6² + 6. Те са 87, заедно със стаята зад стената. Радиусът не знае за стени.
Към всеки кандидат тръгва права линия (Bresenham). Тя спира на първата стена по пътя, но стига до нея, затова самата стена се вижда. 37 линии спират по-рано (сивите).
От (6, 3) виждаш 50 клетки и всички влизат в seen. Стаята вдясно е в радиуса, но затворената врата и стената я крият: стълбите остават непознати.
Героят отваря вратата и минава (wdddddd). Всеки ход visible се чисти, а seen остава: видяното, което вече не виждаш, става мъгла.
От (11, 2) линиите минават през отворената врата. В лявата стая се вижда само тесен клин: стената крие останалото.
Виждаш 63, помниш 109 от 112 клетки. Мъглата пази формата на лявата стая, но не и какво става в нея сега.

Всеки ход visible се чисти и се смята наново, а seen само се пълни. Програмата рисува видимото със знака му, видяното, което вече не се вижда, с :, а непознатото празно. Първо от старта, после след 7 хода (горе, вратата, пет пъти надясно):

level = Level(MAP)
visible = [[False] * level.width for _ in range(level.height)]
seen = [[False] * level.width for _ in range(level.height)]
compute_fov(level, visible, seen)
report(level, visible, seen)
for command in "wdddddd":
    direction = MOVES.find(command)
    step(level, DX[direction], DY[direction])
    compute_fov(level, visible, seen)
report(level, visible, seen)

герой (6, 3): виждаш 50, помниш 50
| ######         |
|#......         |
|#......+        |
|#...~~@#        |
|#...~~.#        |
|#......         |
| ######         |
герой (11, 2): виждаш 63, помниш 109
| :::::::####### |
|:::::::#.......#|
|:::::..'...@...#|
|:::::::#....>..#|
|:::::::#.......#|
|:::::::#.......#|
| ::::::#########|

Отначало стълбите не се виждат: стената и затворената врата ги крият. След като героят мине, лявата стая е мъгла. Той знае каква е, но не вижда какво става в нея: враг, който влезе там, няма да се появи на екрана.

В играта полето е същият код, на същото място в хода:

# Поле на видимост: клетка се вижда, ако е в радиуса и линията до нея (Bresenham) не минава
# през стена или затворена врата. Видяното се помни: това е мъглата.
FOV_RADIUS = 6


def line_of_sight(level, x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = -abs(y1 - y0)
    step_x = 1 if x0 < x1 else -1
    step_y = 1 if y0 < y1 else -1
    error = dx + dy
    x = x0
    y = y0
    while True:
        if x == x1 and y == y1:
            return True
        if (x != x0 or y != y0) and level.is_opaque(x, y):
            return False
        doubled = 2 * error
        if doubled >= dy:
            error += dy
            x += step_x
        if doubled <= dx:
            error += dx
            y += step_y


def compute_fov(level, origin_x, origin_y):
    for y in range(level.height):
        for x in range(level.width):
            level.visible[y][x] = False
    for y in range(origin_y - FOV_RADIUS, origin_y + FOV_RADIUS + 1):
        for x in range(origin_x - FOV_RADIUS, origin_x + FOV_RADIUS + 1):
            if not level.in_bounds(x, y):
                continue
            dx = x - origin_x
            dy = y - origin_y
            if dx * dx + dy * dy > FOV_RADIUS * FOV_RADIUS + FOV_RADIUS:
                continue
            if line_of_sight(level, origin_x, origin_y, x, y):
                level.visible[y][x] = True
                level.seen[y][x] = True

MapScreen го вика в update, след всяка команда. Рисуването на картата пък показва камерата и мъглата наведнъж: клетка, която никога не е видяна, се прескача (continue), видимата е в цвета си, а видяната е сива:

def draw(self, buffer):
    game = self.game
    level = game.level()
    hero = game.hero
    camera_x = clamp(hero.x - VIEW_WIDTH // 2, 0, level.width - VIEW_WIDTH)
    camera_y = clamp(hero.y - VIEW_HEIGHT // 2, 0, level.height - VIEW_HEIGHT)
    for view_y in range(VIEW_HEIGHT):
        for view_x in range(VIEW_WIDTH):
            x = camera_x + view_x
            y = camera_y + view_y
            if not level.seen[y][x]:
                continue
            cell = cell_look(level, x, y)
            buffer.put(view_x, view_y, cell.ch, cell.color if level.visible[y][x] else 'gray')
    buffer.put(hero.x - camera_x, hero.y - camera_y, '@', 'white')
    self.draw_side_panel(buffer, level)
    draw_hud(buffer, game, VIEW_HEIGHT)
    draw_messages(buffer, game, VIEW_HEIGHT + 2, 3)

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

########                                 Горната галерия
#<.....# ....                            Ниво 1 от 3
#.....@'....r
#......# ....                            Наоколо:
#......#   ..                            r гигантски плъх
########







Ива, варварин ур.1  опит 0/20  злато 5
Ж [############] 48/48   М [########] 4/4
Вратата изскърцва и се отваря.
Гигантски плъх те забелязва!
Виждаш: гигантски плъх.

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

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

Колко струва? Кръгът с радиус 6 има 137 клетки, а линията до всяка е най-много 6 крачки: под 1000 проверки на ход. Това е O(r³) на ход: r² клетки по r крачки.

Пробвай

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

Малка стая с колона в средата. Героят е вляво от колоната, а радиусът стига до всяка клетка. Какво печата програмата?

room = """
#######
#.....#
#@.#..#
#.....#
#######
""".strip()
level = Level(room)
visible = [[False] * level.width for _ in range(level.height)]
seen = [[False] * level.width for _ in range(level.height)]
compute_fov(level, visible, seen)
print_sight(level, visible, seen)

Отговор

| ####  |
|#..... |
|#@.#   |
|#..... |
| ####  |

|       |
| ..... |
| @.    |
| ..... |
|       |

|#######|
|#.....#|
|#@.#..#|
|#.....#|
|#######|

Пробвай

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

Колега пипна линията и сега от старта програмата печата това:

def line_of_sight(level, x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = -abs(y1 - y0)
    step_x = 1 if x0 < x1 else -1
    step_y = 1 if y0 < y1 else -1
    error = dx + dy
    x = x0
    y = y0
    while True:
        if (x != x0 or y != y0) and level.at(x, y).opaque:
            return False
        if x == x1 and y == y1:
            return True
        doubled = 2 * error
        if doubled >= dy:
            error += dy
            x += step_x
        if doubled <= dx:
            error += dx
            y += step_y

герой (6, 3): виждаш 30, помниш 30
|                |
| ......         |
| ......         |
| ...~~@         |
| ...~~.         |
| ......         |
|                |

Подът се вижда, вратата и стените са изчезнали, а през водата е както преди. Кой ред проверява твърде рано?

Избери реда с грешката.

По-точно

Слабостите на простия метод

Линия до всяка клетка е най-простото поле на видимост. Има три известни слабости, и всичките се виждат в нашата игра.

Дупки до стените. Погледни пак първия кадър от старта: героят е до вратата, а стената на (7, 1) и (7, 5) не се вижда, макар че подът до нея се вижда. Линията до (7, 1) прави първата си крачка по диагонал и стъпва на вратата (7, 2): спира. Същото е в кадъра от мината в началото на урока: героят е до лявата стена и тя има дупка. Когато гледаш стена почти по дължината ѝ, линията опира в съседната клетка от същата стена.

Асиметрия. От A виждаш B, а от B не виждаш A, защото линията обратно минава през други клетки (видя го с 4,2 и 4,1). На първото ниво на мината такива двойки клетки са 89 от 17248: от (12, 4) се вижда (14, 8), а обратно не. В канона това има последствия. Врагът гледа със своя линия, от себе си към героя (enemySeesHero, до 8 клетки), а ти виждаш с полето от героя. Затова гоблин може да те забележи, преди ти да го видиш. Играта поне не издава повече, отколкото виждаш: съобщението, че врагът се е събудил, се пише само ако той е във видимото.

По-евтиният вариант има дупки в залите. Вместо линия до всяка клетка може да пускаш линии само до ръба на кръга и да отбелязваш всичко по пътя им. Това е O(r²) вместо O(r³). Но лъчите се разминават с разстоянието и между тях остават непокрити клетки: при радиус 6 те са 8 от 137, а при радиус 20 са 80 от 1313. В голяма зала това са дупки в пода и в далечните стени.

По-добрите алгоритми. Shadowcasting обхожда осемте сектора около героя ред по ред и пази „сенките“ като интервали от наклони. Всяка клетка се поглежда веднъж, няма дупки, а има и симетрично shadowcasting, при което A вижда B точно когато B вижда A. Permissive FOV казва, че клетката се вижда, ако някоя права от някоя точка на клетката на героя до някоя точка на целта е свободна. Той е симетричен по определение и вижда повече около ъглите.

Защо канонът пази простия. Нивата са 50 × 20, а радиусът е 6: под 1000 проверки на ход, нищо за който и да е компютър. Целите числа дават един и същ резултат на четирите езика, а това е проверката на портовете. И се обяснява в една карта. Ако играта стане с големи открити пространства и далечно гледане, тогава смяната на computeFov е на едно място.

Упражнение

Тайната врата

Реши задачата в редактора си.

Тайна врата. Добави плочка ?: изглежда като стена (рисува се #), не се минава и спира погледа. Когато героят се блъсне в нея, тя става затворена врата + и програмата пише „Стената кънти на кухо... Тайна врата!“. Следващото блъскане я отваря, както всяка врата. Нивото е:

################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.?.......#
#......#.......#
################

С вход s d d d d (по един на ред) изходът е:

> s
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@#.......#
#......#.......#
################
> d  Стената кънти на кухо... Тайна врата!
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@+.......#
#......#.......#
################
> d  Вратата изскърцва и се отваря.
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@'.......#
#......#.......#
################
> d
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~.@.......#
#......#.......#
################
> d
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~.'@......#
#......#.......#
################

Още задачи

Факла. Направи радиуса параметър. Героят с факла вижда на 6, без факла на 2. Каква част от лявата стая вижда от старта без факла?
Изгледът и мъглата заедно. Събери камерата и полето: изглед 9 × 5 върху нивото, който показва видимото, видяното (:) и непознатото, както draw в играта.
Кой кого вижда. Напиши програма, която за нивото на урока брои двойките подови клетки, от които едната вижда другата, а обратното не.

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·

Картата и гледането

Бисквитки