Impossible paths

[Tiger]

It seems that the games continuously tries to find impossible paths (i.e. foot soldiers trying to attack a naval vessel that is out-of-range). As you can imagine, this creates massive lag even with small amount of units. In my scenario a ship was just outside a range of my ranged units, the units got as close as possible to the ship but couldn't walk any closer since there was water creating massive lag because the pathfinder tried to find an impossible path to the ship.

I think it would be nice to cancel the path finding if one cannot be found in an alloted time; or give an audio/visual warning on which units are stuck.

[agentx]

Actually path finding should even not start if the target is unreachable as the result is always a very costly full map scan. I had another effect recently while playing a random game on Alpine Valleys against 2 AIs. My CC was in the middle so I isolated one AI completely with a wall. Framerate instantly dropped to 2 fps.

Edited November 21, 2014 by agentx

[historic_bruno]

Philip's work-in-progress pathfinder had a fairly efficient reachability test, so that certainly could help, and there does need to be a limit to how often a unit can request a new path.

[agentx]

Well, there are different types of reachability:

Unit wants to go from land cell to another land cell, both not connected: No pathfinder needed, that's terrain analysis. The path can be blocked by water, mountains or other non-walkable cells. It helps to have a list of regions which are connected and the mean of transport (ship, feet).

Unit wants to go from island beyond shore into water: pathfinder should stop at first or nearest dee water cell and no repeat.

Unit wants to go from land cell to another land cell, obstructions can be non-movable (houses, etc), completely blocking the path or just some cells. If full blocking there is no need to run the pathfinder again as long as the house is still on the map. This can be solved by temporarily splitting a region into two and make the pathfinder listen to destroy events.

Or there are other units blocking cells or the path. Here a time limit makes sense.

I think the challenge is to tell the module asking the pathfinder, why the pathfinder failed and that module should be clever enough to not hammer the pathfinder with unsolvable requests. Basically a pathfinder response is success w/ path, partial success w/ partial path, permanently blocked by terrain, temporarily blocked by immobile obstruction or temporarily blocked by mobile obstacles with partial path if available.

On top the size of a unit matters, elephants and sieges should not get lost in a forest.

I'm not sure if temporarily blocked by wall should get a partial path or not. The player might want to destroy the blocker with his units or not. In case of an AI having it self locked out, I'm not sure too. But an AI should be clever enough to not build houses on the only way out of the village. Unfortunately that sounds more easy than it is. What should not happen are AIs randomly building structures on the map and destroying them because the pathfinder said so.

What I have in mind for Hannibal is taking the CC, creating a circle around and from 10-16 points on that circle let the pathfinder compute a path to the cc. Then you have a list of cells from multiple paths. I think building houses on cells which appear multiple times in that list is not a good idea. The idea is to make "streets" an obstruction for buildings.