搜尋此網誌

Glossary script

Time model and determinism


         Time model and determinism
why use a fixed interval game clock
category: game systems

Terminologies

Time model

There are two types of time model in game systems: fixed interval and variable interval.
- A game clock is the parameter t which all simulations in a game varies with.
- Time model refers to how the game clock advances.
A fixed interval model is, thus, one that advances the game clock in fixed steps. In other words,
- The time interval between any two adjacent frames is always fixed in a fixed interval system.
- The time interval between any two adjacent frames may vary in a variable interval system.

Determinism

In a deterministic system, the next state is completely determined by the current state. In a computer simulation, it is often judged by whether repeating with the same input produces the exact same output. If the outputs are different across multiple trials, it means there are some critical variables not captured by the state of the system. In this case, the system is said to be not deterministic.

Relation between the two

Variable time interval destroys determinism, simply because the time interval is not part of the system state.
The above diagram demonstrates the problem. A bullet is fired toward a wall, and the blue dots show its trace. (in reality, the intervals should be much smaller). In a fixed interval system, if the wall is thicker than the distance the bullet can travel in one frame (its speed), we can safely deduce the bullet must collide with the wall and can never pass through it, in any number of trials.
However, in a variable interval system, because the distance the bullet can travel in one frame is variable, we cannot guarantee. In some rare occasions, the bullet can pass through, creating a very interesting bug. In fact, you can argue we can draw a vector from the current position to the next position and perform intersection test with the wall. But in general, the different trajectories produced in different trials is the evidence of non-determinism.

Input handling

A system given the same input, will always produce the same output, note, they must be given in the exact same time. In a game, input interrupt (please do not use polling) can arrive at any time, and if a game respond to input immediately, it effectively disrupts the fixed-interval protocol. To align inputs to a fixed interval, inputs must be buffered and fetched each frame. This is the reason behind fetch-and-dispatch input handling model in virtually all game engines.

Real time vs determinism

In order to be synchronizable over network, a game has to be deterministic. In some game genre, like first person shooter and rhythm games, real time performance is often favoured over determinism. These systems use variable time interval to compensate the changing frame rate, creating an illusion of constant time progress. This characteristic makes it extremely hard to develop multiplayer. In first person shooters, determinism at client side is completely thrown away, dictatorship over game states is granted to the game server. In rhythm games, we just trust the clients.

Animation and simulation

A good system separates animation from simulation, such that the two can use different time models. The technique of interpolated animation between fixed interval key frames is often used in games that require both determinism and smooth animation. In particular, Age of Empires does this to implement a synchronizable system for networked multiplayer.

Reference

[1] "Time-based animation", Sacred Software, <http://www.sacredsoftware.net/tutorials/Animation/TimeBasedAnimation.xhtml
[2] "What every programmer needs to know about game networking", Glenn Fiedler, http://gafferongames.com/networking-for-game-programmers/what-every-programmer-needs-to-know-about-game-networking/
[3] "1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond", Mark Terrano and Paul Bettner, http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php

0 comments:

Post a Comment