Skip to content

Instantly share code, notes, and snippets.

@lethern

lethern/queue 2020 07 16.js

Last active July 16, 2020 16:35
Show Gist options
  • Save lethern/723e65363e987afbafb3b7859ca8c482 to your computer and use it in GitHub Desktop.
Save lethern/723e65363e987afbafb3b7859ca8c482 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
queue 2020 07 16.js
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_Peek = function () {
if (!Memory._name) Memory._name = 0;
Memory._name;
return 'C' + Memory._name;
};
UTILS.generateName_Next = function () {
++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_memory
- entries[]
entry: { id, body, interval, owner_id, finish_at_time, last_tick_end, memory }
- queues[1..3] of [] of
{ start, end, id, spawned }
- last_id
- spawner_last_updated
- window_tick_start
*/
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, 'full_reset');
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, 'full_reset');
};
SPAWN_QUEUE.add = function (room, body, params) {
let { finish_at_time, interval, owner_id, memory } = params;
if (!room.memory.queue) init(room);
let spawn_memory = room.memory.queue;
let entry = {
id: 0,
body,
interval,
owner_id,
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;
// console.log(`${i} deleting ${it}, ${queue[0].end} vs ${currentTime}`);
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);
// console.log('entry ' + i + ' finish ' + finish_at_time)
if (!finish_at_time) throw `!finish_at_time ${entry.last_tick_end} ${entry.interval} ${entry.finish_at_time}`;
if (entry.interval == 0 && entry.last_tick_end) {
console.log('Q interval 0: ignoring entry ' + entry.id);
return;
}
let res = fitInQueue(entry, finish_at_time, spawn_memory);
});
};
SPAWN_QUEUE.rebuild = function (room, full_reset) {
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, undefined, full_reset);
//fitInQueue(entry, 0, spawn_memory, 'shift');
});
};
function fitInQueue(entry, finish_at_time, spawn_memory, shift_to_fit, full_reset) {
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;
if (full_reset || finish_at_time < 0) finish_at_time = 0;
if (finish_at_time < 1500) {
finish_at_time = spawner_last_updated + 1 + job_duration + finish_at_time;
}else if (finish_at_time < spawner_last_updated - 1500) {
if (shift_to_fit) {
finish_at_time = spawner_last_updated + 1 + job_duration;
} else {
if (interval) {
let diff = spawner_last_updated - finish_at_time;
finish_at_time += Math.floor(diff / interval) * interval;
} else {
finish_at_time = spawner_last_updated + 1 + job_duration;
}
}
}
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 + ' = '+finish_at_time + ' - ' +job_duration +' + '+loop_offset+', max ' + max_next_tick +', offset '+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;
// console.log('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);
if (!entry) {
console.log("!Q bug for " + JSON.stringify(elem));
elem.spawned = true;
_delete = it;
} else {
let body = entry.body;
let name = UTILS.generateName_Peek();
let res = spawn.spawnCreep(body, name, { memory: entry.memory });
if (res != OK) {
//console.log('spawn error ' + UTILS.printResult(res));
pushQueueElements(queue, from, 2);
} else {
UTILS.generateName_Next();
console.log('spawn ', JSON.stringify(entry.memory));
//_delete = it;
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;
//if no fail, update timer -> ale wymagane jest delete, bo inaczej bedzie spawnic tego samego na innym queue
};
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;
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment