The Zombie Invasion

With bonzAI picking its own harvest rooms now, it was time to deal with the case where a potential harvest room is already inhabited. I already have code for a more decisive raid where tower damage is healed even at close range, rather than trying to drain the tower. In quite a few cases, these players will be inactive, a.k.a. "zombies", who won't put up much of a fight. I thought it worthwhile to try to write code that better scales to this situation.

This is the room I used as a test-case and also the type of situation I wanted to be able to handle with this code:

ZombieMission.ts (link)

"braaaains..."

My solution was to fight fire with fire and code some zombies of my own. These creeps will be slow and stupid. The pseudocode in a nutshell:

if health is above threshold
    approach nearest spawn in enemy room
    ignore most structures while pathing, attack any structures in the way
if health is below threshold
    approach fallback position

I also wanted tower-draining behavior to emerge from this pattern, having the creep utilize the exit mechanic to assist with healing. When a creep is standing an exit, it is in the room only every other tick, effectively halving the damage received. So I added this to the creep logic:

if standing on the exit for the enemy room
    wait for at least 10 consecutive ticks with full health

Making an entrance

Tower damage is graded by distance, certain exits will be preferable above others based on their average distance to towers in the room. My solution was to look at every exit in the room and figure out how much damage it would receive, and picking the lowest one. I'd ensure my zombies would use this exit by blocking off all the other exits in the CostMatrix.

Here is my first attempt to construct such a matrix:

let exitPositions: RoomPosition[] = [];
for (let x = 0; x < 50; x ++) {
    for (let y = 0; y < 50; y++) {
        if (x !== 0 && y !== 0 && x !== 49 && y !== 49) { continue; }
        if (Game.map.getTerrainAt(x, y, this.room.name) === "wall") { continue; }
        exitPositions.push(new RoomPosition(x, y, this.room.name));
        matrix.set(x, y, 0xff);
    }
}

let bestExit = _(exitPositions)
    .sortBy((p: RoomPosition) => -_.sum(towers, (t: Structure) => p.getRangeTo(t)))
    .head();
matrix.set(bestExit.x, bestExit.y, 1);

let expectedDamage = 0;
for (let tower of towers) {
    let range = bestExit.getRangeTo(tower);
    expectedDamage += helper.towerDamageAtRange(range);
}
expectedDamage /= 2;

Using this algorithm, my code reported the following:

This position is in the upper right exit of the room. If you want to check out what the matrix looks like, I uploaded the portion that describes the exits. I also put the storage in there so that my zombies don't plow through a full storage.

The path of least resistance

In addition to using the safest entrance, it would be good to have our zombie take the best path, only attacking walls as necessary and going for the weakest walls. A simple and effective algorithm for describing these costs is to find the wall with the most hits and grade all walls based on the number of hits they have relative to that wall.

let walls = this.room.findStructures<Structure>(STRUCTURE_WALL)
    .concat(this.room.findStructures<Structure>(STRUCTURE_RAMPART));
if (walls.length > 0) {
    let highestHits = _(walls).sortBy("hits").last().hits;
    for (let wall of walls) {
        matrix.set(wall.pos.x, wall.pos.y, Math.ceil(wall.hits * 10 / highestHits) * 10)
    }
}

Using our test room as an example, here is what the costs would look like near the entrance our zombie has picked:

Here is the portion of the room that the matrix is describing:

The 1 is where the zombie will enter the room. All f values represent 0xff which means they are describing positions we want to be impassible. These are the exits we've blocked off and the storage. The other non-0 values are describing the walls. Most are 9 and one is an 8. The 8 is the wall that the zombies have been attacking. Our algorithm will actually make these values something like 80 or 90, but I wanted to make the matrix more readable.

Based on these costs, our zombie should at least be smart enough not to waste his time running into a wall.

Building the creeps

I use the expectedDamage value I calculated before to decide how to build my creeps and what boosts to use. If the value is 0 (no towers), it builds a very small creep that doesn't get boosted. Anything above that, it will build a 50-part creep that can move once every other tick. The number of heal parts used scales with the amount of damage. Here is an example for a situation where the expected damage is less than 240:

if (this.memory.expectedDamage <= 240) {
    let healCount = Math.ceil(this.memory.expectedDamage / 12);
    let dismantleCount = 33 - healCount;
    return this.configBody({[WORK]: dismantleCount, [MOVE]: 17, [HEAL]: healCount })
}

At 240 expectedDamage this would build a creep with 13 work, 17 move, and 20 heal parts. Any more than that and the configuration would switch based on how much can be healed with boosted tough and heal parts. At greater than 1600 damage it will just disable the operation and call in the bigger guns (RaidOperation.ts).

There should also be a time limit to ZombieOperation, if it hasn't made progress within 10000 ticks or so, it should uprade to RaidOperation.ts. as well.

Finally, there should be an algorithm where expectedDamage is increased if a zombie dies an early death. This will handle situations where defense creeps are being spawned. A zombie can take a look at nearby creeps and add the damage it would be getting from attack parts it finds within a range of 1 and ranged attack parts it finds within a range of 3.

Testing

Off to a rocky start

The first zombie didn't do so hot. In true Zombie style, he completely ignored my pathfinding cost matrix and picked his own entrance. Dadou's 12-gauge Remington towers made short work of him.

I started to suspect that (gasp) there was a bug in my code. I won't lie, it took me about 30 minutes to find that issue, I was stumped. It turns out it was something really simple, I calculated a path but then forgot to have the creep take that path instead of its default path.

Doing better

This gif demonstrates the intended behavior so far:

Back-to-back action

It would be good to enjoy zombies in the same way as episodes of It's Always Sunny In Philidelphia on Netflix. And by that I mean one right after the other.

As you can see, the the previous zombie times out right as the next one arrives. It can do this by just taking note of how many ticks it has left when it first arrives at the room:

if (!zombie.memory.setPrespawn && zombie.pos.isNearTo(fallback)) {
    zombie.memory.setPrespawn = true;
    this.memory.prespawn = 1500 - zombie.ticksToLive;
}

We can use that value with our general purpose spawning function (mission.headCount). It can accept a prespawn value as an optional argument:

this.zombies = this.headCount("zombie", this.getBody, max, {
        memory: {boosts: this.getBoosts(), safeCount: 0},
        prespawn: this.memory.prespawn, // <--- used here
        skipMoveToRoom: true,
        blindSpawn: true
});

Doing this begins spawning the next creep that many ticks early (accounting for creep spawn time as well).

Another test case

Because my first test case stands to take a little while, I decided to try it out on another room.

I used the opportunity to add a bit of code that would have it first see if a path to the spawn is possible, and use whatever entrance accommodates that path.

Everything goes as planned, except for the fact that it just stands next to the spawn awkwardly at the end. This is because I forgot to actually add that code (^_^'''), it was just a couple more lines.

Conclusions

This ended up being a simple but effective algorithm when used in the right case. Given enough time, this code will successfully clear a large proportion of rooms, particularly rooms owned by zombie players. It turns out that the first room's walls are at 19m hits, so in that case it might actually be better to use a quicker solution. I expect ZombieOperation to take 1-2 days to take down the room. I'll update this when it is complete to let you know how long it actually took. Even zombie players can get notifications and come back to safe-mode and ruin your picnic.

There are a lot of ways this could be improved. It might be worthwhile to give the zombie some teeth for attacking defender creeps. Perhaps it could be toothless by default and teeth can be added as necessary.

How would you improve this algorithm? I've posted this on reddit to allow for a discussion.

If you enjoyed this article, you might consider checking out the one I wrote about moveTo. All my code is public here in this github repository if you want to have a look around. If you haven't yet tried Screeps, do it!