const CLOCKTICK = 10;
const MAXSTEPS = 10000000;
const SCREENSHOT_STEP = 50;
const GRIDSIZE = 3;
const SQUARESIZE = 200;
const MAXPOS = GRIDSIZE * SQUARESIZE;
const SKYCOLOR = 0xccffff;
const BLANKCOLOR = SKYCOLOR;
const STARTRADIUS = MAXPOS * 1;
const MAXRADIUS = MAXPOS * 3;
const UP = 0;
const LEFT = 1;
const DOWN = 2;
const RIGHT = 3;
const CORRECT = "12345678#";
// 1 2 3
// 4 5 6
// 7 8 #
const CORRECTMAPPING = {
"1" : [0,0],
"2" : [1,0],
"3" : [2,0],
"4" : [0,1],
"5" : [1,1],
"6" : [2,1],
"7" : [0,2],
"8" : [1,2],
"#" : [2,2],
}
const UPLOAD_PATH = "/uploads/mati/";
const IMG_FILES = [ '1.png', '2.png', '3.png',
'4.png', '5.png', '6.png',
'7.png', '8.png', '9s.png'];
const IMAGE_PATH = UPLOAD_PATH + randomInt(0,5).toString() + "-";
// const IMAGE_PATH = UPLOAD_PATH + "0-";
var GRID = [];
function randomFloat(a, b) {
return (a + (Math.random() * (b - a)));
}
function randomInt(a, b) {
return (Math.round(randomFloat(a, b)));
}
function randomBoolean() {
if (Math.random() < 0.5) { return false; }
else { return true; }
}
function translate(x) {
return (x - (MAXPOS / 2));
}
function shuffle(array, num) {
var tmp, current, top = array.length;
if (top) {
while(num--) {
top = randomInt(0,8)
current = randomInt(0,8);
tmp = array[current];
array[current] = array[top];
array[top] = tmp;
}
}
return array;
}
function randomizeArray(arr, num) {
a = arr;
return shuffle(a, num);
}
function stringToArray(str) {
var val = [];
for (var i = 0; i < str.length; i++) {
val[i] = str[i];
}
return val;
}
function arrayToString(arr) {
var val = "";
for (var i = 0; i < arr.length; i++) {
val += arr[i];
}
return val;
}
function HashMap() {
this.length = 0;
this.store = [];
this.mapped = {};
this.lowest = 10000000;
this.put = function(key, value) {
if (!this.hasItem(key)) {
try {
var tmpkeys = Object.getOwnPropertyNames(this.store[value.f]);
} catch (e) {
this.store[value.f] = {};
}
this.store[value.f][key] = value;
this.mapped[key] = value.f;
if (this.lowest > value.f) {
this.lowest = value.f;
}
this.length++;
return true;
} else {
return false;
}
}
this.getKeys = function() {
return Object.getOwnPropertyNames(this.mapped);
}
this.remove = function(key) {
if (this.hasItem(key)) {
delete this.store[this.mapped[key]][key];
delete this.mapped[key];
this.length--;
return true;
} else {
return false;
}
}
this.get = function(key) {
if (this.hasItem(key)) {
return this.store[this.mapped[key]][key];
} else {
return null;
}
}
this.getFirst = function() {
if (this.length > 0) {
var keys = this.getKeys();
return this.get(keys[0]);
} else {
return null;
}
}
this.hasItem = function(key) {
return this.mapped.hasOwnProperty(key);
}
}
function Cube(number, gridX, gridY, cords) {
this.number = number;
this.gridX = gridX;
this.gridY = gridY;
this.cords = cords;
this.getHeuristicValue = function() {
var var1 = Math.abs(this.cords[0] - this.gridX);
var var2 = Math.abs(this.cords[1] - this.gridY);
return (var1 + var2);
}
this.isCorrect = function() {
var val1 = this.gridX === this.cords[0];
var val2 = this.gridY === this.cords[1];
return (val1 && val2);
}
}
function Slot(number, x, y, cube) {
this.number = number;
this.cube = null;
this.x = x;
this.y = y;
this.isEmpty = function() {
return this.cube == null;
}
this.assignCube = function(slot) {
this.cube = slot.cube;
slot.cube = null;
this.cube.gridY = this.y;
this.cube.gridX = this.x;
}
this.move = function(direction) {
if (direction == UP && this.y != 0) {
var target = GRID[this.x][this.y - 1];
this.assignCube(target);
return true;
} else if (direction == LEFT && this.x != 0) {
var target = GRID[this.x - 1][this.y];
this.assignCube(target);
return true;
} else if (direction == DOWN && this.y != 2) {
var target = GRID[this.x][this.y + 1];
this.assignCube(target);
return true;
} else if (direction == RIGHT && this.x != 2) {
var target = GRID[this.x + 1][this.y];
this.assignCube(target);
return true;
}
return false;
}
}
function World() {
function initGrid() {
for (var x = 0; x < GRIDSIZE; x++) {
GRID[x] = new Array(GRIDSIZE);
}
var i = 0;
for (var y = 0; y < GRIDSIZE; y++) {
for (var x = 0; x < GRIDSIZE ; x++) {
GRID[x][y] = new Slot(i + 1, x, y);
slots[i] = GRID[x][y];
i++;
}
}
}
function initCubes(str) {
var arr = stringToArray(str);
var j = 0;
for (var i = 0; i < slots.length; i++) {
if (arr[i] != '#') {
var cords = CORRECTMAPPING[arr[i]];
slots[i].cube = new Cube(arr[i], slots[i].x, slots[i].y, cords);
cubes[j] = slots[i].cube;
j++;
} else {
slots[i].cube = null;
}
}
}
function initThreeCube(cube) {
var shape = new THREE.BoxGeometry(SQUARESIZE, SQUARESIZE/2, SQUARESIZE);
cube.drawable = new THREE.Mesh(shape);
cube.drawable.material.color.setHex(BLANKCOLOR);
}
function loadTexture(cube) {
var filename = IMAGE_PATH + IMG_FILES[cube.number-1];
var loader = new THREE.TextureLoader();
loader.load(filename, function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
cube.drawable.material = new THREE.MeshBasicMaterial({
map : thetexture
});
});
}
function drawCube(cube) {
var x = translate(cube.gridX * SQUARESIZE);
var z = translate(cube.gridY * SQUARESIZE);
var y = 0;
cube.drawable.position.x = x;
cube.drawable.position.y = y;
cube.drawable.position.z = z;
threeworld.scene.add(cube.drawable);
}
function initAllTHREECubes() {
for (var i = 0; i < cubes.length; i++) {
initThreeCube(cubes[i]);
loadTexture(cubes[i]);
}
}
function drawAllCubes() {
for (var i = 0; i < slots.length; i++) {
if (slots[i].cube != null) {
drawCube(slots[i].cube);
}
}
}
function move(direction) {
for (var i = 0; i < slots.length; i++) {
if (slots[i].isEmpty()) {
return slots[i].move(direction);
}
}
}
function reverseMove(direction) {
if (direction === UP) {
move(DOWN);
} else if (direction === DOWN) {
move(UP);
} else if (direction === RIGHT) {
move(LEFT);
} else if (direction === LEFT) {
move(RIGHT);
}
}
function actionHandler(e) {
if (e.keyCode == 37) move(LEFT);
if (e.keyCode == 38) move(UP);
if (e.keyCode == 39) move(RIGHT);
if (e.keyCode == 40) move(DOWN);
}
function Stats() {
this.count = 0;
this.heuristicValue = 0;
for (var i = 0; i < slots.length; i++) {
if (slots[i].cube != null) {
if (slots[i].cube.isCorrect()) {
this.count++;
}
var tmp = slots[i].cube.getHeuristicValue();
this.heuristicValue += tmp;
}
}
}
function printStatus() {
var stats = new Stats();
var text = "Correct: " + stats.count;
$("#user_span4").text(text);
var text = "Heuristic: " + stats.heuristicValue;
$("#user_span5").text(text);
var text = "Steps: " + moves;
$("#user_span6").text(text);
}
function printSolvingStatus(totalOpen, totalClosed, totalmoves) {
$("#user_span1").text("Open cases: " + totalOpen);
$("#user_span2").text("Closed cases: " + totalClosed);
$("#user_span3").text("Moves taken to find the solution: " + totalmoves);
}
function boardToString() {
var val = "";
for (var i = 0; i < slots.length; i++) {
if (slots[i].cube == null) {
val += "#";
} else {
val += slots[i].cube.number;
}
}
return val;
}
function directionToString(direction) {
switch (direction) {
case UP:
return "UP";
break;
case DOWN:
return "DOWN";
break;
case LEFT:
return "LEFT";
break;
case RIGHT:
return "RIGHT";
break;
default:
return "NONE";
}
}
function cloneSlots() {
var arr = [];
for (var i = 0; i < slots.length; i++) {
var tmp = new Slot(0,0,0,new Cube(0,0,0,null));
arr[i] = $.extend(true, tmp, slots[i]);
}
return arr;
}
function bringClonesToLife(step) {
for (var i = 0; i < step.clones.length; i++) {
slots[i] = step.clones[i];
if (step.boardString[i] == '#') {
slots[i].cube = null;
}
}
var i = 0;
for (var y = 0; y < GRIDSIZE; y++) {
for (var x = 0; x < GRIDSIZE; x++) {
GRID[x][y] = slots[i];
i++;
}
}
fixGridPosition();
}
function fixGridPosition() {
for (var i = 0; i < slots.length; i++) {
if (slots[i].cube != null) {
slots[i].cube.gridX = slots[i].x;
slots[i].cube.gridY = slots[i].y;
}
}
}
function Step(g, direction) {
this.stats = new Stats();
this.clones = cloneSlots();
this.direction = direction;
this.move = directionToString(direction);
this.correct = this.stats.count;
this.h = this.stats.heuristicValue;
this.g = g;
this.f = g + this.h;
this.boardString = boardToString();
this.isSolved = function() {
return this.correct === (slots.length - 1);
}
}
function solveWithAStar() {
if (open.length > 0) {
var currentStep = bestOpen(open);
var current = currentStep.boardString;
bringClonesToLife(currentStep);
open.remove(current);
closed.put(current, currentStep);
if (currentStep.isSolved()) {
solved = true;
return rebuildPath(path, current, closed);
}
for (var direction = 0; direction < 4; direction++) {
if (move(direction)) {
solvingMoves++;
printSolvingStatus(open.length, closed.length, solvingMoves);
printStatus();
var neighbour = boardToString();
if (closed.hasItem(neighbour)) {
reverseMove(direction);
continue;
}
var tempG = gMap.get(current) + 1;
var neighbourStep = new Step(tempG, direction);
var isBetter = false;
if (!open.hasItem(neighbour)) {
open.put(neighbour, neighbourStep);
isBetter = true;
} else if (tempG < gMap.get(neighbour)) {
gMap.remove(neighbour);
path.remove(neighbour);
isBetter = true;
} else {
isBetter = false;
}
if (isBetter) {
path.put(neighbour, current);
gMap.put(neighbour, neighbourStep.g);
}
reverseMove(direction);
};
}
}
return null;
}
function bestOpen(map) {
var keys = map.getKeys();
for (var i = map.lowest; i < map.store.length; i++) {
var subkeys = [];
try {
subkeys = Object.getOwnPropertyNames(map.store[i]);
} catch (e) {
map.lowest = i + 1;
continue;
}
if (subkeys.length > 0) {
var best = map.store[i][subkeys[0]];
for (var j = 0; j < subkeys.length; j++) {
var tmp = map.store[i][subkeys[j]];
if (best.g > tmp.g) {
best = tmp;
}
}
return best;
} else {
map.lowest = i + 1;
}
}
}
function rebuildPath(map, current, closed) {
var rebuilt = [current];
current = map.get(current);
rebuilt.push(current);
while (map.hasItem(current)) {
current = map.get(current);
rebuilt.push(current);
}
var solution = [];
for (var i = 0; i < rebuilt.length; i++) {
solution.push(closed.get(rebuilt[i]));
}
return solution;
}
function shuffleCubes(min, max){
var r = randomInt(min, max);
var minHeurVal = randomInt(15,22);
for (var i = 0; i < r; i++) {
move(randomInt(0,3));
var stats = new Stats();
if (i > (r / 2) && stats.heuristicValue >= minHeurVal) {
console.log("Shuffles: %d H: %d", i,stats.heuristicValue);
break;
}
}
}
function logSlots(msg) {
var arr = [];
var j = 0;
for (var i = 0; i < slots.length; i++) {
if (slots[i].cube != null) {
arr[j++] = slots[i].cube.number;
arr[j++] = slots[i].cube.gridX;
arr[j++] = slots[i].cube.gridY;
} else {
arr[j++] = '#';
arr[j++] = 'X';
arr[j++] = 'Y';
}
}
for (var i = 0; i < arr.length; i++) {
msg += "Slot["+i+"] : " + arr[i++] + " ("+ arr[i++] + "," + arr[i] + ") ";
}
console.log(msg);
}
GRID = new Array(GRIDSIZE);
var slots = new Array(GRIDSIZE * GRIDSIZE);
var cubes = new Array(GRIDSIZE * GRIDSIZE - 1);
var open = new HashMap();
var closed = new HashMap();
var path = new HashMap();
var gMap = new HashMap();
var moves;
var solved;
var solvedPath = [];
var solveIndex;
var originalState;
var initial;
var solvingMoves;
var self = this;
this.endCondition;
this.newRun = function() {
$("#user_span1").siblings('span').css({
"margin":"15px 15px", "padding":"10px"
});
this.endCondition = false;
moves = 0;
solvingMoves = 0;
solved = false;
initGrid();
initCubes(CORRECT);
shuffleCubes(25000,100000);
var stats = new Stats();
var h = stats.heuristicValue;
var g = 0;
var state = boardToString();
var step = new Step(g, -1);
originalState = step;
gMap.put(state, g);
open.put(state, step);
if (true) {
threeworld.init3d(STARTRADIUS, MAXRADIUS, SKYCOLOR);
initAllTHREECubes();
}
};
this.getState = function() {
return null;
};
var wait = 500;
this.nextStep = function()
{
var a = 5;
if (wait) {
$("#user_span7").text(Math.round(wait / 100));
$("#user_span7").css({"color": "red", "font-weight": "bold"});
wait--;
} else if (!solved) {
$("#user_span7").text("Looking for a solution!");
$("#user_span7").css({"color": "blue", "font-weight": "bold"});
solvedPath = solveWithAStar();
if (solvedPath != null) {
solveIndex = solvedPath.length - 2;
}
if (solved) {
initial = true;
}
} else if (solveIndex >= 0) {
$("#user_span7").text("Keep going!");
if (solveIndex == 1) {
$("#user_span7").text("One more time...");
}
$("#user_span7").css({"color": "black", "font-weight": "bold"});
if (initial) {
$("#pausebutton").click();
$("#user_span7").text("Found it! Click on 'STEP'");
$("#user_span7").css({"color": "red", "font-weight": "bold"});
bringClonesToLife(originalState);
initial = false;
} else {
move(solvedPath[solveIndex].direction);
moves++;
solveIndex--;
}
if (solveIndex < 0) {
$("#user_span7").text("HURRAY!");
$("#user_span7").css({"color": "green", "font-weight": "bold", "font-size": "1.5em"});
this.endCondition = true;
}
}
if (true) {
drawAllCubes();
printStatus();
}
};
this.endRun = function() {
$("#user_span7").text("HURRAY!");
$("#user_span7").css({"color": "green", "font-weight": "bold", "font-size": "1.5em"});
};
this.getScore = function() {
return moves;
};
}