Performance, Path Finding, Flamegraph

[tnmurphy]

Hi,

I sometimes seem to get into games where everything gets extremely slow - basically unplayable. One of my CPU's is at 100% when this happens.

I tried recording what was going on with perf and then I produced a flamegraph. ( https://www.brendangregg.com/FlameGraphs/cpuflamegraphs.html#perf )

A lot of the time seems to get spent in path planning - and allocating nodes of some kind relating to path planning and pushing things on and off a heap. I'm too clueless to do much but there was one area where I tried a diff that seemed to help a little - the cost of calling empty() on a vector many times seems quite high so I tried to arrange for a simple boolean instead that gets updated only when the vector is changed. This is just a suggestion of course and it doesn't deal with the major issues but I thought I would offer it up anyhow.

I'm also attaching the flamegraph for you to take a look at. This is from a skirmish game against a Cobra in the SK-Basingstoke map where there is possibly an especially challenging path. I've had the same thing on the Little Egyptian map (unsure of the name).

Best regards,

Tim

diff --git a/src/astar.cpp b/src/astar.cpp
index 858dabccb..08b3a3769 100644
--- a/src/astar.cpp
+++ b/src/astar.cpp
@@ -129,6 +129,7 @@ struct PathBlockingMap
 	PathBlockingType type;
 	std::vector<bool> map;
 	std::vector<bool> dangerMap;	// using threatBits
+	bool dangerMapEmpty;
 };
 
 struct PathNonblockingArea
@@ -167,9 +168,9 @@ struct PathfindContext
 		// Not sure whether the out-of-bounds check is needed, can only happen if pathfinding is started on a blocking tile (or off the map).
 		return x < 0 || y < 0 || x >= mapWidth || y >= mapHeight || pBlockingMap->map[x + y * mapWidth];
 	}
-	bool isDangerous(int x, int y) const
+	bool inline isDangerous(int x, int y) const
 	{
-		return !pBlockingMap->dangerMap.empty() && pBlockingMap->dangerMap[x + y * mapWidth];
+		return !pBlockingMap->dangerMapEmpty && pBlockingMap->dangerMap[x + y * mapWidth];
 	}
 	bool matches(std::shared_ptr<PathBlockingMap> &blockingMap_, PathCoord tileS_, PathNonblockingArea dstIgnore_) const
 	{
@@ -678,6 +679,7 @@ void fpathSetBlockingMap(PATHJOB *psJob)
 	{
 		// Didn't find the map, so i does not point to a map.
 		PathBlockingMap *blockMap = new PathBlockingMap();
+		blockMap->dangerMapEmpty = true;
 		fpathBlockingMaps.emplace_back(blockMap);
 
 		// blockMap now points to an empty map with no data. Fill the map.
@@ -701,6 +703,7 @@ void fpathSetBlockingMap(PATHJOB *psJob)
 					dangerMap[x + y * mapWidth] = auxTile(x, y, type.owner) & AUXBITS_THREAT;
 					checksumDangerMap ^= dangerMap[x + y * mapWidth] * (factor = 3 * factor + 1);
 				}
+			blockMap->dangerMapEmpty = dangerMap.empty();
 		}
 		syncDebug("blockingMap(%d,%d,%d,%d) = %08X %08X", gameTime, psJob->propulsion, psJob->owner, psJob->moveType, checksumMap, checksumDangerMap);

[past-due]

@tnmurphy Thank you for the investigation. There are some attempts underway at hopefully improving pathfinding, but nothing ready just yet.

Is this running the latest stable release (4.3.5), or a master branch build? (And if so, what commit?)
(If you’re experiencing this on a master branch build, can you try 4.3.5 and see if you can reproduce it as easily under the same circumstances?)

[past-due]

Another note: If you can get the game into a state where this is occurring, please create a savegame file (and upload a zip of the savegame folder here) - it should be possible to load the savegame and resume the problematic pathfinding processing in most cases, making it much easier to reproduce (and hopefully debug).

[tnmurphy]

Cheers for replying! I'm using master at this changeset:
458fbd9
skbasingstoke2.tar.gz
I uploaded my savegame - hope it's useful! For me this is excruciatingly slow every time I load it.

[dkargin]

Thank you for the save. I can check the performance of newer PF on that.
Regarding that flamegraph: it shows that any kind of good long PF queries are spending 60% (30% add, 30% remove) time adding to the priority queue, and ~20-30% on cost/collision checking.

The actual problem is the fact that there is no path at all, and A* must cover all the map before it proves that no path is possible (and return the path to the nearest point). Then this action is repeated for all other units. This problem can be caused by either units on different continents, or target tile is inside some area, isolated by structures.

[tnmurphy]

It sounds roughly like there's a need for a cache that lasts for one animation frame (sorry not sure the right terminology) - so that an unreachable tile gets marked as "unreachable" and then all the other units that try to get there will fail without going through the full effort until the next frame of the animation where something might have changed.

Obviously this is probably silly because one cannot guarantee that a place is unreachable from every where in the map without trying from everywhere and that might be almost as bad as going through all the units.

So you might want a tile-to-tile cache which sort of says "from tile X you cannot get to tile Y" and if you did that it might allow one to short-circuit the search