// Created by Stefano Marzo on 20 Sep 2021
class Puzzle{
constructor(size) {
this.size = size;
this.cell = [];
this.BLANK = 0;
this.LEFT = 'LEFT';
this.RIGHT = 'RIGHT';
this.UP = 'UP';
this.DOWN = 'DOWN';
this.generate();
}
generate(){
this.cell = [];
for(let i = 0; i < this.size; i++) {
let row = [];
for(let j = 0; j < this.size; j++) {
row.push((this.size*i)+(j+1));
}
this.cell.push(row);
}
this.cell[this.size-1][this.size-1] = this.BLANK;
}
shuffle(moves) {
let reachedStates = [];
reachedStates[this.getState()] = true;
let numberOfMoves = (moves !== undefined) ? moves : Math.pow(this.size,4);
console.log(numberOfMoves);
for(let i = 0; i < numberOfMoves; i++){
let moves = this.getPossibleRawDirections();
let r = Math.round(Math.random() * (moves.length-1));
let move = moves[r];
while(reachedStates[this.getNextState(move)] === true) {
moves.splice(r, 1);
if(moves.length === 0) {
return;
}
r = Math.round(Math.random() * (moves.length-1));
move = moves[r];
}
this.move(move);
reachedStates[this.getState()] = true;
}
}
printStateConsole(){
let s = '';
for(let i in this.cell) {
for(let j in this.cell[i]){
s+=this.cell[i][j];
}
s+="<br>";
}
console.log(s);
}
getHtml(){
let s = '';
for(let i in this.cell) {
for(let j in this.cell[i]){
if(this.cell[i][j] == 0){
s+='<span class="puzzle-cell">·</span>';
} else{
s+='<span class="puzzle-cell">'+this.cell[i][j]+'</span>';
}
}
s+= '<br>';
}
document.getElementById('puzzle').innerHTML = s;
}
getCell(x, y) {
return this.cell[x][y];
}
swap(x1, y1, x2, y2) {
let tempCell = this.getCell(x1, y1);
this.cell[x1][y1] = this.getCell(x2, y2);
this.cell[x2][y2] = tempCell;
}
getBlankCell() {
for(let i in this.cell){
for(let j in this.cell[i]) {
if(this.getCell(i,j) == this.BLANK)
return {x:Number(i), y:Number(j)};
}
}
}
isPossibleMove(x, y) {
let blankCoords = this.getBlankCell();
let distX = Math.abs(x-blankCoords.x);
let distY = Math.abs(y-blankCoords.y);
let dist = distX + distY;
return (dist == 1 && this.inRange(x) && this.inRange(y));
}
inRange(n) {
return n >= 0 && n < this.size;
}
getPossibleMoves() {
let moves = [];
for(let i in this.cell) {
for(let j in this.cell[i]) {
if(this.isPossibleMove(i,j)) {
moves.push({x: Number(i), y: Number(j)});
}
}
}
return moves;
}
getDirection(x1, y1, x2, y2){
let distX = x1 - x2;
let distY = y1 - y2;
if(distX == 1) return this.UP;
if(distX == -1) return this.DOWN;
if(distY == 1) return this.LEFT;
if(distY == -1) return this.RIGHT;
}
getPossibleDirections() {
let moves = this.getPossibleMoves();
let blankCoords = this.getBlankCell();
let directionList = [];
for(let move of moves) {
directionList[this.getDirection(blankCoords.x, blankCoords.y,move.x, move.y)] = move;
}
return directionList;
}
getPossibleRawDirections() {
let moves = this.getPossibleMoves();
let blankCoords = this.getBlankCell();
let directionList = [];
for(let move of moves) {
directionList.push(this.getDirection(blankCoords.x, blankCoords.y,move.x, move.y));
}
return directionList;
}
move(direction) {
this.moveWithoutTemplate(direction);
//this.getHtml();
}
moveWithoutTemplate(direction) {
let directions = this.getPossibleDirections();
let move = directions[direction];
if(typeof move !== 'undefined') {
let blankCell = this.getBlankCell();
this.swap(blankCell.x, blankCell.y, move.x, move.y);
}
}
getState(){
return this.cell;
}
cloneState(){
let l = [];
for(let i in this.cell) {
let s = [];
for(let j in this.cell[i]){
s.push(this.cell[i][j]);
}
l.push(s);
}
return l;
}
getNextState(direction) {
let puzzle = new Puzzle(this.size);
puzzle.cell = this.cloneState();
puzzle.moveWithoutTemplate(direction);
return puzzle.getState();
}
loadState(state) {
for(let i in this.cell) {
for(let j in this.cell[i]){
this.cell[i][j] = state[i][j];
}
}
}
getNextPossibleStatesDirections(){
let directions = this.getPossibleDirections();
let statesDirections = [];
if(typeof directions[this.LEFT] != 'undefined'){
statesDirections.push({
state: this.getNextState(this.LEFT),
direction: this.LEFT
});
}
if(typeof directions[this.RIGHT] != 'undefined'){
statesDirections.push({
state: this.getNextState(this.RIGHT),
direction: this.RIGHT
});
}
if(typeof directions[this.UP] != 'undefined'){
statesDirections.push({
state: this.getNextState(this.UP),
direction: this.UP
});
}
if(typeof directions[this.DOWN] != 'undefined'){
statesDirections.push({
state: this.getNextState(this.DOWN),
direction: this.DOWN
});
}
return statesDirections;
}
getOppositeDirection(direction) {
if(direction == this.LEFT) return this.RIGHT;
if(direction == this.RIGHT) return this.LEFT;
if(direction == this.DOWN) return this.UP;
if(direction == this.UP) return this.DOWN;
}
}
/**
* the Stack mantains the elements ordered by their cost.
* it always pops the minimum cost Node with O(1) time
* it adds new node with O(log_2(n)) time
*/
class Stack{
constructor(){
this.stack = [];
}
add(el) {
this.stack.splice(this.sortedIndex(this.stack, el.cost), 0, el);
}
getNext() {
return this.stack.shift();
}
getMinCost() {
let min = this.stack[0].cost;
let i = 0;
let j = 0;
for(i = 0; i < this.stack.length; i++) {
if(this.stack[i].cost < min){
j = i;
}
}
return this.stack.splice(j, 1);
}
/**
*
* @param {*} array array to look into
* @param {*} value new element to insert
* @returns the index of the array where
* insert the new element in O(log_2(n)) time
*
*/
sortedIndex(array, value) {
let low = 0,
high = array.length;
let mid = 0; //bit shifting
while (low < high) {
mid = (low + high) >>> 1; //bit shifting
if (array[mid].cost < value) low = mid + 1;
else high = mid;
}
return low;
}
pop(){
return this.stack.shift();
}
}
/**
* HashTable of the states reached
*/
class StateTable{
constructor(){
this.states = [];
}
}
/**
* Graph Node
*/
class Node{
constructor(state, direction, parent, cost, depth){
this.state = state;
this.direction = direction;
this.parent = parent;
this.cost = cost; //depth + manhattan distance
this.depth = depth;
}
}
class BestFirstSolver{
constructor(randomPuzzle, goalPuzzle, memLimit){
this.randomPuzzle = randomPuzzle;
this.dimension = randomPuzzle.size;
this.stack = new Stack();
this.solution = [];
this.stateTable = new StateTable();
let p = new Puzzle(this.dimension);
p.generate();
this.goal = goalPuzzle.cloneState();
this.nodeCreated = 0;
this.iterationsCount = 0;
this.createNode(randomPuzzle.cloneState(), null, null);
this.memLimit = memLimit;
}
createNode(state, direction, parent) {
if(typeof this.stateTable.states[state] === 'undefined') {
let cost = 0;
let depth = 0;
if(parent !== null) {
cost = parent.depth + this.distance(state);
depth = parent.depth + 1;
}
let node = new Node(state, direction, parent, cost, depth);
this.stack.add(node);
//this.stateTable.states[state] = false;
this.stateTable.states[state] = node;
this.nodeCreated += 1;
}
}
isGoal(state){
for(let i in this.goal){
for(let j in this.goal[i]){
if(this.goal[i][j] != state[i][j]){
return false;
}
}
}
return true;
}
expand(node) {
if(typeof this.stateTable.states[node.state] !== 'undefined') {
//this.stateTable.states[node.state] = true;
let p = new Puzzle(this.dimension);
p.loadState(node.state);
let nextPossibleStates = p.getNextPossibleStatesDirections();
for(let stateDirection of nextPossibleStates) {
this.createNode(stateDirection.state, stateDirection.direction, node);
}
}
}
/**
*
* @returns the last node expandend which contains the solution
*/
search() {
let next = this.stack.getNext();
while(!this.isGoal(next.state)) {
this.expand(next);
next = this.stack.getNext();
this.iterationsCount+=1;
}
return next;
}
solve(node) {
let directions = [];
while(node.parent != null) {
directions.push(node.direction);
node = node.parent;
}
return directions;
}
calcSolution() {
this.solution = this.solve(this.search());
}
distance(state) {
let target = this.createCoordsMap(this.goal);
let current = this.createCoordsMap(state);
let d = 0;
for(let i in target) {
d += Math.abs(target[i].x - current[i].x);
d += Math.abs(target[i].y - current[i].y);
}
//it shall not overestimate
return d/2;
}
createCoordsMap(state) {
let m = [];
for(let i = 0; i < Math.pow(this.dimension,2); i++) {
m[i] = this.getCoord(i, state);
}
return m;
}
getCoord(num, state) {
for(let i = 0; i < this.dimension; i++) {
for(let j = 0; j < this.dimension; j++) {
if(state[i][j] == num) return {x: i, y: j};
}
}
}
/**
* @returns the average number of branches expanded
*/
getAverageExpansion() {
return this.nodeCreated/this.iterationsCount;
}
}
class BidirectionalBestFirstSolver{
constructor(puzzle, goal, memLimit) {
this.puzzle = puzzle;
this.goal = goal;
this.memLimit = memLimit;
this.directSolver = new BestFirstSolver(puzzle, goal, memLimit);
this.invertSolver = new BestFirstSolver(goal, puzzle, memLimit);
this.directSolution = [];
this.invertSolution = [];
this.solution = [];
//analytics
this.blockedByMemory = false;
this.noAdmissibleSolution = false;
this.statesHasMet = false;
this.solvedWithoutMet = false;
}
search() {
let nextD = this.directSolver.stack.getNext();
let nextI = this.invertSolver.stack.getNext();
while(!this.directSolver.isGoal(nextD.state) && !this.invertSolver.isGoal(nextI.state)) {
this.directSolver.expand(nextD);
this.invertSolver.expand(nextI);
nextD = this.directSolver.stack.getNext();
nextI = this.invertSolver.stack.getNext();
this.directSolver.iterationsCount+=1;
this.invertSolver.iterationsCount+=1;
if(this.directSolver.iterationsCount > this.memLimit) {
// search blocked manually to avoid long waits
this.blockedByMemory = true;
return;
}
if(this.statesMet(nextD, nextI)) {
// direct and invert solutions are combined
this.statesHasMet = true;
return;
}
if(typeof nextD === 'undefined' && typeof nextI == 'undefined'){
// no admissible solution
this.noAdmissibleSolution = true;
return;
}
}
//solved without states meeting
this.solvedWithoutMet = true;
return;
}
combineSolution(node) {
let direct = this.directSolver.stateTable.states[node.state];
let invert = this.invertSolver.stateTable.states[node.state];
while(invert.direction != null) {
this.invertSolution.push(invert.direction);
invert = invert.parent;
}
while(direct.direction != null) {
this.directSolution.push(direct.direction);
direct = direct.parent;
}
for(let i = this.directSolution.length-1; i >= 0; i--) {
this.solution.push(this.directSolution[i]);
}
for(let i = 0; i < this.invertSolution.length; i++) {
this.solution.push(this.puzzle.getOppositeDirection(this.invertSolution[i]));
}
}
statesMet(nodeD, nodeI) {
let d = typeof this.directSolver.stateTable.states[nodeI.state] !== 'undefined';
let i = typeof this.invertSolver.stateTable.states[nodeD.state] !== 'undefined';
if(d) {
this.combineSolution(nodeI);
return true;
} else if(i) {
this.combineSolution(nodeD);
return true;
} else return false;
}
logAnalytics() {
let s = '';
s += 'direct solution cost: ' + this.directSolution.length + '\n';
s += 'invert solution cost: ' + this.invertSolution.length + '\n';
s += 'solution cost: ' + this.solution.length + '\n';
s += 'direct solver node created: ' + this.directSolver.nodeCreated + '\n';
s += 'direct & invert solver iterations: ' + this.directSolver.iterationsCount + '\n';
s += 'invert solver node created: ' + this.invertSolver.nodeCreated + '\n';
s += 'direct solver branching rate: ' + this.directSolver.getAverageExpansion() + '\n';
s += 'invert solver branching rate: ' + this.invertSolver.getAverageExpansion() + '\n';
s += 'blocked by memory: ' + this.blockedByMemory + '\n';
s += 'no admissible solution: ' + this.noAdmissibleSolution + '\n';
s += 'states has met in the middle: ' + this.statesHasMet + '\n';
s += 'solved without states met: ' + this.solvedWithoutMet;
return s;
}
}
const memLimit = 10000000;
const puzzleSize = 3;
var p = new Puzzle(puzzleSize);
//p.getHtml();
function resetPuzzle() {
p.generate();
p.getHtml();
}
function shufflePuzzle() {
p.shuffle();
}
function showAnalytics(b) {
let directSolCost = b.directSolution.length;
let invertSolCost = b.invertSolution.length;
let solCost = b.solution.length;
let directNodeCreated = b.directSolver.nodeCreated;
let invertNodeCreated = b.invertSolver.nodeCreated;
let iterations = b.directSolver.iterationsCount;
let directBranchingRate = (Math.round(b.directSolver.getAverageExpansion() * 100) / 100).toFixed(2);
let invertBranchingRate = (Math.round(b.invertSolver.getAverageExpansion() * 100) / 100).toFixed(2);
let admissible = (b.noAdmissibleSolution) ? 'No' : 'Yes';
let met = (b.statesHasMet) ? 'Yes' : 'No';
document.getElementById("direct-solution-cost").innerHTML = directSolCost;
document.getElementById("invert-solution-cost").innerHTML = invertSolCost;
document.getElementById("solution-cost").innerHTML = solCost;
document.getElementById("direct-nodes-created").innerHTML = directNodeCreated;
document.getElementById("invert-nodes-created").innerHTML = invertNodeCreated;
document.getElementById("tot-iterations").innerHTML = iterations;
document.getElementById("invert-branching-rate").innerHTML = invertBranchingRate;
document.getElementById("direct-branching-rate").innerHTML = directBranchingRate;
document.getElementById("admissible-solution").innerHTML = admissible;
document.getElementById("solvers-met").innerHTML = met;
}
/* CONTROLS */
function solvePuzzle() {
var solved = new Puzzle(puzzleSize);
var b = new BidirectionalBestFirstSolver(p, solved, memLimit);
b.search();
console.log(b.logAnalytics());
console.log(b.solution);
let i = 0;
function solveStep() { // create a function
setTimeout(function() { // initialize a setTimeout
p.move(b.solution[i]); // execute instructions
i++; // increment the counter
if (i < b.solution.length) { // recursive if controller
solveStep(); // recursive call
}
}, 300)
}
solveStep();
showAnalytics(b);
}
function resetPuzzle() {
p = new Puzzle(puzzleSize);
}
function shufflePuzzle() {
p.shuffle();
}
/* PUZZLE GRAPHICS */
let cellSize = 80;
let ratio = (cellSize*p.cell.length/2);
function drawPuzzle(p) {
fill(color(0, 95, 163));
let frameThickness = 30;
rect(-(cellSize * p.cell.length + frameThickness)/2, -(cellSize * p.cell.length + frameThickness)/2, cellSize * p.cell.length + frameThickness, cellSize * p.cell.length + frameThickness);
for(let i = 0; i < p.cell.length; i++) {
for(let j = 0; j < p.cell[i].length; j++) {
rect(i*cellSize - ratio, j*cellSize - ratio, cellSize, cellSize);
image(img[p.cell[j][i]], i*cellSize - ratio, j*cellSize - ratio, cellSize, cellSize);
}
}
}
let img = [];
function preload() {
for(let i = 0; i < 9; i++) {
img[i] = loadImage('/uploads/stefano/'+i+'.jpg');
}
}
//BACKGROUND GRAPHICS
let backChangeR = 0;
let backChangeG = 0;
let backChangeB = 0;
let backIncremR = 0.01;
let backIncremG = 0.02;
let backIncremB = 0.03;
/* *************** */
/* KEYBOARD LISTENER */
document.onkeyup = checkKey;
function checkKey(e) {
e = e || window.event;
if (e.keyCode == '38') {
p.move(p.UP);
}
else if (e.keyCode == '40') {
p.move(p.DOWN);
}
else if (e.keyCode == '37') {
p.move(p.LEFT);
}
else if (e.keyCode == '39') {
p.move(p.RIGHT);
}
}
/* *************** */
/* HEADER */
AB.msg('<h4>Use the buttons below to interact:</h4>', 1);
AB.msg ( '<button class="ab-normbutton" onclick="resetPuzzle()">Reset</button>', 2 );
AB.msg ( '<button class="ab-normbutton" onclick="shufflePuzzle()">Shuffle</button>', 3 );
AB.msg ( '<button class="ab-normbutton" onclick="solvePuzzle()">Solve</button>', 4 );
AB.msg('<p><i><b>Tip: </b>use arrow keys to move the tiles!</i></p>', 5);
AB.msg(`
<div id="analytics-container" class="inline-container">
<div class="analytics-container">
<h4>Direct Solver</h4>
Solution cost: <span id="direct-solution-cost">0</span> <br>
Nodes created: <span id="direct-nodes-created">0</span> <br>
Branching rate: <span id="direct-branching-rate">0</span> <br>
</div>
<div class="analytics-container">
<h4>Invert Solver</h4>
Solution cost: <span id="invert-solution-cost">0</span> <br>
Nodes created: <span id="invert-nodes-created">0</span> <br>
Branching rate: <span id="invert-branching-rate">0</span> <br>
</div>
<div id="general-solution" class="analytics-container">
<h4>Solution</h4>
Iteration (per solver): <span id="tot-iterations">0</span> <br>
Solution cost: <span id="solution-cost">0</span> <br>
Admissible solution: <span id="admissible-solution">-</span> <br>
Solvers have found common state: <span id="solvers-met">-</span> <br>
</div>
</div>
</div>
`, 6);
/* *************** */
/* INITIAL PUZZLE */
p.shuffle();
solvePuzzle();
/* *************** */
function setup() // "setup" is called once at start of run
{
createCanvas ( ABWorld.fullwidth(), ABWorld.fullheight(), WEBGL );
}
function draw() // "draw" is called every timestep during run
{
background(19 + 20*Math.sin(backChangeR), 181 + 20*Math.sin(backChangeG), 235 + 20*Math.sin(backChangeB));
drawPuzzle(p);
backChangeR += backIncremR;
backChangeG += backIncremG;
backChangeB += backIncremB;
if(backChangeR >= Math.PI * 2) {
backChangeR = 0;
}
if(backChangeG >= Math.PI * 2) {
backChangeG = 0;
}
if(backChangeB >= Math.PI * 2) {
backChangeB = 0;
}
}