/greed_ogres.js
Created Jun 12, 2014
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