Improving on moveTo's efficiency

The default function for moving creeps around is highly versatile and fairly efficient with the right parameters. It can be difficult to improve upon. I've been using the same moveTo function pretty much since I started screepin'. I've tried to write one from scratch a couple times and I've had a difficult time beating it. There are at least a few reasons for why it is efficient, but I won't get bogged down with that here.

All that being said, eventually you'll outgrow moveTo. There are reasons to use your own Pathfinder.search call beyond CPU savings. For example, moveTo seems to have certain "bermuda triangles" where the pathfinding straight-up fails, most likely because maxRooms was reached too soon. I've been unable to use moveTo to travel long distances without using a waypoint system.

Waypoints seem like they should be unnecessary, so I took another stab at writing my own function. The result was something that was finally worthy to be used instead of moveTo. Here is what made a difference this time around:

• findRoute: To keep creeps from traveling into hostile rooms and to narrow down which rooms should be used for the search, I am using Game.map.findRoute. This means a better chance of finding a complete path
• serialization: I use a very similar path value to the one used by moveTo, it is just a string of directions.

Both functions can be located in my code by searching for "travelTo" (found within Empire.ts) and "blindMoveTo" (found within initCreepPrototype.ts).

The tests

I've spawned two creeps named blindMoveTo and travelTo. Their only behavior is to approach a flag that I am manually placing.

if (creepName === "blindMoveTo") {
    if (!creep.pos.inRangeTo(testFlag, 1)) {
        profiler.start("blindMoveTo");
        creep.blindMoveTo(testFlag);
        profiler.end("blindMoveTo");
    }
}
if (creepName === "travelTo") {
    if (!creep.pos.inRangeTo(testFlag, 1)) {
        profiler.start("travelTo");
        emp.travelTo(creep, testFlag);
        profiler.end("travelTo");
    }
}

Short distances: path length ~20

My hypothesis was that the difference would be more apparent with longer paths. To test this, I started out with something short.

As the graph shows, for shorter distances, moveTo is still looking pretty good. I'd be willing to bet that for very short distances, it is even better.

The lower graph breaks down the costs involved with travelTo. findAllowedRooms is my function that calls findRoute to narrow down which rooms are used. serializePath converts the path from an array of RoomPositions to a string. pathSearch tracks the cost of Pathfinder.search, and addStructures tracks the cost of modifying the cost matrix. These all happen on the same tick, I'm actually not sure why they appear to be on different ticks (must be an artifact of my profiler code). The nice thing is that they only need to be called once, so the general pathfinding/stuck algorithm seems to work.

For the remaining graphs, I've only included the upper graph, since the lower graph follows the same pattern for each test.

Medium distances: path length ~50

This test corresponds to the typical remove harvesting case. The circle is where they started and the square is where they ended up.

This graph might be a little misleading. The big spike was probably some garbage-collection event. If you exclude that outlier, they are still pretty fairly matched in efficiency. I'm not 100% sure on this, but I believe moveTo might do an additional pathfinding call for each new room it enters, which is why you see it peaking above near the end.

Long distances: Path length ~400

travelTo is winning so far, but not by much. This longer test is where it should shine. Not only should it be more efficient, but it has a better chance of finding a good path.

In this test they ended up taking two different paths (the green circle is moveTo, and the yellow circle is travelTo). I believe this is because moveTo got an incomplete path at first and went in the wrong direction. It actually never made it to the destination, it kept going back and forth between to paths and eventually suicided by going into Tav's room.

Finally we have some interesting differences. This test took place over a much longer time period, and we can see moveTo needs to repath quite a few more times whereas travelTo only needs to path once. The trade-off is that travelTo saves a much longer value to memory. Take a look at the memory objects used for each function:

moveTo keeps a much shorter path value in memory (up to 50).

travelTo's path can be quite long, I believe the maximum would be determined by the highest possible maxRooms value (16), which would be 800 characters (as the crow flies).

Another noteworthy observation from the graph above, travelTo's single pathfinding cost was half that of moveTo's. I believe this is because findRoute is starting to pay off cpu-wise.

Very long distances: Path length ~1200

I wanted to push the limit of how far these functions could go. I decided to make the destination room one of TheGeneral's remote harvest rooms. TheGeneral wrote all the A* pathfinding code being used, the real magic behind Pathfinder.search, so it seems like a fitting place to end up. I realized the moveTo would probably not do so well with avoiding enemy rooms.

Like a true Don Quixote, moveTo was happy to path right into Tav's rooms, die, and do it all over again.

I was very happy to see how far travelTo could take a creep, and without a single waypoint. The result here was a bit skewed because moveTo decided to take a 10 minute break in the middle due to an oversight in how I was spawning them. Since it didn't even make it half way to the finish before meeting an unfortunate fate in Tav's room, it was disqualified. Despite this, the average was still quite a bit lower for travelTo.

Conclusions

I'm sure there are still many ways to improve upon travelTo, but I'm very encouraged by the results so far. I may continue to use moveTo for short distances (like a spawn-refiller creep), and slowly transition the rest of my creeps to travelTo.

Here are the main observations that held up between tests:

• similar pathfinding costs for short distances, possibly some pathfinding savings due to using findRoute
• travelTo had slightly lower overhead per tick when disregarding pathfinding costs, blindMoveTo seem to hover at around .28 per tick and travelTo at around .25 per tick.
• highly preferable success rate in getting to the destination with travelTo

Overall, I don't actually expect this to make much of a difference for my total CPU use. The most typical case is the medium distance test, which was pretty darn close if you ignore that outlier. The real advantage is in the increased control we get from doing our own pathfinder search.

I'm still not caching any paths between creeps. I have a feeling that the only time this pays off is when more than one creep needs to use a given path at the same time. Pathfinder is relatively cheap if it doesn't need to be used very often, and I'm worried about the overhead of serializing/deserializing memory. I'd love to hear what other folks are doing and how they are squeezing more CPU out of path-caching.