Skip to content
Ayotl
Español

← How a game is made: Daily Challenge's Snake · Lesson 9/16

Text maps and an unbroken arena

✕
1/7

From text to grid

Each level is a file like snake_03.txt, "Broken edges": the gaps on the border aren't exits, because leaving the board also loses. core/map.js turns it into a grid of true/false with parseMap:

  • Lines starting with # are comments and get skipped.
  • x is a wall (true); . or a space, empty.
  • The p marks the start, and is kept separately in start.

What it returns, grid[y][x], is what isFree checks on every step.

  • x wall
  • c start (the file's p)
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The p became { x: 3, y: 1 } and in the grid it's floor, not wall. The comment on the first line doesn't take up a row. If a row is short, ?? " " fills it with empty: an editor that trims trailing spaces doesn't break the map.

The whole lesson on one page

From text to grid

Each level is a file like snake_03.txt, "Broken edges": the gaps on the border aren't exits, because leaving the board also loses. core/map.js turns it into a grid of true/false with parseMap:

  • Lines starting with # are comments and get skipped.
  • x is a wall (true); . or a space, empty.
  • The p marks the start, and is kept separately in start.

What it returns, grid[y][x], is what isFree checks on every step.

  • x wall
  • c start (the file's p)
// parseMap, just like in core/map.js
function parseMap(text, cols, rows) {
  const lines = text.split("\n").filter(l => !l.startsWith("#"));
  const grid = [];
  let start = null;
  for (let y = 0; y < rows; y++) {
    const line = lines[y] ?? "";
    const row = [];
    for (let x = 0; x < cols; x++) {
      const c = line[x] ?? " ";
      row.push(c === "x" || c === "X");
      if (c === "p" || c === "P") start = { x, y };
    }
    grid.push(row);
  }
  return { grid, start, cols, rows };
}

const texto = "# A tiny map\nxxxxxx\nx..p.x\nx.x..x\nxxxxxx";
const m = parseMap(texto, 6, 4);
console.log("start:", m.start);
for (const fila of m.grid) console.log(fila.map(b => (b ? "#" : ".")).join(""));
console.log("wall at (2,2)?", m.grid[2][2]);

The p became { x: 3, y: 1 } and in the grid it's floor, not wall. The comment on the first line doesn't take up a row. If a row is short, ?? " " fills it with empty: an editor that trims trailing spaces doesn't break the map.

Extra walls that don't split the arena

So the same map never plays the same twice, the calendar gives Snake extra walls each day (opts.param, 4 if it says nothing). Each one goes on a random free cell, more than 5 cells from the start so you don't die on the first step. But a badly placed wall can split the arena in two: if the fruit then appeared on the other side, you could never reach it.

The constructor solves it by trying: it places the wall, asks arenaEntera(start) and, if the arena got split, removes it and draws another cell (up to 12 tries per wall):

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

  • x wall
  • c start
  • m an extra wall here would close the only passage
const mapa = ["xxxxxxxxx", "x...x...x", "x...m...x", "x...x...x", "xxxxxxxxx"];
const walls = mapa.map(f => [...f].map(c => c === "x"));
const ROWS = walls.length, COLS = walls[0].length;

function cuantasAlcanzo(start) {
  const visto = new Set([start.y * COLS + start.x]), pila = [start];
  while (pila.length) {
    const { x, y } = pila.pop();
    for (const [dx, dy] of [[0, -1], [0, 1], [-1, 0], [1, 0]]) {
      const nx = x + dx, ny = y + dy, k = ny * COLS + nx;
      if (walls[ny][nx] || visto.has(k)) continue;
      visto.add(k); pila.push({ x: nx, y: ny });
    }
  }
  return visto.size;
}

const libres = () => walls.flat().filter(w => !w).length;
const start = { x: 2, y: 2 };
console.log("without the extra wall:", cuantasAlcanzo(start), "of", libres());
walls[2][4] = true;   // the extra wall, right in the passage
console.log("with the extra wall:", cuantasAlcanzo(start), "of", libres());

Without the wall all 19 free cells are reachable; with it, 9 of 18. Reachable and free no longer match: the arena is split and that wall would be thrown out. (Bounds aren't checked here because the map is walled in; the real code does check them.)

arenaEntera: a graph search

The question "can I reach every free cell?" is a graph search: each cell is a node and each free neighbor, an edge. arenaEntera counts the free cells, then starts from the start cell visiting neighbors, and finally compares:

return visto.size === libres;

A detail of the real code: the pending list is called cola (queue), but it's taken with cola.pop(), which takes the last one. That makes it a stack, and the search is depth-first (DFS), not level by level (BFS). For this question it doesn't matter: both visit exactly the same cells, just in a different order. It's the same algorithm as "Number of Islands", the islands challenge.

// arenaEntera's search, writing down the visiting order
const mapa = ["xxxxxx", "x....x", "x.xx.x", "x....x", "xxxxxx"];
const walls = mapa.map(f => [...f].map(c => c === "x"));
const COLS = 6, ROWS = 5;

function recorrer(start, conPop) {
  const visto = new Set([start.y * COLS + start.x]), pendientes = [start], orden = [];
  while (pendientes.length) {
    const { x, y } = conPop ? pendientes.pop() : pendientes.shift();
    orden.push(x + "," + y);
    for (const [dx, dy] of [[0, -1], [0, 1], [-1, 0], [1, 0]]) {
      const nx = x + dx, ny = y + dy, k = ny * COLS + nx;
      if (nx < 0 || ny < 0 || nx >= COLS || ny >= ROWS || walls[ny][nx] || visto.has(k)) continue;
      visto.add(k); pendientes.push({ x: nx, y: ny });
    }
  }
  return orden;
}

console.log("pop   (stack, DFS):", recorrer({ x: 1, y: 1 }, true).join(" "));
console.log("shift (queue, BFS):", recorrer({ x: 1, y: 1 }, false).join(" "));

Both lists have the same 10 cells in a different order. With pop it goes all the way down one side before coming back; with shift it spreads evenly, like a stain. For counting, either one; for the shortest path, only BFS (that's in the graphs unit).

Practice with a video challenge