Skip to content

Instantly share code, notes, and snippets.

@dested

dested/dotgame.js

Last active Dec 7, 2017
Embed
What would you like to do?
const width = 7;
const height = 7;
let grid = new Array(width * height);
const WALL = 0;
const DOT = 1;
const EMPTY = 2;
for (let x = 0; x < width; x++) {
for (let y = 0; y < height; y++) {
grid[x + y * width] = WALL;
}
}
const inset = 2;
for (let x = inset; x < width - inset; x++) {
for (let y = 0; y < height; y++) {
grid[x + y * width] = DOT;
}
}
for (let x = 0; x < width; x++) {
for (let y = inset; y < height - inset; y++) {
grid[x + y * width] = DOT;
}
}
let centerX = Math.floor(width / 2);
let centerY = Math.floor(height / 2);
grid[centerX + centerY * width] = EMPTY;
function processPath(grid) {
let initStatus = calcStatus(grid);
let newStates = [{grid, lastGrid: null, ser: initStatus.ser, score: initStatus.score}];
let now = +new Date();
let closedStates = {};
let tries = 0;
let lowestScore = width * height;
let lowestScoreIndex = 0;
while (newStates.length > 0) {
let state = newStates[lowestScoreIndex];
newStates.splice(lowestScoreIndex, 1);
closedStates[state.ser] = true;
let grid = state.grid;
if (tries++ % 10000 === 0) {
console.log(newStates.length, Object.keys(closedStates).length, state.score, ((+new Date()) - now) / 10000 + " per try");
now = +new Date();
// drawUI(grid)
}
processNeighbors(grid, state, newStates, closedStates);
lowestScore = width * height;
for (let i = 0; i < newStates.length; i++) {
if (newStates[i].score < lowestScore) {
lowestScoreIndex = i;
lowestScore = newStates[i].score;
}
}
if (lowestScore === 1) {
if (newStates[lowestScoreIndex].grid[centerX + centerY * width] === DOT) {
break;
} else {
console.log('made it to 1');
let s = newStates[lowestScoreIndex];
closedStates[s.ser] = true;
newStates.splice(0, 1);
}
}
}
let path = [newStates[lowestScoreIndex].grid];
let state = newStates[lowestScoreIndex];
while (state.lastState) {
path.push(state.lastState.grid);
state = state.lastState;
}
console.log(`${path.length} moves, ${tries} tries`);
path.reverse();
return path;
}
function processNeighbors(grid, lastState, newStates, closedStates) {
for (let x = 0; x < width; x++) {
for (let y = 0; y < height; y++) {
if (grid[x + y * width] === EMPTY) {
let neighbors = getDotNeighbors(grid, x, y);
for (let i = 0; i < 4; i++) {
let neighbor = neighbors[i];
if (neighbor.inner === -1) break;
let newGrid = grid.slice(0);
newGrid[x + y * width] = DOT;
newGrid[neighbor.inner] = EMPTY;
newGrid[neighbor.outer] = EMPTY;
let ser = newGrid.join();
if (closedStates[ser]) {
continue;
}
newStates.push({grid: newGrid, lastState: lastState, ser: ser, score: lastState.score - 1});
}
}
}
}
};
function calcStatus(grid) {
let score = 0;
let size = width * height;
for (let i = 0; i < size; i++) {
if (grid[i] === DOT) {
score++;
}
}
return {score, ser: grid.join()};
}
const neighborItems = new Array(4);
neighborItems[0] = {inner: -1, outer: -1};
neighborItems[1] = {inner: -1, outer: -1};
neighborItems[2] = {inner: -1, outer: -1};
neighborItems[3] = {inner: -1, outer: -1};
function getDotNeighbors(grid, x, y) {
neighborItems[0].inner = -1;
neighborItems[1].inner = -1;
neighborItems[2].inner = -1;
neighborItems[3].inner = -1;
let count = 0;
if (x > 1 && grid[(x - 2) + y * width] === DOT && grid[(x - 1) + y * width] === DOT) {
neighborItems[count].inner = (x - 1) + y * width;
neighborItems[count++].outer = (x - 2) + y * width;
}
if (x < width - 2 && grid[(x + 2) + y * width] === DOT && grid[(x + 1) + y * width] === DOT) {
neighborItems[count].inner = (x + 1) + y * width;
neighborItems[count++].outer = (x + 2) + y * width;
}
if (y > 1 && grid[x + (y - 2) * width] === DOT && grid[x + (y - 1) * width] === DOT) {
neighborItems[count].inner = x + (y - 1) * width;
neighborItems[count++].outer = x + (y - 2) * width;
}
if (y < width - 2 && grid[x + (y + 2) * width] === DOT && grid[x + (y + 1) * width] === DOT) {
neighborItems[count].inner = x + (y + 1) * width;
neighborItems[count].outer = x + (y + 2) * width;
}
return neighborItems;
}
function drawUI(grid) {
let ui = '';
for (let x = 0; x < width; x++) {
for (let y = 0; y < height; y++) {
if (grid[x + y * width] === WALL) {
ui += "X";
} else {
if (grid[x + y * width] === DOT) {
ui += ".";
} else {
ui += " ";
}
}
}
ui += "\r\n";
}
console.clear();
console.log(ui);
}
let path = processPath(grid);
for (let i = 0; i < path.length; i++) {
let p = path[i];
drawUI(p);
}
//0.0369
//0.0409
//820001 0.0721 made it to 1
//0.04
//0.0409
//0.0349
//820001 0.0654 made it to 1
//0.0291
//820001 0.0568 made it to 1
//0.0248
//820001 0.0549 made it to 1
//0.0207
//820001 0.0523 made it to 1
//solved at 1390001 0.0755
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment