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