Working on it so updated my page on wiki:
wiki.vcmi.eu/index.php?title=Use … d_movement
Some very basic refactoring can be found there:
github.com/ArseniyShestakov/vcm … mentSystem
Feel free to share any thoughts. Maybe I must do some dirty-hacky implementation instead as proper one not really needed for single player and map testing. 
Going to post updates there once get something working.
So long time ago original VCMI pathfinding developer(s ?) attempted to implement flying and water walking while keep using old 2D tiles map and obviously this didn’t work out. For quite some time I’m been thinking about solving the same issues and there is many problems if you attempt to utilize multiple different movement types while only have 2D tiles map.
Currently best solution I see for solving pathfinding issues it’s make pathfinder and movement work with 3D map representation instead of 2D. At moment there is one graph used for both maps levels (overground and underground), but each level represented as 2D tile map. What I want to do is turn each map level into several different layers:
This of course create some overhead and increase memory usage, but it’s not critical:
So here is some example to explain the difference of how it’s works now and and how it’s going to work in 3D. Some introduction:
x - hero
n - not used for this layer (we can ignore it and even not allocate this tile information in graph)
With current pathfinder he just have 8 neighbour tiles:
* v *
* x *
v b bWith 3D pathfinding hero with FLYING_MOVEMENT and WATER_WALKING bonuses will have 19 neighbour tiles in total:
[ul]*]8 for normal movement:
* v *
* x *
v b b/*:m]
*]8 for flying:
* * *
* x *
* * */*:m]
*]3 for water walking:
n n n
n x n
b * */*:m][/ul]
So here is example of how this whole map going to looks like when pathfinder go through all tiles.
Let’s pretend that whirlpool it’s just blocking object. 
[ul]*]Air layer
* * * // ground
* x * // ground
* * * // water
* * * // water + whirlpool
* * * // water + whirlpool
* * * // water
* * * // ground
* * * // ground/*:m]
*]Land layer
* v * // ground
* x * // ground
v b b // water
n n n // water + whirlpool
n n n // water + whirlpool
b b b // water
* * * // ground (connected to other side via air layer)
* * * // ground/*:m]
*]Water walking layer
n n n // ground
n x n // ground
* * * // water
n n n // water + whirlpool
n n n // water + whirlpool
* * * // water
n n n // ground
n n n // ground/*:m]
*]Sail layer
n n n // ground
n n n // ground
b * * // water
n n n // water + whirlpool
n n n // water + whirlpool
n n n // water
n n n // ground
n n n // ground/*:m][/ul]
Just in case want to notice: all of this won’t affect performance except in case when hero actually have those bonuses. Pathfinder won’t even allocate extra nodes in graph when specific movement type is not available for hero.
And once I get it working additional optimizations possible because in most cases when special movement types are used they only applied within one turn limit. So for example we’ll only calculate paths via air layer for bonus duration and likely it’s will be also possible to not allocate nodes in graph for every tile in air layer. Only exception within H3 game mechanics it’s artifacts that give permanent effect, but usually there is only two of them on whole map.
I was going to review all of these (and Wiki talk)… just can’t find the time :V
Don’t worry, you’ll have plenty of time.
There is still tons of work needed to make pathfinder respect all H3 movement rules, different bonus specific, etc. And even more work needed on client/server movement code. I think I’ll need at least 3 weeks to finish that work and probably more. 
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
Actually it should be possible for UI thread to access pathfinder data directly, without any copying or even locks.
Pathfinder marks every calculated node as “locked” ( part of A* algorithm). So any node that was marked as locked is guaranteed to be constant. This simple fact resolves pretty much all multithreading issues - there can be no race conditions with read-only data.
UI thread only needs to check if destination tile is locked. If it is - then all data that UI needs is ready and can be accessed without any issues. Othervice UI will have to wait for required node to lock. Should be rare event - e.g. after player selects a hero and quick enough to select a tile in another corner of the map.
@Ivan
This is sounds like a good solution. Copying would require some “locking” too anyway as there always can be can be edge cases when movement cost via one layer with greater distance (more tiles) is much cheaper than movement over shorter distance.
BTW there is edge case I talking about, introduction on what hero have:[ul]]Hero have Admiral’s hat. Yes I know it’s tricky artifact in H3, but for now we can just forgot./:m]]Basic fly spell that have 40% penalty. In H3 It’s maximum penalty, but VCMI should correctly calculate paths even if there going to be artifact that let you fly with 90% penalty./:m]
]Hero also have expert navigation skill./:m][/ul]Problem is that currently there is no priority support within pathfinder. So faster, but longer path always always built faster than shorter, but more expensive path via air. And of course we can’t consider tiles as “locked” after only shorter path found.
So I next thing I’m going to do is implement proper priority queue (though I’m still not 100% sure it’s cover every possible case). Almost sure Boost should have some ready-to-use and efficient code for that. 
So it’s interesting task as priority queue make path calculation slower due to sorting, but in same time it’s let pathfinder to be actually called A* and make possible to implement what Ivan suggested.
Still I won’t push it into branch for now as I wish to actually benchmark it because for test I only implemented it using std::priority_queue with std::vector.
Serious issue occur within rewriting cursor handling code using pathfinding information. 
HoMM assets don’t have cursor icons for my super-powerful pathfinding! 
PS: Also find out that sail icon misplaced. It’s always looked weird for me.
So I’m almost finished my work on current branch:
github.com/vcmi/vcmi/pull/133
It’s have most important things implemented or fixed, but unfortunately few things have to wait till other parts are ready:
[ul]]Cost calculations are wrong. I can’t fix it for now because server still using old code and it’s have no idea about layers. I’m think that for now it’s better to keep costs wrong, but same on both server and client as different costs going to break everything badly./:m]
]Castle gate support started, but not implemented on client/server./:m][/ul]Anyway once it’s merged there is already future work planned:
[ul]]Separate thread branch: pull request #138/:m]
*]@AVS suggested two nice ideas for pathfinder design:
Also want to share few ideas about possible pathfinding related optimizations. I’m not going to implement them anytime soon, but still want to share my thoughts.
[ul]*]This one is mainly for human players as animation take a while and most of time human players don’t interrupt their movement.
Trick is that we can start paths graph calculation before hero movement is finished. Basically we just fake changed game state inside pathfinder by ignoring currently moving hero and pretending it’s already stopped on last tile.
Though this one require additional changes as moving hero may change FoW state. So probably this one can only be used when FoW changes during movement not going to happen.
/*:m]
*]Other idea is to avoid pathfinder graph recreation when hero picking objects around. Usually those objects only accessible from from tile hero standing on. If hero don’t have fly bonus these tiles are dead end. So we can update old graph for these tiles only instead of recreating it from scratch.
Then when hero picked some object we start path calculation in new unlocked direction only. If we found that any of “locked” nodes from previous graph is touched by current calculation then we start full graph recreation, but if none of “locked” tiles touched we just merge new graph with old one.
Note. This one wouldn’t work when fly or water walking used (as one turn boundary depend on movement price) and will require changes in how CGPathNode store price. E.g we’ll have to store total cost instead of remaining MP, but this is feel like a good change even without that optimization now./*:m][/ul]
So thanks to @AVS we find way to boost code in my current branch a lot. I had some issues that AI being slow and he not only find two super-slow pieces of code within VCAI, but also helped me to find out what make pathfinder code slow.
I’m attach archive with valgrind’s callgrind data of calculatePaths before and after that commit:
github.com/vcmi/vcmi/commit/5ae … 30d82d20ab
You can view data using KCacheGrind / QCacheGrind. Please check readme for more details about performance testing.
End up that Bonus system shouldn’t be used for cases when there’s going to be tons of calls and using own static cache is best solution as selector creation is slow. With a bit of hacky code performance of pathfinder become 20-30% better (or even more).
pathfinder-callgrind-comparison.7z (726 KB)
For anyone who may be interested here is dumps from release build (with debug info).
It’s commit after all optimizations applied: 6dacb84404c25b7a5baadf793eceb3f0197359e8
It’s of course much faster than original code.
8_pathfinder_newopt.zip (603 KB)
So the first branch is merged. Now I’ll work a bit on stability issues (there is few issues cause crashes and stuck within AI that I likely responsible for) and then go back to pathfinder improvements.
Another pathfinding / monolith probing / AI issue:
On map Reunion (my favourite 
) there’s a complex network of one-way teleporters which AI needs to explore in order to complete the map. However, it has single one-way entry monolith and AI tries it only once. All following heroes of target player get stuck in black Keymaster area (62,60,1).
Not sure how it should be solved, though. Especially due to “channel probing” complexity.
Mind if you try to test it, it might go smooth until like month 6 or later.
(WoG) Reunion very hard (edit).h3m (162 KB)
Hosting provided by DigitalOcean
