131 lines
3.9 KiB
JavaScript
131 lines
3.9 KiB
JavaScript
class Sokoban {
|
|
constructor(board) {
|
|
this.nCols = board[0].length;
|
|
let destBuf = '';
|
|
let currBuf = '';
|
|
|
|
for (let r = 0; r < board.length; r++) {
|
|
for (let c = 0; c < this.nCols; c++) {
|
|
const ch = board[r].charAt(c);
|
|
|
|
destBuf += (ch !== '$' && ch !== '@') ? ch : ' ';
|
|
currBuf += (ch !== '.') ? ch : ' ';
|
|
|
|
if (ch === '@') {
|
|
this.playerX = c;
|
|
this.playerY = r;
|
|
}
|
|
}
|
|
}
|
|
this.destBoard = destBuf;
|
|
this.currBoard = currBuf;
|
|
}
|
|
|
|
move(x, y, dx, dy, trialBoard) {
|
|
const newPlayerPos = (y + dy) * this.nCols + x + dx;
|
|
|
|
if (trialBoard.charAt(newPlayerPos) !== ' ') {
|
|
return null;
|
|
}
|
|
|
|
const trial = trialBoard.split('');
|
|
trial[y * this.nCols + x] = ' ';
|
|
trial[newPlayerPos] = '@';
|
|
|
|
return trial.join('');
|
|
}
|
|
|
|
push(x, y, dx, dy, trialBoard) {
|
|
const newBoxPos = (y + 2 * dy) * this.nCols + x + 2 * dx;
|
|
|
|
if (trialBoard.charAt(newBoxPos) !== ' ') {
|
|
return null;
|
|
}
|
|
|
|
const trial = trialBoard.split('');
|
|
trial[y * this.nCols + x] = ' ';
|
|
trial[(y + dy) * this.nCols + x + dx] = '@';
|
|
trial[newBoxPos] = '$';
|
|
|
|
return trial.join('');
|
|
}
|
|
|
|
isSolved(trialBoard) {
|
|
for (let i = 0; i < trialBoard.length; i++) {
|
|
if ((this.destBoard.charAt(i) === '.') !== (trialBoard.charAt(i) === '$')) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
solve() {
|
|
class Board {
|
|
constructor(cur, sol, x, y) {
|
|
this.cur = cur;
|
|
this.sol = sol;
|
|
this.x = x;
|
|
this.y = y;
|
|
}
|
|
}
|
|
|
|
const dirLabels = [['u', 'U'], ['r', 'R'], ['d', 'D'], ['l', 'L']];
|
|
const dirs = [[0, -1], [1, 0], [0, 1], [-1, 0]];
|
|
|
|
const history = new Set();
|
|
const open = [];
|
|
|
|
history.add(this.currBoard);
|
|
open.push(new Board(this.currBoard, "", this.playerX, this.playerY));
|
|
|
|
while (open.length > 0) {
|
|
const item = open.shift(); // poll() equivalent
|
|
const cur = item.cur;
|
|
const sol = item.sol;
|
|
const x = item.x;
|
|
const y = item.y;
|
|
|
|
for (let i = 0; i < dirs.length; i++) {
|
|
let trial = cur;
|
|
const dx = dirs[i][0];
|
|
const dy = dirs[i][1];
|
|
|
|
// are we standing next to a box?
|
|
if (trial.charAt((y + dy) * this.nCols + x + dx) === '$') {
|
|
// can we push it?
|
|
trial = this.push(x, y, dx, dy, trial);
|
|
if (trial !== null) {
|
|
// or did we already try this one?
|
|
if (!history.has(trial)) {
|
|
const newSol = sol + dirLabels[i][1];
|
|
|
|
if (this.isSolved(trial)) {
|
|
return newSol;
|
|
}
|
|
|
|
open.push(new Board(trial, newSol, x + dx, y + dy));
|
|
history.add(trial);
|
|
}
|
|
}
|
|
// otherwise try changing position
|
|
} else {
|
|
trial = this.move(x, y, dx, dy, trial);
|
|
if (trial !== null) {
|
|
if (!history.has(trial)) {
|
|
const newSol = sol + dirLabels[i][0];
|
|
open.push(new Board(trial, newSol, x + dx, y + dy));
|
|
history.add(trial);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return "No solution";
|
|
}
|
|
}
|
|
|
|
// Example usage
|
|
const level = "#######,# #,# #,#. # #,#. $$ #,#.$$ #,#.# @#,#######";
|
|
const sokoban = new Sokoban(level.split(","));
|
|
console.log(sokoban.solve());
|