Improving on moveTo's efficiency

The default function for moving creeps around is highly versatile and fairly efficient with the 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. 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 is to implement 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:

The tests

I've spawned two creeps named blindMoveTo and travelTo. There 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. 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.