So here is one more interesting performance-related challenge that caused by permanent flying bonus that for example Angel Wings provide.
Air layer is available everywhere and if we set rule that hero can go into air from every land tile path calculation become really slow on large maps.
This isn’t really a problem in case of spells because they only give bonus for one turn and we only need to use air layer within that turn which most of time only let you cover one part of map.
It’s what everyone was worried about and @AVS suggested to make an default option to only let hero go into air layer from node he standing on. This possible make pathfinder to choose less MP effective paths in some cases, but also decrease pathfinding complexity a lot.
In addition to that I get few more ideas for future optimization:[ul]]Instead of limiting transition into air level for initial node only we may instead only allow it within N tile radius around initial node. This way even if we can’t make full calculations for whole map we can still do that for 10-15 tiles around hero which going to make that limitation really hard to notice most of time./:m]
]Also if there going to be more or less permanent pathfinder instance then it’s may also “remember” how long last paths calculation take and increase/decrease that radius depend on it./:m][/ul]
I’m need about same logic for heroes on “patrol” so it’s would be easy to implement.
Also just in case there is more ideas how to keep complex path calculations in place without making player experience worse:
[ul]]@Ivan suggestion. Do path calculations in separate thread so it’s won’t lock UI./:m]
*]@Ivan suggestion. Give client access to path information before calculation is fully finished. So pathfinder can create graph in own background thread while client going to get updated copy of graph every N milliseconds.
So client may almost instantly get access to part of graph that can be considered “ready”. Once player move cursor on tile that not yet available in client copy of graph client getting updated copy from pathfinder or starting to wait till pathfinder consider that tile as “ready”/*:m][/ul]
PS: Version that @AVS suggested already in my branch:
github.com/vcmi/vcmi/commit/1bc … 74e7127816