El mapa y el campo de visión

En resumen: El campo de visión es el conjunto de celdas que el héroe ve: hacia cada celda al alcance se traza una línea de Bresenham, una pared la detiene, y lo que se vio una vez queda en el mapa como niebla.

Problema

El jefe se ve desde la entrada

El primer nivel de la mina mide 50 × 20 celdas, y el mapa en la pantalla es de 40 × 13. El nivel entero no cabe. Y aunque cupiera, no deberías verlo todo: si ves al Guardián abisal y cada cofre desde la entrada, no queda nada por descubrir.

Por eso el juego muestra solo lo que el héroe ve, y recuerda lo que el héroe ha visto. Este es el primer fotograma después de que el héroe baja a la mina (del recorrido con el que se comprueba el juego):

###                                      Galería alta
#@.....#                                 Nivel 1 de 3
#......+
 ......#                                 Alrededor:
 ......                                  nadie
 ######







Iva, bárbaro nv.1  exp 0/20  oro 5
V [############] 48/48   M [########] 4/4
Nueva misión: El rastro de sangre.
Nueva misión: Plata para la herrera.
Nivel 1: Galería alta.

Ves la sala y la puerta. El pasillo y la sala grande detrás de la puerta no están, aunque están a cinco o seis celdas. Este fotograma necesita cinco cosas: un mapa hecho de texto, movimiento con colisión, una cámara, un campo de visión y niebla. La lección las construye una a una en un nivel pequeño de 16 × 7, y después muestra el mismo lugar en el juego.

La idea

El nivel es texto

El nivel de esta lección es de 16 × 7:

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

Cada carácter es una celda: # pared, . suelo, + puerta cerrada, ~ agua, > escaleras hacia abajo, @ el héroe. El código no conoce la forma del nivel. Lee el texto. Un nivel nuevo es un texto nuevo, sin una sola línea de código nueva.

Para moverse y mirar, una celda tiene que responder dos preguntas: ¿se puede pasar por ella? y ¿bloquea la vista? Las dos respuestas no siempre van juntas. Se puede ver a través del agua, pero no se puede pasar por ella. Una puerta cerrada bloquea la vista y no te deja entrar. Así que una baldosa es un registro con un carácter, un nombre y las dos respuestas, y la tabla de baldosas son datos:

const TILES = [
  { glyph: "#", name: "pared", walkable: false, opaque: true },
  { glyph: ".", name: "suelo", walkable: true, opaque: false },
  { glyph: "+", name: "puerta", walkable: false, opaque: true },
  { glyph: "'", name: "puerta abierta", walkable: true, opaque: false },
  { glyph: "~", name: "agua", walkable: false, opaque: false },
  { glyph: ">", name: "escaleras", walkable: true, opaque: false },
];

function tileOf(glyph) {
  for (const tile of TILES) {
    if (tile.glyph === glyph) return tile;
  }
  throw new Error(`Celda desconocida: ${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;
  }

  // Fuera del mapa hay pared: nadie sale y nadie mira hacia afuera.
  at(x, y) {
    return this.inBounds(x, y) ? this.cells[y][x] : TILES[0];
  }
}

const MAP = `
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################`.trim();

const level = new Level(MAP);
console.log(`El nivel es ${level.width} × ${level.height}, el héroe está en (${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 ? "sí" : "no";
  const sight = tile.opaque ? "sí" : "no";
  console.log(`${tile.glyph} ${tile.name}: ${count}, se puede pasar: ${walk}, bloquea la vista: ${sight}`);
}

El nivel es 16 × 7, el héroe está en (6, 3).
# pared: 46, se puede pasar: no, bloquea la vista: sí
. suelo: 60, se puede pasar: sí, bloquea la vista: no
+ puerta: 1, se puede pasar: no, bloquea la vista: sí
~ agua: 4, se puede pasar: no, bloquea la vista: no
> escaleras: 1, se puede pasar: sí, bloquea la vista: no

at(x, y) devuelve una pared para todo lo que está fuera del mapa. Así ni el movimiento ni la vista tienen que comprobar los límites: nadie sale del mapa, porque fuera hay pared.

Las baldosas son objetos simples en un arreglo. La cuadrícula guarda referencias a ellas, no copias.

Más precisamente, para curiosos

La cuadrícula tiene 112 celdas, pero solo hay seis objetos baldosa. Cada celda guarda una referencia a uno de ellos, por eso el conteo de arriba compara con ===. Cuando la puerta se abre, la celda simplemente empieza a apuntar a otra baldosa. Es el patrón Flyweight: lo que se comparte (el nombre, las propiedades) está en un solo lugar, y la posición en el mapa está en la cuadrícula.

En el canon las celdas son caracteres, y las propiedades son dos métodos pequeños: isWalkable e isOpaque. La idea es la misma y la forma es más simple, porque hay ocho tipos y dos propiedades. Si añades más (coste de movimiento, ruido, luz), la tabla vuelve a ganar.

La idea

Los niveles del juego

Los tres niveles de la mina están en un solo texto dentro del código del juego. Cada uno empieza con una línea level|1|… (la profundidad y el nombre en los cuatro idiomas), luego vienen las filas del mapa, la leyenda y end. Aquí está el primer nivel sin su línea de encabezado:

##################################################
#<.....#............#........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

Hay más caracteres que baldosas. Las letras (r, g, s, L) son enemigos de la tabla de enemigos. Los dígitos vienen de la leyenda debajo del mapa: un objeto, oro, una marca de misión. < es donde baja el héroe. ? es una puerta secreta que parece una pared. , es sangre en el suelo.

// El mapa es texto: las líneas entre «level|…» y «legend|…» son el mapa en sí, la leyenda dice qué
// significa cada dígito. Aquí solo se leen las definiciones; el nivel vivo se construye en 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);
    }
  }
}

La lectura ocurre en dos pasos. loadMaps solo divide el texto en definiciones. El nivel vivo se construye con buildLevel al empezar una partida nueva (y al cargar): las letras se convierten en enemigos, los dígitos en objetos, y el suelo queda debajo. Por eso no hay ningún goblin en la cuadrícula del nivel. Las criaturas son una lista aparte que se mueve sobre el mapa, y el mapa se queda quieto.

La idea

Un movimiento es una petición

El movimiento más simple es heroX += dx. Con él el héroe atraviesa paredes y sale del mapa. Un movimiento tiene que ser una petición: «quiero ir allí». Decide la celda a la que el héroe quiere entrar:

// Un movimiento es una petición: decide la celda a la que quieres entrar.
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 "La puerta cruje y se abre.";
  }
  if (!target.walkable) return `No pasas: ${target.name}.`;
  level.heroX = x;
  level.heroY = y;
  return "";
}

una pared o agua: no, y dice por qué;
una puerta cerrada: se abre (pasa a ser '), pero el héroe se queda donde está. Abrirla es el movimiento;
cualquier otra cosa: el héroe entra.

El programa lee los comandos w a s d (arriba, izquierda, abajo, derecha), uno por línea, y dibuja el nivel después de cada uno. La entrada es 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  No pasas: pared.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> a  No pasas: agua.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> w
################
#......#.......#
#.....@+.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d  La puerta cruje y se abre.
################
#......#.......#
#.....@'.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......@.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......'@......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################

Los dos primeros movimientos van contra una pared y contra el agua: el héroe se queda quieto. Después el héroe sube, abre la puerta y la atraviesa.

En el juego el paso hace más, y el orden importa:

// Un paso del héroe: combate, conversación, puerta, escondite oculto, pared o movimiento.
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';
}

Primero pregunta por un enemigo: el enemigo está sobre el suelo, y si la baldosa decidiera primero, el héroe entraría en el enemigo. Luego una persona (una conversación), una puerta, una puerta secreta, y solo después la baldosa. Cuando el héroe de verdad se mueve, un héroe que sangra deja sangre en el suelo, el evento TileEntered avisa a las misiones de dónde está el héroe, y al final el mundo juega su turno.

Chocar con una pared devuelve blocked y no llama a worldTurn: un error del jugador no cuesta un turno, y los enemigos no se acercan. La puerta sí cuesta un turno.

Más precisamente, para curiosos

Aquí el agua simplemente no deja pasar. En muchos juegos el agua poco profunda sí deja pasar, pero despacio: cada baldosa tiene un coste de movimiento (suelo 1, agua poco profunda 2, pantano 3), y el héroe acumula energía hasta que alcanza el coste, como la energía en el combate (la lección sobre el sistema de combate). Entonces walkable pasa a ser un número en vez de sí o no. La búsqueda de caminos también tiene que conocer los costes: BFS ya no basta, y hace falta Dijkstra.

La idea

La cámara

El nivel del juego mide 50 × 20, y la vista 40 × 13. La cámara es el mundo visto a través de una ventana: cameraX y cameraY son la celda del mundo que está en la esquina superior izquierda de la pantalla. Las dos direcciones están a una suma de distancia:

del mundo a la pantalla: screenX = x − cameraX;
de la pantalla al mundo: x = cameraX + screenX.

La cámara sigue al héroe: el héroe está en el centro, así que cameraX = heroX − VIEW_W / 2. Cerca del borde del mapa esto da un número negativo, o una vista que se sale del mapa. Por eso la cámara se limita (clamp) entre 0 y width − VIEW_W. Ahí la vista se detiene, y el héroe se mueve hacia el borde de la pantalla.

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(`héroe (${level.heroX}, ${level.heroY}), cámara (${cameraX}, ${cameraY}` +
    `), en la pantalla (${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);
  }
}

El programa usa una vista de 9 × 5 en el nivel de 16 × 7 e imprime la vista después de cada tramo del camino del héroe:

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);
}

héroe (6, 3), cámara (2, 1), en la pantalla (4, 2)
.....#...
.....+...
..~~@#...
..~~.#...
.....#...
héroe (9, 2), cámara (5, 0), en la pantalla (4, 2)
#########
..#......
..'.@....
~.#....>.
~.#......
héroe (14, 2), cámara (7, 0), en la pantalla (7, 2)
#########
#.......#
'......@#
#....>..#
#.......#
héroe (14, 5), cámara (7, 2), en la pantalla (7, 3)
'.......#
#....>..#
#.......#
#......@#
#########

Las dos primeras vistas están centradas: el héroe está en (4, 2) de la pantalla. En la tercera la cámara ha llegado al límite derecho 16 − 9 = 7 y se detiene, mientras el héroe sigue caminando hacia el borde. En la cuarta la cámara se ha detenido también abajo.

Math.floor(VIEW_W / 2) es la división entera: 4.

const cameraX = clamp(level.heroX - Math.floor(VIEW_W / 2), 0, );

Más precisamente, para curiosos

Si el nivel es más estrecho que la vista, width − VIEW_W es negativo, y según dónde esté el héroe, clamp devuelve 0 o un número negativo: la cámara salta o se sale del mapa por la izquierda. En el canon esto no pasa, porque los tres niveles miden 50 × 20, pero en un juego con salas pequeñas el nivel se centra en la vista: cameraX = (width − VIEW_W) / 2.

Una cámara que se mueve con cada paso hace saltar toda la pantalla. Muchos juegos mantienen una zona muerta: la cámara se mueve solo cuando el héroe sale de un rectángulo en el centro. En un juego de consola por turnos casi nunca hace falta; en un juego con movimiento fluido sí.

El juego hace lo mismo con 40 × 13. Aquí hay un fotograma más abajo en el primer nivel: la cámara ha bajado, así que las filas de arriba del nivel quedan fuera de la vista:

########............############........ Galería alta
       #............#          #........ Nivel 1 de 3
       #######.#####           #########
                                       # Alrededor:
                 ######       ########## nadie
              ........#########.........
              ...%.%@.'.................
              ........#########.........
              ........#       ##########
               ########                .
                                     ...
                                    ....
                                    ....
Iva, bárbaro nv.2  exp 40/55  oro 30
V [############] 57/57   M [########] 5/5
¡Goblin lancero te ha visto!
¡Victoria! Experiencia del combate: 21.
Iva llega al nivel 2: nueva habilidad: Torbellino (Furia).

La idea

Primer intento: un radio

El héroe debe ver lo que tiene alrededor. La primera idea es un radio: ves todas las celdas más cercanas que 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 significa «lo veo ahora». seen significa «lo he visto alguna vez», y se usa después para la niebla. Esto es lo que el héroe ve desde el inicio:

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);

héroe (6, 3): ves 87, recuerdas 87
| ###########    |
|#......#.....   |
|#......+.....   |
|#...~~@#....>   |
|#...~~.#.....   |
|#......#.....   |
| ###########    |

Hay 87 celdas visibles, y entre ellas las escaleras (>) detrás de la pared. La puerta cerrada no importa. El radio sabe a qué distancia está una celda, pero no qué hay entre ella y el héroe. Este es el jefe que ves desde la entrada.

Más precisamente, para curiosos

¿Por qué la condición es dx² + dy² ≤ R² + R y no ≤ R²? Con ≤ R², cuatro celdas sueltas sobresalen del círculo: (R, 0), (0, R) y sus imágenes especulares. El + R extra lo redondea: para números enteros, dx² + dy² ≤ R² + R es lo mismo que una distancia al centro de la celda menor que R + ½, porque (R + ½)² = R² + R + ¼. Sin raíz cuadrada y sin fracciones.

La idea

Una línea recta: Bresenham

Una celda es visible si la línea recta del héroe a ella no pasa por una pared. En una cuadrícula una línea recta es una sucesión de celdas, y hay que decidir cuáles. El algoritmo de Bresenham lo hace solo con números enteros: sumas, restas y multiplicaciones por 2.

La idea: empiezas en un extremo, y en cada paso avanzas en x, en y, o en ambos. Lo decide error: cuánto se ha desviado la línea de la recta verdadera. Cuando la desviación en un eje se hace demasiado grande, das un paso en ese eje y reduces la desviación.

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;
    }
  }
}

El programa dibuja la línea de A = (0, 0) a B = (8, 3), y luego de vuelta, de B a 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

Las dos direcciones pasan por casi las mismas celdas, pero no exactamente: el camino de ida pasa por 4,2, y el de vuelta por 4,1. A la mitad el error es exactamente igual, y el algoritmo elige un lado. Al volver elige el otro. Recuérdalo: lo necesitarás para los puntos débiles del método.

Más precisamente, para curiosos

¿De dónde sale error = dx + dy (con dy negativo)? La recta que pasa por los dos extremos es f(x, y) = 0, donde f es lineal, y el signo de f te dice de qué lado estás. error es f, escalada para que sea un entero, en el punto que vendría a continuación. Las comprobaciones 2 · error ≥ dy y 2 · error ≤ dx preguntan si un paso en x, o en y, te acerca a la recta. Por eso el algoritmo funciona en las ocho direcciones y nunca divide.

Jack Bresenham lo inventó en IBM en 1962 para un plóter: la máquina mueve la pluma un paso cada vez, y dividir es caro. Hoy dividir no es caro, pero los enteros dan el mismo resultado en cualquier computadora y en cualquier lenguaje, y para nuestro juego eso es obligatorio.

Míralo

Campo de visión y niebla

Ahora se juntan las dos cosas. Una línea de Bresenham va hacia cada celda del radio. En cada paso la línea comprueba dos cosas: ¿hemos llegado? y ¿hay una pared aquí? El orden importa. Si la línea ha llegado al destino, la celda es visible, aunque sea una pared. Si hay una pared en el camino antes del destino, la línea se detiene: la celda no es visible.

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;
      }
    }
  }
}

Paso a paso, en palabras

El héroe está en (6, 3). El campo de visión se calcula de nuevo en cada turno, y primero cada celda pasa a ser invisible. Todavía no se ha visto nada: todo el nivel es desconocido.
Los candidatos son las celdas dentro del radio 6: dx² + dy² ≤ 6² + 6. Son 87, incluida la sala detrás de la pared. El radio no sabe nada de paredes.
Hacia cada candidato sale una línea recta (Bresenham). Se detiene en la primera pared del camino, pero llega hasta ella, así que la pared misma se ve. 37 líneas se detienen antes (las grises).
Desde (6, 3) ves 50 celdas, y todas pasan a seen. La sala de la derecha está dentro del radio, pero la puerta cerrada y la pared la ocultan: las escaleras siguen desconocidas.
El héroe abre la puerta y pasa (wdddddd). En cada turno visible se limpia y seen se queda: lo que viste y ya no ves se vuelve niebla.
Desde (11, 2) las líneas pasan por la puerta abierta. En la sala de la izquierda solo se ve una cuña estrecha: la pared oculta el resto.
Ves 63, recuerdas 109 de 112 celdas. La niebla conserva la forma de la sala de la izquierda, pero no lo que pasa ahora en ella.

En cada turno visible se limpia y se calcula de nuevo, mientras que seen solo se va llenando. El programa dibuja las celdas visibles con su carácter, las vistas que ya no son visibles con : y las desconocidas como espacios. Primero desde el inicio, y luego después de 7 movimientos (arriba, la puerta, cinco veces a la derecha):

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);

héroe (6, 3): ves 50, recuerdas 50
| ######         |
|#......         |
|#......+        |
|#...~~@#        |
|#...~~.#        |
|#......         |
| ######         |
héroe (11, 2): ves 63, recuerdas 109
| :::::::####### |
|:::::::#.......#|
|:::::..'...@...#|
|:::::::#....>..#|
|:::::::#.......#|
|:::::::#.......#|
| ::::::#########|

Al principio las escaleras no son visibles: la pared y la puerta cerrada las ocultan. Después de que el héroe pasa, la sala de la izquierda es niebla. El héroe sabe cómo es, pero no ve lo que pasa dentro: un enemigo que entre ahí no aparecerá en la pantalla.

En el juego el campo de visión es el mismo código, en el mismo punto del turno:

// Campo de visión: una casilla es visible si está dentro del radio y la línea hasta ella (Bresenham) no pasa
// por una pared ni por una puerta cerrada. Lo visto se recuerda: eso es la niebla.
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 lo llama en update, después de cada comando. Dibujar el mapa muestra la cámara y la niebla juntas: una celda que nunca se ha visto se salta (continue), una visible tiene su propio color, y una vista es gris:

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);
}

Aquí está el fotograma en el que el héroe abre la puerta de la gran sala del primer nivel. A través de la puerta abierta ves una cuña de la sala, y en ella una rata gigante:

########                                 Galería alta
#<.....# ....                            Nivel 1 de 3
#.....@'....r
#......# ....                            Alrededor:
#......#   ..                            r rata gigante
########







Iva, bárbaro nv.1  exp 0/20  oro 5
V [############] 48/48   M [########] 4/4
La puerta cruje y se abre.
¡Rata gigante te ha visto!
Ves: rata gigante.

Más precisamente, para curiosos

En una terminal simple (--plain), las celdas vistas y las visibles se ven igual: el carácter es el mismo y no hay color. En una terminal con colores ANSI, las celdas vistas son grises. Por eso el programa de esta lección usa : para la niebla: para que veas la diferencia sin colores.

¿Cuánto cuesta? El círculo de radio 6 tiene 137 celdas, y la línea a cada una tiene como máximo 6 pasos: menos de 1000 comprobaciones por turno. Eso es O(r³) por turno: r² celdas por r pasos.

Pruébalo

Predice la salida

Una sala pequeña con un pilar en el medio. El héroe está a la izquierda del pilar, y el radio llega a todas las celdas. ¿Qué imprime el programa?

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);

Respuesta

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

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

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

Pruébalo

Encuentra el error

Un compañero tocó la función de la línea, y ahora el programa imprime esto desde el inicio:

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;
    }
  }
}

héroe (6, 3): ves 30, recuerdas 30
|                |
| ......         |
| ......         |
| ...~~@         |
| ...~~.         |
| ......         |
|                |

El suelo es visible, la puerta y las paredes han desaparecido, y el agua sigue igual. ¿Qué línea comprueba demasiado pronto?

Elige la línea con el error.

Más precisamente

Los puntos débiles del método simple

Una línea hacia cada celda es el campo de visión más simple. Tiene tres puntos débiles bien conocidos, y todos aparecen en nuestro juego.

Huecos junto a las paredes. Mira otra vez el primer fotograma del inicio: el héroe está junto a la puerta, y la pared en (7, 1) y (7, 5) no es visible, aunque el suelo junto a ella sí lo es. La línea hacia (7, 1) da su primer paso en diagonal y cae en la puerta de (7, 2): se detiene. Lo mismo se ve en el fotograma de la mina al principio de la lección: el héroe está junto a la pared izquierda, y tiene un hueco. Cuando miras una pared casi a lo largo, la línea choca con la celda vecina de la misma pared.

Asimetría. Desde A ves B, pero desde B no ves A, porque la línea de vuelta pasa por otras celdas (lo viste con 4,2 y 4,1). En el primer nivel de la mina hay 89 pares de celdas así de 17248: desde (12, 4) puedes ver (14, 8), pero no al revés. En el canon esto tiene consecuencias. Un enemigo mira con su propia línea, de sí mismo al héroe (enemySeesHero, hasta 8 celdas), y tú ves con el campo de visión desde el héroe. Así que un goblin puede notarte antes de que lo veas. Al menos el juego no revela más de lo que ves: el mensaje de que un enemigo se despertó se muestra solo si el enemigo es visible.

La variante más barata deja huecos en las salas grandes. En vez de una línea hacia cada celda, puedes enviar líneas solo hasta el borde del círculo y marcar todo lo que hay por el camino. Eso es O(r²) en vez de O(r³). Pero los rayos se separan con la distancia, y las celdas entre ellos quedan sin cubrir: con radio 6 son 8 de 137, y con radio 20 son 80 de 1313. En una sala grande son huecos en el suelo y en las paredes lejanas.

Mejores algoritmos. El shadowcasting recorre los ocho sectores alrededor del héroe fila por fila y guarda las «sombras» como rangos de pendientes. Cada celda se mira una vez, no hay huecos, y existe también el shadowcasting simétrico, donde A ve a B exactamente cuando B ve a A. El FOV permisivo dice que una celda es visible si alguna línea recta desde algún punto de la celda del héroe hasta algún punto del destino está libre. Es simétrico por definición y ve más alrededor de las esquinas.

Por qué el canon se queda con el simple. Los niveles miden 50 × 20 y el radio es 6: menos de 1000 comprobaciones por turno, nada para cualquier computadora. Los enteros dan el mismo resultado en los cuatro lenguajes, y así se comprueban los ports. Y cabe en una sola tarjeta. Si el juego llega a tener grandes zonas abiertas y líneas de visión largas, computeFov se reemplaza en un solo lugar.

Ejercicio

La puerta secreta

Resuélvelo en tu editor.

Una puerta secreta. Añade una baldosa ?: parece una pared (se dibuja como #), no se puede pasar por ella y bloquea la vista. Cuando el héroe choca con ella, se convierte en una puerta cerrada + y el programa imprime «La pared suena hueca... ¡Una puerta secreta!». El siguiente choque la abre, como cualquier puerta. El nivel es:

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

Con la entrada s d d d d (una por línea) la salida es:

> s
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@#.......#
#......#.......#
################
> d  La pared suena hueca... ¡Una puerta secreta!
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@+.......#
#......#.......#
################
> d  La puerta cruje y se abre.
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@'.......#
#......#.......#
################
> d
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~.@.......#
#......#.......#
################
> d
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~.'@......#
#......#.......#
################

Más ejercicios

Una antorcha. Haz que el radio sea un parámetro. Con antorcha el héroe ve 6 celdas, sin ella 2. ¿Cuánto de la sala de la izquierda ve el héroe desde el inicio sin antorcha?
La vista y la niebla juntas. Combina la cámara y el campo de visión: una vista de 9 × 5 en el nivel que muestre celdas visibles, vistas (:) y desconocidas, como draw en el juego.
Quién ve a quién. Escribe un programa que cuente, en el nivel de esta lección, los pares de celdas de suelo en los que una ve a la otra pero no al revés.

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·

El mapa y el campo de visión

Cookies