I have a simple event system:

class GameEvent{
    float executionTime;
    Action action;
}

class EventMgr : MonoBehaviour{

    List<GameEvent> events = new List<GameEvent>();

    void Update(){

        float timeNow = Time.time;

        for(int i=events.Count - 1; i >= 0; i--)
        {
            if(timeNow >= events[i].executionTime)
            {
                exents[i].action();
                events.RemoveAt(i);
            }
        }
    }


    public void ScheduleEvent(float delay, Action action){
        events.Add(new GameEvent(){
            action = action,
            executionTime = Time.time + delay;
        });
    }
}

Then,

I schedule events like this:

eventMgr.ScheduleEvent(0.1f, () => {
    // EVENT A - should be fired first
};

eventMgr.ScheduleEvent(0.15f, () => {
    // EVENT B - should be fired second
};

Everything works fine when I play on 60 FPS. Update() is fired once every ~0.016s. When I play the game on a device with 20-40FPS - things got a little bit tricky. Events seem to run in an incorrect order (Event B fired before event A).

The only possible cause is of course the framerate itself. If the game runs at 20FPS, Update() would be called less frequently and both of these events would be fired in the same frame - and then, the order of their execution depends on the list itself.

What to do here? Is there any trick to prevent this, is there any pattern for accurate, ordered event system in games which is FPS friendly?

  • Granted I haven't had my coffee yet, but isn't your condition (events[i].executionTime >= timeNow) reversed? Don't you want to execute the events for which the executionTime has already passed? – Rotem Oct 16 at 7:02
  • If timeNow is at 0 and executionTime is at 1 it means that we've just scheduled an event for 1 second. Then, timeNow grows, grows, grows and after one second it has a value like 1.0013424 - which makes the condition == true, fires the event and removes it from the list. – Spectre Oct 16 at 7:33
  • I understand that, but am I missing something? Your code executes events when executionTime is greater than timeNow, what you just described is the opposite. if timeNow is at 0 and executionTime is at 1, then executionTime >= timeNow is true, not false. The event will be fired immediately. – Rotem Oct 16 at 7:43
  • Awww nice catch! I've corrected the code. Written from memory :) Thanks! – Spectre Oct 16 at 7:49
up vote 9 down vote accepted

This looks like you could solve it with a priority queue or min-heap. The code to process the queue would look something like this:

while(eventQueue.Count > 0 && eventQueue.Peek().executionTime <= Time.time) {
    eventQueue.Dequeue().action();
}

This means you have only one check to do on frames when no events happen - you don't have to scan the whole list.

The nature of the priority data structure ensures that the next event to fire is always the first one you check, and when multiple events fire in the same frame, you process them in non-decreasing order of executionTime.

Insertion and removal from such a data structure are typically logarithmic, so they remain reasonable even for large collections of events.

  • Are these any ready-to-go data structures like a priority queue available in Unity, .NET 4.5? – Spectre Oct 15 at 17:49
  • 2
    It's absent from the standards .NET collections, but easy to whip up your own custom-suited to your needs. It's also a popular enough data structure that you can find implementations in several third-party libraries you could include too, if you want something battle-tested without writing it from scratch yourself. – DMGregory Oct 15 at 17:52
  • 1
    @Spectre The quick&dirty solution to see if it works would be to just use a vanilla List<GameEvent> and sort it before the code above. If the sorting starts to take too much CPU time (I don' think it will unless the queue contains over a few hundred items), you can start to look for a more efficient self-sorting data structure. – Philipp Oct 16 at 8:33

If sufficient time passes between Update calls to trigger multiple events, then as you note the actual firing order depends on the order in which you process the list. Since you process the list backwards you will evaluate and thus potentially fire "later" events sooner.

If you want your events to create an implicit dependency through their firing time (e.g., an event A with an absolute time Ta must fire before any events with absolute time Tn > Ta), then you need to ensure you process them in that order.

In your case, you could just sort the list by absolute time, either before you process it in Update or by ensuring during scheduling you put new events in the proper sorted position.

Sorting the list backwards by absolute time means you can continue to process it backwards and rely on the efficiency of removing items from the end of the list (versus from the beginning, which would require moving the remaining items down).

  • I suspect if you are removing items from the end, you are probably adding items to the beginning, which has a similar expense. If this is the case, fancier data structures like a linked list or a circular queue could provide improved performance at the cost of increased code complexity. – Mutant Bob Oct 15 at 20:38
  • Yes; really a wholly different structure like DMGregory proposes is probably best. I was trying to take a minimally disruptive angle on my answer. – Josh Oct 15 at 20:39

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.