Source Keeper Avoidance Fails to Find New Path

[rougeayrn]

A creep is trying to path long distance and also avoid source keepers, but runs into a case where it can't bypass the source keeper in room. Ideally, this should generate a completely new path using a different route, yeah?

In-room:

Map:

[glitchassassin]

It should, yes. I think the problem here is with the routing.

findRoute doesn't know that this passage is impassible. We are enriching the route by adding extra rooms, but the side rooms to the left will only get added if the top exit is on the right half of the border. Otherwise, it assumes the exit is probably the fastest route.

[glitchassassin]

All right - pushing out a provisional fix that adds all rooms adjacent to the route, if the creep is repathing because it's stuck. Give v1.3.11 a try and let me know if that resolves this issue.

[rougeayrn]

It doesn't look as if the changes respect routeCallback, which could lead to fallback routing choosing to path through an otherwise blocked out room, yeah?

Not respecting routeCallback: https://github.com/glitchassassin/screeps-cartographer/blob/0ebd2fbecd080ef0d0d285c31b3f3327e8bf97c8/src/lib/WorldMap/findRoute.ts#L43

Potential solution: Object.values(Game.map.describeExits(route[i].room)).forEach(room => if (actualOpts.routeCallback?.(room, route[i].room) !== Infinity) rooms.add(room));

[glitchassassin]

Good call. We're invoking that callback a lot, we can make it a bit more efficient. I'll have a fix ready shortly

[glitchassassin]

v1.3.12 pushed out

[rougeayrn]

Looks gorgeous to me! Will test when I get a chance.

[rougeayrn]

Mkay! So I updated to the most recent. Here's where we are at: It is trying to get to the "target" room from the "start" room. Originally, it tried the green path, realized it'd be stuck by a source keeper, and repathed (orange path) into the unexplored room to the north, realizing that it is not safe for measly 1M creeps. Upon the creep's replacement, it failed to find a path, spending a variable 2-7 CPU a tick. There is a cheap-ish path (blue line), but it's failing to find it.

[glitchassassin]

Hmm. Best solution I'm coming up with at the moment: start from the set of rooms in the found route (maybe with the heuristic enhancement as an improved baseline) and floodfill (breadth-first) to add rooms up to maxRooms. For shorter paths like this we should be fine; sufficiently long paths will probably still run into issues. If we avoid floodfilling from highway rooms we can cut down some search space.

There's probably no reason not to do this by default; my original theory was that limiting rooms would save CPU as PathFinder wouldn't need to search outside the route, but I suppose I can measure that and find out for sure.

I'll test further in the morning.

[glitchassassin]

https://user-images.githubusercontent.com/7684744/198312459-50d6a1dd-8651-4fca-98ba-a1b8970f77b9.mp4

Sample animation of expanding the rooms with floodfill

[glitchassassin]

Did some analysis with randomly-generated routes on a private server, just to check my theory. The heuristics to enhance findRoute do slightly increase CPU, but they also tend to find better paths than simple floodfill, so seem to be worth the effort.

[glitchassassin]

that is, heuristics + floodfill are better than just floodfill

[glitchassassin]

All right, v1.3.16 pushed up. Let me know how it looks, and especially if you see any significant CPU impact with this change

[rougeayrn]

Thanks for the work on this issue! Will test and notify.

[glitchassassin]

Closing as no further issues reported