Spring RTS Engine

Another lag thread \o/
This one about pathing.

Attached replay, from ~33min to ~37min ismo's factory waypoint is set on top of a wreck. It seems whenever a few units try to reach the waypoint, it causes extreme lag.
When the units move away, the lag instantly stops.
Replay is with /luaui disable

http://www.abload.de/img/screen00320mxu3a.png
http://www.abload.de/img/screen003180yutu.png

Before everybody panic, notice that it only happens sometimes.
And very unlikely to be related to 9.728 / 9.729

"Humping lag" is a misnomer (but I'm sure the name will stick anyway), humping is just the collision detection trying to keep units from getting too close to obstacles.

The real cause is a degenerate condition that all pathfinders suffer from, which is that when a chosen goal location is unreachable from a unit's POV they will explore the maximum allowed number of nodes (effectively the entire map except Spring limits this, notice all the red lines on screen003180yutu) triggering a CPU spike. When many units do this at once, the spike becomes a mountain. It is the same issue as http://springrts.com/mantis/view.php?id=3594 or http://springrts.com/mantis/view.php?id=2426 and totally unrelated to game code.

I thought the actual collision cause the lag.
So maybe "repathing lag" is more correct name.

when a chosen goal location is unreachable from a unit's POV they will explore the maximum allowed number of nodes (effectively the entire map except Spring limits this, notice all the red lines on screen003180yutu) triggering a CPU spike.

Ok, so it could happen not only with humping units but also with units going large distance and not finding a way?

With the humpers it is reproduceable though.
Those units are already as close to their destination as possible. They can not stand ON the wreck or atop each other.
So maybe if the engine notices a unit is already very close to its target and after a while is still trying to reach it, the pathfinder should just "time out" for that unit? Maybe many collisions in small timeframe (=humping) could make it time out faster.
Sometimes a unit might not reach its unreachable target superexcactly but think player can live with that.

I see 3 solutions:

• Get rid of the estimators and replace them with a proper mipmap approach. atm the estimators call each the CPathFinder to create their lower res pathmap, instead this should be just done once in high res and then via a minmax mipmap algo reduced to lower res.
  (I already tried to implement this but wanted first to create an unified interface for CPathFinder & CPathEstimator, but didn't commit the changes early enough so it was breaking quite fast and at the end the whole pathfinder didn't worked anymore)
• cache unreachable paths somehow (don't got an idea how yet)
• instead of pathing from the unit to the targetpos, try also to path from the targetpos to the unit, e.g. if targetpos is in water, on a hill, ... this will very fast finish and so can work as early-out for the pathfinding

knorke wrote:Ok, so it could happen not only with humping units but also with units going large distance and not finding a way?

yes, see eg. http://springrts.com/mantis/view.php?id=3602

jK wrote: can't you cache unreachable paths? e.g. divide the map in 16x16 bigger squares (than pathmap res) and then cache which are reachable from each other.

Yes, but:

1) the cache would constantly be invalidated (explosions, buildings, terraforming, ...) so it would always need background maintenance
2) the cache would be only _very_ approximately correct if you picked a single representative spot per square to determine reachability, more spots means it would take more CPU to rebuild and maintain and the break-even point would be hard to determine
3) the situation here occurs mostly when unit and obstacle(s) are already within the same square, it would be more useful for a case like #3602

jK wrote: instead of pathing from the unit to the targetpos, try also to path from the targetpos to the unit, e.g. if targetpos is in water, on a hill, ... this will very fast finish and so can work as early-out for the pathfinding

That makes pathfinding twice as expensive in the general case where a path does exist (and it cannot be assumed the backward search would meet the forward search in the middle), so it's not a good early-out condition IMO.

Kloot wrote:

instead of pathing from the unit to the targetpos, try also to path from the targetpos to the unit, e.g. if targetpos is in water, on a hill, ... this will very fast finish and so can work as early-out for the pathfinding

That makes pathfinding twice as expensive in the general case where a path does exist (and it cannot be assumed the backward search would meet the forward search in the middle), so it's not a good early-out condition IMO.

Yeah it's not perfect but couldn't it i.e. limited to the case when the lowest estimator fails? Neither do you need to path the whole way from targetpos->unit, you can just check if it is on an `island` and skip if so.

knorke wrote:So maybe if the engine notices a unit is already very close to its target and after a while is still trying to reach it, the pathfinder should just "time out" for that unit?

Already exists in some form, but it's too sensitive to small movements currently.

jK wrote:Yeah it's not perfect but couldn't it i.e. limited to the case when the lowest estimator fails? Neither do you need to path the whole way from targetpos->unit, you can just check if it is on an `island` and skip if so.

That would help the long-distance (#3602) situations but those aren't very problematic to begin with: the lowest-resolution estimator block size is 32x32 so even full-map searches are usually _fast_ and can not cause crippling spikes. OTOH an "island" test (if it did not use some sort of cache) would most easily be implemented via floodfill which is on the same order of complexity as pathfinding without a heuristic --> no gain.