Code vs zombies

solution.js

"use strict";

// Policy:
// - Keep zombies away from humans
// - Cluster zombies
// - Kill all at once

/**
 * Save humans, destroy zombies!
 **/

const WIDTH = 16000;
const HEIGHT = 9000;
const ASH_KILL_RANGE = 2000;
const ASH_SPEED = 1000;
const ZOMBIE_SPEED = 400;

var globalState = {
    current: undefined,
    impacts: undefined
};


////////////////////////////////////////////////////////////////////////////
//// INPUTS
////////////////////////////////////////////////////////////////////////////

var fetchInputs = function() {
    let state = {};
    let inputs = readline().split(' ');

    // Fetch current location
    state.x = parseInt(inputs[0]);
    state.y = parseInt(inputs[1]);

    // Fetch humans
    state.humanCount = parseInt(readline());
    state.humans = [];
    state.human = {};
    for (let i = 0; i < state.humanCount; i++) {
        inputs = readline().split(' ');
        let id = parseInt(inputs[0]);
        state.human[id] = {
            id: id,
            x: parseInt(inputs[1]),
            y: parseInt(inputs[2]),
            safe: true,
            expires: false,
            zombie: false
        };
        state.humans.push(state.human[id]);
    }

    // Fetch zombies
    state.zombieCount = parseInt(readline());
    state.zombies = [];
    state.zombie = {};
    for (let i = 0; i < state.zombieCount; i++) {
        inputs = readline().split(' ');
        let id = parseInt(inputs[0]);
        state.zombie[id] = {
            id: id,
            x: parseInt(inputs[1]),
            y: parseInt(inputs[2]),
            xNext: parseInt(inputs[3]),
            yNext: parseInt(inputs[4]),
            xImpact: undefined,
            yImpact: undefined,
            human: undefined,
            impact: 0,
            impactCounter: 0
        };
        state.zombie[id].xImpact = state.zombie[id].x;
        state.zombie[id].yImpact = state.zombie[id].y;
        state.zombies.push(state.zombie[id]);
    }

    return state;
};

var move = function(x, y) {
    // Calculate coordination at border if necessary
    if (x < 0) {
        let step = (y - globalState.current.y) / (x - globalState.current.x);
        let diff = -x;
        x = 0;
        y = y + Math.floor(diff * step);
    } else if (x > WIDTH) {
        let step = (y - globalState.current.y) / (x - globalState.current.x);
        let diff = WIDTH - x;
        x = WIDTH;
        y = y + Math.floor(diff * step);
    }
    if (y < 0) {
        let step = (y - globalState.current.y) / (x - globalState.current.x);
        let diff = -y;
        x = x + Math.floor(diff / step);
        y = 0;
    } else if (y > HEIGHT) {
        let step = (y - globalState.current.y) / (x - globalState.current.x);
        let diff = HEIGHT - y;
        x = x + Math.floor(diff / step);
        y = HEIGHT;
    }

    x = Math.floor(x);
    y = Math.floor(y);

    // TODO debug stuff
    if (x < 0 || x > WIDTH || y < 0 || y > HEIGHT || x !== x || y !== y || typeof x !== "number" || typeof y !== "number") {
        throw Error("Error: Invalid coordinates\n" + Error().stack);
    }

    debug(x + ' ' + y);
    print(x + ' ' + y);
};

var debug = function(message) {
    printErr(message);
};

//////////////////////////////////////////////////////////////////////////////////////////
//// LIBRARY
//////////////////////////////////////////////////////////////////////////////////////////
var distance = function(x1, y1, x2, y2) {
    return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
};

var tangentPoints = function(px, py, cx, cy, r) {
    // Calculate diffs
    let dx = cx - px;
    let dy = cy - py;

    // Calculate distance between points
    let dd = Math.sqrt(dx * dx + dy * dy);

    // Calculate touching points on circle
    // TODO I don't know what the code below does
    let ratio = r / dd;

    if (ratio > -1) {
        ratio = -1;
    } else if (ration > 1) {
        ratio = 1;
    }

    let a = Math.asin(ratio);
    let b = Math.atan2(dy, dx);

    let t = b - a
    let ta = { x:cx + r * Math.sin(t), y:cy + r * -Math.cos(t) };

    let t = b + a
    let tb = { x:cx + r * -Math.sin(t), y: cy + r * Math.cos(t) };

    return {
        a: ta,
        b: tb
    };
}

//////////////////////////////////////////////////////////////////////////////////////////
//// HELPERS
//////////////////////////////////////////////////////////////////////////////////////////

// Returns the id of the human closest, or undefined if ash is closer or the only one left
// Optionally there can be given a time limit (human.expires is timelimit, options.cap activates cap)
// a speed (options.speed) and time offset (options.offset)
var closestHuman = function(x, y, options) {
    let closestX;
    let closestY;
    let closestDistance;
    let result = undefined;
    let i;

    options = options || {};
    options.humans = options.humans || globalState.current.humans;
    options.offset = typeof options.offset === "number" ? options.offset : 0;
    options.speed = typeof options.offset === "number" ? options.speed : ZOMBIE_SPEED;
    options.cap = options.cap;
    options.collide = options.collide;


    if (options.ash !== false) {
        i = 0;
        closestX = globalState.current.x;
        closestY = globalState.current.y;
    } else {
        i = 1;
        closestX = globalState.current.humans[0].x;
        closestY = globalState.current.humans[0].y;
        result = globalState.current.humans[0].id;
    }

    closestDistance = distance(x, y, closestX, closestY);

    for (; i < options.humans.length; i++) {
        // Check if distance is closer
        let d = distance(x, y, options.humans[i].x, options.humans[i].y);

        // Collision check
        if (options.collide !== true && d === 0) {
            continue;
        }

        // Update variables if human is closer to a given distance
        // TODO calculate if we can actually kill the human by then if options are provided
        if (d < closestDistance || (
            // Distance check
            d === closestDistance && (
                result === undefined ||
                result > options.humans[i].id
            ) && (
                // Cap check once passed the distance check
                options.cap !== true ||
                options.humans[i].expires === undefined ||
                Math.ceil((d / options.speed) + options.offset) <= Math.ceil(options.humans[i].expires)
            )
        )) {
            closestX = options.humans[i].x;
            closestY = options.humans[i].y;
            closestDistance = d;
            result = options.humans[i].id;
        }
    }

    return result;
};

var closestZombie = function(x, y) {
    if (globalState.current.zombieCount === 0) {
        return undefined
    }

    let closestX = globalState.current.zombies[0].x;
    let closestY = globalState.current.zombies[0].y;
    let closestDistance = distance(x, y, closestX, closestY);
    let result = globalState.current.zombies[0].id;

    for (let i = 1; i < globalState.current.humanCount; i++) {
        let d = distance(x, y, globalState.current.zombies[i].x, globalState.current.zombies[i].y);

        if (d < closestDistance) {
            closestX = globalState.current.zombies[i].x;
            closestY = globalState.current.zombies[i].y;
            closestDistance = d;
            result = globalState.current.zombies[i].id;
        }
    }

    return result;
};

var zombieSpread = function(zombies) {
    if (zombies.length < 1) {
        return;
    }

    let loX = zombies[0].x;
    let hiX = zombies[0].x;
    let loY = zombies[0].y;
    let hiY = zombies[0].y;

    for (var i = 1; i < zombies.length; i++) {
        if (zombies[i].x > hiX) {
            hiX = zombies[i].x;
        } else if (zombies[i].x < loX) {
            loX = zombies[i].x;
        }

        if (zombies[i].y > hiY) {
            hiY = zombies[i].y;
        } else if (zombies[i].y < loY) {
            loY = zombies[i].y;
        }
    }

    return {
        spread: distance(loX, loY, hiX, hiY),
        loX: loX,
        hiX: hiX,
        loY: loY,
        hiY: hiY
    };
};

var meetup = function(zombieId) {
    // Assuming that the zombie goes in a straight line, calculate heading to meetup with the zombie
    let location = {
        x: 0,
        y: 0
    };

    if (
        globalState.current.zombie[zombieId].x === globalState.current.zombie[zombieId].xNext &&
        globalState.current.zombie[zombieId].y === globalState.current.zombie[zombieId].yNext
    ) {
        location.x = globalState.current.zombie[zombieId].xNext;
        location.y = globalState.current.zombie[zombieId].yNext;
    } else {
        // calculate meetup distance given zombie vector, current position and speeds
        let zombie = globalState.current.zombie[zombieId];

        // Estimate meetup location
        let d = distance(zombie.x, zombie.y, globalState.current.x, globalState.current.y) - ASH_KILL_RANGE;
        let steps = Math.ceil(d / ASH_SPEED);

        location.x = zombie.x + Math.floor((zombie.xNext - zombie.x) * steps);
        location.y = zombie.y + Math.floor((zombie.yNext - zombie.y) * steps);
    }

    return location;
};

// TODO shorten distance in case we violate non-threat cases
var resolveThreats = function() {
    // Check if we can safe everybody
    globalState.impacts.threats.sort(function(a, b) {
        return a.impact - b.impact;
    });

    let zombie = globalState.impacts.threats[0];
    let human = globalState.current.human[zombie.human];
    let target = typeof human.zombie === "number"? meetup(human.zombie) : human;

    let d = distance(globalState.current.x, globalState.current.y, target.x, target.y);
    let overshoot = d - Math.floor(d / ASH_SPEED) * ASH_SPEED;
    let bounce = false;

    // Find next target if we can affort it
    if (overshoot > 0 && globalState.impacts.threats.length > 1) {
        debug("We can do more!!! We have an overshoot of " + overshoot);

        let steps = Math.ceil(d / ASH_SPEED);
        let nextZombie = globalState.impacts.threats[1];

        // Lets do a tangentpoint math to get the limits
        let tangents = tangentPoints(globalState.current.x, globalState.current.y, target.x, target.y, ASH_KILL_RANGE);
        let angle = (globalState.current.y - target.y) / (globalState.current.x - target.x);
        let angleNext = (globalState.current.y - nextZombie.y) / (globalState.current.x - nextZombie.y);
        let angleTangent = (globalState.current.y - tangents.a.y) / (globalState.current.x - tangents.a.x);
        let angleLimit = angleTangent - angle; // y/x ratio limit we can deviate from line to zombie to target nextZombie
        let angleDeltaNext = angleNext - angle;

        // Find out if angles are out of limits
        // TODO if angle is within limit, go to that direction instead
        if (angleDeltaNext > angleLimit || angleDeltaNext < -angleLimit) {
            debug("Changing angle!");
            bounce = true;

            // Change target to tangent edge
            if (angleDeltaNext > 0) {
                target = tangents.a;
            } else {
                target = tangents.b;
            }

            // Check if target can be reached in 1 step (including fire range), so its possible to shortcut to other zombie even more
            // TODO this needed some more fine tuning...
            let newD = distance(globalState.current.x, globalState.current.y, target.x, target.y);
            let cutoff = ASH_SPEED + ASH_KILL_RANGE - newD;
            if (cutoff > 0) {
                debug("Changing angle after changing angle!");
                let tangents2 = tangentPoints(globalState.current.x, globalState.current.y, target.x, target.y, ASH_KILL_RANGE);
                let angleNext2 = (globalState.current.y - tangents2.a.y) / (globalState.current.x - tangents2.a.x);
                let angleLimit2 = angleNext2 - angle;

                // TODO check if angle overshoots

                if (angleDeltaNext > angleLimit2 || angleDeltaNext < -angleLimit2) {
                    if (angleDeltaNext > 0) {
                        target = tangents2.a;
                    } else {
                        target = tangents2.b;
                    }
                } else {
                    target = nextZombie;
                }
            }
        } else {
            // Next zombie is target
            target = nextZombie;
        }

    }

    // TODO test for regressions (making non-threats change in a threatening situation)
    move(target.x, target.y);
};

// Called when there is only 1 person and when there are no threats
var safeLastHuman = function() {
    let human;
    for (let i = 0; i < globalState.current.humanCount; i++) {
        if (globalState.current.humans[i].safe === true) {
            human = globalState.current.humans[i];
        }
    }

    if (human === undefined) {
        return;
    }

    // Optimize for bonus while keeping the human alive
    let limitZombie = closestZombie(human.x, human.y);
    let limit = distance(limitZombie.xNext, limitZombie.yNext, human.x, human.y);

    let spread = zombieSpread(globalState.current.zombies);

    // Measure if zombies are close enough to each other, so we can kill them all
    if (spread.spread < (ASH_KILL_RANGE * 2)) {
        // In theory, we can all the zombies at once, but we need to locate ash on the right place
        debug("We can kill all zombies at once!!!");
    }

    // Attempt to get get zombies closer while keeping distance
    // Find the position in the middle of the zombies, still not touching it

    move(globalState.current.x, globalState.current.y); // TODO for now we will just stand still
};

// Calculates where the zombie is heading to, we can use or update cache
// TODO calculate next zombie target, account for safeable humans
var calculateImpacts = function() {
    let previousImpacts = globalState.impacts;
    globalState.impacts = {
        threats: [],
        ashDistance: [],
        safeHumans: globalState.current.humanCount
    };

    let zombieQueue = [];
    let zombieNextQueue = globalState.current.zombies;
    let dept = 5;

    // TODO make sure the zombies are hunting humans still alive by then
    while(zombieNextQueue.length > 0) {
        // Don't get stuck forever
        if (dept === 0) {
            break;
        }
        dept--;

        zombieQueue = zombieNextQueue;
        zombieNextQueue = [];

        for (let i = 0; i < zombieQueue.length; i++) {
            // Fetch variables
            let zombie = zombieQueue[i];
            let human = globalState.current.human[closestHuman(zombie.xImpact, zombie.yImpact, {
                offset: Math.ceil(zombie.impact),
                cap: true
            })];
            let distanceAsh = distance(zombie.x, zombie.y, globalState.current.x, globalState.current.y);
            let distanceHuman, distanceAshHuman;

            if (human !== undefined) {
                distanceHuman = distance(zombie.x, zombie.y, human.x, human.y);
                distanceAshHuman = distance(human.x, human.y, globalState.current.x, globalState.current.y);
            }
    
            // Calculate threats, update structures
            if (human !== undefined && distanceAsh > distanceHuman) {
                zombie.human = zombie.human === undefined ? human.id : zombie.human;
                zombie.impact += distanceHuman / ZOMBIE_SPEED;
                zombie.xImpact = human.x;
                zombie.yImpact = human.y;
                zombie.impactCounter++;
    
                if (zombie.impact < ((Math.min(distanceAsh, distanceAshHuman) - ASH_KILL_RANGE) / ASH_SPEED)) {
                    // zombie will catch human, so mark human as unsafable
                    if (human.safe === true) {
                        debug("Human " + human.id + " will die");
                        globalState.impacts.safeHumans--;
                        human.safe = false;
                    }
    
                    // add zombie to nextQueue because the impact is a bit later
                    zombieNextQueue.push(zombie);
                }

                if (human.expires === undefined || human.expires > zombie.impact) {
                    human.expires = zombie.impact;
                    human.zombie = zombie.id;
                }
    
                // Zombie is considered a threat
                globalState.impacts.threats.push(zombie);
            } else {
                // NOTE: impact location and time CAN be different here than estimated

                // Zombie could be a thread
                zombie.impact = distanceAsh / ZOMBIE_SPEED;
                zombie.xImpact = globalState.current.x;
                zombie.yImpact = globalState.current.y;
    
                // Track distances to ash
                globalState.impacts.ashDistance.push(zombie);
            }
        }
    }

    // Check for every zombie chasing unsaveable humans where they head next
};

//////////////////////////////////////////////////////////////////////////////////////////
//// MAIN HANDLER
//////////////////////////////////////////////////////////////////////////////////////////

var tick = function(state) {
    if (state.zombieCount === 0) {
        // Go to center
        // TODO we may prefer to stand between humans or near the human closest to the edge
        move(WIDTH / 2, HEIGHT / 2);

    } else if (state.zombieCount === 1) {
        // Go straight to zombie
        debug("Targetting last zombie with id " + state.zombies[0].id);
        let target = meetup(state.zombies[0].id);
        move(target.x, target.y);

    } else {

        // Check which zombie has the closest impact to a human
        calculateImpacts();

        let deadHumans = globalState.current.humanCount - globalState.impacts.safeHumans;

        debug(globalState.impacts.threats.length + " threats");
        debug(globalState.impacts.ashDistance.length + " going to ash");
        debug(globalState.impacts.safeHumans + " can be saved");

        if (deadHumans > 0) {
            debug("However, " + deadHumans + " can not be saved.");
        }

        // We have to pick a human if there is a threat
        if (globalState.impacts.threats.length > 0) {
            return resolveThreats();
        }

        // If we have only 1 human...
        if (globalState.impacts.safeHumans === 1) {
            return safeLastHuman();
        }
        
        debug('Not implemented yet');

        // Stay separated from other zombies if possible, while staying attracting them away from them

        // Else we go for max score

        // TODO - TEMP
        move(globalState.current.x, globalState.current.y);
    }
};

// game loop
while (true) {
    var newState = fetchInputs();
    globalState.current = newState;
    tick(newState);
}