Improving Traveler
It has been about 6 months since I released my first version of Traveler, and in the meantime I have been looking for ways to improve it.
I've added a few visuals to make traveler more interesting and useful. These visuals do not add any overhead to the cpu. Instead of having an option to show visuals or not, I've made it very clear in the code which statements are producing them, and you can comment them out if it is undesirable.
This is a new option that allows you to avoid making a new pathfinding call when your destination is only 1 position away from what it was previously. The new direction is just added to the path. This should be used with caution or with a higher range value as it could end up giving you a winding path, depending on how your destination is moving.
In this mode, swamps are given a cost of 1. So all passable tiles will have a cost of 1 regardless if they are a road, plain, or swamp. This is useful for creeps that carry energy on their trips to pickup the energy. If they aren't carrying anything, they won't incur fatigue even when moving over swamps. This lets you keep your roads clear for traffic that can benefit from the road.
This replaces options.ignoreStuck and represents the stuckCount at which your creep considers itself stuck. As before, stuckCount is incremented on ticks where your creep is trying to move but isn't going anywhere (and reset to 0 on ticks where it has successfully moved along the path). However, creeps don't repath automatically after reaching the stuckValue. Rather, there is a 50% chance they will repath after this happens. In my experience this results in better unstuck-behavior. There is a chance one creep will move first and that breaks up the congestion, and also stops them from all trying to move along the same detour at once. The default value is 2.
This lets you set a probability that your creeps will repath even with the same destination. It can be helpful in situations where your creeps need to reevaluate their path more often (perhaps a raiding situation where the costmatrix is changing). Setting it to 1 will make them repath every tick, .5 will give them a 50% chance of repathing, and .1 a 10% chance.
The basic algorithm that traveler uses hasn't changed much, but I spent some time investigating small ways that I could improve performance. Much thanks to all the people in #help who put up with my questions/tests. It is best to use the averages in the following graphs as just a rule of thumb, I discovered that there were order effects and there were also small things that might skew the results (like whether one creep gets "stuck" at the end because the other stopped in front of it).
I will follow the same battery of tests that I used in my examination of travelTo vs. moveTo;
This gif shows the new visualization that happens when a traveler finds a new path. This is really helpful for debugging and adds pretty much no overhead.
We don't see much difference here, the pathfinding was fairly quick for both versions and path-following ticks were pretty close. The spike at the end shouldn't be counted against oldTraveler, it was because the newTraveler creep had stopped in front of it after reaching the destination, after the "stuck timer" triggered it found a new path which brought it to the destination.
Oddly satisfying how they seem to fit each other like a glove, really. Had to double check that I really was using two different instances (here's a full gist of the testing code show instantiation).
I thought this would be a handy test, one of the potential weak points of Traveler is that it doesn't account for other creeps unless a creep determines that it is "stuck". If creeps need to repath often or they lose a lot of ticks waiting to move, that is a problem.
Because watching creeps move in real time can be like watching paint dry, this is a history view. The newTraveler creep is the one selected.
One thing that concerned me at first, you don't see the initial pathfinding bump in cost. This is because my profiler was averaging the performance over a span of 5 ticks. Since the creeps were idle for the ticks preceding the pathfinding call, this brought the average down. Unfortunately this is a necessary evil; my grafana app cannot check the status every tick. We would potentially lose information if we didn't do some kind of averaging. It should just be noted that the initial pathfinding costs could be mitigated due to this.
Pretty similar performance. Again, the last bump shouldn't be counted against oldTraveler, he was just the last one to arrive and had to do a stuck-repath. These creeps-included pathfinding calls tend to cost a lot because building the matrix is more intense in rooms with a decent number of creeps, and the cost of using the matrix is also higher. Overall, both performed well and both versions do a decent job of avoiding getting stuck as long as the roads are free of idle creeps.
To make sure the long distance pathing still worked as expected, I had them both go on another epic journey.
Both creeps were able to make the journey in one piece! There appears to be a much higher initial spike for newTraveler, but then it paths less often as well.
I discovered something unexpected in my testing, there were order effects that influenced performance. In all the previous tests, I called newTraveler's function first, and then oldTraveler's. Here is what you see when you zoom in:
newTraveler seemed to be consistently worse than oldTraveler. I spent a long time trying to figure out why this was the case, because I had made a few "optimizations" that should have given it slightly less overhead.
When I switched the order, I saw newTraveler now beat oldTraveler by quite a bit. After randomizing the order that the tests were performed, I saw this.
Much better! Overall, I found that on ticks where no pathfinding is needed, newTraveler was about .01 cpu faster, just over 5%. That may not seem like much, but with ~500 creeps moving each tick that comes to ~5 cpu!
Pathfinding performance seemed to favor newTraveler as well, but more systematic testing should be done to verify that.