0002212: Loop detected while calculating AI move (visiting same tile)

Notes
(0005764) AVS (administrator) 2015-06-28 19:51	Version of VCMI? Logs? Mods used?

(0005765) peter_lemenkov (reporter) 2015-06-28 20:08	I'm using latest Git revision right now (90bf1a5a54b78946b6ca5e631ccb4f128a0d4375) but it triggered earlier. I'm not using any mods except "VCMI Essential Files" (whatever it is). As for logs they re quite simple - the entire console is flooded with something like that: ... Player 0 starting turn Another allied hero stands in our way Another allied hero stands in our way Another allied hero stands in our way Another allied hero stands in our way Another allied hero stands in our way Why do I want to move hero Aislinn to tile 13 21 0? Already standing on that tile! Another allied hero stands in our way Why do I want to move hero Aislinn to tile 13 21 0? Already standing on that tile! Another allied hero stands in our way Why do I want to move hero Aislinn to tile 13 21 0? Already standing on that tile! Another allied hero stands in our way ... The last two lines are constantly repeating until I kill the application.

(0005888) flandree (reporter) 2015-10-02 11:02	Can also confirm that this also happens for me with latest git version (273392752754a8d766cf3b80c02b5b0c49d8f64d)

(0006095) denspb (reporter) 2015-11-19 11:44	Yet another example on 98e version. On previous days there were some cases when there was some kind of repetitive data in logs, but then there was some guard condition that broke the loop at some point. VCMI_Client console logs contain only this repeating part: ---------------- const struct TerrainTile __thiscall CGameInfoCallback::getTile(class int3,bool) const: 113 123 0 is not visible! class std::vector<class CGObjectInstance const ,class std::allocator<class CGOb jectInstance const *> > __thiscall CGameInfoCallback::getVisitableObjs(class int 3,bool) const: 113 123 0 is not visible! Another allied hero stands in our way Another allied hero stands in our way --------------

(0006096) denspb (reporter) 2015-11-19 11:46	File "Saves.rar" attached, VCMI version is 0.98e.

(0006099) denspb (reporter) 2015-11-19 16:27	One more instance here. This time it was not the endless loop, it just took about several minutes to proceed. I had the cartographer, so I could see that the AI player had 6 heroes on 1 segment of the road between two cities - that might be the cause.

(0006142) SXX (administrator) 2015-12-04 15:55	Currently AI performs really badly when heroes are blocked. Reason is that code that decide what to visit is super ineffective and go through all objects on map. When AI moving just fine it's hard to notice, but once hero blocked AI re-check these objects dozens of times that take extremely long time on slow hardware. I'm working on it btw.

(0006143) denspb (reporter) 2015-12-04 17:06	In other game I had part of the map opened, and I saw 6 or 7 computer heroes sitting on one segment of the road going through swamp when I saw this message.

(0006151) SXX (administrator) 2015-12-08 04:46 edited on: 2015-12-08 04:49	BTW I can't reproduce infinite loop with current git using saves provided by bug creator. (Autosave_51.vcgm1 Autosave_51.vsgm1)

(0006152) SXX (administrator) 2015-12-08 04:50 edited on: 2015-12-08 04:50	@denspb for some reason I unable to load your save. If you met problem one more time please upload new one.

(0006167) SXX (administrator) 2015-12-09 14:01	So I find at least one more problem that cause loops in subterranean gate. It's issue with SectorMap::firstTileToGet. Problem is tricky: - AI decide to visit some object while using sector map. - firstTileToGet return him gate position. - Hero go into gate and appear on other side of gate. - Now something happen and VCAI decide to not continue that movement. - It's select new object to visit that now on other side of gate. - firstTileToGet tell him go into gate he stay on. - Hero go inside gate and then it's repeat... Now hero is staying on teleporter and just attempt to visit those two objects indefinitely. I suppose sectormap code may also cause issue with loop when one of subterranean gate exits are blocked by friendly hero because it's doesn't check if exit is clear and I'm not sure that "clear way" goal work properly.

(0006168) SXX (administrator) 2015-12-09 14:04	So to properly solve that I'll need to learn how VCAI actually work and find out in what situation we need to use something like SectorMap and when we should move more code into pathfinder. From what I see now usage of shipyard when no boat available is good use case of something like sector map, but teleports probably shouldn't be handled there at all.

(0006171) Warmonger (administrator) 2015-12-09 16:23	The issue is that AI can't properly deduce (monster) danger through gates / portals. So it sees free path at one side and dangerous monster once it reaches the other side, going bakc and forth. The proper implementation of paths through gates would effectively duplicate Pathfinder.

(0006172) denspb (reporter) 2015-12-09 17:00	Sidenote: you can also add defense-in-depth check, that would count time or number of iterations spent in pathfinding, and abort calculations if they take too long. You can also dump current state of search to logs in this case for easier debugging. That would ruin some AI turns, but would remove the showstopper.

(0006173) SXX (administrator) 2015-12-09 17:12	@denspb This is not pathfinding issue, but logical error that together with free teleporter make it keep in loop. Also if there is broken code there shouldn't be workarounds: broken code have to be fixed or commented out. Also I'll try to check your issue, but likely save is affected by other bonus corruption bug so if you'll met issue one more time please upload new save. @all BTW can we please continue talk in 0002119? Because current issue posted by @peter_lemenkov is fixed. It's was related to completely unrelated bug.

Issue History
Date Modified	Username	Field	Change
2015-06-28 14:02	peter_lemenkov	New Issue
2015-06-28 14:02	peter_lemenkov	File Added: Autosave_51.vcgm1
2015-06-28 16:52	peter_lemenkov	File Added: Autosave_51.vsgm1
2015-06-28 19:51	AVS	Note Added: 0005764
2015-06-28 19:54	AVS	Assigned To	=> AVS
2015-06-28 19:54	AVS	Status	new => confirmed
2015-06-28 19:55	AVS	Severity	minor => major
2015-06-28 19:55	AVS	Reproducibility	have not tried => N/A
2015-06-28 19:55	AVS	Category	Other => AI - Adventure Map
2015-06-28 19:55	AVS	Product Version	=> 0.98
2015-06-28 19:55	AVS	Assigned To	AVS => Warmonger
2015-06-28 19:55	AVS	Status	confirmed => assigned
2015-06-28 20:08	peter_lemenkov	Note Added: 0005765
2015-10-02 11:02	flandree	Note Added: 0005888
2015-11-19 11:44	denspb	Note Added: 0006095
2015-11-19 11:45	denspb	File Added: Saves.rar
2015-11-19 11:46	denspb	Note Added: 0006096
2015-11-19 16:27	denspb	Note Added: 0006099
2015-12-04 15:55	SXX	Note Added: 0006142
2015-12-04 15:56	SXX	Relationship added	related to 0002326
2015-12-04 17:06	denspb	Note Added: 0006143
2015-12-08 04:46	SXX	Note Added: 0006151
2015-12-08 04:49	SXX	Note Edited: 0006151	View Revisions
2015-12-08 04:50	SXX	Note Added: 0006152
2015-12-08 04:50	SXX	Note Edited: 0006152	View Revisions
2015-12-09 14:01	SXX	Note Added: 0006167
2015-12-09 14:04	SXX	Note Added: 0006168
2015-12-09 14:47	SXX	Relationship deleted	related to 0002326
2015-12-09 14:48	SXX	Relationship added	duplicate of 0002051
2015-12-09 14:54	SXX	Summary	Loop detected while calculating AI move => Loop detected while calculating AI move (visiting same tile)
2015-12-09 16:23	Warmonger	Note Added: 0006171
2015-12-09 17:00	denspb	Note Added: 0006172
2015-12-09 17:12	SXX	Note Added: 0006173
2016-09-24 08:51	SXX	Status	assigned => resolved
2016-09-24 08:51	SXX	Fixed in Version	=> 0.99
2016-09-24 08:51	SXX	Resolution	open => fixed
2016-09-24 08:51	SXX	Assigned To	Warmonger => SXX
2022-04-12 11:04	Povelitel	Status	resolved => closed