Skip to content

Instantly share code, notes, and snippets.

@schmatz
Created June 12, 2014 18:35
Show Gist options
  • Save schmatz/4d216782b46d73c45813 to your computer and use it in GitHub Desktop.
Save schmatz/4d216782b46d73c45813 to your computer and use it in GitHub Desktop.
Michael Heasell's CodeCombat Greed Code
// 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;
@Julix91
Copy link

Julix91 commented Aug 23, 2018

maxkey doesn't seem to get used at all... - any reason it got to stay in anyway?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment