Forum index VCMI Project - Heroes 3: WoG recreated
Forum of the project aiming to recreate best turn-based strategy ever!

FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  StatisticsStatistics
RegisterRegister  Log inLog in  AlbumAlbum  DownloadDownload

Previous topic :: Next topic
Pathfinding, movement and Fly / Water walking challenges
Author Message
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-10-23, 23:46   Pathfinding, movement and Fly / Water walking challenges

Working on it so updated my page on wiki:
http://wiki.vcmi.eu/index...ng_and_movement
Some very basic refactoring can be found there:
https://github.com/ArseniyShestakov/vcmi/tree/newMovementSystem

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. :evil:

Going to post updates there once get something working.
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-10-24, 12:03   3D Pathfinding

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, 14:44; edited 1 time in total  
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-10-24, 12:32   Some example

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:
Code:
* 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:
    Code:
    * v *
    * x *
    v b b

  • 8 for flying:
    Code:
    * * *
    * x *
    * * *

  • 3 for water walking:
    Code:
    n n n
    n x n
    b * *


example.png
Hero with 8 neighbour tiles around
2976 Time(s) 109.14 KB

Last edited by SXX on 2015-10-24, 18:19; edited 1 time in total  
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-10-24, 12:46   

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. :-P
  • Air layer
    Code:
    * * * // ground
    * x * // ground
    * * * // water
    * * * // water + whirlpool
    * * * // water + whirlpool
    * * * // water
    * * * // ground
    * * * // ground

  • Land layer
    Code:
    * 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

  • Water walking layer
    Code:
    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

  • Sail layer
    Code:
    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
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-10-24, 13:55   

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.
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-03, 03:01   

Pull request for this work:
https://github.com/vcmi/vcmi/pull/133
 
     
Warmonger 
VCMI programmer


Age: 27
Joined: 07 Jun 2008
Posts: 1530
Location: Warsaw, Poland
Posted: 2015-11-03, 06:48   

I was going to review all of these (and Wiki talk)... just can't find the time :V
_________________
Think twice if you really need to send me private message. Use public forum for general questions.
DJ Warmonger blog
beegee wrote:
Warmonger, you are the best!
 
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-03, 07:46   

Warmonger wrote:
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. :-)
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-04, 13:13   

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"


PS: Version that @AVS suggested already in my branch:
https://github.com/vcmi/vcmi/commit/1bc335323d8a4618eea31341bdf61474e7127816
 
     
Ivan 
VCMI programmer

Age: 25
Joined: 08 May 2009
Posts: 1438
Location: Ukraine
Posted: 2015-11-04, 23:17   

Quote:
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.
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-05, 01:28   

@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.
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-05, 02:16   

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. :-)

pathfinding_edge_case.jpg
44 Time(s) 64.16 KB

SXX_pathfinding_edge_case.h3m
Download 62 Time(s) 1.85 KB

 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-05, 05:44   

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.
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-07, 23:14   

Serious issue occur within rewriting cursor handling code using pathfinding information. :shock:
HoMM assets don't have cursor icons for my super-powerful pathfinding! :roll:

PS: Also find out that sail icon misplaced. It's always looked weird for me.
 
     
SXX 

Age: 25
Joined: 04 Jul 2014
Posts: 291
Posted: 2015-11-18, 00:09   

So I'm almost finished my work on current branch:
https://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:
  • 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:
  • Separate thread branch: pull request #138
  • @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.
 
     
Display posts from previous:   
Reply to topic
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
Add this topic to your bookmarks
Printable version

Jump to:  

Powered by phpBB modified by Przemo © 2003 phpBB Group
Template Chronicles modified by Nasedo modified by Tow.
© VCMI Team
Page generated in 0.09 second. SQL queries: 16