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

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

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

Проблем

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

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

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

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














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

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

Идеята

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

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

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

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

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

const TILES = [
  { glyph: "#", name: "стена", walkable: false, opaque: true },
  { glyph: ".", name: "под", walkable: true, opaque: false },
  { glyph: "+", name: "врата", walkable: false, opaque: true },
  { glyph: "'", name: "отворена врата", walkable: true, opaque: false },
  { glyph: "~", name: "вода", walkable: false, opaque: false },
  { glyph: ">", name: "стълби", walkable: true, opaque: false },
];


function tileOf(glyph) {
  for (const tile of TILES) {
    if (tile.glyph === glyph) return tile;
  }
  throw new Error(`Непозната клетка: ${glyph}`);
}


class Level {
  constructor(text) {
    const rows = text.split("\n");
    this.height = rows.length;
    this.width = rows[0].length;
    this.heroX = 0;
    this.heroY = 0;
    this.cells = [];
    for (let y = 0; y < this.height; y++) {
      const row = [];
      for (let x = 0; x < this.width; x++) {
        let glyph = rows[y][x];
        if (glyph === "@") {
          this.heroX = x;
          this.heroY = y;
          glyph = ".";
        }
        row.push(tileOf(glyph));
      }
      this.cells.push(row);
    }
  }


  inBounds(x, y) {
    return x >= 0 && y >= 0 && x < this.width && y < this.height;
  }


  // Извън картата е стена: никой не излиза и никой не гледа навън.
  at(x, y) {
    return this.inBounds(x, y) ? this.cells[y][x] : TILES[0];
  }
}
const MAP = `
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################`.trim();


const level = new Level(MAP);
console.log(`Нивото е ${level.width} × ${level.height}, героят е на (${level.heroX}, ${level.heroY}).`);
for (const tile of TILES) {
  let count = 0;
  for (const row of level.cells) {
    for (const cell of row) {
      if (cell === tile) count++;
    }
  }
  if (count === 0) continue;
  const walk = tile.walkable ? "да" : "не";
  const sight = tile.opaque ? "да" : "не";
  console.log(`${tile.glyph} ${tile.name}: ${count}, минава се: ${walk}, спира погледа: ${sight}`);
}
Изход
Нивото е 16 × 7, героят е на (6, 3).
# стена: 46, минава се: не, спира погледа: да
. под: 60, минава се: да, спира погледа: не
+ врата: 1, минава се: не, спира погледа: да
~ вода: 4, минава се: не, спира погледа: не
> стълби: 1, минава се: да, спира погледа: не

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

Плочките са обикновени обекти в масив. Решетката пази препратки към тях, не копия.
По-точно, за любопитните

В решетката има 112 клетки, но плочките са само шест обекта. Всяка клетка пази препратка към една от тях, затова броенето по-горе сравнява с ===. Когато вратата се отвори, клетката просто започва да сочи друга плочка. Това е шаблонът „споделени леки обекти“ (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|…“ са самата карта, легендата казва какво
// значи всяка цифра. Тук само се четат определенията; живото ниво се строи в buildLevel.
function loadMaps() {
  let current = null;
  for (const rawLine of MAPS_DATA.split('\n')) {
    const line = trimSpaces(rawLine);
    if (line.length === 0) continue;
    if (line.startsWith('level|')) {
      const cells = line.split('|');
      current = { depth: toInt(cells[1]), bg: cells[2], en: cells[3], de: cells[4], es: cells[5], rows: [], legend: new Map() };
    } else if (line.startsWith('legend|')) {
      const cells = line.split('|');
      current.legend.set(cells[1], { kind: cells[2], value: cells[3], amount: toInt(cells[4]) });
    } else if (line === 'end') {
      MAP_DEFS.push(current);
      current = null;
    } else {
      current.rows.push(line);
    }
  }
}

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

Идеята

Ходът е молба

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

// Ходът е молба: клетката, в която искаш да влезеш, решава.
function step(level, dx, dy) {
  const x = level.heroX + dx;
  const y = level.heroY + dy;
  const target = level.at(x, y);
  if (target.glyph === "+") {
    level.cells[y][x] = tileOf("'");
    return "Вратата изскърцва и се отваря.";
  }
  if (!target.walkable) return `Не минаваш: ${target.name}.`;
  level.heroX = x;
  level.heroY = y;
  return "";
}
  • стена или вода: не, и казва защо;
  • затворена врата: отваря се (става '), но героят остава на мястото си. Отварянето е ходът;
  • всичко друго: героят влиза.

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

const level = new Level(MAP);
const rl = createInterface({ input: process.stdin });
for await (const line of rl) {
  const command = line.trim();
  if (command.length !== 1) continue;
  const dir = MOVES.indexOf(command);
  if (dir < 0) continue;
  const message = step(level, DX[dir], DY[dir]);
  console.log(message === "" ? `> ${command}` : `> ${command}  ${message}`);
  printLevel(level);
}
Изход
> d  Не минаваш: стена.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> a  Не минаваш: вода.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> w
################
#......#.......#
#.....@+.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d  Вратата изскърцва и се отваря.
################
#......#.......#
#.....@'.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......@.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......'@......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################

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

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

// Стъпка на героя: бой, разговор, врата, тайник, стена или движение.
stepHero(dx, dy) {
  const level = this.level();
  const hero = this.hero;
  const x = hero.x + dx;
  const y = hero.y + dy;
  const enemy = level.enemyAt(x, y);
  if (enemy !== null) {
    this.startBattle(enemy);
    return 'stop';
  }
  const npc = level.npcAt(x, y);
  if (npc !== null) {
    this.stack.push(new DialogScreen(this, npc.id));
    return 'stop';
  }
  const tile = level.tile(x, y);
  if (tile === '+') {
    level.tiles[y][x] = "'";
    this.say(t('map.door'));
    this.worldTurn();
    return this.stack.changes.length > 0 ? 'stop' : 'acted';
  }
  if (tile === '?') {
    level.tiles[y][x] = '+';
    this.say(t('map.secret'));
    this.worldTurn();
    return this.stack.changes.length > 0 ? 'stop' : 'acted';
  }
  if (!level.isWalkable(x, y)) {
    this.say(t(tile === '~' ? 'map.water' : 'map.wall'));
    return 'blocked';
  }
  if (hero.hasEffect('bleed')) level.addBlood(hero.x, hero.y);
  hero.x = x;
  hero.y = y;
  this.bus.publish({ type: 'TileEntered', depth: this.depth, x: x, y: y, decor: level.decor[y][x], marker: level.markers[y][x] });
  const here = level.itemsAt(x, y);
  if (here.length > 0) {
    const names = [];
    for (const item of here) names.push(itemLabel(item.id, item.count));
    this.say(t('map.itemsHere', { items: names.join(', ') }));
  }
  this.worldTurn();
  return this.stack.changes.length > 0 ? 'stop' : '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. Там изгледът спира, а героят тръгва към ръба на екрана.

const VIEW_W = 9;
const VIEW_H = 5;


function clamp(value, low, high) {
  if (value < low) return low;
  if (value > high) return high;
  return value;
}


function printView(level) {
  const cameraX = clamp(level.heroX - Math.floor(VIEW_W / 2), 0, level.width - VIEW_W);
  const cameraY = clamp(level.heroY - Math.floor(VIEW_H / 2), 0, level.height - VIEW_H);
  console.log(`герой (${level.heroX}, ${level.heroY}), камера (${cameraX}, ${cameraY}` +
    `), на екрана (${level.heroX - cameraX}, ${level.heroY - cameraY})`);
  for (let viewY = 0; viewY < VIEW_H; viewY++) {
    let row = "";
    for (let viewX = 0; viewX < VIEW_W; viewX++) {
      const x = cameraX + viewX;
      const y = cameraY + viewY;
      row += x === level.heroX && y === level.heroY ? "@" : level.at(x, y).glyph;
    }
    console.log(row);
  }
}

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

const level = new Level(MAP);
for (const leg of ["", "wdddd", "ddddd", "sss"]) {
  for (const command of leg) {
    const dir = MOVES.indexOf(command);
    step(level, DX[dir], DY[dir]);
  }
  printView(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 и спира, а героят продължава към ръба. В четвъртия камерата е спряла и отдолу.

Math.floor(VIEW_W / 2) е цялото деление: 4.
const cameraX = clamp(level.heroX - Math.floor(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.

const RADIUS = 6;


function radiusOnly(level, visible, seen) {
  const originX = level.heroX;
  const originY = level.heroY;
  for (let y = 0; y < level.height; y++) {
    for (let x = 0; x < level.width; x++) visible[y][x] = false;
  }
  for (let y = originY - RADIUS; y <= originY + RADIUS; y++) {
    for (let x = originX - RADIUS; x <= originX + RADIUS; x++) {
      if (!level.inBounds(x, y)) continue;
      const dx = x - originX;
      const dy = y - originY;
      if (dx * dx + dy * dy > RADIUS * RADIUS + RADIUS) continue;
      visible[y][x] = true;
      seen[y][x] = true;
    }
  }
}

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

const level = new Level(MAP);
const visible = Array.from({ length: level.height }, () => new Array(level.width).fill(false));
const seen = Array.from({ length: level.height }, () => new Array(level.width).fill(false));
radiusOnly(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: колко се е отклонила линията от истинската права. Когато отклонението по едната ос стане голямо, правиш крачка по нея и го намаляваш.

function line(x0, y0, x1, y1) {
  const cells = [];
  const dx = Math.abs(x1 - x0);
  const dy = -Math.abs(y1 - y0);
  const stepX = x0 < x1 ? 1 : -1;
  const stepY = y0 < y1 ? 1 : -1;
  let error = dx + dy;
  let x = x0;
  let y = y0;
  while (true) {
    cells.push([x, y]);
    if (x === x1 && y === y1) return cells;
    const doubled = 2 * error;
    if (doubled >= dy) {
      error += dy;
      x += stepX;
    }
    if (doubled <= dx) {
      error += dx;
      y += stepY;
    }
  }
}

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

const there = line(0, 0, 8, 3);
const back = line(8, 3, 0, 0);
console.log(`A → B: ${format(there)}`);
console.log(`B → A: ${format(back)}`);
const picture = Array.from({ length: 4 }, () => new Array(9).fill("."));
for (const [x, y] of there) picture[y][x] = "*";
picture[0][0] = "A";
picture[3][8] = "B";
for (const row of picture) console.log(row.join(""));
Изход
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. Линията проверява две неща на всяка крачка: стигнахме ли и стена ли е тук. Редът им е важен. Ако е стигнала целта, клетката се вижда, дори да е стена. Ако по пътя преди целта има стена, линията спира: клетката не се вижда.

const RADIUS = 6;


function lineOfSight(level, x0, y0, x1, y1) {
  const dx = Math.abs(x1 - x0);
  const dy = -Math.abs(y1 - y0);
  const stepX = x0 < x1 ? 1 : -1;
  const stepY = y0 < y1 ? 1 : -1;
  let error = dx + dy;
  let x = x0;
  let y = y0;
  while (true) {
    if (x === x1 && y === y1) return true;
    if ((x !== x0 || y !== y0) && level.at(x, y).opaque) return false;
    const doubled = 2 * error;
    if (doubled >= dy) {
      error += dy;
      x += stepX;
    }
    if (doubled <= dx) {
      error += dx;
      y += stepY;
    }
  }
}


function computeFov(level, visible, seen) {
  const originX = level.heroX;
  const originY = level.heroY;
  for (let y = 0; y < level.height; y++) {
    for (let x = 0; x < level.width; x++) visible[y][x] = false;
  }
  for (let y = originY - RADIUS; y <= originY + RADIUS; y++) {
    for (let x = originX - RADIUS; x <= originX + RADIUS; x++) {
      if (!level.inBounds(x, y)) continue;
      const dx = x - originX;
      const dy = y - originY;
      if (dx * dx + dy * dy > RADIUS * RADIUS + RADIUS) continue;
      if (lineOfSight(level, originX, originY, x, y)) {
        visible[y][x] = true;
        seen[y][x] = true;
      }
    }
  }
}

function lineOfSight(level, x0, y0, x1, y1) {
  const dx = Math.abs(x1 - x0);
  const dy = -Math.abs(y1 - y0);
  const stepX = x0 < x1 ? 1 : -1;
  const stepY = y0 < y1 ? 1 : -1;
  let error = dx + dy;
  let x = x0;
  let y = y0;
  while (true) {
    if (x === x1 && y === y1) return true;
    if ((x !== x0 || y !== y0) && level.at(x, y).opaque) return false;
    const doubled = 2 * error;
    if (doubled >= dy) {
      error += dy;
      x += stepX;
    }
    if (doubled <= dx) {
      error += dx;
      y += stepY;
    }
  }
}


function computeFov(level, visible, seen) {
  const originX = level.heroX;
  const originY = level.heroY;
  for (let y = 0; y < level.height; y++) {
    for (let x = 0; x < level.width; x++) visible[y][x] = false;
  }
  for (let y = originY - RADIUS; y <= originY + RADIUS; y++) {
    for (let x = originX - RADIUS; x <= originX + RADIUS; x++) {
      if (!level.inBounds(x, y)) continue;
      const dx = x - originX;
      const dy = y - originY;
      if (dx * dx + dy * dy > RADIUS * RADIUS + RADIUS) continue;
      if (lineOfSight(level, originX, originY, x, y)) {
        visible[y][x] = true;
        seen[y][x] = true;
      }
    }
  }
}
Стъпка по стъпка, с думи
  1. Героят е на (6, 3). Полето се смята наново всеки ход и първо всяка клетка става невидима. Още нищо не е видяно: цялото ниво е непознато.
  2. Кандидатите са клетките в радиус 6: dx² + dy² ≤ 6² + 6. Те са 87, заедно със стаята зад стената. Радиусът не знае за стени.
  3. Към всеки кандидат тръгва права линия (Bresenham). Тя спира на първата стена по пътя, но стига до нея, затова самата стена се вижда. 37 линии спират по-рано (сивите).
  4. От (6, 3) виждаш 50 клетки и всички влизат в seen. Стаята вдясно е в радиуса, но затворената врата и стената я крият: стълбите остават непознати.
  5. Героят отваря вратата и минава (wdddddd). Всеки ход visible се чисти, а seen остава: видяното, което вече не виждаш, става мъгла.
  6. От (11, 2) линиите минават през отворената врата. В лявата стая се вижда само тесен клин: стената крие останалото.
  7. Виждаш 63, помниш 109 от 112 клетки. Мъглата пази формата на лявата стая, но не и какво става в нея сега.

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

const level = new Level(MAP);
const visible = Array.from({ length: level.height }, () => new Array(level.width).fill(false));
const seen = Array.from({ length: level.height }, () => new Array(level.width).fill(false));
computeFov(level, visible, seen);
report(level, visible, seen);
for (const command of "wdddddd") {
  const dir = MOVES.indexOf(command);
  step(level, DX[dir], DY[dir]);
  computeFov(level, visible, seen);
}
report(level, visible, seen);
Изход
герой (6, 3): виждаш 50, помниш 50
| ######         |
|#......         |
|#......+        |
|#...~~@#        |
|#...~~.#        |
|#......         |
| ######         |
герой (11, 2): виждаш 63, помниш 109
| :::::::####### |
|:::::::#.......#|
|:::::..'...@...#|
|:::::::#....>..#|
|:::::::#.......#|
|:::::::#.......#|
| ::::::#########|

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

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

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


function lineOfSight(level, x0, y0, x1, y1) {
  const dx = Math.abs(x1 - x0);
  const dy = -Math.abs(y1 - y0);
  const stepX = x0 < x1 ? 1 : -1;
  const stepY = y0 < y1 ? 1 : -1;
  let error = dx + dy;
  let x = x0;
  let y = y0;
  while (true) {
    if (x === x1 && y === y1) return true;
    if ((x !== x0 || y !== y0) && level.isOpaque(x, y)) return false;
    const doubled = 2 * error;
    if (doubled >= dy) {
      error += dy;
      x += stepX;
    }
    if (doubled <= dx) {
      error += dx;
      y += stepY;
    }
  }
}


function computeFov(level, originX, originY) {
  for (let y = 0; y < level.height; y++) {
    for (let x = 0; x < level.width; x++) level.visible[y][x] = false;
  }
  for (let y = originY - FOV_RADIUS; y <= originY + FOV_RADIUS; y++) {
    for (let x = originX - FOV_RADIUS; x <= originX + FOV_RADIUS; x++) {
      if (!level.inBounds(x, y)) continue;
      const dx = x - originX;
      const dy = y - originY;
      if (dx * dx + dy * dy > FOV_RADIUS * FOV_RADIUS + FOV_RADIUS) continue;
      if (lineOfSight(level, originX, originY, x, y)) {
        level.visible[y][x] = true;
        level.seen[y][x] = true;
      }
    }
  }
}

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

draw(buffer) {
  const game = this.game;
  const level = game.level();
  const hero = game.hero;
  const cameraX = clamp(hero.x - Math.floor(VIEW_WIDTH / 2), 0, level.width - VIEW_WIDTH);
  const cameraY = clamp(hero.y - Math.floor(VIEW_HEIGHT / 2), 0, level.height - VIEW_HEIGHT);
  for (let viewY = 0; viewY < VIEW_HEIGHT; viewY++) {
    for (let viewX = 0; viewX < VIEW_WIDTH; viewX++) {
      const x = cameraX + viewX;
      const y = cameraY + viewY;
      if (!level.seen[y][x]) continue;
      const cell = cellLook(level, x, y);
      buffer.put(viewX, viewY, cell.ch, level.visible[y][x] ? cell.color : 'gray');
    }
  }
  buffer.put(hero.x - cameraX, hero.y - cameraY, '@', 'white');
  this.drawSidePanel(buffer, level);
  drawHud(buffer, game, VIEW_HEIGHT);
  drawMessages(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 крачки.

Пробвай

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

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

const room = `
#######
#.....#
#@.#..#
#.....#
#######`.trim();
const level = new Level(room);
const visible = Array.from({ length: level.height }, () => new Array(level.width).fill(false));
const seen = Array.from({ length: level.height }, () => new Array(level.width).fill(false));
computeFov(level, visible, seen);
printSight(level, visible, seen);
Отговор

Пробвай

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

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

function lineOfSight(level, x0, y0, x1, y1) {
  const dx = Math.abs(x1 - x0);
  const dy = -Math.abs(y1 - y0);
  const stepX = x0 < x1 ? 1 : -1;
  const stepY = y0 < y1 ? 1 : -1;
  let error = dx + dy;
  let x = x0;
  let y = y0;
  while (true) {
    if ((x !== x0 || y !== y0) && level.at(x, y).opaque) return false;
    if (x === x1 && y === y1) return true;
    const doubled = 2 * error;
    if (doubled >= dy) {
      error += dy;
      x += stepX;
    }
    if (doubled <= dx) {
      error += dx;
      y += stepY;
    }
  }
}
Изход
герой (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 в играта.
  • Кой кого вижда. Напиши програма, която за нивото на урока брои двойките подови клетки, от които едната вижда другата, а обратното не.

Тест

Провери се

1. В играта героят се блъска в стена и нищо не става. Отваря врата и враговете правят ход. Защо е различно?
2. Нивото е 50 × 20, изгледът е 40 × 13, героят е на x = 47. Колко е cameraX?
3. Стената спира погледа. Защо тогава самата стена се вижда?
4. Кое е вярно за visible и seen?
5. В играта от клетка A виждаш клетка B, а от B не виждаш A. Как е възможно?

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