MantisBT - VCMI
View Issue Details
0000327VCMIMechanics - Adventure Mappublic2009-12-27 20:512015-12-24 19:05
Zamolxis 
SXX 
normalminoralways
assignedopen 
0.75 
 
0000327: Minor difference(s) in path calculation (last move rule + penalty from slow creatures)
There seems to be a minor difference in path calculations between H3 & VCMI. If you load the attached map, have Ivor visit the Redwood Observatory, then set path South-West as in the screeshots, you'll see that in H3 he will be able to go 1 tile further on the cobblestone road at the end of his path.

To be investigated if this is due to the visit to the Redwood Observatory, or due to rounding of terrain penalty.
IMPORTANT - see notes 579 & 580 from Phomm below - possible cause of the "bug" identified (plus separate bug spotted):

1. H3 seems to remove the diagonal penalty if the hero doesn't have enough MP to make the last move. If pathfinder sees that hero does not have enough MP for the last diagonal move (e.g.: 202 i/o 141*1.5=212 necessary) then it removes the diagonal penalty (but not the terrain one), so the formula becomes 100*1.5=150, which explains the 52 MP left for our hero when arriving on the road.

2. Another issue is that all heroes with units speed 3 as in the posted map (Ivor has dwarves - speed 3) have only 1480 MP but should have 1500. And in that tile where he should have 202, he actualy has 182. This is the reason of the difference between the movement bar in VCMI (1 pixel) and H3 (2 pixels) in that position, as I reported in note 534 (and it may actually be the bug mentioned by Tow in his final comment to note 533). To easily test this, just move Ivor on the vertical: in H3 he will move 10 tiles, while in VCMI he can only move 9 tiles.

(3) There could be a 3rd issue related (see my note 558 below), which is causing heroes to lose up to 3 tiles on a diagonal move containing different roads. But I'll have to check that after the above two are fixed, to see if we're dealing with a separate issue, or just a combination of the two above.
No tags attached.
related to 0000335closed Tow VCMI pathfinder seems to go for the most cost effective path at end of day, while H3 went for the most intuitive choice. 
?  VCMI_Tests.h3m (11,763) 2009-12-27 20:51
https://bugs.vcmi.eu/file_download.php?file_id=195&type=bug
jpg 2009-12-27_VCMISnowPath.jpg (25,179) 2009-12-27 20:52
https://bugs.vcmi.eu/file_download.php?file_id=196&type=bug
jpg

jpg 2009-12-27_H3SnowPath.jpg (27,826) 2009-12-27 20:52
https://bugs.vcmi.eu/file_download.php?file_id=197&type=bug
jpg

jpg 2009-12-31_VCMI-47.20.jpg (9,641) 2009-12-31 13:12
https://bugs.vcmi.eu/file_download.php?file_id=204&type=bug
jpg

jpg 2009-12-31_H3-47.20.jpg (10,823) 2009-12-31 13:13
https://bugs.vcmi.eu/file_download.php?file_id=205&type=bug
jpg

jpg 2010-01-01_H3MPleft.jpg (10,135) 2010-01-01 20:11
https://bugs.vcmi.eu/file_download.php?file_id=213&type=bug
jpg

jpg lastmove.jpg (10,834) 2010-01-01 21:14
https://bugs.vcmi.eu/file_download.php?file_id=214&type=bug
jpg

? _Movement_Test.h3m (12,043) 2010-01-01 23:58
https://bugs.vcmi.eu/file_download.php?file_id=215&type=bug
Issue History
2009-12-27 20:51ZamolxisNew Issue
2009-12-27 20:51ZamolxisFile Added: VCMI_Tests.h3m
2009-12-27 20:52ZamolxisFile Added: 2009-12-27_VCMISnowPath.jpg
2009-12-27 20:52ZamolxisFile Added: 2009-12-27_H3SnowPath.jpg
2009-12-27 20:54WarmongerCategoryGUI - Adventure Map => Mechanics - Adventure Map
2009-12-31 10:45TowNote Added: 0000533
2009-12-31 10:45TowStatusnew => feedback
2009-12-31 13:12ZamolxisNote Added: 0000534
2009-12-31 13:12ZamolxisFile Added: 2009-12-31_VCMI-47.20.jpg
2009-12-31 13:13ZamolxisFile Added: 2009-12-31_H3-47.20.jpg
2009-12-31 13:16ZamolxisNote Edited: 0000534bug_revision_view_page.php?bugnote_id=534#r511
2010-01-01 18:23IvanNote Added: 0000544
2010-01-01 19:23ZamolxisNote Added: 0000548
2010-01-01 19:43WarmongerNote Added: 0000549
2010-01-01 19:44ZamolxisIssue cloned: 0000335
2010-01-01 19:44ZamolxisRelationship addedrelated to 0000335
2010-01-01 20:11ZamolxisFile Added: 2010-01-01_H3MPleft.jpg
2010-01-01 20:17ZamolxisNote Added: 0000550
2010-01-01 21:14IvanNote Added: 0000555
2010-01-01 21:14IvanFile Added: lastmove.jpg
2010-01-01 21:15IvanNote Edited: 0000555bug_revision_view_page.php?bugnote_id=555#r525
2010-01-01 21:40ZamolxisNote Added: 0000556
2010-01-01 21:43ZamolxisNote Edited: 0000556bug_revision_view_page.php?bugnote_id=556#r529
2010-01-01 22:27IvanNote Added: 0000557
2010-01-01 23:58ZamolxisFile Added: _Movement_Test.h3m
2010-01-02 00:13ZamolxisNote Added: 0000558
2010-01-02 00:17ZamolxisNote Edited: 0000558bug_revision_view_page.php?bugnote_id=558#r531
2010-01-02 00:21ZamolxisNote Edited: 0000558bug_revision_view_page.php?bugnote_id=558#r532
2010-01-02 15:31OnionKnightNote Added: 0000564
2010-01-03 14:32majaczekNote Added: 0000567
2010-01-04 18:05majaczekNote Edited: 0000567bug_revision_view_page.php?bugnote_id=567#r538
2010-01-12 06:53phommNote Added: 0000579
2010-01-12 09:24phommNote Added: 0000580
2010-01-12 09:28ZamolxisNote Added: 0000581
2010-01-12 09:42ZamolxisNote Edited: 0000581bug_revision_view_page.php?bugnote_id=581#r546
2010-01-12 10:33ZamolxisSummaryMinor difference in path calculation (possibly due to visit to Redwood Observatory, or else due to rounding of terrain penalty) => Minor difference(s) in path calculation (last move rule + penalty from slow creatures)
2010-01-12 10:33ZamolxisDescription Updatedbug_revision_view_page.php?rev_id=548#r548
2010-01-12 10:33ZamolxisAdditional Information Updatedbug_revision_view_page.php?rev_id=550#r550
2010-01-12 10:38ZamolxisNote Edited: 0000581bug_revision_view_page.php?bugnote_id=581#r551
2010-01-12 10:40ZamolxisNote Edited: 0000581bug_revision_view_page.php?bugnote_id=581#r552
2010-01-12 10:42ZamolxisStatusfeedback => acknowledged
2010-02-11 22:32ZamolxisNote Added: 0000629
2010-02-11 22:32ZamolxisStatusacknowledged => confirmed
2010-05-30 14:50ZamolxisAdditional Information Updatedbug_revision_view_page.php?rev_id=840#r840
2015-12-24 19:05SXXAssigned To => SXX
2015-12-24 19:05SXXStatusconfirmed => assigned

Notes
(0000533)
Tow   
2009-12-31 10:45   
Strange.
At (51,15) (the last straight diagonal arrow) hero has 202 movement points. After making diagonal move onto road on snow he has 52 points (in H3), so the move took 150 points only.
It's the base cost for snow but for diagonal movement it should be multiplied by sqrt(2). So the correct cost is 212 which is more than hero has => movement should take all movement => no further move possible.

Road shouldn't give any bonuses from stepping onto it or leaving it.
There is no pathfinding / native creature bonus.

Does anyone understands H3 behaviour here?

(Btw I found a little bug with initial move points but it didn't make difference here)
(0000534)
Zamolxis   
2009-12-31 13:12   
(edited on: 2009-12-31 13:16)
a) The visit to the Redwood Observatory has nothing to do with the difference in paths. I've tested it with the same path w/o the object, and the results are the same (as in the same for each game as in the report above).

b) The last straight diagonal arrow for me is at (47,20) - unless I'm missing sth. (51,15) is somewhere behind (above) the Redwood Observatory.

c) If we are talking about (47,20), then in that position, the green bar left of hero icon, indicating the remaining movement points, is bigger in H3 as compared to VCMI. See the 2 newly attached screenshots. So I guess in H3 the hero has more than 202 movement points in that position, and the fact that he can move further has nothing to do with the change of terrain from snow to road. I guess H3 applies less of a penalty somewhere before:
- either the first 2 tiles vertical down,
- or the next tile to the left (R.Observatory),
- (or perhaps when there's a change of direction the penalties apply differently)
- or else, for the final diagonal movement, the penalty is perhaps a rounded down value of sqrt(2).

(0000544)
Ivan   
2010-01-01 18:23   
>>Does anyone understands H3 behaviour here?
If I am right then this may be a bug in H3 (VCMI behavior is more logical IMO)

On last move we have 202 MP. Diagonal cost is 212 (212 > 202) -> we can not move in diagonal direction.

In this situation we have "last move rule" - hero can move in diagonal direction if we have enough MP to normal move (202 > 150, changing movement cost from 212 to 150)

Moving hero according to this rule - after this only 150 MP will be used, 202-150=52 - enough to one more move on the stone road
(0000548)
Zamolxis   
2010-01-01 19:23   
Yes, but that is supposing we still have 202 MP in that position. But as mentioned in my previous note, based on the movement bar from H3, it seems that the hero has more MP left in H3 as compared to VCMI. Maybe this is too technical for me to understand (e.g. I don't get where the exact value of 150 comes from), but it's what the movement bar seems to indicate, regardless of hero's next move (on diagonal or not).
(0000549)
Warmonger   
2010-01-01 19:43   
I suppose this was made so that hero who has some points left can still interact with nearest object, no matter where it's placed.
It may be important as some custom scenarios have paths calculated with tile precision, so if VCMI gives shorter path it might be even impossible to finish them!
(0000550)
Zamolxis   
2010-01-01 20:17   
Perhaps. Though I'm not sure what to think anymore. Maybe H3 was a bit buggy after all. I edited the map by removing the piece of road at the end of Ivor's diagonal path, and when he got there, the movement bar still had a tiny bit of green at its end (see screenshot attached today 21:11). But after I added a resource to see if the hero can pick it, I could not reproduce the situation anymore (nothing left of the movement bar in the same position; hero couldn't pick up the resource).
(0000555)
Ivan   
2010-01-01 21:14   
(edited on: 2010-01-01 21:15)
Zamolxis
in H3 we have 202 there - I've tested this with H3+ArtMoney. Difference in movement bars looks to be a small graphical bug.
150 is movement cost: 100 for distance (diagonal will take 141) + 1,5 penalty for snow = 150

Warmonger
Yes it is a feature and it present in both VCMI and H3. Problem is how many MP hero will have after this:

Zero in VCMI - hero already had not enough MP to move in diagonal direction. How he can move one more tile after this?

((Previous MP) - (cost for non-diagonal move)) in H3 - there is still chance for one more move.

Note - it seems that this rule can't be used twice in H3 - look on lastmove.jpg - after move to the road hero will have 52 mp - enough to one move to sphinx (like on Zamolxis pics) and trigger this rule again but he can't make that diagonal move (70 MP needed)

(0000556)
Zamolxis   
2010-01-01 21:40   
(edited on: 2010-01-01 21:43)
I'm just taking a guess here, but what if H3 calculates penalties (but not bonuses) depending on the destination slot. In our case the destination slot is not snow anymore, so the diagonal move uses only 141 MP, after which hero still has 202-141=61 MP.

Another guess would be that the change of terrain ignores all bonuses and penalties in H3. This way, for the move from snow to road, both the snow penalty & road bonus are ignored (with the same result of 61 MP remaining after the diagonal move).

@Ivan: Do I need coding skills, or can anyone use ArtMoney? It may help in investigating this, i/o of talking with assumptions. :p

(0000557)
Ivan   
2010-01-01 22:27   
The main problem is that we have 52 MP remaining before the last move but not 61 or something else.

ArtMoney is mostly used by gamers to hack some game stuff like money. No coding skills required but you need to find required data (like MP) in memory.
It may take time to find out how it works but can help in checking some stuff like this.
(0000558)
Zamolxis   
2010-01-02 00:13   
(edited on: 2010-01-02 00:21)
I didn't figure out what's causing the difference, but while testing I found new aspects of the issue. Take the Movement_Test map attached today @ 00:58 in H3 & VCMI and move the 2 heroes up & down on the 2 diagonal paths that begin from where they are placed.

Both diagonal paths have 6 patches: 2 of each of the 3 road types, only 1st path has them interlaced, while the 2nd has the same type patches next to each other.

After going 3 times on the "road" (up-down-up), here's what's left:

H3: Edric can still go 2 tiles back (could go a 3rd one, if the 3rd tile would be cobblestone i/o dirt) and Sylvia can still go 3 tiles back. The way the road types alternate seem to have no effect on them, as long as the total of each type is the same.

VCMI: Edric cannot move anymore, while Sylvia can move back only 2 tiles. The way road patches alternate seem to have an effect in path calculations in VCMI. Could be only that, or a combination of that and different rounding or calculation logic for these paths.

I guess ArtMoney will show you the exact MP loss that applies at each step and help us figure out how these bonus/penalty values are calculated in H3.

(0000564)
OnionKnight   
2010-01-02 15:31   
The H3 strategy manual says "if the hero has at least 100 movement points left he will still be able to make a diagonal move on non penalty terrain. This is not true for penalty terrains, even in case you have native creatures or (any level of) Pathfinding.". Snow is a penalty terrain, but maybe the manual is wrong or it's something else.
(0000567)
majaczek   
2010-01-03 14:32   
(edited on: 2010-01-04 18:05)
Snow is a penalty terrain... but road not :P
I believe 3DO treats roads as terrain type

EDIT:
also H3 engine may save temporary values during counting paths, so using artmoney may be inaccurate (eg. value is correct but effect depends on earlier value and was saved elsewhere, or value it finds is not fresh etc.)

(0000579)
phomm   
2010-01-12 06:53   
Actually, Ivan is right. There is no problem with this cause, my opinion :

when pathfinder iterates that diagonal move it is cheking that 212 (141*1.5) is not enough for move and acts using lastmove rule - subtracts 100*1.5 from 202 and here we get difference in algorithm - vcmi probably gets directive "it's last move" and subtracts ALL of mp BUT h3 subtracts only 150 and provides check of making the rest iterations (without getting such a directive) and of course check says - here is 1 more step available

so vcmi in the code of lastmove takes all of mp and h3 only that what it counted (150) and the next iteration of them both gives differences.

actually this is possible only with combination of penalty terreain and road, without them there will be not a big rest of mp, not enough (here we get 52)
you can get same result if using swamp and gravelroad 141*1.75 = 246.75 if hero has 240-246 mp in that tile he will be able to make a diagonal last-move step 100*1.75=175 and will have 71 left which is enough for 1 straight step on gravel road (65). Wog-exe even shows the last straight move by road with horse-2 cursor (means on next turn hero can get there)

This is confirmed(i think so) by the fact that if you have i/e/ 250 mp in that place or >212 in case of snow(on map posted) there will be no possibility to get further, because no last-move rule is applied (there will be some mp after a move, i.e. 215-212=3 , so the rule is not applied)
(0000580)
phomm   
2010-01-12 09:24   
Strange, i can't edit my previous report, it says Access denied.

Note for previous report : Checked memory and found that ALL of Heroes with units speed 3 as in the posted map (Ivor has dwarves - speed 3) have only 1480 mp but should have 1500(and in that tile where should have 202 he actualy has 182), didn't cheked the other units' speed, but cheked even with 202mp (set in memory) we haven't h3 behaviour

This fact is actualy explains that graphical glitch that frightened :) Zamolxis. On that tile in VCMI hero has 182 mp which is shown as tiny (1 pixel width) and in H3 hero has 202 mp, mp-bar for that is wider.

if you want to chek this fact and cannot use artmoney (or other memory-editing tool) you can perform a test: Ivor should have 1500 mp and each straight step on snow takes 150 (1.5*100) so he must step 10 times, but he can't do 10 , he makes only 9 , and in sod/wog he makes truly 10 steps


SO !!! this is more like a bug about wrong starting mp's (but still behaviour with laststep isn't same as compared to h3)
(0000581)
Zamolxis   
2010-01-12 09:28   
(edited on: 2010-01-12 10:40)
So what you are basically saying, is that H3 actually removes the diagonal penalty if the hero doesn't have enough MP to make the move.

It makes sense and will probably bring us closer to the H3 formula. It may not solve also the aspect I added in note 558 above, though I'm considering splitting that in a separate report, as it could be that the cause is not the same.


EDIT: Phomm, you're brilliant! :)

Not only have you (most probably) identified the cause, but even found another bug related (maybe the one Tow was referring to in note 533?). Yes, I can reproduce the fact that Ivor can only move 9 tiles on a straight path in the snow in VCMI, while in H3 he moves 10 tiles. I'm glad also that what I noticed about the movement bar was not a "graphic glitch" (one potential bug less to worry about, plus confirmation of the cause of this bug here). This may also be the cause of the behavior I reported in note 558 above - so I may not need to split that after all. ;)

I updated the original report with the details from your notes and also changed the Mantis settings so that you can edit your notes. :)

(0000629)
Zamolxis   
2010-02-11 22:32   
I see the 2nd issue reported (see Additional Info section) is fixed in 0.75c, so it's probably what Tow referred to in note 533.

The main issue reported, as well as the 3rd one (with diagonal movements - possibly related) are still there.