← Así se hace un juego: Snake de Daily Challenge · Lección 9/16

Mapas de texto y una arena entera

1/7

Del texto a la cuadrícula

Cada nivel es un archivo como snake_03.txt, «Bordes rotos»: los huecos en la orilla no son salidas, porque salir del tablero también es perder. core/map.js lo convierte en una cuadrícula de true/false con parseMap:

Los renglones que empiezan con # son comentarios y se saltan.
x es muro (true); . o espacio, vacío.
La p marca la salida, y se guarda aparte en start.

Lo que devuelve, grid[y][x], es lo que isFree consulta en cada paso.

x muro
c salida (la p del archivo)

leccion.js

1// parseMap, igual que en core/map.js
2function parseMap(text, cols, rows) {
3  const lines = text.split("\n").filter(l => !l.startsWith("#"));
4  const grid = [];
5  let start = null;
6  for (let y = 0; y < rows; y++) {
7    const line = lines[y] ?? "";
8    const row = [];
9    for (let x = 0; x < cols; x++) {
10      const c = line[x] ?? " ";
11      row.push(c === "x" || c === "X");
12      if (c === "p" || c === "P") start = { x, y };
13    }
14    grid.push(row);
15  }
16  return { grid, start, cols, rows };
17}
18
19const texto = "# Un mapa chiquito\nxxxxxx\nx..p.x\nx.x..x\nxxxxxx";
20const m = parseMap(texto, 6, 4);
21console.log("salida:", m.start);
22for (const fila of m.grid) console.log(fila.map(b => (b ? "#" : ".")).join(""));
23console.log("¿muro en (2,2)?", m.grid[2][2]);

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

La p se volvió { x: 3, y: 1 } y en la cuadrícula es piso, no muro. El comentario de la primera línea no ocupa renglón. Si a un renglón le faltan letras, ?? " " las rellena de vacío: un editor que borra espacios al final no rompe el mapa.

Toda la lección en una página

Del texto a la cuadrícula

Los renglones que empiezan con # son comentarios y se saltan.
x es muro (true); . o espacio, vacío.
La p marca la salida, y se guarda aparte en start.

Lo que devuelve, grid[y][x], es lo que isFree consulta en cada paso.

x muro
c salida (la p del archivo)

1// parseMap, igual que en core/map.js
2function parseMap(text, cols, rows) {
3  const lines = text.split("\n").filter(l => !l.startsWith("#"));
4  const grid = [];
5  let start = null;
6  for (let y = 0; y < rows; y++) {
7    const line = lines[y] ?? "";
8    const row = [];
9    for (let x = 0; x < cols; x++) {
10      const c = line[x] ?? " ";
11      row.push(c === "x" || c === "X");
12      if (c === "p" || c === "P") start = { x, y };
13    }
14    grid.push(row);
15  }
16  return { grid, start, cols, rows };
17}
18
19const texto = "# Un mapa chiquito\nxxxxxx\nx..p.x\nx.x..x\nxxxxxx";
20const m = parseMap(texto, 6, 4);
21console.log("salida:", m.start);
22for (const fila of m.grid) console.log(fila.map(b => (b ? "#" : ".")).join(""));
23console.log("¿muro en (2,2)?", m.grid[2][2]);

Muros extra que no parten la arena

Para que el mismo mapa no se juegue igual dos veces, el calendario le pone a Snake muros extra cada día (opts.param, 4 si no dice nada). Cada uno sale en una casilla libre al azar, a más de 5 casillas de la salida para no morir en el primer paso. Pero un muro mal puesto puede partir la arena en dos: si la fruta luego sale del otro lado, nunca la alcanzarías.

El constructor lo resuelve probando: pone el muro, pregunta arenaEntera(start) y, si la arena quedó partida, lo quita y sortea otra casilla (hasta 12 intentos por muro):

this.walls[c.y][c.x] = true; if (this.arenaEntera(start)) break; this.walls[c.y][c.x] = false;

x muro
c salida
m un muro extra aquí cerraría el único paso

1const mapa = ["xxxxxxxxx", "x...x...x", "x...m...x", "x...x...x", "xxxxxxxxx"];
2const walls = mapa.map(f => [...f].map(c => c === "x"));
3const ROWS = walls.length, COLS = walls[0].length;
4
5function cuantasAlcanzo(start) {
6  const visto = new Set([start.y * COLS + start.x]), pila = [start];
7  while (pila.length) {
8    const { x, y } = pila.pop();
9    for (const [dx, dy] of [[0, -1], [0, 1], [-1, 0], [1, 0]]) {
10      const nx = x + dx, ny = y + dy, k = ny * COLS + nx;
11      if (walls[ny][nx] || visto.has(k)) continue;
12      visto.add(k); pila.push({ x: nx, y: ny });
13    }
14  }
15  return visto.size;
16}
17
18const libres = () => walls.flat().filter(w => !w).length;
19const start = { x: 2, y: 2 };
20console.log("sin el muro extra:", cuantasAlcanzo(start), "de", libres());
21walls[2][4] = true;   // el muro extra, justo en el paso
22console.log("con el muro extra:", cuantasAlcanzo(start), "de", libres());

Sin el muro se llega a las 19 casillas libres; con él, a 9 de 18. Alcanzables y libres ya no coinciden: la arena quedó partida y ese muro se descartaría. (Aquí no se revisan las orillas porque el mapa está cerrado con muros; el código real sí las revisa.)

arenaEntera: un recorrido de grafo

La pregunta «¿llego a todas las casillas libres?» es un recorrido de grafo: cada casilla es un nodo y cada vecina libre, una arista. arenaEntera cuenta las libres, luego sale de la salida visitando vecinas y al final compara:

return visto.size === libres;

Un detalle del código real: la lista de pendientes se llama cola, pero se saca con cola.pop(), que toma el último. Eso la vuelve una pila, y el recorrido es en profundidad (DFS), no por niveles (BFS). Para esta pregunta da igual: los dos visitan exactamente las mismas casillas, sólo que en otro orden. Es el mismo algoritmo que «Number of Islands», el reto de las islas.

1// La búsqueda de arenaEntera, anotando el orden de visita
2const mapa = ["xxxxxx", "x....x", "x.xx.x", "x....x", "xxxxxx"];
3const walls = mapa.map(f => [...f].map(c => c === "x"));
4const COLS = 6, ROWS = 5;
5
6function recorrer(start, conPop) {
7  const visto = new Set([start.y * COLS + start.x]), pendientes = [start], orden = [];
8  while (pendientes.length) {
9    const { x, y } = conPop ? pendientes.pop() : pendientes.shift();
10    orden.push(x + "," + y);
11    for (const [dx, dy] of [[0, -1], [0, 1], [-1, 0], [1, 0]]) {
12      const nx = x + dx, ny = y + dy, k = ny * COLS + nx;
13      if (nx < 0 || ny < 0 || nx >= COLS || ny >= ROWS || walls[ny][nx] || visto.has(k)) continue;
14      visto.add(k); pendientes.push({ x: nx, y: ny });
15    }
16  }
17  return orden;
18}
19
20console.log("pop   (pila, DFS):", recorrer({ x: 1, y: 1 }, true).join(" "));
21console.log("shift (cola, BFS):", recorrer({ x: 1, y: 1 }, false).join(" "));

Las dos listas tienen las mismas 10 casillas en distinto orden. Con pop se va hasta el fondo de un lado antes de volver; con shift se expande parejo, como una mancha. Para contar, cualquiera; para el camino más corto, sólo BFS (eso viene en la unidad de grafos).

Practica con un reto en vídeo

Number of Islands