const direction = [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]];
class Node {
constructor(state, move, player, map) {
this.move = move;
this.value = null;
this.treeValue = this.value;
this.player = player;
this.state = state;
this.child = [];
}
addDepth(map) {
var x;
var y;
var c;
var i = 0;
if (this.child.length) {
for (c = 0; c < this.child.length; ++c) {
this.child[c].addDepth(map);
}
}
else
{
if (this.player) {
for (i = 0; i < 5; ++i) {
x = this.state[0] + direction[i][0];
y = this.state[1] + direction[i][1];
if (map.get(x, y) !== 1 && !(x === this.state[2] && y === this.state[3])) {
this.child.push(new Node([x, y, this.state[2], this.state[3]], i, !this.player, map));
}
}
}
else {
for (i = 0; i < 5; ++i) {
x = this.state[2] + direction[i][0];
y = this.state[3] + direction[i][1];
if (map.get(x, y) !== 1 && !(x === this.state[2] && y === this.state[3])) {
this.child.push(new Node([this.state[0], this.state[1], x, y], i, !this.player, map));
}
}
}
}
}
getBest(map, minned = true, alpha = -500, beta = 500) {
if (this.value === null) {
this.value = map.distance(this.state);
}
if (!this.child.length) {
return [this.value, this.move];
}
var cur;
var c;
var tmp;
if (this.player) {
cur = [-500, 0];
for (c = 0; c < this.child.length; ++c) {
tmp = this.child[c].getBest(map, alpha, beta);
if (tmp[0] > cur[0]) {
cur = [tmp[0], this.child[c].move];
}
//alpha = Math.max(alpha, cur[0]);
//if (alpha >= beta) {
// break;
//}
}
}
else
{
cur = [500, 0];
for (c = 0; c < this.child.length; ++c) {
tmp = this.child[c].getBest(map, alpha, beta);
if (tmp[0] < cur[0]) {
cur = [tmp[0], this.child[c].move];
}
//beta = Math.min(beta, cur[0]);
//if (alpha >= beta) {
// break;
//}
}
}
if (minned && this.value < 3) {
cur[0] = Math.min(this.value, cur[0]);
}
this.treeValue = cur[0];
return cur;
}
}
function Mind()
{
function Map() {
this.map = [];
this.dict = {};
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.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(' '));
}
};
function ManhatanDist(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()] = 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 + 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 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);
return true;
};
this.moveTree = function(state) {
var i;
var reset = true;
for (i = 0; i < this.tree.child.length; ++i) {
if (this.tree.child[i].state[0] === state[0] && this.tree.child[i].state[1] === state[1]) {
this.tree = this.tree.child[i];
reset = false;
break;
}
}
if (reset) {
return false;
}
reset = true;
for (i = 0; i < this.tree.child.length; ++i) {
if (this.tree.child[i].state[2] === state[2] && this.tree.child[i].state[3] === state[3]) {
this.tree = this.tree.child[i];
reset = false;
break;
}
}
return !reset;
};
this.reset = function( state ) {
this.tree = new Node(state, 4, true, this.map);
this.tree.addDepth(this.map);
this.tree.addDepth(this.map);
this.tree.addDepth(this.map);
this.tree.addDepth(this.map);
this.tree.addDepth(this.map);
this.tree.addDepth(this.map);
};
function nodeSorter(map) {
return function(a, b) {
if (a.treeValue > 5 && b.treeValue > 5 && map.get(a.state[0], a.state[1]) > map.get(b.state[0], b.state[1])) {
return -1;
}
if (a.treeValue > b.treeValue) {
return -1;
}
if (a.treeValue < b.treeValue) {
return 1;
}
return 1;
};
}
this.choose = function() {
this.tree.child.sort(nodeSorter(this.map));
if (this.tree.child[0].treeValue < 3) {
this.tree.getBest(this.map, false);
}
this.dir = this.tree.child[0].move;
};
this.getAction = function ( state )
{
this.map.set(state[0], state[1], 0);
if (this.last[0] === 0 || this.setWall(state) || !this.moveTree(state)) {
this.reset(state);
}
else
{
this.tree.addDepth(this.map);
this.tree.addDepth(this.map);
}
this.last = state;
this.tree.getBest(this.map);
this.choose();
if (this.tree.treeValue < 4) {
console.error(this.tree);
}
else {
console.log(this.tree);
}
console.log(this.dir);
return ( this.dir );
};
this.endRun = function()
{
};
}