queue.js

//let UTILS = require('./utils');
//let UTILS_ROOM = require('./utils.room');


let UTILS_ROOM = {};
UTILS_ROOM.getSpawns = function (room) {
	//return getCached(room.name, "spawn", () =>
	return	room.find(FIND_MY_STRUCTURES, {
			filter: { structureType: STRUCTURE_SPAWN }
		})
	//);
};

let UTILS = {};

UTILS.generateName = function () {
	if (!Memory._name) Memory._name = 0;
	++Memory._name;
	return 'C' + Memory._name;
};

UTILS.hsv2rgb = function (h, s, v) {
	// adapted from http://schinckel.net/2012/01/10/hsv-to-rgb-in-javascript/
	var rgb,
		i,
		data = [];
	if (s === 0) {
		rgb = [v, v, v];
	} else {
		h = h / 60;
		i = Math.floor(h);
		data = [v * (1 - s), v * (1 - s * (h - i)), v * (1 - s * (1 - (h - i)))];
		switch (i) {
			case 0:
				rgb = [v, data[2], data[0]];
				break;
			case 1:
				rgb = [data[1], v, data[0]];
				break;
			case 2:
				rgb = [data[0], v, data[2]];
				break;
			case 3:
				rgb = [data[0], data[1], v];
				break;
			case 4:
				rgb = [data[2], data[0], v];
				break;
			default:
				rgb = [v, data[0], data[1]];
				break;
		}
	}
	return (
		"#" +
		rgb
			.map(function (x) {
				return ("0" + Math.round(x * 255).toString(16)).slice(-2);
			})
			.join("")
	);
};





let SPAWN_QUEUE = {};

const MAX_WINDOW_TIME = 750;
const WINDOW_BUFFER_TIME = 100;


SPAWN_QUEUE.tick = function (room) {
	let spawns = UTILS_ROOM.getSpawns(room);
	if (!spawns.length) return;

	checkFlags(room);

	SPAWN_QUEUE.updateQueueWindow(room);

	SPAWN_QUEUE.spawn(room);

	if (Memory.queue_render == room.name) {
		renderQueue(room, 2, 2);
	}
};


function checkFlags(room) {
	if (Memory.queue_rebuild == room.name) {
		SPAWN_QUEUE.rebuild(room);
		delete Memory.queue_rebuild;
	}
};

function init(room) {
	room.memory.queue = {};
	let spawn_memory = room.memory.queue;

	spawn_memory.entries = [];
	spawn_memory.last_id = 0;
	spawn_memory.spawner_last_updated = Game.time - 1;

	SPAWN_QUEUE.rebuild(room);
};

SPAWN_QUEUE.add = function (room, body, params) {
	let { finish_at_time, interval, memory } = params;

	if (!room.memory.queue) init(room);
	let spawn_memory = room.memory.queue;

	let entry = {
		id:				0,
		body,
		interval,
		finish_at_time:	finish_at_time,
		last_tick_end:	0,
		memory:			memory,
	};
	
	entry.id = spawn_memory.last_id+1;

	let res = fitInQueue(entry, entry.finish_at_time, spawn_memory, 'shift_to_fit');
	if (res == 0) {
		spawn_memory.entries.push(entry);
		spawn_memory.last_id++;
	}

	return { res, id: entry.id };
};


SPAWN_QUEUE.remove = function (room, id) {
	let spawn_memory = room.memory.queue;
	spawn_memory.queues.forEach(queue => {
		for (let it = queue.length - 1; it >= 0; --it) {
			let q = queue[it];
			if (id==q.id) {
				queue.splice(it, 1);
			}
		}
	});
	
	let it = spawn_memory.entries.findIndex(e => e.id == id);
	if (it >= 0) spawn_memory.entries.splice(it, 1);
};

SPAWN_QUEUE.removeAll = function (room, ids) {
	let spawn_memory = room.memory.queue;

	spawn_memory.queues.forEach(queue => {
		for (let it = queue.length - 1; it >= 0; --it) {
			let q = queue[it];
			if (ids.includes(q.id)) {
				queue.splice(it, 1);
			}
		}
	});

	let least_last_tick_end;
	let entries = spawn_memory.entries;
	for (let it = entries.length - 1; it >= 0; --it) {
		let e = entries[it];
		if (ids.includes(e.id)) {
			if (least_last_tick_end === undefined || e.last_tick_end < least_last_tick_end)
				least_last_tick_end = e.last_tick_end;
			entries.splice(it, 1);
		}
	}
	return least_last_tick_end || 0;
};

SPAWN_QUEUE.updateQueueWindow = function (room) {
	if (!room.memory.queue) init(room);
	let spawn_memory = room.memory.queue;

	let spawns = UTILS_ROOM.getSpawns(room);
	if (spawns.length != spawn_memory.queues.length) {
		SPAWN_QUEUE.rebuild(room);
		return;
	}

	let currentTime = Game.time;
	let diff = currentTime - spawn_memory.window_tick_start;

	if (diff < 0 || diff > WINDOW_BUFFER_TIME + 10) {
		console.log('queue rebuild, diff = ' + diff);
		SPAWN_QUEUE.rebuild(room);
		return;
	}
	if (diff < WINDOW_BUFFER_TIME) return;

	updateQueueWindow_impl(spawn_memory, currentTime);
}


function updateQueueWindow_impl(spawn_memory, currentTime) {
	spawn_memory.queues.forEach((queue, i)=> {
		let it = 0;
		for (; it < queue.length; ++it)
			if (queue[it].end >= currentTime) break;

		queue.splice(0, it);
	});


	spawn_memory.window_tick_start = currentTime;

	spawn_memory.entries.forEach( (entry, i)=> {
		let finish_at_time = (entry.last_tick_end ? entry.last_tick_end + entry.interval : entry.finish_at_time);
		if (!finish_at_time) throw `!finish_at_time  ${entry.last_tick_end} ${entry.interval} ${entry.finish_at_time}`;

		let res = fitInQueue(entry, finish_at_time, spawn_memory);
	});
};

SPAWN_QUEUE.rebuild = function (room) {
	if (!room.memory.queue) init(room);
	let spawn_memory = room.memory.queue;

	spawn_memory.queues = [];

	let spawns = UTILS_ROOM.getSpawns(room);
	for (let s of spawns) spawn_memory.queues.push([]);

	spawn_memory.window_tick_start = Game.time;

	console.log('rebuild');
	spawn_memory.entries.forEach((entry) => {
		fitInQueue(entry, entry.finish_at_time, spawn_memory);
	});
};

function fitInQueue(entry, finish_at_time, spawn_memory, shift_to_fit) {
	let interval = +entry.interval;
	finish_at_time = +finish_at_time;
	let job_duration = 3 * entry.body.length;
	
	let max_next_tick = spawn_memory.window_tick_start + MAX_WINDOW_TIME + WINDOW_BUFFER_TIME;
	let loop_offset = 0;

	const spawnsN = spawn_memory.queues.length;

	const spawner_last_updated = spawn_memory.spawner_last_updated;

	let cache_it = new Array(spawnsN).fill(0);
	let next_tick_end = 0;
	let watchDog = 0;
	while (true) {
		let next_tick_start = finish_at_time - job_duration + loop_offset;

		if (watchDog++ > 100) throw 'watchDog: next ' + next_tick_start + ', max ' + max_next_tick + ', at ' + finish_at_time+', off '+loop_offset;

		if (shift_to_fit && next_tick_start <= spawner_last_updated) {
			next_tick_start = spawner_last_updated + 1;
			finish_at_time = next_tick_start + job_duration - loop_offset;
		}

		if (next_tick_start > spawner_last_updated) {
			if (next_tick_start > max_next_tick) break;

			next_tick_end = next_tick_start + job_duration;

			let queue_obj = {
				start: next_tick_start,
				end: next_tick_end,
				id: entry.id,
			};

			let success = false;
			for (let it = 0; it < spawnsN; ++it) {
				success = canFit_addQueue(spawn_memory, it, cache_it, queue_obj);
				if (success) break;
			}

			if (!success) {
				success = queue_resolveConflict(spawn_memory, spawnsN, cache_it, queue_obj);
				if (!success) break;

				next_tick_end = queue_obj.end;
			}

		} else {
			entry.finish_at_time += interval;
		}
		loop_offset += interval;

		if (interval == 0) {
			break; // one timer
		}
	}
	if (next_tick_end) {
		entry.last_tick_end = next_tick_end;
	}

	return 0;
};

function canFit_addQueue(spawn_memory, number, cache_it, queue_obj) {
	/* warning: queue_resolveConflict is highly dependent on this code, don't change */
	let queue = spawn_memory.queues[number];
	let it = cache_it[number]
	for (; it < queue.length; ++it) {
		let elem = queue[it];
		if (elem.start >= queue_obj.end) break;
	}
	cache_it[number] = it;
	if (it == 0) {
		// nothing preceeds, we can fit
		queue.unshift(queue_obj);
		return true;
	}

	// else: we have to fit between 2 elements, it-1 and it
	let previous = queue[it - 1];
	if (previous.end > queue_obj.start) return false;

	// we can fit
	queue.splice(it, 0, queue_obj);
	return true;
};

function queue_resolveConflict(spawn_memory, spawnsN, cache_it, queue_obj) {

	const spawner_last_updated = spawn_memory.spawner_last_updated;

	let times = [];
	for (let number = 0; number < spawnsN; ++number) {
		let queue = spawn_memory.queues[number];
		let it = cache_it[number];
		let previous = queue[it - 1];
		// we know that (previous.end > queue_obj.start)

		let time_back = queue_obj.end - previous.start;
		{
			let start_back = queue_obj.start - time_back;
			if (start_back <= spawner_last_updated) time_back = 0;
			let previous2 = it >= 2 ? queue[it - 2] : null;
			if (previous2) {
				if (previous2.end > start_back) time_back = 0;
			}
		}
		let time_forward = previous.end - queue_obj.start;
		{
			let end_forward = queue_obj.end + time_forward;
			let forward2 = queue[it];
			if (forward2) {
				if (forward2.start < end_forward) time_forward = 0;
			}
		}
		times[number] = [time_back, time_forward];
	}

	let min_time = 1500;
	let min_indx;
	let min_forward;
	for (let number = 0; number < spawnsN; ++number) {
		if (times[number][0] && times[number][0] < min_time) {
			min_time = times[number][0];
			min_indx = number;
			min_forward = 0;
		}
		if (times[number][1] && times[number][1] < min_time) {
			min_time = times[number][1];
			min_indx = number;
			min_forward = 1;
		}
	}

	if (min_time == 1500) return queue_resolveConflict_2(spawn_memory, spawnsN, cache_it, queue_obj);


	let queue = spawn_memory.queues[min_indx];
	let it = cache_it[min_indx];
	if (min_forward) {
		queue_obj.start += min_time;
		queue_obj.end += min_time;
		queue.splice(it, 0, queue_obj);
	} else {
		queue_obj.start -= min_time;
		queue_obj.end -= min_time;
		queue.splice(it-1, 0, queue_obj);
	}
	return true;
};

function queue_resolveConflict_2(spawn_memory, spawnsN, cache_it, queue_obj){

	// one spawn for now
	let number = 0;
	let queue = spawn_memory.queues[number];
	let spawn_time = queue_obj.end - queue_obj.start;

	let it = cache_it[number];
	for (; it < queue.length-1; ++it) {
		
		let elem = queue[it];
		let next = queue[it + 1];
		if (elem.end + spawn_time <= next.start) {
			break;
		}
	}

	let elem = queue[it];
	queue_obj.start = elem.end;
	queue_obj.end = queue_obj.start + spawn_time;

	queue.splice(it + 1, 0, queue_obj);

	return true;
};

SPAWN_QUEUE.spawn = function (room) {
	let spawn_memory = room.memory.queue;

	let from = spawn_memory.spawner_last_updated+1;
	let to = Game.time;

	let spawns = UTILS_ROOM.getSpawns(room);
	const spawnsN = spawn_memory.queues.length;
	let spawned = false;

	for (let number = 0; number < spawnsN; ++number) {
		let spawn = spawns[number];

		let queue = spawn_memory.queues[number];

		if (spawn.spawning) {
			pushQueueElements(queue, from, 2);
			continue;
		}

		let elem;
		let it = 0;
		let _delete = -1;
		while (true) {
			if (it >= queue.length) break;
			elem = queue[it];
			if (elem.spawned && elem.start < from) {
				_delete=it;
				++it;
			} else {
				break;
			}
		}
		
		if (elem && /*elem.start >= from*/ elem.start <= to && !elem.spawned) {
			let entry = spawn_memory.entries.find(e => e.id == elem.id);
			let body = entry.body;
			let name = entry.name || UTILS.generateName();
			let res = spawn.spawnCreep(body, name, { memory: entry.memory });
			if (res != OK) {
				pushQueueElements(queue, from, 2);
			} else {
				console.log('spawn ', JSON.stringify(entry.memory));
				elem.spawned = true;
				spawned = true;
				if (entry.interval == 0) {
					spawn_memory.entries.splice(spawn_memory.entries.indexOf(entry), 1);
				}
			}
		}

		if (_delete != -1) {
			for (let i = 0; i < _delete + 1; ++i) {
				let elem = queue[i];
				if (!elem.spawned) {
					console.log(`delete !spawned ${i}, ${_delete + 1}`)
					_delete = i - 1;
					break;
				}
			}

			queue.splice(0, _delete+1);
		}

		if (spawned) {
			// we can't allow different spawns to spawn at the same time -> can lead to bugs (getting OK from 2 spawns, but only 1 spawn working)
			break;
		}
	}
	spawn_memory.spawner_last_updated = Game.time;
};


function pushQueueElements(queue, from, diff) {
	let q_it = 0;
	let prev = queue[q_it];
	while (prev) {
		if (!prev.spawned) break;
		q_it++;
		prev = queue[q_it];
	};

	if (!prev) return;
	if (prev.start > from) return;

	prev.start += diff;
	prev.end += diff;

	for (let it = q_it+1; it < queue.length; ++it) {
		let elem = queue[it];
		if (elem.start < prev.end) {
			diff = prev.end - elem.start;
			elem.start += diff;
			elem.end += diff;
		} else {
			break;
		}
		prev = elem;
	}
};




let WIDTH = 20;
let HEIGHT = 1
let pix_per_time = WIDTH / (MAX_WINDOW_TIME + WINDOW_BUFFER_TIME);

function renderQueue(room, offset_x, offset_y) {
	let spawn_memory = room.memory.queue;
	if (!spawn_memory || !spawn_memory.queues) return;
	let visual = room.visual;

	// Frame + timeline
	let x1 = offset_x - 0.1;
	let x2 = offset_x + WIDTH + 0.1;
	let y1 = offset_y - 0.1;
	let y2 = offset_y + (spawn_memory.queues.length) * HEIGHT + 0.1;
	visual.poly([[x1, y1], [x2, y1], [x2, y2], [x1, y2], [x1, y1]], { stroke: '#AAA', lineStyle: 'dotted', strokeWidth: 0.05  });

	let timeline = Game.time - spawn_memory.window_tick_start;
	x1 = offset_x + timeline * pix_per_time;
	y1 = offset_y - 0.1;
	y2 = offset_y + (spawn_memory.queues.length) * HEIGHT + 0.1;
	visual.line(x1, y1, x1, y2, { color: '#AA3', lineStyle: 'dashed', width: 0.15, opacity: 0.7 });

	// Queues
	spawn_memory.queues.forEach( (queue, i)=> {
		renderQueue_impl(spawn_memory, visual, queue, offset_x, offset_y, i);
	});

	// Legend
	x1 = offset_x;
	y1 = offset_y + (spawn_memory.queues.length + 1) * HEIGHT;

	for (let e of spawn_memory.entries) {
		let s, v;
		let _id = e.id % 48;
		if (_id < 16) { s = 0.75; v = 0.75; }
		if (_id >= 16 && _id < 2 * 16) { s = 0.95; v = 0.95; }
		if (_id >= 2 * 16) { s = 0.5; v = 0.7; }
		let bias = _id < 16 ? 0 : (360 / 16 / 2);
		let color = UTILS.hsv2rgb((_id % 16) * (360 / 16) + bias, s, v);
		visual.poly([[x1, y1], [x1 + 1, y1], [x1 + 1, y1 + 1], [x1, y1 + 1], [x1, y1]], { fill: color, strokeWidth:0.05 });
		var counts = {};
		e.body.forEach(function (x) { counts[x] = (counts[x] || 0) + 1; });
		
		visual.text(Object.entries(counts).join('; '), x1 + 1.3, y1 + 0.75, { align: 'left', color: '#e5e5e5'});
		y1 += 1;
		if (y1 > 40) break;
	}
};


function renderQueue_impl(spawn_memory, visual, queue, offset_x, offset_y, row) {
	let diff = spawn_memory.window_tick_start;

	queue.forEach((elem, el_i) => {
		let s, v;
		let _id = elem.id % 48;
		if (_id < 16) { s = 0.75; v = 0.75; }
		if (_id >= 16 && _id<2*16) { s = 0.95; v = 0.95; }
		if (_id >= 2*16) { s = 0.5; v = 0.7; }
		let bias = _id < 16 ? 0 : (360 / 16 / 2);
		let color = UTILS.hsv2rgb((_id % 16) * (360 / 16) + bias, s, v);
		let x1 = (elem.start - diff) * pix_per_time; if (x1 < 0) x1 = 0;
		x1 += offset_x;

		let x2 = (elem.end - diff) * pix_per_time;
		if (x2 < 0) {
			return;
		}
		if (x2 > WIDTH) x2 = WIDTH;


		x2 += offset_x;
		let y1 = offset_y + row * HEIGHT;
		let y2 = y1 + HEIGHT;
		let params = { fill: color, strokeWidth: 0.05 };
		visual.poly([[x1,y1], [x2,y1], [x2,y2], [x1,y2], [x1,y1]], params);
	});
};




module.exports.loop = function () {
	if(!Memory.test){
	    Memory.queue_render = 'sim';
	    Memory.test= 1;
	} 
	
	let room = Game.rooms.sim;
	
	SPAWN_QUEUE.tick(room);
	
	if(Memory.test==1){
	    let body = [MOVE];
	    SPAWN_QUEUE.add(room, body,  {
				finish_at_time: 0,
				interval: 1500,
				memory: { role: 'test' }
			});
		Memory.test= 2;
	}
	else if(Memory.test==2){
		let body = [MOVE, WORK, CARRY];
		for(let i=0; i<5; ++i){
			SPAWN_QUEUE.add(room, body,  {
					finish_at_time: 0,
					interval: 1500,
					memory: { role: 'test2' }
				});
			
			}
		Memory.test= 3;
	}
}