MantisBT - VCMI
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0002454VCMIAI - Adventure Mappublic2016-08-10 21:392022-04-12 11:04
ReporterSXX 
Assigned ToSXX 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version0.98g 
Target VersionFixed in Version0.99 
Summary0002454: AI turn extremely slow when wandering
DescriptionThis one is from one of saves @Povelitel passed me.
Going to profile it soon.

Map is called "This is legion 5". Player is Orange.
Steps To Reproduce
Additional Information
TagsNo tags attached.
Relationships
related to 0001713closed Warmonger very long turn AI - SectorMap memory leak 
related to 0002431closed SXX Crash during AI turn. (battle in crypt) 
Attached Fileszip AISTUCK.zip (2,315,709) 2016-08-10 21:39
https://bugs.vcmi.eu/file_download.php?file_id=2510&type=bug
zip callgrind.zip (380,764) 2016-08-10 22:40
https://bugs.vcmi.eu/file_download.php?file_id=2511&type=bug
zip callgrind_25fd4d85e24f60552948ea10ffb47acaddc8ba8c.zip (267,130) 2016-08-11 08:23
https://bugs.vcmi.eu/file_download.php?file_id=2512&type=bug
zip callgrind_2.zip (264,928) 2016-08-11 08:35
https://bugs.vcmi.eu/file_download.php?file_id=2513&type=bug
Issue History
Date ModifiedUsernameFieldChange
2016-08-10 21:39SXXNew Issue
2016-08-10 21:39SXXStatusnew => assigned
2016-08-10 21:39SXXAssigned To => Warmonger
2016-08-10 21:39SXXFile Added: AISTUCK.zip
2016-08-10 22:40SXXFile Added: callgrind.zip
2016-08-10 23:23SXXRelationship addedrelated to 0001713
2016-08-10 23:24SXXNote Added: 0006545
2016-08-11 00:09SXXNote Added: 0006546
2016-08-11 00:09SXXNote Edited: 0006546bug_revision_view_page.php?bugnote_id=6546#r3194
2016-08-11 00:27SXXAssigned ToWarmonger => SXX
2016-08-11 01:03SXXNote Added: 0006547
2016-08-11 07:29AVSNote Added: 0006548
2016-08-11 08:23SXXFile Added: callgrind_25fd4d85e24f60552948ea10ffb47acaddc8ba8c.zip
2016-08-11 08:35SXXFile Added: callgrind_2.zip
2016-08-11 14:01SXXNote Added: 0006552
2016-08-11 14:02SXXNote Edited: 0006552bug_revision_view_page.php?bugnote_id=6552#r3203
2016-08-12 06:13SXXNote Added: 0006553
2016-08-12 06:13SXXStatusassigned => resolved
2016-08-12 06:13SXXFixed in Version => 0.99
2016-08-12 06:13SXXResolutionopen => fixed
2016-09-12 12:33SXXRelationship addedrelated to 0002431
2022-04-12 11:04PovelitelStatusresolved => closed

Notes
(0006545)
SXX   
2016-08-10 23:24   
While I'm not 100% sure I'll for now mark this one as related to 0001713 since extreme amount of time spent inside SectorMap code.
(0006546)
SXX   
2016-08-11 00:09   
So while I not yet sure why exactly AI spend so much time to decide where to move, but it's pretty clear that it's getFlaggedObjects inside SectorMap create most of load while checking for embarking options

Not yet decide what is best solution for this one since it's not only the place where this weird code is used.
(0006547)
SXX   
2016-08-11 01:03   
So for whatever reason VCMI::getFlaggedObjects didn't used "visitableObjs", but instead tried to get all the objects on map from scratch every time.

So I fixed this hog already:
https://github.com/vcmi/vcmi/commit/25fd4d85e24f60552948ea10ffb47acaddc8ba8c [^]

Even if now turn is few thousand times faster there no explanation why AI wander is slow slow so more investigation is needed.
(0006548)
AVS   
2016-08-11 07:29   
Post updated callgraph please
(0006552)
SXX   
2016-08-11 14:01   
(edited on: 2016-08-11 14:02)
So other directly related commit:
https://github.com/vcmi/vcmi/commit/b83dea20080b74b8e571f28c8616bb4efeef02d2 [^]

End up that AI have problem with map since it's have full visibility and there is 5500+ objects on it. For now we just optimized code so it's not as slow, but there is no big changes.
(0006553)
SXX   
2016-08-12 06:13   
Added more optimizations that let AI avoid checking every object when possible.
https://github.com/vcmi/vcmi/commit/7bdcd209e61ec9dfa69f459c7f630ca082e2e20b [^]

While there is still more to improve these changes are good enough for that particular case.