Change game tick granularity

[GoogleCodeExporter]

This is a discussion bug for examining the feasibility of altering the game 
tick granularity.

The problem.
Right now, a game tick is one thousandth of a second.  Most system clocks do 
not wake at anything close to that rate, so it is quite common for it to wake, 
calculate a sleep of, oh, 20ms, and loop over the gear list, calling their 
function callbacks 20 times.
This is obviously inefficient, and probably one of the reasons the game strains 
a bit on iOS/Android despite some of the prior optimisations, especially during 
napalm strikes. (The other unrelated reason is separate draw calls).

So. Benefits - less function calls, less CPU cycles.  Disadvantages - 
acceleration would change slightly, collision becomes problematic, more work to 
change (see below).

The general solution is to make function calls happen less often.  Since this 
needs more discussion, I thought I'd lay out a couple of possibilities, as I 
see them anyway, for hashing out.

Approach #1.  Alter game tick from 1000/s to 100/s or 50/s.
    1) Alter all game constants like cGravity
    2) Repeat with all the various hardcoded manipulations of X/Y/dX/dY by constant values which are not instantaneous values.  Skip decay for example should be fine.
        2b) Probably adjust the nested pixel tests in hog movement (kinda falls under specialcased X/Y manip)
    3) Alter uCollisions to avoid objects flying through walls.  Right now, the game clamps velocity in doStepFallingGear and doStepHedgehogMoving to 1.9.  This avoids a problem in the past where if there was enough force behind an explosion or a fall, you could fly right through things.  There are 2 ways this could be done.
        * One would be to search more pixels in uCollisions if dX or dY was high.  The entire collision area or at least going further in based on dX/dY.
        * Another could be to calc X or Y offset from dX, dY and repeat current test procedure there, and possibly a couple of points in between.
       Both these approaches though would end up w/ an X/Y that could go further into a surface and sample different pixels.  This could impact some collision tests.

Main advantage w/ #1 is that iteration over the gear list happens only 50 or 
100 times per second. Period.  This has obvious performance gains.  Compared to 
#2, determining when gears run is clearly simpler.

Problems w/ #1 include:
* Players very sensitive game mechanics (shoppa players) might notice if 
velocity becomes slightly different.
* Objects will move further past other objects.  This impacts pixel sampling, 
and also possibly things like portals.
* Explosions might also occur at slightly different points.

--------------------------------------------------------------------------------
---------------------------------

Approach #2.  Maintain game tick at 1000/s but try to cut down on the function 
calls by adding a step parameter to the function callbacks.

This would probably be approached something like this.
    1) Add 2nd parameter to callback, call it, say, step.  Probably make it default to 1 for places that call steps.
    2) In main gear list iteration, if dX/dY is very low, use a step of 20.  As dX/dY climb, shift to other step values, such as 10, 5 and for high velocities, 1.
        2b) Additional criteria could be things such as the gear's radius, its type, whether it is currenthedgehog (always use 1 to avoid changing hog movement), and possibly a gear flag (perhaps treat snowflakes differently from land spray).
    3) The gametick and step the gear was executed in would be stored, and the gear would not be invoked again until the GameTick caught up.  Obviously if the main sleep had overshot, a few steps of 1 would be thrown in for that gear.

Advantages #2 are that the game math stays essentially the same.  Gear handlers 
can apply changes in velocity appropriately, and collision does not need to 
change since as velocity climbs the steps drop to 1.  Gears at high velocity 
should also interact appropriately with mines, sticky mines, portals etc.

Disadvantages to #2 include:
* More complex implementation in the main loop to track when gears need to be 
called
* Requires adjusting every gear handler to take a step into account.  Since 
steps >1 are more expensive to calculate, either if step <> 1 would need to be 
added, or, if the tests are too great a cost, 2 copies of each handler provided 
(personally I'm betting on the tests not being a huge cost)
* Iteration over the gear list still occurs 1000 times per second, even if not 
all function handlers are called.  However, it seems to me that for the case of 
idling gears, which is a surprising number of them, which would only get called 
20 times per second, that we could perhaps maintain a couple of lists for the 
main loop. A 20x list and "everyone else".  The cost of maintaining 2 extra 
lists in gear addition and deletion is not horrible, and moving gears from one 
list to another would probably be a small cost if velocities did not rapidly 
switch.
So, taking a game with, say, 2 crates, 10 mines, 24 hogs and 4 explosives.  All 
would be in the 20x list and only iterated over 50 times per second.  Once a 
hog became active, it would move to the !20x list.  It might dynamite another 
hog (dynamite in 20x, possibly briefly in !20x), "kicking" it into the !20x 
list.  But we'd still have 38 other gears in the 20x list.

If we make the steps multiples of each other, it would not be difficult to 
force all 20x to be called at same time, all 10x, all 5x, etc.  This seems to 
me like it would simplify accounting and list maintenance.

Sooooo.   That's how I was looking at it.  What do you guys think?

Original issue reported on code.google.com by kyberneticist@gmail.com on 30 Nov 2011 at 4:27

[GoogleCodeExporter]

I dislike Approach #2 since it makes the code more complicated and harder to 
understand/extend. Also due to  steps  the addition of many multiplication 
operations will be necessary which will further reduce performance gains.

Approach #1 seems more sensible to me.
Of the problems listed I only consider the changed "feel" of motion/controls to 
experienced players a real problem.
The other 2 problems listed (moving further into objects and different 
explosion locations for fast gears) could be fixed or at least lessened into 
insignificance I believe
(by adding adjustments and position restore to collision detection and by 
creating an additional MakeExplosion routine specifically for moving gear that 
will cause an explosion at a past position depending on dx/dy and negative 
timer value offset)

Original comment by sheepyluva on 30 Nov 2011 at 5:05

• Added labels: Component-Engine, Component-Logic

[GoogleCodeExporter]

Well #1 will involve changing a lot of code, but it is a one-time cost.  Later, 
yes, new additions would just use the new rules.
Other things impacted by #1 are I guess anything that checks GameTicks - value 
of GameTick is assumed to increment 1 at a time, so it would probably be 
appropriate to keep doing that, just w/ 50 or 100ms granularity.  So pretty 
much anything that does a test on GameTicks should be considered as well.

Oh. Also, given the alterations to physics, probably 100ms would be safer. 50ms 
might be too much.

One additional point w/ #1.  Game just has the one sleep.  So, while #2 keeps 
sleeps as low as possible still, #1 would obviously change that.  This impacts 
max FPS.   Probably another reason to stick w/ more conservative 100ms if 
picking #1.

Original comment by kyberneticist@gmail.com on 30 Nov 2011 at 5:15

[GoogleCodeExporter]

Hm. WRT step thing.  Dunno. People seem to have adapted ok w/ visual gears.
Also inlineable helper functions could be added (quadratic for velocity, or 
maybe even iterative + function pointer).

Overall impact on maintainability for #2 might not be high, and the performance 
gains more configurable.
But. Hey. Dunno. That's why I thought I'd get ideas.  Heck.  There might be 
other options too.

Original comment by kyberneticist@gmail.com on 30 Nov 2011 at 5:19

[GoogleCodeExporter]

WRT math in #2, if we had fixed step intervals, we could possibly also use 
approximations that are close enough, based on testing.
Constant values to avoid math.  That would be similar to #1, but w/ a bit more 
granularity/flexibility.

Original comment by kyberneticist@gmail.com on 30 Nov 2011 at 7:16

[GoogleCodeExporter]

Just a small remark about collisions: with despeckling there's no chance for 
1-2 px width line, so collision checks could probably stay as they are. On the 
other hand, object could get stuck in solid land penetrating it deeply.

Original comment by unC0Rr on 21 Dec 2011 at 8:04

[GoogleCodeExporter]

despeckling only cleans up damaged land, so thin lines on existing map surfaces 
are preserved. also, current despeckling would preserve a 2px thick line of 
damaged land, so long as sweeps did not examine end pixels.  Damaged pixels in 
the middle of the line would have 5 neighbours, over the 3 neighbour threshold. 
 An isolated block of 4 damaged pixels is of course cleaned up.  Also 
despeckling ignores "indestructible" terrain even if it was flagged damaged.

So, I think considering collision impact is still warranted.

Original comment by kyberneticist@gmail.com on 27 Dec 2011 at 6:54

[GoogleCodeExporter]

So, I think the rope was instructive.
The stickiness was, and probably still is, a bit problematic.
On the plus side, the rope was probably the worst of the bunch.

Original comment by kyberneticist@gmail.com on 25 Aug 2012 at 2:46