bugBos Wars - Bugs: bug #29657, Movement cost 4 in patch type is...

 
 

bug #29657: Movement cost 4 in patch type is far too slow because of 1 << (1 << cost)) calculation

Submitted by:  Kalle Olavi Niemitalo <kon>
Submitted on:  Sat 24 Apr 2010 03:57:08 PM UTC  
 
Severity: 3 - NormalItem Group: Bug
Status: FixedPrivacy: Public
Assigned to: Kalle Olavi Niemitalo <kon>Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Thu 29 Apr 2010 08:44:52 PM UTC, comment #1:

Fixed in trunk r9810.

Kalle Olavi Niemitalo <kon>
Project MemberIn charge of this item.
Sat 24 Apr 2010 03:57:08 PM UTC, original submission:

Bos Wars trunk r9789 on Debian GNU/Linux testing amd64.

In the patch editor, you can set a movement cost for each tile. 0 is fastest (roads), 3 is the default, and 7 is supposedly slowest. The bug is that although cost 4 should be only a little slower than cost 3, it is 256 times slower. And cost 5 looks as fast as cost 3 (at least for the buggy) even though it should be slower than cost 4.

The bug happens because Bos Wars in effect calculates the animation delay as (Wait << (1 << cost)) >> 8. Consider what happens with different costs if Wait happens to be e.g. 256:

  • If cost is 0, the delay is (256 << (1 << 0)) >> 8, or 2.
  • If cost is 1, the delay is (256 << (1 << 1)) >> 8, or 4.
  • If cost is 2, the delay is (256 << (1 << 2)) >> 8, or 16.
  • If cost is 3, the delay is (256 << (1 << 3)) >> 8, or 256.
  • If cost is 4, the delay is (256 << (1 << 4)) >> 8, or 65536.
  • If cost is 5, the delay is (256 << (1 << 5)) >> 8, or (256 << 32) >> 8. Because 32 is typically the number of bits in int, the result of 256 << 32 is undefined in standard C; x86 and amd64 processors treat it as 256 << 0, so the delay is 256 >> 8, or 256, the same as with cost 3.

The shifts happen in two different places:

  • engine/map/patch_manager.cpp (CPatchManager::updateMapFlags): Map.Field(i, j)->Cost = 1 << (flags & MapFieldSpeedMask);
  • engine/action/action_move.cpp (DoActionMove): move = UnitShowAnimationScaled(unit, unit->Type->Animations->Move, unit->Type->AirUnit ? 8 : Map.Field(unit->X, unit->Y)->Cost);
  • engine/action/actions.cpp (UnitShowAnimationScaled): unit->Anim.Wait = unit->Anim.Anim->D.Wait.Wait << scale >> 8;

i.e., CMapField::Cost is already 1 << (the cost from the patch type), and then it is used as a shift count again.

The pathfinder uses CMapField::Cost too:

  • engine/pathfinder/pathfinder.cpp (CostMoveTo): cost += Map.Field(i, j)->Cost;

I think, to let the pathfinder find as fast paths as possible, the cost calculation there should be the same as in the animation code. And to avoid slowing down the pathfinder, it may be good not to require shifts there (although the effect is probably negligible on modern processors). Therefore, I think the shifting should be kept in CPatchManager::updateMapFlags but removed from UnitShowAnimationScaled.

If the simple 1 << (the cost from the patch type) calculation does not result in a curve that is steep enough, it may be easiest to make CPatchManager::updateMapFlags use a constant array for mapping the 0-7 values in the patch types to the actual costs; the values in that array can then be tuned as much as desired.

Kalle Olavi Niemitalo <kon>
Project MemberIn charge of this item.

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #20322:  0001-Reduce-the-effects-of-terrain-speeds-4-5-6-and-7.patch added by kon (2KiB - text/x-patch - [PATCH] Reduce the effects of terrain speeds 4, 5, 6, and 7)

 

Depends on the following items: None found

Digest:
   patch dependencies.

 

Carbon-Copy List
  • -unavailable- added by kon (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Thu 29 Apr 2010 08:44:52 PM UTCkonStatusPatch available=>Fixed
      Assigned toNone=>kon
      Open/ClosedOpen=>Closed
    Sun 25 Apr 2010 04:08:16 AM UTCkonAttached File-=>Added 0001-Reduce-the-effects-of-terrain-speeds-4-5-6-and-7.patch, #20322
      StatusNone=>Patch available

    Back to the top


    Powered by Savane 3.1-cleanup1