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.