Sokoban на JavaScript: ящики, цели и отмена хода

Коротко

Sokoban на JavaScript умещается в 5 функций: разбор уровня из строк, ход с толчком ящика, проверка победы, поиск тупиков в углах и отмена хода. Ящики хранятся множеством строк вида "x,y", поэтому проверка «есть ли здесь ящик» — один вызов has. Для отмены каждый ход записывает направление и сдвинутый ящик, а не копию уровня: на 1000 ходов в нашем расчёте это 51 000 байт текста против 275 000.

Содержание

  1. Уровень из строк символов
  2. Ход и толчок ящика
  3. Победа и тупики
  4. Отмена хода: записи против снимков
  5. Код на JavaScript
  6. Практический сценарий: игра для кружка за одно занятие
  7. Когда вам это не подойдёт

Уровень из строк символов

Уровень удобнее всего записать массивом строк, где каждый символ — одна клетка. Такой уровень можно набрать в любом текстовом редакторе и сразу увидеть его форму.

СимволКлетка
#стена
пробелпол
.цель (склад)
$ящик
*ящик на цели
@игрок
+игрок на цели

При разборе стены, цели и ящики складываются в три множества Set с ключами "x,y". Ящик на цели попадает сразу в два множества — ящиков и целей, поэтому отдельного состояния «ящик на цели» в коде нет.

Ход и толчок ящика

Ход — это проверка клетки в направлении движения: стена — ход отменяется, пусто — игрок шагает, ящик — проверяется клетка за ящиком. Если за ящиком стена или другой ящик, ход отменяется целиком; иначе ящик сдвигается на 1 клетку, а игрок занимает его место. Так в коде воплощены два правила Sokoban: тянуть нельзя, толкать два ящика сразу нельзя.

Счётчики moves и pushes растут при каждом успешном ходе и толчке. По ним игрок сравнивает своё решение с лучшим, а вы — с записанным решением уровня.

Победа и тупики

Победа — это когда каждый ящик стоит на цели: [...boxes].every((b) => goals.has(b)). Число ящиков равно числу целей, поэтому проверять цели отдельно не нужно.

Тупик проще всего искать в углах: ящик не на цели, у которого стена сверху или снизу и одновременно слева или справа, сдвинуть уже нельзя. В прогоне игрок вытолкал верхний ящик в правый верхний угол поля, проверка вернула ['5,1'], а 3 отмены вернули ящик на место. Остальные тупики — например, 2 ящика рядом вдоль стены — эта проверка не находит; для подсветки в учебной игре её хватает.

Отмена хода: записи против снимков

Для отмены выгоднее хранить запись каждого хода, а не копию всего уровня. Запись — это направление и, если был толчок, клетки «откуда» и «куда» сдвинулся ящик; отмена двигает игрока в обратную сторону и возвращает ящик.

Снимок уровня проще в написании, но растёт вместе с числом ящиков. Наш расчёт для уровня с 30 ящиками:

снимок уровня  ≈ 275 байт JSON  × 1000 ходов = 275 000 байт
запись хода    ≈  51 байт JSON  × 1000 ходов =  51 000 байт

Запись не зависит от размера уровня. Снимки оправданы, когда за ход меняется много объектов сразу, — например, если ящики после толчка скользят по льду.

Код на JavaScript

Код содержит разбор уровня, ход, отмену, проверку победы и тупиков, отрисовку в текст и расчёт памяти. Он запускается в Node.js 24, вывод совпадает с комментариями; в браузере draw заменяется рисованием спрайтов на canvas, а направления приходят с клавиатуры.

// # стена, . цель, $ ящик, * ящик на цели, @ игрок, + игрок на цели, пробел — пол
const LEVEL = [
  '#######',
  '#.    #',
  '# $ # #',
  '#  $@ #',
  '#.    #',
  '#######',
];

function parse(rows) {
  const walls = new Set(), goals = new Set(), boxes = new Set();
  let player = null;
  rows.forEach((row, y) => [...row].forEach((ch, x) => {
    const k = x + ',' + y;
    if (ch === '#') walls.add(k);
    if (ch === '.' || ch === '*' || ch === '+') goals.add(k);
    if (ch === '$' || ch === '*') boxes.add(k);
    if (ch === '@' || ch === '+') player = { x, y };
  }));
  return { walls, goals, boxes, player, history: [], moves: 0, pushes: 0 };
}

const DIRS = { up: [0, -1], down: [0, 1], left: [-1, 0], right: [1, 0] };

function move(s, dir) {
  const [dx, dy] = DIRS[dir];
  const nx = s.player.x + dx, ny = s.player.y + dy;
  const next = nx + ',' + ny;
  if (s.walls.has(next)) return false;
  let pushed = null;
  if (s.boxes.has(next)) {
    const beyond = (nx + dx) + ',' + (ny + dy);
    if (s.walls.has(beyond) || s.boxes.has(beyond)) return false; // толкаем только один ящик
    s.boxes.delete(next); s.boxes.add(beyond);
    pushed = { from: next, to: beyond };
    s.pushes++;
  }
  s.history.push({ dir, pushed }); // запись хода: направление и, если был, сдвинутый ящик
  s.player = { x: nx, y: ny };
  s.moves++;
  return true;
}

function undo(s) {
  const last = s.history.pop();
  if (!last) return false;
  const [dx, dy] = DIRS[last.dir];
  s.player = { x: s.player.x - dx, y: s.player.y - dy };
  if (last.pushed) { s.boxes.delete(last.pushed.to); s.boxes.add(last.pushed.from); s.pushes--; }
  s.moves--;
  return true;
}

const solved = (s) => [...s.boxes].every((b) => s.goals.has(b));

// Простой тупик: ящик не на цели стоит в углу из двух стен
function cornerDeadlocks(s) {
  return [...s.boxes].filter((b) => {
    if (s.goals.has(b)) return false;
    const [x, y] = b.split(',').map(Number);
    const w = (dx, dy) => s.walls.has((x + dx) + ',' + (y + dy));
    return (w(0, -1) || w(0, 1)) && (w(-1, 0) || w(1, 0));
  });
}

function draw(s, rows) {
  return rows.map((row, y) => [...row].map((_, x) => {
    const k = x + ',' + y;
    if (s.walls.has(k)) return '#';
    const p = s.player.x === x && s.player.y === y;
    if (p) return s.goals.has(k) ? '+' : '@';
    if (s.boxes.has(k)) return s.goals.has(k) ? '*' : '$';
    return s.goals.has(k) ? '.' : ' ';
  }).join('')).join('\n');
}

const s = parse(LEVEL);
// Решение: ящик B влево и вниз на цель, ящик A вверх и влево на цель
const plan = 'left left up left down up right right up left'.split(' ');
for (const d of plan) move(s, d);
console.log(draw(s, LEVEL));
console.log(s.moves, s.pushes, solved(s));

// Тупик и отмена
const t = parse(LEVEL);
for (const d of ['left', 'left', 'up', 'left', 'up', 'right', 'right', 'right']) move(t, d);
console.log(cornerDeadlocks(t));
undo(t); undo(t); undo(t);
console.log(cornerDeadlocks(t), t.moves);

// Отмена до начала возвращает исходный уровень
while (undo(s));
console.log(draw(s, LEVEL) === LEVEL.join('\n'), s.moves, s.pushes);

// Размер истории на 1000 ходов: снимок уровня с 30 ящиками против записи хода
const many = Array.from({ length: 30 }, (_, i) => (10 + i) + ',' + (10 + i));
const snapshot = JSON.stringify({ boxes: many, player: { x: 12, y: 7 } }).length;
const record = JSON.stringify({ dir: 'left', pushed: { from: '13,7', to: '12,7' } }).length;
console.log(snapshot * 1000, record * 1000); // байт текста на 1000 ходов

Ожидаемый вывод программы:

#######
#*@   #
#   # #
#     #
#*    #
#######
10 5 true
[ '5,1' ]
[] 5
true 0 0
275000 51000

Практический сценарий: игра для кружка за одно занятие

Возьмём школьный кружок и занятие на 90 минут. Входные условия: готовый код выше, цель — играбельный Sokoban в браузере с 3 уровнями, отменой на Z и перезапуском на R. Порядок работы:

  1. Уровни. Каждый ученик рисует уровень строками символов: до 8×8 клеток, 1–3 ящика.
  2. Решение. К каждому уровню записывается решение массивом направлений, как plan в коде, и прогоняется: solved(s) должен вернуть true.
  3. Управление. Стрелки вызывают move, Z — undo, R — заново parse того же уровня.
  4. Подсветка тупиков. Клетки из cornerDeadlocks рисуются красным ящиком.
  5. Переход. После solved(s) показывается число ходов и толчков и загружается следующий уровень.
  6. Проверка. Сосед по парте проходит чужой уровень, нажимает Z до самого начала, и уровень совпадает с исходным: в прогоне сравнение вернуло true, счётчики — 0 и 0.

Как дизайнить сами уровни и откуда взялись правила жанра, — в дневной статье этого дня про головоломки на сетке.

Когда вам это не подойдёт

Такой код рассчитан на классический Sokoban и учебные проекты:

  • Плавная анимация. Здесь игрок перемещается мгновенно. Для анимации шага нужна интерполяция между клетками, а ввод на время шага блокируется или буферизуется.
  • Большие уровни с сотнями ящиков. Множества строк "x,y" удобны, но для полей 200×200 быстрее хранить сетку числовым массивом с индексом y * width + x.
  • Нужна проверка решаемости. Поиск углов не говорит, решаем ли уровень. Для этого нужен поиск решения, а для сложных уровней — решатель с отсечением тупиков, и это отдельная большая задача.
  • Новые правила. Лёд, телепорты и тянущие блоки меняют функцию move и запись истории; с ними снимки иногда проще, чем записи.

Мы разрабатываем J2DRU — браузерный 2D игровой движок с картами из тайлов, где логика собирается из событий, а проект можно углублять на TypeScript. Движок в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).

Источники: внешних фактов в статье нет; правила игры описаны по статье о головоломках на сетке. Уровень, решение, размеры записей и все выводы — наш пример и наш прогон в Node.js 24.

Читайте также:

Частые вопросы

Как хранить уровень Sokoban в коде?

Удобно записать уровень строками символов: # — стена, . — цель, $ — ящик, * — ящик на цели, @ — игрок, + — игрок на цели. При разборе стены, цели и ящики складываются в множества с ключами «x,y».

Как сделать отмену хода?

Каждый ход кладёт в массив истории запись: направление и, если был толчок, откуда и куда сдвинулся ящик. Отмена снимает последнюю запись, двигает игрока назад и возвращает ящик.

Как понять, что уровень зашёл в тупик?

Простейший признак — ящик не на цели стоит в углу из двух стен: его больше нельзя сдвинуть. Такие ящики можно подсветить. Остальные виды тупиков сложнее, и простая проверка их не найдёт.

Почему ящик не двигается, если за ним другой ящик?

Таково правило Sokoban: толкать можно только один ящик за раз и только на свободную клетку. В коде это одна проверка — стена или ящик за ящиком отменяют ход.