Continuous time
Author
Until now, video games I made were used fixed time steps every 15 or so milliseconds. During each of these steps, every object in the game was updated using an "update" method of my objects.
There are many inefficiencies with this. First, quite often there's nothing to do for a lot of objects (such as objects that spawn a monster once every X seconds, countdowns, linear movement, regular HP increase etc.), and second I might want to have more versatility to this than a plain "60,30,20,15,12,10,6,5,3,2,1" times per second, especially when there are some effects that are separated by very little time (such as 10 milliseconds) but must happen in a definite order (so they cannot occur on the same step).
I'm asking you for your opinion on something I though of.
My idea was to use a scheduling system: for every action or event in the game, I add the action, associated with a time for execution, to one of the many time managers in the game. The time is then advanced on each manager, and the actions are executed in the order corresponding to the time they were schedulet for. The internal implementation uses heaps for O(log n) scheduling and O(1) extraction of the next action.
In many games, there would be only one manager, since all events might be correlated. However, if there is no correlation (or if it can be controlled through other means), it can be possible to reduce the (log n) factor by distributing actions across more managers (as would happen in a multi-level game, where each level is independent and can be managed independently).
So, what is your opinion on the efficiency and the implementability of this question? As a side-note, do you have better ideas than a heap for implementing priority queues (since actions are scheduled at more or less increasing times, it should be the kind of information that allows an algorithmic optimization).
Obviously you can get into a scalability problem if you call a tick() function sufficiently often for a sufficiently large number of objects.
The trick would be to slow the tick rate of distant or uninteresting objects down, until something more exciting happens.
Object movement could then be sorted out in the renderer (i.e. for objects in the frustum only) by interpolating between the previous and next locations.
Or objects could be temporarily woken up while the player was looking at them, although that could have unintended side effects - for example, in a multiplayer RTS you would want the game to be entirely deterministic still.
---
Using priority queues for time-based events is a good idea, and works pretty well (I've used it on a non-game project).
The thing I can say, is that (IMHO) you need a way of removing events from the queue efficiently, because it will happen very frequently. I used STL multi_map to model a priority queue and stored an iterator pointing at the current entry in the object itself, so it could be removed quickly (iterators remain valid forever in a map provided the element is not removed, I think)
Mark
The trick would be to slow the tick rate of distant or uninteresting objects down, until something more exciting happens.
Object movement could then be sorted out in the renderer (i.e. for objects in the frustum only) by interpolating between the previous and next locations.
Or objects could be temporarily woken up while the player was looking at them, although that could have unintended side effects - for example, in a multiplayer RTS you would want the game to be entirely deterministic still.
---
Using priority queues for time-based events is a good idea, and works pretty well (I've used it on a non-game project).
The thing I can say, is that (IMHO) you need a way of removing events from the queue efficiently, because it will happen very frequently. I used STL multi_map to model a priority queue and stored an iterator pointing at the current entry in the object itself, so it could be removed quickly (iterators remain valid forever in a map provided the element is not removed, I think)
Mark
Author
Quote:Original post by markr
Obviously you can get into a scalability problem if you call a tick() function sufficiently often for a sufficiently large number of objects.
The trick would be to slow the tick rate of distant or uninteresting objects down, until something more exciting happens.
Object movement could then be sorted out in the renderer (i.e. for objects in the frustum only) by interpolating between the previous and next locations.
Or objects could be temporarily woken up while the player was looking at them, although that could have unintended side effects - for example, in a multiplayer RTS you would want the game to be entirely deterministic still.
Even then, using continuous time instead of discrete time would have its uses. For instance, a Tank Factory doesn't need to be updated every 15 milliseconds: we know for sure it's going to pop out a tank in 15 seconds, so simply register the action 15 seconds from now and spare the 999 useless checks that would have been made otherwise.
Quote:
Using priority queues for time-based events is a good idea, and works pretty well (I've used it on a non-game project).
The thing I can say, is that (IMHO) you need a way of removing events from the queue efficiently, because it will happen very frequently. I used STL multi_map to model a priority queue and stored an iterator pointing at the current entry in the object itself, so it could be removed quickly (iterators remain valid forever in a map provided the element is not removed, I think)
Well, once the action is executed, it is removed from the priority queue. Now, if the action fails (because the action's owner is dead, or the target has become invalid, or it was canceled), this has no impact on things around. So it's just as easy to leave potentially failing actions in the queue and let them fail once they are removed and executed.
I came up with the same idea for my scheduling system. But! I still need to find a way to schedule the same object multiple times and to safely remove them when needed. Currently I can schedule the same object only a single time. I think the problem roots from the fact that the events are scheduled by default as repeatable so the same object can undergo multiple modifications at the same time. (I'm using C as the programming language).
To be more precise, I'm doing a Tetris game, so that's why the events are scheduled as repeatable. The figure will be moved on the Y axes every 2 seconds. But at the same time the figure can undergo other animations... So here comes the problem...
Hope you understood me :).
I use timeGetTime(), with granularity set to 1 ms with timeBeginPeriod(1), so the events are parsed every 1 ms :)... These should assure a smooth gameplay.
To be more precise, I'm doing a Tetris game, so that's why the events are scheduled as repeatable. The figure will be moved on the Y axes every 2 seconds. But at the same time the figure can undergo other animations... So here comes the problem...
Hope you understood me :).
I use timeGetTime(), with granularity set to 1 ms with timeBeginPeriod(1), so the events are parsed every 1 ms :)... These should assure a smooth gameplay.
to rechedule an object, if needed, it's just a matter of, well, re-scheduling it.
something like that?
class CThing: public CObject{private:public: void Start() { // global game scheduler g_pxGameScheduler()->AddToSchedule(this, 0, 15/*15 ms*/, CThing::gScheduleUpdate); } void Update(u_int uTimeInMS) { //...... // do stuff // Then reschedule if needed if (bReschedule) { g_pxGameScheduler()->AddToSchedule(this, 0, uTimerInMS/*15 ms*/, CThing::gScheduleUpdate); } } static void gScheduleUpdate(CObject* pxObject, u_int uExtraData, u_int uScheduleTimerInMS) { (static_cast<CThing*>(pxObject))->Update(uScheduleTimerInMS); }};something like that?
Quote:Original post by ToohrVyk
Well, once the action is executed, it is removed from the priority queue. Now, if the action fails (because the action's owner is dead, or the target has become invalid, or it was canceled), this has no impact on things around. So it's just as easy to leave potentially failing actions in the queue and let them fail once they are removed and executed.
That's not quite true.
Because the tank factory could stop producing tanks because it had been instructed to stop. Or to start producing a different type of tanks.
In either case, you'd need to cancel the timeout (and possibly register a new one).
As far as using variable timestep is concerned, I'm totally unconvinced about it. I tried using variable timesteps and it worked really well for some types of games, but I got jittery problems (with varying framerate). But also, it won't work well in a multiplayer game because it's going to have to be deterministic.
Mark
Well... Currently ( for my C implementation ) the only way to schedule the same object multiple times and be able to find it in the scheduled tasks list afterwards in order to delete it, I have to give as parameter to the deleting function 1) the action type, 2) the time interval the object does the specified action and 3) the object pointer... This is because the same object cannot perform simultaneous the same activity at the same rate. ( well, maybe it could, but not in my game ).
I know it doesn't answer your question but my time-based system has every time-sensitive object (pretty much everything) tied to an "sequencing engine" which updates all objects registered with it. The engine keeps track of time and time deltas and makes this info available for all objects tied to it. The objects do whatever they want with the time internally. I understand this is what you are trying to avoid, BUT i think it's much more flexible since many objects require the time every single frame anyway (anything animated or moving, for instance). The overhead of scheduling "events" for objects requiring time data every frame might undo your gains from objects that only need to update once in a while.
Now one interesting side effect is that you can have multiple engines and you can alter the time calculations in the engine. So you could, say, multiply all the time deltas every frame by * 0.5. Every object tied to the engine will get the halved time and you literally slow down every object tied to that engine to half-speed, while objects tied to a different engine go the normal speed (or double speed, or whatever you want)
Now one interesting side effect is that you can have multiple engines and you can alter the time calculations in the engine. So you could, say, multiply all the time deltas every frame by * 0.5. Every object tied to the engine will get the halved time and you literally slow down every object tied to that engine to half-speed, while objects tied to a different engine go the normal speed (or double speed, or whatever you want)
Well, this is really an elegant solution. But it's appliable only to OOP. I should try it some day.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
