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:
- Air. Only accessible for hero with FLYING_MOVEMENT bonus.
- Land layer.
- Water walking layer.
- Sail layer. It's where all objects located on water belongs as they can be only visitable by hero on boat.
In the end instead of 2D tile map we'll have 3D map that A* can handle great include hard choices on cost calculations that impossible to solve when each X,Y coord (tile) may only have one previous tile: e.g when hero have FLYING_MOVEMENT and we try to reach water tile.
This of course create some overhead and increase memory usage, but it's not critical:
- Normal non-water tile will only have two layers (Land and Air)
- Water tile will have 4 layers.
It's basically one more layer for each kind of movement.
Last edited by SXX on 2015-10-24, 13:44; edited 1 time in total
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)
* is accessible tile
v - visitable tile
b - blocked tile
With current pathfinder he just have 8 neighbour tiles:
* v *
* x *
v b b
With 3D pathfinding hero with FLYING_MOVEMENT and WATER_WALKING bonuses will have 19 neighbour tiles in total:
8 for normal movement:
* v *
* x *
v b b
8 for flying:
* * *
* x *
* * *
3 for water walking:
n n n
n x n
b * *
example.png Hero with 8 neighbour tiles around
3358 Time(s) 109.14 KB
Last edited by SXX on 2015-10-24, 17:19; edited 1 time in total
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:
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.
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.
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:
@Ivan suggestion. Do path calculations in separate thread so it's won't lock UI.
@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"
Age: 25 Joined: 08 May 2009 Posts: 1438 Location: Ukraine
Posted: 2015-11-04, 23:17
So pathfinder can create graph in own background thread while client going to get updated copy of graph every N milliseconds.
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.
_________________ Send PM if there is something that needs my attention.
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:
Hero have Admiral's hat. Yes I know it's tricky artifact in H3, but for now we can just forgot.
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.
Hero also have expert navigation skill.
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.
So I'm almost finished my work on current branch:
It's have most important things implemented or fixed, but unfortunately few things have to wait till other parts are ready:
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.
Castle gate support started, but not implemented on client/server.
Anyway once it's merged there is already future work planned:
@AVS suggested two nice ideas for pathfinder design:
- Replace "addNeighbours" / "addTeleportExits" with iterators. This way I can move many of layer-specific checks out of loop that currently handle neighbour tiles.
- Implement pathfinder interface within CGObjectInstance. This is needed to avoid dynamic_cast usage in following cases: teleporting include castle gate support, garrisons and town accessibility and probably ignored objects (events).
Small redesign of TeleportDialog so it's allow choose exits for teleporters with multiple exit points (whirlpools).
Of course there is going to be work for path validation and reimplementing movement code on both client and server (explained on wiki), but first I'll likely fix things above.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You can download files in this forum