Created
June 12, 2014 18:52
-
-
Save schmatz/fcc04d92473c179b4a28 to your computer and use it in GitHub Desktop.
Ian Elliott's CodeCombat Greed code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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