Created
June 12, 2014 18:35
-
-
Save schmatz/4d216782b46d73c45813 to your computer and use it in GitHub Desktop.
Michael Heasell'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
// constants ------------------------------------------------------------------- | |
var alliedTypes = { | |
peasant: 'peasant', | |
soldier: 'soldier', | |
knight: 'knight', | |
librarian: 'librarian', | |
griffinRider: 'griffin-rider', | |
captain: 'captain' | |
}; | |
var enemyTypes = { | |
peasant: 'peon', | |
soldier: 'munchkin', | |
knight: 'ogre', | |
librarian: 'shaman', | |
griffinRider: 'fangrider', | |
captain: 'brawler' | |
}; | |
if (this.buildables.peasant === undefined) { | |
var tmp = alliedTypes; | |
alliedTypes = enemyTypes; | |
enemyTypes = tmp; | |
} | |
// generic utility functions --------------------------------------------------- | |
// Searches the given array for the element with the maximum value | |
// as determined by the given function, f. | |
function maxkey(f, arr) { | |
var winner = null; | |
var winScore = -10000; | |
for (var i = 0; i < arr.length; ++i) { | |
var elem = arr[i]; | |
var score = f(elem); | |
if (score > winScore) { | |
winner = elem; | |
winScore = score; | |
} | |
} | |
return winner; | |
} | |
// Filters the given array of entities to those of the given type | |
function filterType(type, arr) { | |
return arr.filter(function(x) { return x.type === type; }, arr); | |
} | |
// Filters the given array of entities to those NOT of the type | |
function filterNotType(type, arr) { | |
return arr.filter(function(x) { return x.type !== type; }, arr); | |
} | |
// returns the linear interpolation from the start number to the end number | |
// according to the given fraction, a number from 0 to 1 | |
function lerp(start, end, frac) { | |
return start + ((end - start) * frac); | |
} | |
function clamp(val, low, high) { | |
return Math.max(Math.min(val, high), low); | |
} | |
// removes and returns the given element from the array | |
function remove(elem, arr) { | |
return arr.splice(arr.indexOf(elem), 1)[0]; | |
} | |
// removes and returns the element at the given index from the array | |
function removeIndex(i, arr) { | |
return arr.splice(i, 1)[0]; | |
} | |
// combat utilities ------------------------------------------------------------ | |
// Returns the heuristic value of the given type of fighter. | |
function valueFighter(type) { | |
switch (type) { | |
case "munchkin": | |
case "soldier": | |
return 10; | |
case "knight": | |
case "ogre": | |
return 25; | |
case "librarian": | |
case "shaman": | |
return 40; | |
case "griffin-rider": | |
case "fangrider": | |
return 60; | |
case "captain": | |
case "brawler": | |
return 100; | |
case 'base': | |
return 0; | |
case "peasant": | |
case "peon": | |
return 50; | |
} | |
} | |
// Returns the heuristic total value of the given collection of fighters. | |
function valuateFighters(fighters) { | |
var score = 0; | |
for (var i = 0, len = fighters.length; i < len; i++) { | |
score += valueFighter(fighters[i].type); | |
} | |
return score; | |
} | |
// coin gathering utilities ---------------------------------------------------- | |
function computeMinDistances(peasants, coins) { | |
var dict = {}; | |
for (var i = 0, len = coins.length; i < len; i++) { | |
var coin = coins[i]; | |
var winScore = 10000; | |
for (var j = 0, pLen = peasants.length; j < pLen; j++) { | |
var dist = coin.pos.distance(peasants[j].pos); | |
if (dist < winScore) { | |
winScore = dist; | |
} | |
} | |
dict[coin.id] = winScore; | |
} | |
return dict; | |
} | |
function computeEnemyMult(ourDistance, enemyDistance) { | |
var enemyDistFrac = (ourDistance + enemyDistance) / enemyDistance; | |
if (enemyDistFrac > 2.2222222222) { | |
return 0.5; | |
} | |
return enemyDistFrac; | |
} | |
function computeAttractionSquared(itemPos, attractorPos, attractorMass) { | |
var distance = itemPos.distance(attractorPos); | |
var strength = attractorMass / (distance * distance); | |
var direction = Vector.normalize(Vector.subtract(attractorPos, itemPos)); | |
return Vector.multiply(direction, strength); | |
} | |
function computeSpringAssignments(friends, enemies, coins, computeAttraction) { | |
var WALL_ATTRACTION = -1; | |
var FRIEND_ATTRACTION = -5; | |
var DIRECTION_CASTAHEAD = 6; | |
var ARENA_WIDTH = 85; | |
var ARENA_HEIGHT = 70; | |
var limits = computeMinDistances(enemies, coins); | |
var assignments = []; | |
for (var i = 0, fLen = friends.length; i < fLen; i++) { | |
var friend = friends[i]; | |
var friendPos = friend.pos; | |
var force = new Vector(0, 0); | |
for (var j = 0, cLen = coins.length; j < cLen; j++) { | |
var coin = coins[j]; | |
var coinPos = coin.pos; | |
var dist = friendPos.distance(coinPos); | |
var enemyDist = limits[coin.id]; | |
var strength = (coin.bountyGold * computeEnemyMult(dist, enemyDist)) / (dist * dist); | |
var direction = Vector.normalize(Vector.subtract(coinPos, friendPos)); | |
force = Vector.add(force, Vector.multiply(direction, strength)); | |
} | |
for (var k = 0; k < fLen; k++) { | |
if (k === i) { | |
continue; | |
} | |
force = Vector.add(force, computeAttraction(friendPos, friends[k].pos, FRIEND_ATTRACTION)); | |
} | |
// wall influence | |
force = Vector.add(force, computeAttraction(friendPos, new Vector(-0.1, friendPos.y), WALL_ATTRACTION)); // left | |
force = Vector.add(force, computeAttraction(friendPos, new Vector(ARENA_WIDTH + 0.1, friendPos.y), WALL_ATTRACTION)); // right | |
force = Vector.add(force, computeAttraction(friendPos, new Vector(friendPos.x, -0.1), WALL_ATTRACTION)); // bottom | |
force = Vector.add(force, computeAttraction(friendPos, new Vector(friendPos.x, ARENA_HEIGHT + 0.1), WALL_ATTRACTION)); // top | |
var newPos = Vector.add(friendPos, Vector.multiply(Vector.normalize(force), DIRECTION_CASTAHEAD)); | |
newPos = new Vector( | |
Math.min(Math.max(newPos.x, 0.0), ARENA_WIDTH), | |
Math.min(Math.max(newPos.y, 0.0), ARENA_HEIGHT)); | |
assignments.push({src: friend, target: newPos}); | |
} | |
return assignments; | |
} | |
// coin gathering main --------------------------------------------------------- | |
var items = this.getItems(); | |
var friends = this.getFriends(); | |
var enemies = this.getEnemies(); | |
var enemyBase = this.getByType('base')[0]; | |
var enemyGold = enemyBase ? enemyBase.gold : 0; | |
var peasants = this.getByType(alliedTypes.peasant); | |
var peons = this.getByType(enemyTypes.peasant); | |
var assignments = computeSpringAssignments(peasants, peons, items, computeAttractionSquared); | |
for (var i = 0; i < assignments.length; i++) { | |
var as = assignments[i]; | |
this.command(as.src, 'move', as.target); | |
} | |
// gold prediction utils ------------------------------------------------------- | |
function createRegressionFunc(points) { | |
var n = points.length; | |
var sumX = points.reduce(function(a, b) { return a + b.x; }, 0); | |
var sumY = points.reduce(function(a, b) { return a + b.y; }, 0); | |
var meanX = sumX / n; | |
var meanY = sumY / n; | |
var sumXSquared = points.reduce(function(a, b) { return a + (b.x * b.x); }, 0); | |
var sumXY = points.reduce(function(a, b) { return a + (b.x * b.y); }, 0); | |
var slope = (sumXY - ((sumX * sumY) / n)) / (sumXSquared - ((sumX * sumX) / n)); | |
var intercept = meanY - (slope * meanX); | |
return function(x) { | |
return (slope * x) + intercept; | |
}; | |
} | |
function estimateVariance(points, regFunc) { | |
var mseSum = points.reduce(function(a, b) { var ms = b.y - regFunc(b.x); return a + (ms * ms); }, 0); | |
var mse = mseSum / (points.length - 2); | |
return mse; | |
} | |
function estimateHighLow(points, time) { | |
var regFunc = createRegressionFunc(points); | |
var deviation = Math.sqrt(estimateVariance(points, regFunc)); | |
var bound = deviation * 2; // ~95% coverage | |
var start = regFunc(points[0].x); | |
var lowStart = start - bound; | |
var highStart = start + bound; | |
var end = regFunc(points[points.length - 1].x); | |
var lowEnd = end - bound; | |
var highEnd = end + bound; | |
var upperBound = lerp(lowStart, highEnd, (time - points[0].x) / (points[points.length - 1].x - points[0].x)); | |
var lowerBound = lerp(highStart, lowEnd, (time - points[0].x) / (points[points.length - 1].x - points[0].x)); | |
var estimate = regFunc(time); | |
return [upperBound, estimate, lowerBound]; | |
} | |
// base building --------------------------------------------------------------- | |
var militaryFriends = filterNotType(alliedTypes.peasant, friends); | |
var friendlySoldiers = filterType(alliedTypes.soldier, friends); | |
var militaryEnemies = filterNotType('base', filterNotType(enemyTypes.peasant, enemies)); | |
var nearestEnemy = this.getNearest(militaryEnemies); | |
// gold prediction main -------------------------------------------------------- | |
if (this.enemyGoldHistory === undefined) { | |
this.enemyGoldHistory = []; | |
} | |
if (this.counter === undefined) { | |
this.counter = 0; | |
} | |
var PREDICTOR_HISTORY_LENGTH = 25; | |
var PREDICTOR_SAMPLE_INTERVAL = 4; | |
var PREDICTOR_LOOKAHEAD_TIME = 17; | |
var enemyTotalWorth = 0; | |
if (enemyBase) { | |
enemyTotalWorth = valuateFighters(enemyBase.built) + enemyGold; | |
} | |
if (this.counter++ % PREDICTOR_SAMPLE_INTERVAL === 0) { | |
this.enemyGoldHistory.push({x: this.now(), y: enemyTotalWorth}); | |
} | |
if (this.enemyGoldHistory.length > PREDICTOR_HISTORY_LENGTH) { | |
this.enemyGoldHistory.shift(); | |
} | |
var ourMilitaryStrength = valuateFighters(militaryFriends); | |
var enemyMilitaryStrength = valuateFighters(militaryEnemies); | |
var ourStrength = ourMilitaryStrength + this.gold; | |
var enemyStrength = enemyMilitaryStrength + enemyGold; | |
var enemyStrengthForecast = null; | |
if (this.enemyGoldHistory.length >= PREDICTOR_HISTORY_LENGTH) { | |
var highLowE = estimateHighLow(this.enemyGoldHistory, this.now() + PREDICTOR_LOOKAHEAD_TIME); | |
var futureEnemyBonus = highLowE[0] - enemyTotalWorth; | |
enemyStrengthForecast = enemyStrength + futureEnemyBonus; | |
} | |
// subsumption behaviours ------------------------------------------------------ | |
var doNothingState = { | |
name: "doNothing", | |
wantsControl: function() { | |
return true; | |
}, | |
selectBuildType: function() { | |
return null; | |
} | |
}; | |
var collectState = { | |
name: "collect", | |
wantsControl: function(base) { | |
// always build the initial peasant | |
if (peasants.length < 1) { | |
return true; | |
} | |
// build another if we're behind on the enemy | |
if (enemyGold <= 70 && peasants.length < peons.length && peasants.length < 6) { | |
return true; | |
} | |
// build another if we think there is enough free gold | |
// to be worth it. | |
var coinsPerPeasant = items.length / peasants.length; | |
if (coinsPerPeasant >= 2) { | |
return true; | |
} | |
return false; | |
}, | |
selectBuildType: function(base) { | |
return alliedTypes.peasant; | |
} | |
}; | |
var pokeState = { | |
name: "poke", | |
wantsControl: function(base) { | |
return !base.poked; | |
}, | |
selectBuildType: function(base) { | |
if (base.gold >= 10) { | |
base.poked = true; | |
return alliedTypes.soldier; | |
} | |
return null; | |
} | |
}; | |
var stockpileState = { | |
name: "stockpile", | |
wantsControl: function(base) { | |
var strengthRatio = (ourMilitaryStrength + base.gold) / enemyMilitaryStrength; | |
if (strengthRatio <= 1.2) { | |
return true; | |
} | |
return false; | |
}, | |
selectBuildType: function(base) { | |
return null; | |
} | |
}; | |
function decideMilitaryToBuild(base) { | |
var soldierPercent = friendlySoldiers.length / militaryFriends.length; | |
if (friendlySoldiers.length < 3 || soldierPercent <= 0.45) { | |
return alliedTypes.soldier; | |
} | |
var friendlyLibs = filterType(alliedTypes.librarian, militaryFriends); | |
var libPercent = friendlyLibs.length / militaryFriends.length; | |
if (friendlyLibs.length < 2 || libPercent <= 0.33) { | |
return alliedTypes.librarian; | |
} | |
var friendlyGrif = filterType(alliedTypes.griffinRider, militaryFriends); | |
var grifPercent = friendlyGrif.length / militaryFriends.length; | |
if (grifPercent < 0.125) { | |
return alliedTypes.griffinRider; | |
} | |
var friendlyKnight = filterType(alliedTypes.knight, militaryFriends); | |
var knightPercent = friendlyKnight.length / militaryFriends.length; | |
if (knightPercent < 0.100) { | |
return alliedTypes.knight; | |
} | |
return alliedTypes.soldier; | |
} | |
var attackState = { | |
name: "attack", | |
wantsControl: function(base) { | |
// last ditch attack if the game is almost over | |
if (base.now() >= 140) { | |
return true; | |
} | |
// if we think that by the time our military gets there | |
// we will still have an advantage, then attack | |
var threshold = (base.currentState && base.currentState.name === "attack") ? 0 : 20; | |
if (enemyStrengthForecast && ourStrength - enemyStrengthForecast >= threshold) { | |
return true; | |
} | |
return false; | |
}, | |
selectBuildType: decideMilitaryToBuild | |
}; | |
var defendState = { | |
name: "defend", | |
wantsControl: function(base) { | |
var nearEnemies = militaryEnemies.filter(function(x) { return base.distance(x) < 55; }); | |
var militaryRatio = ourMilitaryStrength / valuateFighters(nearEnemies); | |
// if the enemy is near and we don't have enough defenders, build more | |
if (nearestEnemy && base.distance(nearestEnemy) <= 40 && militaryRatio < 1.2) { | |
return true; | |
} | |
return false; | |
}, | |
selectBuildType: decideMilitaryToBuild | |
}; | |
// subsumption main ------------------------------------------------------------ | |
var states = [ | |
attackState, | |
defendState, | |
stockpileState, | |
collectState, | |
pokeState, | |
doNothingState | |
]; | |
this.updateState = function() { | |
for (var i = 0, sLen = states.length; i < sLen; i++) { | |
var st = states[i]; | |
if (st.wantsControl(this)) { | |
this.currentState = st; | |
break; | |
} | |
} | |
}; | |
// base building main ---------------------------------------------------------- | |
this.updateState(); | |
var type = this.currentState.selectBuildType(this); | |
if (type && this.gold >= this.buildables[type].goldCost) { | |
this.build(type); | |
} | |
//var n = this.now(); | |
//if (this.lastRunTime !== undefined) { | |
// this.say("Last run: " + (n - this.lastRunTime)); | |
//} | |
//this.lastRunTime = n; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
maxkey doesn't seem to get used at all... - any reason it got to stay in anyway?