Коротко
Sokoban на JavaScript умещается в 5 функций: разбор уровня из строк, ход с толчком ящика, проверка победы, поиск тупиков в углах и отмена хода. Ящики хранятся множеством строк вида "x,y", поэтому проверка «есть ли здесь ящик» — один вызов has. Для отмены каждый ход записывает направление и сдвинутый ящик, а не копию уровня: на 1000 ходов в нашем расчёте это 51 000 байт текста против 275 000.
Содержание
- Уровень из строк символов
- Ход и толчок ящика
- Победа и тупики
- Отмена хода: записи против снимков
- Код на JavaScript
- Практический сценарий: игра для кружка за одно занятие
- Когда вам это не подойдёт
Уровень из строк символов
Уровень удобнее всего записать массивом строк, где каждый символ — одна клетка. Такой уровень можно набрать в любом текстовом редакторе и сразу увидеть его форму.
| Символ | Клетка |
|---|---|
# | стена |
| пробел | пол |
. | цель (склад) |
$ | ящик |
* | ящик на цели |
@ | игрок |
+ | игрок на цели |
При разборе стены, цели и ящики складываются в три множества 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. Порядок работы:
- Уровни. Каждый ученик рисует уровень строками символов: до 8×8 клеток, 1–3 ящика.
- Решение. К каждому уровню записывается решение массивом направлений, как
planв коде, и прогоняется:solved(s)должен вернутьtrue. - Управление. Стрелки вызывают
move,Z—undo,R— зановоparseтого же уровня. - Подсветка тупиков. Клетки из
cornerDeadlocksрисуются красным ящиком. - Переход. После
solved(s)показывается число ходов и толчков и загружается следующий уровень. - Проверка. Сосед по парте проходит чужой уровень, нажимает
Zдо самого начала, и уровень совпадает с исходным: в прогоне сравнение вернулоtrue, счётчики — 0 и 0.
Как дизайнить сами уровни и откуда взялись правила жанра, — в дневной статье этого дня про головоломки на сетке.
Когда вам это не подойдёт
Такой код рассчитан на классический Sokoban и учебные проекты:
- Плавная анимация. Здесь игрок перемещается мгновенно. Для анимации шага нужна интерполяция между клетками, а ввод на время шага блокируется или буферизуется.
- Большие уровни с сотнями ящиков. Множества строк
"x,y"удобны, но для полей 200×200 быстрее хранить сетку числовым массивом с индексомy * width + x. - Нужна проверка решаемости. Поиск углов не говорит, решаем ли уровень. Для этого нужен поиск решения, а для сложных уровней — решатель с отсечением тупиков, и это отдельная большая задача.
- Новые правила. Лёд, телепорты и тянущие блоки меняют функцию
moveи запись истории; с ними снимки иногда проще, чем записи.
Мы разрабатываем J2DRU — браузерный 2D игровой движок с картами из тайлов, где логика собирается из событий, а проект можно углублять на TypeScript. Движок в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).
Источники: внешних фактов в статье нет; правила игры описаны по статье о головоломках на сетке. Уровень, решение, размеры записей и все выводы — наш пример и наш прогон в Node.js 24.
Читайте также: