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