// Cloned by Musthaq Ahmed on 8 Nov 2022 from Mind "A* Chase Mind" by Chen Zhenshuo
// Please leave this clone trail here.
/**
* =======================================================================================================================
*
* The framework setup.
*
* =======================================================================================================================
*/
AB.mind.newRun = function () {
};
let initRoles = false;
AB.mind.getAction = function (world) {
let { agent, enemy } = world.roles;
if (!initRoles) {
roles.agent = new Agent(pos.agent, world, CONFIG.heuristic);
roles.enemy = new Enemy(pos.enemy, world);
agent = roles.agent;
enemy = roles.enemy;
initRoles = true;
}
// Enemy does not move on this step.
if (AB.step % CONFIG.roundCount !== 0) {
return {
agent: agent.getAction(world),
enemy: MOVE.stay
};
} else {
return {
agent: agent.getAction(world),
enemy: enemy.getAction(world)
};
}
};
/**
* =======================================================================================================================
*
* Roles
*
* =======================================================================================================================
*/
const ACTION_COUNT = 5;
const MOVE = {
stay: 0,
left: 1,
right: 2,
up: 3,
down: 4
};
class Role {
//! The current position.
_pos = { x: null, y: null };
//! Whether the role is trapped in a mud block.
_trapped = false;
//! Whether the previous move failed because of a wall.
_blocked = false;
//! The previous destination the role tries to move to.
_prevTryPos = null;
//! The move strategy chain.
_strategies = [new Random()];
//! The default action selector.
_selector = defaultSeletor(1);
constructor(pos, world) {
this._pos = pos;
}
/**
* Get the role's position.
*/
get pos() {
return this._pos;
}
/**
* Get the terrain of the role's position.
*/
get terrain() {
return terrain(this._pos);
}
/**
* Check whether the role is stuck.
*/
stuck(world) {
return occupied(dest(this._pos, MOVE.left), world) !== OCCUPIED.false
&& occupied(dest(this._pos, MOVE.right), world) !== OCCUPIED.false
&& occupied(dest(this._pos, MOVE.up), world) !== OCCUPIED.false
&& occupied(dest(this._pos, MOVE.down), world) !== OCCUPIED.false;
}
/**
* Move once.
*/
move(world) {
const action = this.getAction(world);
const newPos = dest(this._pos, action);
this.#tryToMove(newPos, world);
}
/**
* Get the action with the highest level of recommendation.
*
* @note Subclasses can implement their own choosing logic.
*/
getAction(world) {
let lvlMatrix = new Array(this._strategies.length);
for (let i = 0; i < this._strategies.length; i++) {
lvlMatrix[i] = this._strategies[i].getActionLvls(world);
}
return this._selector.highest(lvlMatrix);
}
/**
* Try to move to the destination.
*/
#tryToMove(pos, world) {
this._prevTryPos = pos;
this._blocked = false;
if (this.pos.x !== pos.x || this.pos.y !== pos.y) {
if (this._trapped) {
// Lost this turn because of being trapped.
this._trapped = false;
return;
}
const whyOccupied = occupied(pos, world);
if (whyOccupied !== OCCUPIED.false) {
// Blocked by a wall.
this._blocked = whyOccupied === OCCUPIED.wall;
return;
}
this._pos = pos;
// Trapped in mud.
this._trapped = terrain(pos) === TERRAIN.mud;
}
}
}
/**
* Get the destination after a move.
*/
function dest({ x, y }, action) {
switch (action) {
case MOVE.left: {
return { x: x - 1, y };
}
case MOVE.right: {
return { x: x + 1, y };
}
case MOVE.up: {
return { x, y: y + 1 };
}
case MOVE.down: {
return { x, y: y - 1 };
}
default: {
return { x, y };
}
}
}
/**
* Get the next action from the source to the destination.
*/
function actionTo(src, dest) {
const checkX = (src, dest) => {
if (src < dest) {
return MOVE.right;
} else if (src > dest) {
return MOVE.left;
} else {
return MOVE.stay;
}
};
const checkY = (src, dest) => {
if (src < dest) {
return MOVE.up;
} else if (src > dest) {
return MOVE.down;
} else {
return MOVE.stay;
}
};
const actX = checkX(src.x, dest.x);
const actY = checkY(src.y, dest.y);
if (actX === MOVE.stay) {
return actY;
} else if (actY === MOVE.stay) {
return actX;
} else {
return randomPick(actX, actY);
}
}
/**
* A role that can record the terrain of each position it moves to.
*/
class RoleWithTerrainMemo extends Role {
_terrains;
constructor(pos, world) {
super(pos, world);
this._terrains = new TerrainMemo(this, { height: CONFIG.gridSize, width: CONFIG.gridSize });
}
/**
* Update terrains before getting an action.
*/
getAction(world) {
this.#updateTerrain();
return super.getAction(world);
}
/**
* Get the terrain record.
*/
terrain(pos) {
if (this._terrains.valid(pos)) {
return this._terrains.get(pos);
} else {
return undefined;
}
}
/**
* Update the terrain record.
*/
#updateTerrain() {
const memo = this._terrains;
// Update the current position.
memo.set(this.pos, this.terrain);
if (this._blocked) {
// If blocked, then the previous destination is wall.
memo.set(this._prevTryPos, TERRAIN.wall);
}
}
}
class Agent extends RoleWithTerrainMemo {
#moveAway;
constructor(pos, world) {
super(pos, world);
this.#moveAway = new MoveAway(this, { height: CONFIG.gridSize, width: CONFIG.gridSize });
this._strategies = [new Random(), this.#moveAway, this._terrains];
this._selector = new ActionSelector([1, 0, 0])
}
getAction(world) {
this._selector.weights = [1, Math.random() * 0.4, Math.random() * 0.4];
return super.getAction(world);
}
}
class Enemy extends RoleWithTerrainMemo {
#aStar;
#moveClose;
constructor(pos, world, heuristic) {
super(pos, world);
this.#aStar = new AStar(this, this._terrains, heuristic);
this.#moveClose = new MoveClose(this, { height: CONFIG.gridSize, width: CONFIG.gridSize });
this._strategies = [new Random(), this.#aStar, this.#moveClose, this._terrains];
this._selector = new ActionSelector([0.1, 1, 0.2, 0.1])
}
/**
* Get the current A* path to the agent.
*/
get path() {
let path = this.#aStar.path;
if (!path) {
return null;
}
// Delete the previous beginning position.
const next = path[path.length - 2];
if (next.x === this.pos.x && next.y === this.pos.y) {
path.splice(path.length - 1, 1);
}
return path;
}
}
/**
* =======================================================================================================================
*
* Strategies.
*
* =======================================================================================================================
*/
const MAX_ACT_LVL = 10;
/**
* The interface of move strategy.
*/
class Strategy {
/**
* Get an array containing the level of recommendation for every action.
*
* @pure
* @note Subclasses should implement their move logic.
* @warning The level of recommendation is between 0 and 10.
*/
getActionLvls(world) {
console.assert(false);
}
}
function emptyActionLvls() {
return new Array(ACTION_COUNT).fill(0);
}
/**
* Get the action with the highest level of recommendation according to the specific weights.
*/
class ActionSelector {
#weights;
constructor(weights) {
this.#weights = weights;
}
set weights(val) {
this.#weights = val;
}
highest(lvlMatrix) {
let sum = emptyActionLvls();
for (let w = 0; w < this.#weights.length; w++) {
mergeActionLvls(sum, lvlMatrix[w], this.#weights[w]);
}
// If two or more actions have the same level, get a random one.
let best = 0;
let possible = [best];
for (let i = 0; i < ACTION_COUNT; i++) {
if (sum[i] === sum[best]) {
possible.push(i);
} else if (sum[i] > sum[best]) {
possible = [i];
best = i;
}
}
return possible[randomInt(0, possible.length - 1)];
}
}
/**
* Get a default action seletor with all weights are 1.
*/
function defaultSeletor(weightCount) {
const weights = new Array(weightCount).fill(1);
return new ActionSelector(weights);
}
/**
* Merge two action recommendation arrays.
*/
function mergeActionLvls(sum, newlvls, weight) {
for (let i = 0; i < ACTION_COUNT; i++) {
sum[i] += newlvls[i] * weight;
}
}
/**
* Get an action randomly.
*/
class Random {
getActionLvls(world) {
let lvls = new Array(ACTION_COUNT).fill(MAX_ACT_LVL);
lvls[MOVE.stay] = 0;
return lvls;
}
}
/**
* Get an action to move away to the target.
*/
class MoveAway {
#self;
#target = null;
constructor(role) {
this.#self = role;
}
getActionLvls(world) {
if (!this.#target) {
this.#target = opponent(this.#self, world);
}
let lvls = emptyActionLvls();
const target = this.#target.pos;
const { x, y } = this.#self.pos;
if (target.x <= x) {
lvls[MOVE.right] = MAX_ACT_LVL;
} else if (target.x >= x) {
lvls[MOVE.left] = MAX_ACT_LVL;
}
if (target.y <= y) {
lvls[MOVE.up] = MAX_ACT_LVL;
} else if (target.y >= y) {
lvls[MOVE.down] = MAX_ACT_LVL;
}
return lvls;
}
}
/**
* Get an action to move closer to the target.
*/
class MoveClose {
#self;
#target = null;
constructor(role) {
this.#self = role;
}
getActionLvls(world) {
if (!this.#target) {
this.#target = opponent(this.#self, world);
}
let lvls = emptyActionLvls();
const target = this.#target.pos;
const { x, y } = this.#self.pos;
if (target.x < x) {
lvls[MOVE.left] = MAX_ACT_LVL;
} else if (target.x > x) {
lvls[MOVE.right] = MAX_ACT_LVL;
}
if (target.y < y) {
lvls[MOVE.down] = MAX_ACT_LVL;
} else if (target.y > y) {
lvls[MOVE.up] = MAX_ACT_LVL;
}
return lvls;
}
}
class TerrainMemo {
#self;
#memo;
#size;
static #RANGE = 5;
constructor(role, { width, height }) {
this.#size = { width, height };
this.#self = role;
// The tarrains of all positions are unknown.
this.#memo = new Array(width);
for (let x = 0; x < width; x++) {
this.#memo[x] = new Array(height);
for (let y = 0; y < height; y++) {
this.#memo[x][y] = TERRAIN.unknown
}
}
}
getActionLvls(world) {
let lvls = emptyActionLvls();
for (let i = 0; i < ACTION_COUNT; i++) {
const newPos = dest(this.#self.pos, i);
if (this.valid(newPos) && !this.wall(newPos)) {
lvls[i] = MAX_ACT_LVL - this.#wallDensity(i) * 0.5;
}
}
lvls[MOVE.stay] = 0;
return lvls;
}
set({ x, y }, type) {
this.#memo[x][y] = type;
}
get({ x, y }) {
return this.#memo[x][y];
}
wall({ x, y }) {
return this.#memo[x][y] === TERRAIN.wall;
}
valid({ x, y }) {
const validRow = 0 <= y && y < this.#size.height;
const validCol = 0 <= x && x < this.#size.width;
return validRow && validCol;
}
get width() {
return this.#size.width;
}
get height() {
return this.#size.height;
}
get size() {
return this.#size;
}
#wallDensity(action) {
const range = TerrainMemo.#RANGE;
let x = 0, y = 0;
let endX = 0, endY = 0;
const pos = this.#self.pos;
switch (action) {
case MOVE.left: {
x = pos.x - range > 0 ? pos.x - range : 0;
endX = pos.x;
y = pos.y - range > 0 ? pos.y - range : 0;
endY = pos.y + range < this.height ? pos.y + range : this.height;
break;
}
case MOVE.right: {
x = pos.x;
endX = pos.x + range < this.width ? pos.x + range : this.width;
y = pos.y - range > 0 ? pos.y - range : 0;
endY = pos.y + range < this.height ? pos.y + range : this.height;
break;
}
case MOVE.up: {
x = pos.x - range > 0 ? pos.x - range : 0;
endX = pos.x + range < this.width ? pos.x + range : this.width;
y = pos.y;
endY = pos.y + range < this.height ? pos.y + range : this.height;
break;
}
case MOVE.down: {
x = pos.x - range > 0 ? pos.x - range : 0;
endX = pos.x + range < this.width ? pos.x + range : this.width;
y = pos.y - range > 0 ? pos.y - range : 0;
endY = pos.y;
break;
}
default: {
return MAX_ACT_LVL;
}
}
let total = 1, wall = 1;
if (x === 0 || endX === this.width
|| y === 0 || endY === this.height) {
total += range * 2;
wall += range * 2;
}
for (; x !== endX; x++) {
for (; y !== endY; y++) {
total++;
if (this.wall({ x, y })) {
wall++;
}
}
}
return Math.round((wall / total) * MAX_ACT_LVL);
}
}
/**
* =======================================================================================================================
*
* A*
*
* =======================================================================================================================
*/
class Spot {
#pos;
#neighbors = [];
#terrains;
previous = null;
#g = 0;
#h = 0;
#f = 0;
constructor(pos, terrains) {
this.#pos = pos;
this.#terrains = terrains;
}
addNeighbors(grid) {
const memo = this.#terrains;
const neighbors = this.#neighbors;
const { x, y } = this.#pos;
if (memo.valid({ x: x, y: y - 1 })) {
neighbors.push(grid[x][y - 1]);
}
if (memo.valid({ x: x, y: y + 1 })) {
neighbors.push(grid[x][y + 1]);
}
if (memo.valid({ x: x - 1, y: y })) {
neighbors.push(grid[x - 1][y]);
}
if (memo.valid({ x: x + 1, y: y })) {
neighbors.push(grid[x + 1][y]);
}
}
get neighbors() {
const memo = this.#terrains;
const neighbors = this.#neighbors;
// Delete the neighbor which has been known as a wall.
for (let i = 0; i < neighbors.length; i++) {
if (memo.wall(neighbors[i])) {
neighbors.splice(i, 1);
i--;
}
}
return neighbors;
}
get pos() {
return this.#pos;
}
get y() {
return this.#pos.y;
}
get x() {
return this.#pos.x;
}
get g() {
return this.#g;
}
set g(val) {
this.#g = val;
this.#f = this.g + this.h;
}
get h() {
return this.#h;
}
set h(val) {
this.#h = val;
this.#f = this.g + this.h;
}
get f() {
return this.#f;
}
clear() {
this.#g = 0;
this.#h = 0;
this.#f = 0;
this.previous = null;
}
}
/**
* A* pathfinding.
*/
class AStar {
#self;
#target;
#heuristic = (src, dest) => 0;
#terrains;
#pathGrid;
#path;
static #line;
static #points;
constructor(role, terrains, heuristic) {
this.#self = role;
if (heuristic) {
this.#heuristic = heuristic;
}
this.#terrains = terrains;
this.#initPathGrid(terrains);
const material = new THREE.LineBasicMaterial( { color: 0xff0000 } );
const geometry = new THREE.BufferGeometry();
AStar.#points = new Float32Array(CONFIG.gridSize * CONFIG.gridSize * 3 )
geometry.addAttribute( 'position', new THREE.BufferAttribute(AStar.#points, 3));
geometry.setDrawRange( 0, 0 );
AStar.#line = new THREE.Line( geometry, material );
ABWorld.scene.add( AStar.#line );
}
getActionLvls(world) {
if (!this.#target) {
this.#target = opponent(this.#self, world);
}
let lvls = emptyActionLvls();
this.#clearPathGrid();
const src = this.#self.pos;
const dest = this.#target.pos;
let openSet = [];
let closedSet = [];
openSet.push(this.#pathGrid[src.x][src.y]);
while (openSet.length > 0) {
const pos = AStar.#nextPos(openSet);
if (AStar.#isEnd(pos, dest)) {
// Find a valid path.
this.#path = AStar.#trackPath(pos);
const next = this.#path[this.#path.length - 2];
lvls[actionTo(src, next)] = MAX_ACT_LVL;
break;
}
closedSet.push(pos);
// The neighbors having unknown terrains will be regarded as blank blocks.
const neighbors = pos.neighbors;
for (let i = 0; i < neighbors.length; i++) {
const neighbor = neighbors[i];
if (!closedSet.includes(neighbor)) {
// Consider the move cost of the neighbor when calculating `g`.
const newG = pos.g + cost(this.#terrains.get(neighbor.pos));
+ this.#heuristic(neighbor, pos);
let newPath = false;
if (openSet.includes(neighbor)) {
if (newG < neighbor.g) {
neighbor.g = newG;
newPath = true;
}
} else {
neighbor.g = newG;
newPath = true;
openSet.push(neighbor);
}
if (newPath) {
neighbor.h = this.#heuristic(neighbor, dest);
neighbor.previous = pos;
}
}
}
}
return lvls;
}
get path() {
return this.#path;
}
/**
* Create a new terrain record.
*/
#initPathGrid({ width, height }) {
// The tarrains of all positions are unknown.
this.#pathGrid = new Array(width);
for (let x = 0; x < width; x++) {
this.#pathGrid[x] = new Array(height);
for (let y = 0; y < height; y++) {
this.#pathGrid[x][y] = new Spot({ x, y }, this.#terrains);
}
}
for (let x = 0; x < width; x++) {
for (let y = 0; y < height; y++) {
this.#pathGrid[x][y].addNeighbors(this.#pathGrid);
}
}
}
/**
* Clear the previous search data.
*/
#clearPathGrid() {
this.#path = null;
for (let x = 0; x < this.#pathGrid.length; x++) {
for (let y = 0; y < this.#pathGrid[x].length; y++) {
if (this.#pathGrid[x][y]) {
this.#pathGrid[x][y].clear();
}
}
}
}
static #nextPos(openSet) {
let next = 0;
for (let i = 1; i < openSet.length; i++) {
if (openSet[i].f < openSet[next].f) {
next = i;
}
}
const pos = openSet[next];
openSet.splice(next, 1);
return pos;
}
/**
* Check if a position is the destination.
*/
static #isEnd(pos, dest) {
const { x: endX, y: endY } = dest;
return pos.x === endX && pos.y === endY;
}
/**
* Get the entire path ending with a position.
*/
static #trackPath(spot) {
const points = AStar.#line.geometry.attributes.position.array;
let i = 0;
let count = 0;
let path = [];
let curr = spot;
path.push(curr);
while (curr.previous) {
path.push(curr.previous);
points[i++] = (curr.previous.x * CONFIG.squareSize) - (maxPos / 2);
points[i++] = 0
points[i++] = (curr.previous.y * CONFIG.squareSize) - (maxPos / 2);
curr = curr.previous;
count++;
}
AStar.#line.geometry.attributes.position.needsUpdate = true;
AStar.#line.geometry.setDrawRange(0, count);
ABWorld.render();
return path;
}
}