const direction = [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]];
function Mind()
{
function Node(state, player, map) {
this.value = null;
this.gen = -1;
this.player = player;
this.state = state;
this.child = [];
this.par = [];
Node.removeNode = function(x, y) {
x = x.toString();
y = y.toString();
for (var key in Node.memo) {
if (Node.memo.hasOwnProperty(key)) {
var tmp = key.split(',');
if ((tmp[0] === x && tmp[1] === y) || (tmp[2] === x && tmp[3] === y)) {
var cur = Node.memo[key];
var j;
for (j = 0; j < cur.par.length; ++j) {
for (var k = 0; k < cur.par[j].child.length; ++k) {
if (cur.par[j].child[k][1] === cur) {
cur.par[j].child.splice(k, 1);
break;
}
}
}
for (j = 0; j < cur.child.length; ++j) {
var ttmp = cur.child[j][1].par.indexOf(cur);
if (ttmp !== -1) {
cur.child[j][1].par.splice(ttmp, 1);
}
}
delete Node.memo[key];
}
}
}
};
Node.addDepth = function(map) {
while (Node.end.length) {
var cur = Node.end.shift();
var x;
var y;
var tmp;
var i;
if (cur.child.length) {
continue;
}
if (cur.player) {
for (i = 0; i < direction.length; ++i) {
x = cur.state[0] + direction[i][0];
y = cur.state[1] + direction[i][1];
if (map.get(x, y) !== 1 && !(x === cur.state[2] && y === cur.state[3])) {
tmp = Node.memo[[x, y, cur.state[2], cur.state[3]].toString() + ',E'];
if (tmp === undefined) {
tmp = new Node([x, y, cur.state[2], cur.state[3]], !cur.player, map);
Node.memo[tmp.state.toString() + ',E'] = tmp;
Node.end.push(tmp);
}
if (!tmp.par.includes(cur)) {
tmp.par.push(cur);
}
cur.child.push([i, tmp]);
}
}
}
else {
for (i = 0; i < direction.length; ++i) {
x = cur.state[2] + direction[i][0];
y = cur.state[3] + direction[i][1];
if (map.get(x, y) !== 1 && !(x === cur.state[0] && y === cur.state[1])) {
tmp = Node.memo[[cur.state[0], cur.state[1], x, y].toString() + ',P'];
if (tmp === undefined) {
tmp = new Node([cur.state[0], cur.state[1], x, y], !cur.player, map);
Node.memo[tmp.state.toString() + ',P'] = tmp;
Node.end.push(tmp);
}
if (!tmp.par.includes(cur)) {
tmp.par.push(cur);
}
cur.child.push([i, tmp]);
}
}
}
}
};
this.minimax = function(map, depth = 7) {
if (this.gen < map.gen) {
this.value = map.distance(this.state);
this.gen = map.gen;
}
if (!depth) {
this.ret = [this.value, 4];
return this.ret;
}
--depth;
var val;
var inc;
var tmp;
if (this.player) {
val = [-500, 0];
for (inc = 0; inc < this.child.length; ++inc) {
tmp = this.child[inc][1].minimax(map, depth);
if (tmp[0] >= val[0]) {
val = [tmp[0], this.child[inc][0]];
}
}
}
else {
val = [500, 0];
for (inc = 0; inc < this.child.length; ++inc) {
tmp = this.child[inc][1].minimax(map, depth);
if (tmp[0] <= val[0]) {
val = [tmp[0], this.child[inc][0]];
}
}
}
this.ret = val.slice();
this.ret[0] = Math.min(this.ret[0], this.value);
return this.ret;
};
}
function Map() {
this.map = [];
this.dict = {};
this.gen = 0;
for (var i = 0; i < 20; ++i) {
this.map.push([]);
for (var j = 0; j < 20; ++j) {
if (i === 0 || i === 19 || j === 0 || j === 19) {
this.map[i].push(1);
}
else {
this.map[i].push(2);
}
}
}
this.set = function(x, y, val) {
if (val === 1 && this.map[y][x] !== 1) {
this.dict = {};
this.gen += 1;
}
this.map[y][x] = val;
};
this.get = function(x, y) {
return this.map[y][x];
};
this.print = function() {
for (var i = 0; i < this.map.length; ++i) {
console.log(i, this.map[i].join(' '));
}
};
Map.ManhatanDist = function(start, end) {
return Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]);
};
this.UpdateDict = function(cameFrom) {
for (var key in cameFrom) {
if (cameFrom.hasOwnProperty(key)) {
var dest = key;
var cur = cameFrom[key];
var dist = 0;
while (cur !== undefined) {
dist += 1;
var tmp = [cur, dest];
tmp.sort();
tmp = tmp[0] + tmp[1];
if (!(tmp in this.dict) || this.dict[tmp] > dist) {
this.dict[tmp] = dist;
}
cur = cameFrom[cur];
}
}
}
};
this.Astar = function(start, end) {
const fun = function (elem) {
return elem[0] == this[0] && elem[1] == this[1];
};
var done = [];
var open = [start];
var gScore = {};
var fscore = {};
gScore[start.toString()] = 0;
fscore[start.toString()] = Map.ManhatanDist(start, end);
var cameFrom = {};
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
while (open.length) {
var cur = open[0];
var tmp = fscore[cur.toString()];
var index = 0;
var i;
for (i = 1; i < open.length; ++i) {
if (tmp > fscore[open[i].toString()]) {
tmp = fscore[open[i].toString()];
cur = open[i];
index = i;
}
}
open.splice(index, 1);
done.push(cur);
if (cur[0] == end[0] && cur[1] == end[1]) {
this.UpdateDict(cameFrom);
return gScore[cur];
}
for (i = 0; i < dir.length; ++i) {
tmp = [cur[0] + dir[i][0], cur[1] + dir[i][1]];
if (this.map[tmp[1]][tmp[0]] != 1) {
if (done.find(fun, tmp)){
continue;
}
index = gScore[cur.toString()] + 1;
if (!open.find(fun, tmp)) {
open.push(tmp);
}
else if (gScore[tmp.toString()] !== undefined && gScore[tmp.toString()] >= index) {
continue;
}
cameFrom[tmp.toString()] = cur.toString();
gScore[tmp.toString()] = index;
fscore[tmp.toString()] = index + Map.ManhatanDist(tmp, end);
}
}
}
return (900);
};
this.distance = function(state) {
if (Math.abs(state[0] - state[2]) < 2 && Math.abs(state[1] - state[3]) < 2) {
return Map.ManhatanDist([state[0], state[1]], [state[2], state[3]]);
}
var tmp = [ [state[0], state[1]].toString(), [state[2], state[3]].toString() ];
tmp.sort();
var hash = tmp[0] + tmp[1];
if (this.dict[hash] === undefined) {
this.dict[hash] = this.Astar([state[0], state[1]], [state[2], state[3]]);
}
return this.dict[hash];
};
}
this.newRun = function()
{
this.map = new Map();
this.dir = 0;
this.last = [0, 0];
};
this.setWall = function(state) {
if (state[0] != this.last[0] || state[1] != this.last[1] || this.dir === 4) {
return false;
}
x = state[0] + direction[this.dir][0];
y = state[1] + direction[this.dir][1];
if (x == this.last[3] || y == this.last[4]) {
return false;
}
this.map.set(x, y, 1);
Node.removeNode(x, y);
return true;
};
this.reset = function( state ) {
console.log('reset');
this.tree = new Node(state, true, this.map);
Node.memo = {};
Node.end = [this.tree];
Node.memo[this.tree.state.toString() + ',P'] = this.tree;
Node.addDepth(this.map);
};
this.choose = function() {
this.dir = this.tree.ret[1];
};
this.getAction = function ( state )
{
this.map.set(state[0], state[1], 0);
if (this.last[0] === 0) {
this.reset(state);
}
this.setWall(state);
this.tree = Node.memo[state.toString() + ',P'];
this.last = state;
this.tree.minimax(this.map);
this.choose();
return ( this.dir );
};
this.endRun = function()
{
};
}