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 
VCMI programmer

Age: 25
Joined: 04 Jul 2014
Posts: 358
Posted: 2015-11-19, 02:00   

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


  • 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.
 
     
SXX 
VCMI programmer

Age: 25
Joined: 04 Jul 2014
Posts: 358
Posted: 2015-11-21, 08:23   

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:
https://github.com/vcmi/vcmi/commit/5ae6225ebcb38f693dab8824d8983730d82d20ab
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
Download 59 Time(s) 726.01 KB

 
     
SXX 
VCMI programmer

Age: 25
Joined: 04 Jul 2014
Posts: 358
Posted: 2015-11-22, 06:47   

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
Download 67 Time(s) 603.08 KB

 
     
SXX 
VCMI programmer

Age: 25
Joined: 04 Jul 2014
Posts: 358
Posted: 2015-11-24, 12:08   

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. :-)
 
     
Warmonger 
VCMI programmer


Age: 28
Joined: 07 Jun 2008
Posts: 1541
Location: Warsaw, Poland
Posted: 2016-11-29, 17:52   

Another pathfinding / monolith probing / AI issue:

On map Reunion (my favourite :roll: ) 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.

Reunion stuck.png
20 Time(s) 208.89 KB

(WoG) Reunion very hard (edit).h3m
Download 21 Time(s) 162.14 KB

_________________
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 
VCMI programmer

Age: 25
Joined: 04 Jul 2014
Posts: 358
Posted: 2016-11-30, 20:53   

I definitely will. At moment one-way monoliths only used by pathfinder when it's known where exactly hero going to arrive so if there more than one exit this is obvious why it's not working.
 
     
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

Hosting provided by DigitalOcean
Page generated in 0.02 second. SQL queries: 14