Create a gist now

Instantly share code, notes, and snippets.

Ian Elliott's CodeCombat Greed code
var base = this;
if ( !base.init ) {
// Mark that we've ran the init code
base.init = true;
// Starting frame number
base.frames = 0;
// Amount of frames per second
base.frameRate = 4;
// Map unit types so we don't have to worry about them in game
var ogreUnits = { worker: 'peon', soldier: 'munchkin', knight: 'ogre', caster: 'shaman', flyer: 'fangrider', heavy: 'brawler' },
humanUnits = { worker: 'peasant', soldier: 'soldier', knight: 'knight', caster: 'librarian', flyer: 'griffin-rider', heavy: 'captain' };
// Mapping will always refer to the appropriate unit
base.units = (base.id == 'Ogre Base') ?
{ me: ogreUnits, enemy: humanUnits } :
{ me: humanUnits, enemy: ogreUnits };
base.cost = {
worker: 50, solider: 10, knight: 25, caster: 40, flyer: 60, heavy: 100,
peon: 50, munchkin: 10, ogre: 25, shaman: 40, fangrider: 60, brawler: 100,
peasant: 50, soldier: 10, librarian: 40, 'griffin-rider': 60, captain: 100
};
// Map enemy units back to their equivalent of my unit
base.unitsMap = {};
for (var unitName in base.units.enemy) {
base.unitsMap[base.units.enemy[unitName]] = base.units.me[unitName];
}
// Spawn first worker
base.build(base.units.me.worker);
base.prevItems = [];
base.currentItems = [];
base.lastCoin = 1;
base.coinName = 'Hybrid Coin ';
base.coins = 0;
base.maxBuckets = 0;
base.maxCoins = 0;
base.hybridCoins = [];
base.hybridCoinMap = {};
base.centroids = {};
base.centroidList = [];
base.totalCoins = 0;
base.aggressor = 0;
base.launch = false;
base.knights = false;
base.builds = {};
base.startFrame = -1;
base.buildQueue = [];
base.queueCost = 0;
base.queueCaster = false;
base.ignoreEnemies = {};
base.lost = false;
base.armyValue = 0;
base.shouldCancel = false;
// Keeps track of which coins map to the same hybrid coins
base.sameCoins = {};
// Placeholder coin that we never want to reach
base.distantCoin = new Vector(5000,5000);
base.distantCoin.value = 0;
base.distantCoin.magnitude = 'Distant Coin';
var ogreStart = new Vector(75, 60),
humanStart = new Vector(10, 10);
base.myStart = (base.id == 'Ogre Base') ? ogreStart: humanStart;
base.enemyStart = (base.id == 'Ogre Base') ? humanStart: ogreStart;
base.inf = 1/0;
base.lastHealth = base.health;
base.lastArmySize = 0;
base.enemyArmyValue = 0;
base.myArmyValue = 0;
base.inBetweenCoins = {};
} else {
// Remap variables
var hybridCoins = base.hybridCoins,
hybridCoinMap = base.hybridCoinMap,
coinsToAvoid = {},
centroids = base.centroids,
centroidList = base.centroidList,
activeWorkers = {},
enemyCentroids = {};
var distantCoin = base.distantCoin;
var inf = base.inf;
// Update the maps for current and previous keys
var prevItems = base.currentItems,
prevItemCount = prevItems.length,
currentItems = base.currentItems = base.getItems(),
currentItemCount = currentItems.length;
var workerDist = {},
workerCoins = {};
var myWorkers = base.getByType(base.units.me.worker),
myWorkerVectors = [],
enemyWorkerVectors = [],
myWorkerCount = myWorkers.length,
myArmySize = (base.getFriends().length - myWorkerCount),
enemyWorkers = base.getByType(base.units.enemy.worker),
enemyWorkerCount = enemyWorkers.length,
workers = enemyWorkers.concat(myWorkers),
enemies = base.getEnemies(),
cost = base.cost;
var underAttack = (enemies.length - 1) > enemyWorkerCount,
aggressor = base.aggressor;
var indexOf = _.indexOf,
min = Math.min,
max = Math.max,
ceil = Math.ceil,
floor = Math.floor,
abs = Math.abs;
var now = base.now(),
lateGame = now >= 42 && myWorkerCount >= 3,
endGame = false, //now >= 140,
rush = enemyWorkerCount === 0,
dying = base.health < base.lastHealth;
var myGold = base.gold,
enemyGold = enemies[0].gold;
var sizeX = 28.333333,
sizeY = 35,
bucketCount = 2;
var maxWorkers = max(7, min(enemyWorkerCount, 8));
// ------------------------------------------------------------
// Combat
// ------------------------------------------------------------
// Determine my army size
if (myArmySize != base.lastArmySize) {
var myWorkerType = base.units.me.worker,
thisArmyValue = 0;
(base.getFriends()).forEach(function(friend) {
var type = friend.type;
if (type != myWorkerType) {
thisArmyValue += cost[type];
}
});
base.myArmyValue = thisArmyValue;
}
if ( ((underAttack || now >= 125) && !base.launch && base.buildQueue.length === 0) || lateGame ) {
var unitTypes = base.units.enemy,
workerType = unitTypes.worker,
caster = unitTypes.caster,
flyer = unitTypes.flyer,
enemyVectors = [],
rangedVectors = [],
myStart = base.myStart,
enemyStart = base.enemyStart,
armyValue = 0,
enemiesClone = enemies.slice(0),
lastId;
// Who cares about their base...
enemiesClone.shift();
// Get vectors for each enemy
enemiesClone.forEach(function(enemy) {
var type = enemy.type;
if (type != workerType) {
lastId = enemy.id;
// Type data
var enemyVector = new Vector(enemy.pos.x, enemy.pos.y);
enemyVector.dot = type;
enemyVector.magnitude = lastId;
enemyVectors.push(enemyVector);
armyValue += cost[type];
if (type == caster || type == flyer)
rangedVectors.push(enemyVector);
}
});
base.enemyArmyValue = armyValue;
var nearestCaster = base.getNearest(rangedVectors),
nearestEnemy = base.getNearest(enemyVectors),
aggressive = !underAttack && ((!nearestCaster || myStart.distance(nearestCaster) > 70) && (!nearestEnemy || myStart.distance(nearestEnemy) > 30));
// Make sure this is a new threat
if ( (((underAttack && base.enemyArmyValue > 20)|| now >= 125) && !base.launch && base.buildQueue.length === 0) && !base.ignoreEnemies[lastId] ) {
// If under attack and the nearest caster is less than 50 units away, or the nearest melee is less than 30 away
if ( (underAttack && ((nearestCaster && myStart.distance(nearestCaster) <= 70) || (nearestEnemy && myStart.distance(nearestEnemy) <= 30))) || (now >= 125 && (!aggressive || (myGold - 40) > enemyGold)) || (enemyArmyValue >= 50 && myGold <= enemyArmyValue) ) {
// Small scale battle, invested less than 50 minerals - lets build the exact same
// Or I'm broke and losing hard...
if ( (armyValue <= 65 && rangedVectors.length <= 1) && base.buildQueue.length === 0 && now < 125) {
var rangedCost = 0,
rangedUnit;
if (rangedVectors.length) {
rangedCost = cost[rangedVectors[0].dot];
rangedUnit = base.unitsMap[rangedVectors[0].dot];
} else if (base.getByType(base.units.enemy.soldier).length > 4) {
rangedCost = 40;
rangedUnit = base.units.me.caster;
}
var count = max(floor((armyValue - rangedCost) / 10), 0);
base.queueCost = count * 10 + rangedCost;
// Spawn basic workers if they have no casters... mass basic units always beat the other things
while (count--) {
base.buildQueue.push([base.units.me.soldier, base.frames + count]);
if ( (base.buildQueue.length == 1 && !count) || base.buildQueue.length == 2) {
if (rangedCost) {
base.queueCaster = true;
base.buildQueue.push([rangedUnit, base.frames + 10]);
} else {
base.queueCaster = false;
}
}
}
enemyVectors.forEach(function(e) {
// Ignore enemiesClone so that we don't create a new response to an old thread
base.ignoreEnemies[e.magnitude] = true;
});
} else {
// Don't be aggressive with someone we can't beat... stalemate him
if ( !aggressive || (myGold - 40) > enemyGold) {
base.launch = true;
base.startFrame = base.frames;
if (myGold >= 130)
base.knights = true;
}
}
}
} else {
underAttack = false;
}
}
// ------------------------------------------------------------
// Build Units
// ------------------------------------------------------------
// Care !
// If we try to build an item we can't afford, it will be built as soon as possible on any later turn
// This may end in situations where we can't /not/ produce a unit we no longer want
// We can try and back out of it by attempting to produce a unit we can't afford... but if we can afford all units
// then all we can do is try to produce the cheapest one to reduce the effect of the error
// If we're ahead in battle, make workers
if (base.myArmyValue && (base.myArmyValue + myGold - 50 >= base.enemyArmyValue + enemyGold) && myWorkerCount < maxWorkers) {
base.build(base.units.me.worker);
// If dying, spawn workers as required
} else if (dying && base.myArmyValue < base.enemyArmyValue) {
if ( base.getByType(base.units.me.soldier).length > 4 && myGold >= 40 )
base.build(base.units.me.caster);
else
base.build(base.units.me.soldier);
// Fizz buzz of battle
} else if (base.launch) {
var soldierType = base.knights? base.units.me.knight: base.units.me.soldier,
frame = base.frames - base.startFrame,
soldiers = base.getByType(soldierType),
basics = base.getByType(base.units.me.soldier),
casterCount = base.getByType(base.units.me.caster).length,
soldierCount = soldiers.length,
soldierDist = inf,
basicDist = inf;
if (base.knights && soldierCount >= 2) {
soldierCount += base.getByType(base.units.me.soldier).length;
}
if (soldierCount) {
soldierDist = soldiers[0].pos.distance(base.myStart);
}
if (basics.length) {
basicDist = Math.min(basics[0].pos.distance(base.myStart), soldierDist);
}
// We're far ahead... build soldiers
if ( base.myArmyValue >= (base.enemyArmyValue * 1.3) && base.myArmyValue > 140 && rangedVectors && rangedVectors.length < 2 && soldierCount < 6) {
base.build(base.units.me.soldier);
} else if (base.getByType(base.units.enemy.caster).length && casterCount === 0 && soldierCount >= 2) {
base.build(base.units.me.caster);
} else if (basicDist >= 20 && soldierDist >= 20 && rangedVectors && rangedVectors.length) {
base.build(base.units.me.soldier);
// Every 7 frames build a worker
} else if ( soldierCount < 2 || (((frame % 8) === 0 || soldierDist > 10) && (soldierCount < 4)) ) {
if (base.knights && soldierCount >= 2)
base.build(base.units.me.soldier);
else
base.build(soldierType);
// Every frame after build a caster, until next warrior needed
} else if ( frame >= 12 ) {
if ( casterCount > 3 && base.getByType(base.units.me.flyer).length === 0 )
base.build(base.units.me.flyer);
else
base.build(base.units.me.caster);
}
// A unit queue identical to what the enemy sent, should be relatively low value
} else if (base.buildQueue.length) {
if ( !base.queueCaster || base.queueCaster && base.queueCost <= myGold ) {
// Get the first item off the queue without destroying it, in case we can't follow
var queue = base.buildQueue.slice(0),
next = queue.shift();
// Check if its time to build the unit yet, and check if we can build the unit
if (next[1] <= base.frames && myGold >= base.cost[next[0]]) {
base.build(next[0]);
// Actually remove the unit from the queue
base.buildQueue.shift();
base.buildQueue = base.buildQueue.slice(0);
}
}
// Make sure our enemy doesn't try to all in by under producing workers
} else if ((!underAttack || base.enemyArmyValue <= 30) && myWorkerCount < maxWorkers && myGold > 40 && ((myWorkerCount - enemyWorkerCount <= 1 && enemyGold < 50)|| enemyGold < 50)) {
base.build(base.units.me.worker);
// Cancel whatever unit is in the queue by queuing an item we don't want to produce
} else if (myGold <= 90 && myWorkerCount < maxWorkers && base.shouldCancel) {
base.build(base.units.me.heavy);
base.shouldCancel = false;
// Additional safety.. should never reach here
} else if (myWorkerCount < maxWorkers && base.shouldCancel) {
base.build(base.units.me.soldier);
base.shouldCancel = false;
}
// ------------------------------------------------------------
// Functions for working with bounding boxes
// ------------------------------------------------------------
// Convert a positions real location into its a square the size of the unit collection bounding box
var nearestEdge = function(a, b) {
return new Vector(
b.x + max(min(a.x - b.x, 2.95) , -2.95),
b.y + max(min(a.y - b.y, 3.95) , -3.95)
);
},
shortestLink = function(a, b) {
var diff = new Vector.subtract(nearestEdge(a, b), a);
diff.x = min(max(diff.x, -2.95), 2.95);
diff.y = min(max(diff.y, -3.95), 3.95);
diff = new Vector.limit(diff, 25);
return Vector.add(a, diff);
},
longestLink = function(a, b) {
var diff = new Vector.subtract(b, a);
return Vector.add(a, Vector.limit(diff, 5));
},
// Add a to a vector array to improve distance calculation performance
addCoinToBoundedBox = function(coin) {
var coinId = coin.id;
if (!hybridCoinMap[coinId]) {
// Track coin amounts
base.coins++;
base.totalCoins++;
base.maxCoins = max(base.coins, base.maxCoins);
var coinPos = coin.pos,
newCoin = new Vector(coinPos.x, coinPos.y),
bucketX = floor(coinPos.x / sizeX),
bucketY = floor(coinPos.y / sizeY);
newCoin.magnitude = coinId;
newCoin.equals = coin.bountyGold * 1000;
// Add coin to list of hybrid coins, and keep track of which coin ids map to the same hybrid coin
hybridCoins.push(newCoin);
// HybridCoinMap maps all coin ids to their hybrid coin objects
hybridCoinMap[coinId] = coin;
// Manage local centroid
if ( !centroids[bucketX] )
centroids[bucketX] = {};
var bucket = centroids[bucketX][bucketY];
if ( bucket ) {
bucket.normalize = Vector.add(bucket.normalize, coinPos);
var localCentroid = Vector.divide(bucket.normalize, ++bucket.dot);
//bucket.x = localCentroid.x;
//bucket.y = localCentroid.y;
bucket.equals += newCoin.equals;
++bucket.heading;
} else {
var copy = new Vector(bucketX * 26.333 + 26.333 / 2 + 3, bucketY * 31 + 31 / 2 + 4);
copy.dot = copy.heading = 1;
copy.normalize = copy.copy();
copy.equals = newCoin.equals;
centroids[bucketX][bucketY] = copy;
}
}
},
// Remove a single coin from a bounding box. This might decrease the value of the box, or it could remove the box all together
removeCoinFromBoundedBox = function(coin, coinsRemoved) {
var coinId = coin.id;
if (hybridCoinMap[coinId]) {
var hybridIndex = indexOf(prevItems, coin) - coinsRemoved,
coinPos = coin.pos,
bucketX = floor(coinPos.x / sizeX),
bucketY = floor(coinPos.y / sizeY);
var centroidCoin = centroids[bucketX][bucketY];
// Decrease the value of the centroid this coin belonged to
centroidCoin.equals -= (coin.bountyGold * 1000);
--centroidCoin.heading;
base.coins--;
// Remove the collected coin if we havent already
if (hybridIndex !== -1) {
hybridCoins.splice(hybridIndex, 1);
}
delete hybridCoinMap[coinId];
}
},
wd,
// Low op variable store
badChoice = function(worker, coin) {
return ((wd = worker.pos.distance(coin)) && myWorkerVectors.some(function(myWorker) {
return (myWorker.distance(coin) || inf) < wd;
}));
},
// Find approximate sets of clusters nearest to a worker
findNearestClusters = function(worker) {
var clusterPoolLength = 14,
anchorNodes = 3,
pathLength = 2,
clusterPool = [],
nearestCoins = [],
paths = [],
keys = [],
idealCoins = 0,
coins = hybridCoins.slice(0);
// Get the nearest k coins to a worker - all clusters will also be made from these coins
clusterPoolLength = min(base.coins, clusterPoolLength);
while (clusterPoolLength--) {
var nearest = worker.getNearest(coins.slice(0));
// Add the coin to the pool if its not a bad choice... or if theres no better choices
if ( !(coinsToAvoid[nearest.magnitude] || badChoice(worker, nearest)) ) {
clusterPool.push(nearest);
// Once we have 10 ideal coins, we can stop looking for more
if (++idealCoins > 10)
break;
}
// Replace coin so that it wont get selected again - can't splice because we lose index relationship after a coin is removed
coins[indexOf(currentItems, hybridCoinMap[nearest.magnitude])] = distantCoin;
}
// Limit nearest coins to the number of paths we want to return
nearestCoins = clusterPool.slice(0, anchorNodes);
// Locate the nearest cluster of coins from each anchor that we want to test
nearestCoins.forEach(function(anchor, index) {
var path = [],
sorted = [],
result = [],
resultKeys = [],
pool = clusterPool.slice(0);
// Remove self from pool
pool.splice(index, 1);
// Find the distance from the anchor node to all other nodes
pool.forEach(function(coin) {
// Add distance to array for us to sort to find closest
path.push(anchor.distance(coin) / coin.equals);
});
// Sort the distance array to locate closest coins
sorted = path.slice(0);
sorted.sort();
// Take the first k elements of the sorted array, and find out which coin they were
sorted.slice(0, pathLength).forEach(function(dist) {
var coin = pool[indexOf(path, dist)];
result.push(coin);
resultKeys.push(coin.magnitude);
});
// Store result in the index of the anchor coin
paths.push(result);
keys.push(resultKeys);
});
// Return nearest coins and their corresponding clusters
return [nearestCoins, paths, keys];
},
kNearestCoins = function(worker, k) {
var nearestCoins = [],
coins = hybridCoins.slice(0);
// Get the nearest k coins to a worker - all clusters will also be made from these coins
k = min(base.coins, k);
while (k--) {
var nearest = worker.getNearest(coins.slice(0));
nearestCoins.push(nearest);
// Replace coin so that it wont get selected again
coins[indexOf(currentItems, hybridCoinMap[nearest.magnitude])] = distantCoin;
}
return nearestCoins;
},
// Methods for Priority Queue
nodes = [];
// ------------------------------------------------------------
// Track Workers as pure vectors
// ------------------------------------------------------------
if (lateGame) {
myWorkers.forEach(function(worker) {
workerDist[worker.id] = [];
workerCoins[worker.id] = [];
myWorkerVectors.push(worker.pos);
});
enemyWorkers.forEach(function(worker) {
workerDist[worker.id] = [];
workerCoins[worker.id] = [];
enemyWorkerVectors.push(worker.pos);
});
} else {
myWorkers.forEach(function(worker) {
myWorkerVectors.push(worker.pos);
});
enemyWorkers.forEach(function(worker) {
enemyWorkerVectors.push(worker.pos);
});
}
// ------------------------------------------------------------
// Track Newly Added/Removed coins
// ------------------------------------------------------------
// Total amount of coins collected this turn
var coinsRemoved = 0;
// Find coins that were just collected
prevItems.forEach(function(element) {
// Coins collected this turn
if (indexOf(currentItems, element) === -1) {
removeCoinFromBoundedBox(element, coinsRemoved++);
}
});
// The amount of new coins that need to be added
var newCoins = (currentItemCount - prevItemCount) + coinsRemoved;
// If theres new coins, add them to the hybrid list
if (newCoins > 0) {
// The index in currentItem array of the current new coin we need to add
var newCoinIndex = currentItemCount + (prevItemCount - currentItemCount) - coinsRemoved;
// Add all the new coins
while (newCoins--) {
addCoinToBoundedBox(currentItems[newCoinIndex++]);
}
}
// Rebuild centroid list ... array of objects seems to desync
if (newCoins || coinsRemoved) {
centroidList = [];
for (var bucketX in centroids)
for (var bucketY in centroids[bucketX])
centroidList.push(centroids[bucketX][bucketY]);
}
// Force changes to persist - seems to be a bug
base.hybridCoins = hybridCoins.slice(0);
// ------------------------------------------------------------
// Simple pathing
// ------------------------------------------------------------
// Steal enemy coins - don't be fooled by scaled vectors
var arcDistance = 7.85398, // 5 * pi / 2;
commandedWorkers = {},
workersToRemove = [];
if (now <= 80)
enemyWorkers.forEach(function(element, i) {
var targetPos = element.targetPos || false;
if (targetPos) {
// Figure out the distance and direction the enemy is traveling
var nearestCoins = kNearestCoins(element, 10),
elementPos = element.pos,
direction = new Vector.subtract(targetPos, elementPos),
heading = direction.heading(),
workerIndex = -1,
toAvoid = [],
toAvoidCoins = [],
next = [],
nextCoin = [],
realTarget, coinTarget, closestCoin, distance, enemyDistance;
// Find the first coin that will intersect with the workers path
nearestCoins.some(function(coin, index) {
// Find out the distance and direction a coin is from an enemy
var dir = Vector.subtract(coin, elementPos),
dist = dir.magnitude();
// If coin is on the current worker path
if (abs(heading - dir.heading()) <= (arcDistance / dist)) {
// The closest coin on route is the real target of the enemy
if ( !coinTarget ) {
distance = enemyDistance = dist;
coinTarget = coin;
realTarget = Vector.add(elementPos, direction.limit(dist));
nearestCoins.splice(index, 1);
return true;
}
}
});
// If we have found a target coin for the enemy
if (distance) {
var minDist = ceil((distance - max(5, distance)) / 1.25) * 1.25,
newTarget = new Vector.add(elementPos, direction.limit(minDist));
// If the enemy is closer to these coins than we are avoid them for future targeting
// The enemy distance is really distance to current target + distance from target - coin
// Since we know where he's really headed...
nearestCoins.slice(0).forEach(function(coin) {
if (myWorkerVectors.every(function(worker) {
return (minDist + newTarget.distance(coin)) < worker.distance(coin);
})) {
if ( !coinsToAvoid[coin.magnitude] ) {
// Doesn't really matter what we push as long as its unique enough to match back
toAvoid.push(coinTarget.distance(coin) / coin.equals);
toAvoidCoins.push(coin);
}
} else {
next.push(coinTarget.distance(coin) / 1000);
nextCoin.push(coin);
}
});
if ( next.length ) {
var sortedNext = next.slice(0);
sortedNext.sort();
closestCoin = nextCoin[indexOf(next, sortedNext.shift())];
}
} else {
// Enemy doesn't really have a target... so trace distance from worker to 3 nearest coins
nearestCoins.slice(0, 3).forEach(function(coin) {
if (myWorkerVectors.every(function(worker) {
return (elementPos.distance(coin)) < worker.distance(coin);
})) {
if ( !coinsToAvoid[coin.magnitude] ) {
toAvoid.push(elementPos.distance(coin) / coin.equals);
toAvoidCoins.push(coin);
}
}
});
}
// Sort distances in avoidance list
var sortedAvoidDist = toAvoid.slice(0);
sortedAvoidDist.sort();
// Avoid the closest 2 coins, closest coin will also be avoided... so in total up to 3 coins avoided for each enemy
sortedAvoidDist.slice(2).forEach(function(dist) {
var coin = toAvoidCoins[indexOf(toAvoid, dist)];
coinsToAvoid[coin.magnitude] = coin;
});
// If we managed to tie a real coin to the enemies position, check if we can intercept
if (realTarget) {
// Find the distance the enemy is from his intended target
coinsToAvoid[coinTarget.magnitude] = coinTarget;
// Check to see if any of my workers can steal
myWorkerVectors.forEach(function(worker, index) {
var workerDist = worker.distance(coinTarget);
// If i can beat the enemy to wherever hes headed, I'm going to!
// Keep track of distances to locations a coin is already headed to, so we always make the best choice
if (workerDist < distance &&
(!commandedWorkers[index] || workerDist < commandedWorkers[index])) {
workerIndex = index;
distance = workerDist;
commandedWorkers[index] = workerDist;
}
});
// We found a worker that is closer to the coin than the enemy - steal his coin
if (workerIndex != -1) {
var myWorker = myWorkers[workerIndex],
enemyWorkerVectorsClone = enemyWorkerVectors.slice(0);
// Ensure that there isn't an enemy worker closer... sometimes enemies target the same coin
// Lets not follow their mistake
enemyWorkerVectorsClone.splice(i, 1);
// The enemy that we can beat to this coin isn't even the closest enemy... abort
if (enemyWorkerVectorsClone.slice(0).some(function(enemyWorker) {
return enemyWorker.distance(coinTarget) < distance;
})) {
commandedWorkers[workerIndex] = inf;
return;
}
// At this point we know that this worker is for sure the closest to the coin the enemy wants
// See if we can scoop up some coins along the way to the enmies position as well
var alliedNearestCoins = kNearestCoins(myWorker, 5),
closestMidCoin, midCoinValue = 0;
enemyDistance = ceil(enemyDistance / 1.25) * 1.25;
alliedNearestCoins.forEach(function(coin) {
// Find the best path from this coin to the coinTarget
var inBetweenTarget = shortestLink(coin, coinTarget),
myDist = myWorker.distance(inBetweenTarget),
normalDistance = ceil(myDist / 1.25) * 1.25,
dirVector = Vector.subtract(inBetweenTarget, coinTarget);
inBetweenPos = Vector.add(myWorker.pos, Vector.limit(dirVector, normalDistance));
// Now get distance from this intermediate coin to the target coin...
var endDistance = ceil(inBetweenPos.distance(coinTarget) / 1.25) * 1.25;
if ( (normalDistance + endDistance) < enemyDistance ) {
enemyDistance = normalDistance + endDistance;
closestMidCoin = coin;
}
});
// This command may or may not stick... it could be over written by a later loop
// If we find a better coin for this worker to steal
workersToRemove.push(myWorker.id);
if ( closestMidCoin) {
coinTarget = shortestLink(closestMidCoin, coinTarget);
} else if ( closestCoin )
coinTarget = shortestLink(coinTarget, closestCoin);
else
coinTarget = shortestLink(coinTarget, realTarget);
base.command(myWorker, 'move', coinTarget);
activeWorkers[myWorker.id] = coinTarget;
}
}
}
});
var centroidsClone = centroidList.slice(0),
workersLeft = [];
// These workers are stealing coins... remove them from the worker arrays since their moves are already decided
myWorkers.slice(0).forEach(!lateGame? function(element) {
if (workersToRemove.indexOf(element.id) == -1) {
var components = findNearestClusters(element),
minWeight = inf,
nextNode, nextNextNode, lastNode;
components[0].forEach(function(anchor, index) {
var anchorId = anchor.magnitude,
coins = components[1][index],
numCoins = coins.length,
nodesLeft = numCoins,
coinKeys = components[2][index],
clusterValue = 0,
distances = {};
// Add the anchor coin
nodes.push({ coin: anchor, distance: distances[anchorId] = 0 });
// Preset all distances to inf, and add vertices to queue
coins.forEach(function(coin, index) {
// Value of all coins in this set
clusterValue += coin.equals;
// Add node to
nodes.push({ coin: coin, distance: distances[coinKeys[index]] = inf });
});
++nodesLeft;
// Dijkstra - optimized for minimum ops - some fucked up algorithm changes
while ( nodesLeft-- ) {
var smallest = nodes.shift().coin,
smallestId = smallest.magnitude,
smallestDist = distances[smallestId],
coinCount = numCoins;
while (coinCount--) {
var coin = coins[coinCount],
coinId = coin.magnitude,
newDistance = smallestDist + ceil((coin.distance(smallest) || inf) / 1.25);
if (newDistance < distances[coinId]) {
nodes.push({ coin: coin, distance: distances[coinId] = newDistance });
++nodesLeft;
}
}
}
var maxDist = 0;
// Find the furthest distance to a node - this is the shortest path to all nodes
for (var coinDist in distances) {
if (distances[coinDist] > maxDist) {
maxDist = distances[coinDist];
lastNode = hybridCoinMap[coinDist].pos;
}
}
// The distance-per-coin metric
// We want to minimize this value, as the less distance we have to travel for each "value" the better
var pathValue = (element.pos.distance(anchor) / anchor.equals) + (maxDist / clusterValue);
// Check if this is the optimal path so far
if (pathValue < minWeight) {
minWeight = pathValue;
nextNode = anchor;
var minDist = inf;
// Find the coin closest to the anchor coin
for (coinDist in distances) {
if (distances[coinDist] < minDist && distances[coinDist] !== 0) {
minDist = distances[coinDist];
nextNextNode = coinDist;
}
}
if (nextNextNode)
nextNextNode = hybridCoinMap[nextNextNode].pos;
}
});
// If we have a good candidate node to travel to, make our way there
if (nextNode) {
// If theres at least 2 nodes to travel to, optimize path so that we minimize the distance to the next 2 nodes
if (nextNextNode) {
if (lastNode && lastNode !== nextNextNode)
nextNextNode = shortestLink(nextNextNode, lastNode);
nextNode = shortestLink(nextNode, nextNextNode);
}
base.command(element, 'move', nextNode);
activeWorkers[element.id] = nextNode;
} else {
// Further scheduling for these guys
workersLeft.push(element);
}
}
} : (endGame? function(element) {
//base.command(element, 'move', new Vector(80, 65));
} : function(element) {
// Just get a list of workers remaining
if (workersToRemove.indexOf(element.id) == -1)
workersLeft.push(element);
}));
// Calculations are expensive if theres a lot of coins... so only do it when there should be few
if (lateGame) {
// Find the closest coins to each worker
hybridCoins.forEach(function(element) {
var minDist = inf, minWorker;
myWorkers.forEach(function(worker) {
var pos = worker.pos;
if (minDist > pos.distance(element)) {
minDist = pos.distance(element);
minWorker = worker;
}
});
// Give control of the coin to the closest worker
workerDist[minWorker.id].push(minDist / element.equals);
workerCoins[minWorker.id].push(element);
});
// Try to isolate enemies so that if he's moving in a direction away from the centroid, we block him out from moving
// back towards it
var centroidsToRemove = [],
removed = 0;
// We can reasonably expect that all centroids exist by now - find out where enemies are
enemyWorkers.forEach(function(worker) {
var vector = worker.pos,
target = worker.targetPos;
// Figure out where this worker will be in 1 turn
if (target) {
var heading = new Vector.limit(Vector.subtract(target, vector), 1.25);
vector = new Vector.add(vector, heading);
}
var bucketX = floor(vector.x / sizeX),
bucketY = floor(vector.y / sizeY),
index = (bucketX * bucketCount) + bucketY;
if ( !enemyCentroids[index] )
enemyCentroids[index] = [];
enemyCentroids[index].push(vector);
});
// Find the average position of enemy workers in each box
for (var enemyList in enemyCentroids) {
var enemyCentroid = new Vector(0, 0),
list = enemyCentroids[enemyList],
length = list.length;
while (length--) {
enemyCentroid = Vector.add(enemyCentroid, list[length]);
}
enemyCentroids[enemyList] = Vector.divide(enemyCentroid, list.length);
}
// For all of our workers who have real destinations, find out what centroid they're headed to
// These centroids will become off limits to workers who have nothing to do
// (we know they can't reach coins inside them anyways)
for (var worker in activeWorkers) {
var vector = activeWorkers[worker],
index;
bucketX = floor(vector.x / sizeX);
bucketY = floor(vector.y / sizeY);
index = (bucketX * bucketCount) + bucketY;
centroidsToRemove.push(index / 100);
}
// Sort keys so we can remove centroids in order
centroidsToRemove.sort();
centroidsToRemove.forEach(function(index) {
var key = floor(index * 100);
centroidsClone.splice(key - removed++, 1);
});
}
// Move the worker to the closest coin
workersLeft.forEach(function(worker) {
var workerId = worker.id,
sortedDist = (workerDist[workerId] || []).slice(0),
length = sortedDist.length,
nearestCentroid = worker.getNearest(centroidsClone.slice(0)),
midVector = new Vector(42,35);
// Find the nearest centroid
centroidsClone.some(function(centroid, index) {
if (centroid == nearestCentroid) {
centroidsClone.splice(index, 1);
return true;
}
});
sortedDist.sort();
if ( !nearestCentroid )
nearestCentroid = midVector;
// Move to the nearest centroid
if ( !length ) {
var centroidIndex = floor(nearestCentroid.x / sizeX) * bucketCount + floor(nearestCentroid.y / sizeY);
// An enemy is in this square with me... try to zone him out if I can't beat him to coins
if ( enemyCentroids[centroidIndex] && nearestCentroid !== midVector ) {
base.command(worker, 'move', shortestLink(enemyCentroids[centroidIndex], nearestCentroid));
} else {
base.command(worker, 'move', nearestCentroid);
}
// Move to the nearest coin with best path back to centroid
} else {
var coin = workerCoins[workerId][indexOf(workerDist[workerId], sortedDist[0])];
// Shortest path to coin & back to centroid
if ( length == 1 ) {
base.command(worker, 'move', shortestLink(coin, nearestCentroid));
// Shortest path to next 2 coins
} else {
var secondCoin = workerCoins[workerId][indexOf(workerDist[workerId], sortedDist[1])];
base.command(worker, 'move', shortestLink(coin, secondCoin));
}
}
});
}
// How many frames have we dropped up until this point?
base.droppedFrames = (now * base.frameRate) - ( base.frames++ );
base.lastHealth = base.health;
base.lastArmySize = myArmySize;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment