pathfinder_my.js

const PLAIN_COST = 3;
const SWAMP_COST = 6;
const WALL_COST = 30 * PLAIN_COST;
const EXISTING_PATH_COST = PLAIN_COST - 2;




const top = 0;
const parent = i => ((i + 1) >>> 1) - 1;
const left = i => (i << 1) + 1;
const right = i => (i + 1) << 1;

class PriorityQueue {
	constructor(comparator = (a, b) => a > b) {
		this._heap = [];
		this._comparator = comparator;
	}
	size() {
		return this._heap.length;
	}
	isEmpty() {
		return this.size() == 0;
	}
	peek() {
		return this._heap[top];
	}
	push(value) {
		this._heap.push(value);
		this._siftUp();
	}
	pop() {
		const poppedValue = this.peek();
		const bottom = this.size() - 1;
		if (bottom > top) {
			this._swap(top, bottom);
		}
		this._heap.pop();
		this._siftDown();
		return poppedValue;
	}
	replace(value) {
		const replacedValue = this.peek();
		this._heap[top] = value;
		this._siftDown();
		return replacedValue;
	}
	_greater(i, j) {
		return this._comparator(this._heap[i], this._heap[j]);
	}
	_swap(i, j) {
		[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
	}
	_siftUp() {
		let node = this.size() - 1;
		while (node > top && this._greater(node, parent(node))) {
			this._swap(node, parent(node));
			node = parent(node);
		}
	}
	_siftDown() {
		let node = top;
		while (
			(left(node) < this.size() && this._greater(left(node), node)) ||
			(right(node) < this.size() && this._greater(right(node), node))
		) {
			let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node);
			this._swap(node, maxChild);
			node = maxChild;
		}
	}
};


function render_tmp(room, calcs, pos, xx) {
	if (xx > 100) {
		console.log('xx');
		return;
	}
	let x = pos.x;
	let y = pos.y;
	let cost = calcs[x][y];
	let mincost = cost + 9999;
	let go_dx, go_dy;

	room.visual.circle(pos, { radius: 0.07, fill: '#ff0044', opacity: 1 });

	for (let dy = -1; dy <= 1; ++dy) {
		for (let dx = -1; dx <= 1; ++dx) {
			let newx = x + dx;
			let newy = y + dy;
			if ((dx == 0 && dy == 0) || (newx < 0) || (newy < 0) || (newx > 49) || (newy > 49)) continue;
			let newcost = calcs[newx][newy].cost;
			if (newcost == 1) return; // koniec
			if (newcost == 0) continue;
			if (newcost < cost) continue;
			if (newcost > mincost) continue;
			mincost = newcost;
			go_dx = dx;
			go_dy = dy;
		}
	}

	if (go_dx === undefined) return;

	render_tmp(room, calcs, { x: x + go_dx, y: y + go_dy }, xx + 1);
};

function render_map(room, map) {
	for (let x = 0; x < 50; ++x) {
		for (let y = 0; y < 50; ++y) {
			room.visual.text(map[x][y], x, y, { font: 0.3 });
		}
	}
}
function render_costs(room, calcs) {
	for (let x = 0; x < 50; ++x) {
		for (let y = 0; y < 50; ++y) {
			let cost = Math.floor(calcs[x][y].cost);
			if (!cost) continue;
			room.visual.text(cost, x, y, { font: 0.3 });
		}
	}
};
function render_steps(room, calcs) {
	for (let x = 0; x < 50; ++x) {
		for (let y = 0; y < 50; ++y) {
			let cost = Math.floor(calcs[x][y].steps);
			room.visual.text(cost, x, y, { font: 0.3 });
		}
	}
};

/*
function xx_findShortest(go_arr, carr) {
	// 1. find the "active" c
	carr.filter((c) => (c.current.x;
	return go_arr[0];
};
*/

function xxx_func(carr, from_stack) {
	let m = [];
	for (let i = 0; i < 50; ++i) {
		let a = [];
		for (let k = 0; k < 50; ++k) {
			a[k] = 0;
		}
		m.push(a);
	}

	///
	if (from_stack) {

	}
	////

	let stack = [];

	for (let i = 0; i < 1000; ++i) {
		carr.forEach((c) => {
			if (c.finished) return;

			let x = c.current.x;
			let y = c.current.y;
			let cost = c.calcs[x][y].cost;
			let mincost = cost + 9999;
			for (let dy = -1; dy <= 1; ++dy) {
				for (let dx = -1; dx <= 1; ++dx) {
					let newx = x + dx, newy = y + dy;
					let newcost = c.calcs[newx][newy].cost;
					if (newcost == 1) { c.finished = true; return; }
					if (newcost == 0) continue;
					//if (newcost >= mincost) continue;
					if (newcost > mincost && Math.abs(newcost - mincost) > 0.1) continue;
					mincost = newcost;
				}
			}

			c.mincost = mincost;
			for (let dy = -1; dy <= 1; ++dy) {
				for (let dx = -1; dx <= 1; ++dx) {
					let newx = x + dx, newy = y + dy;
					let newcost = c.calcs[newx][newy].cost;

					if (Math.abs(newcost - mincost) > 0.1) continue;
					m[newx][newy]++;
				}
			}
		});

		carr.forEach((c) => {
			if (c.finished) return;

			let x = c.current.x, y = c.current.y;
			let mincost = c.mincost;
			let max_m = 0;
			//let gox, goy;
			for (let dy = -1; dy <= 1; ++dy) {
				for (let dx = -1; dx <= 1; ++dx) {
					let newx = x + dx, newy = y + dy;
					let newcost = c.calcs[newx][newy].cost;
					//if (newcost != mincost) continue;
					if (Math.abs(newcost - mincost) > 0.1) continue;

					if (m[newx][newy] > max_m) {
						max_m = m[newx][newy];
						//gox = newx;
						//goy = newy;
					}
				}
			}
			/**/
			let go_arr = [];
			for (let dy = -1; dy <= 1; ++dy) {
				for (let dx = -1; dx <= 1; ++dx) {
					let newx = x + dx, newy = y + dy;
					let newcost = c.calcs[newx][newy].cost;
					//if (newcost != mincost) continue;
					if (Math.abs(newcost - mincost) > 0.1) continue;

					if (m[newx][newy] == max_m) {
						go_arr.push({ gox: newx, goy: newy });
					}
				}
			}
			let gox, goy;
			if (go_arr.length > 1) {
				stack.push({
					carr: carr.map(c => ({
						mincost: c.mincost,
						current: { x: c.current.x, y: c.current.y },
						go_arr
					}))
				});
				let ix = Math.floor(Math.random() * (go_arr.length ));
				gox = go_arr[ix].gox;
			    goy = go_arr[ix].goy;
			}else{
			gox = go_arr[0].gox;
			goy = go_arr[0].goy;
			}
			/***/

			c.current.x = gox;
			c.current.y = goy;

			c.path.push({ x: gox, y: goy });
		});

		if (carr.every(c => c.finished)) { break; }

		if (i > 990) {
			console.log(":("); break;
		}
	}
}

function xxx(room, carr, start) {
	carr.forEach((c) => {
		c.current = { x: start.x, y: start.y };
	});

	xxx_func(carr);
	

	for (let x = 0; x < 50; ++x) {
		for (let y = 0; y < 50; ++y) {
			//room.visual.text(m[x][y], x, y+0.3, { font: 0.3 });
		}
	}
}

function pathfinding_new(room) {
	let terrain = room.getTerrain();
	let map = [];
	for (let i = 0; i < 50; ++i)map.push([]);

	let start = Game.spawns.Spawn1.pos;
	let destinations = room.find(FIND_SOURCES);

	for (let x = 0; x < 50; ++x) {
		for (let y = 0; y < 50; ++y) {
			switch (terrain.get(x, y)) {
				case TERRAIN_MASK_SWAMP:
					map[x][y] = CONSTRUCTION_COST_ROAD_SWAMP_RATIO * 0.8;
					break;
				case TERRAIN_MASK_WALL:
					map[x][y] = CONSTRUCTION_COST_ROAD_WALL_RATIO * 0.8;
					break;
				default:
					map[x][y] = 1;
					break;
			}
		}
	}

	let carr = [];

	destinations.forEach((dest, indx) => {
	//let dest = destinations[0]; 
		let pos = dest.pos;
		let calcs = [];
		for (let i = 0; i < 50; ++i) {
			let arr = [];
			calcs.push(arr);
			for (let k = 0; k < 50; ++k) {
				arr[k] = { cost: 0, x: i, y: k, steps: 0 };
			}
		}
		const queue = new PriorityQueue((a, b) => a.cost < b.cost );
		calcs[pos.x][pos.y].cost = 1;
		queue.push(calcs[pos.x][pos.y]);
		let __d = 0;
		let end = false;
		while (!end && !queue.isEmpty()) {
			let q = queue.pop();
			let x = q.x;
			let y = q.y;
			let cost = q.cost;
			for (let dy = -1; dy <= 1; ++dy) {
				for (let dx = -1; dx <= 1; ++dx) {
					let newx = x + dx;
					let newy = y + dy;
					if ((dx == 0 && dy == 0) || (newx < 1) || (newy < 1) || (newx > 48) || (newy > 48)) continue;
					let newcost = cost + map[newx][newy];
					if (dx != 0 && dy != 0) newcost += 0.0001;
					let _c = calcs[newx][newy];
					if (_c.cost != 0 && _c.cost <= newcost) continue;

					//if (newx == 29 && newy == 23) console.log("29 23: " + newcost);
					_c.cost = newcost;
					_c.steps++;

					if (newx == start.x && newy == start.y) { end = true; break; }
					queue.push(_c);
				}
			}
			++__d;
			if (__d > 10000) { console.log('...break'); break; }
			//queue.sort((a, b)=> a.cost - b.cost);
		}

		//render_tmp(room, calcs, start, 0);
		//if(indx==2)render_costs(room, calcs);
		//render_steps(room, calcs);
		//render_map(room, map);
		carr.push({ calcs, current: 0, finished: false, path: [], ignored: 3, index: indx });
	 });

	xxx(room, carr, start);


	let _count = {};
	let length = 0;
	carr.forEach(c => {
		let path = c.path;
		path.forEach(pos => {
			if (_count[pos.x + 'x' + pos.y]) return;
			room.visual.circle(pos, { radius: 0.2, fill: '#00ff00', opacity: 0.3 });
			length++;
			_count[pos.x + 'x' + pos.y] = 1;
		});
	});

	console.log('new = ' + length);
}



module.exports.loop = function () {
	let room = Game.rooms.sim;
	
    pathfinding_new(room);
}