flipCode - Tech File - Steven Hugg [an error occurred while processing this directive]
Steven Hugg
Click the name for some bio info

E-Mail: hugg@pobox.com


   04/03/2000, Event-Driven Games


I feel particularly verbose tonight. So while I'm busy preserving my 1.44 floppy disk collection, I'll write a piece on an interesting way of architecting games that I've been playing around with. I know these concepts are already used in the industry, but I rarely see them mentioned in the publications I read. They stem from some very old roots in the SIMULA programming language (which some consider the first OO language).



Games As Simulators


Most video games can be loosely defined as simulators. For instance, Quake is a tactical combat simulator, chess is a very abstract simulation of war, Lemmings is ... well, you get the picture. At their roots, all of these games share a similar feature: they model a system that changes over time.

Why am I getting all metaphysical about simulation and stuff? Well, it's because I want to talk about a different way to write a game than most are accustomed to. What I want to talk about is the main loop. It's the thing that usually looks like this (pseudo-code, of course): 

while (game_is_running) {
   world->draw_to_screen();
   world->get_player_input();
   world->update_state();
   current_time += time_step;
}
9931575517f all arcade games feature a loop that looks something like that. It qualifies as a simulation -- it models a system that changes over time. Each time the loop executes, the state of the "world" updates. We also keep track of a 'current_time' variable, which is also incremented with each update. During each update, the program goes to each object in the world and asks "Do you need to be updated? If so, we'll update you." This is a polling simulation model.

This technique worked for the classic arcade games, and is used to good effect in many modern games. However, it can be inefficient when large number of objects are modeled. Consider an online RPG with 1,000,000 separate interacting objects. Unless every object performs some action at every time step, it it very wasteful to poll each of them in turn N times a second.

The best way to handle games with large numbers of objects is to use an event-driven simulation. If you've done any GUI programming, you probably understand the concept of events. You probably handle even handle events in your main loop, to process input from the keyboard/mouse/whatever. But most people don't use events as the basis of their entire game. (If you do, lemme know!)



Events & Event Queues


What does an event look like? In our world, let's make it look like this: 

class Event {
   int event_time;
   virtual void handle_event(World *world);
}
Each event has an 'event_time' variable, which determines when the event will fire. There is also a handleEvent() method, which is called when the event fires. The programmer would subclass this object to create specific events for the game, overriding the handleEvent() method.

There is also a 'World' object which looks like this: 

class World {
   Queue events;
   void post_event(Event *event);
   void consume_events(int end_time);
   ...
}
This 'World' object manages all events consumed by the game. The 'events' object contains a list of all outstanding events. post_event() is called to add a new event to this queue. consume_events() is called to drain the queue, firing and removing all events that are scheduled to fire earlier than 'end_time' in their chronological order.

consume_events() works kinda like this: 

while (the event queue is not empty) {
   find the earliest event in the queue
   is the event time earlier than 'end_time'?
   if so,
      dispatch the event (call handle_event() on the event)
   otherwise,
      exit the loop.
}
It is important that consume_events() be as fast as possible. We need a way to answer the question "What event in the event queue has the earliest time?" For this, we should use a data structure called a priority queue. There are tons of literature available on building these, but here's a hint: C++'s STL has a template called "priority_queue". Whether you want to pull your hair out trying to figure out how to use it is your decision, but it can be done. Rolling your own is not hard either, and it might even lead to a better implementation.



The Main Event Loop


So here is the main loop pseudo-code for an event-driven game: 

while (game_is_running) {
   world->draw_to_screen();
   world->get_player_input();
   world->consume_events(current_time + time_step);
   current_time += time_step;
}
You see, this is similar to the first loop, except we're not doing an "update world" every time step. What we do instead is consume all outstanding events scheduled to fire in the next 'time_step' time units, by calling the consume_events() method.

So have you had your epiphany yet? Do you feel the love that events provide? Ok, if not ... consider this event class, intended for a tile-based RTS game: 

class UnitMoveEvent extends Event
{
   Unit *unit;
   int deltax, deltay;


   void handleEvent(World *world) {
      unit->x += deltax;
      unit->y += deltay;
      if (unit->getNextMove(&deltax, &deltay)) {
         this->event_time += unit->getMoveDuration();
         world->postEvent(this);
      }
   }
}
This event represents the motion of a unit by one tile. When the event is fired, the unit's coordinates are updated. Then the unit is asked what its next move is, using getNextMove(). If this method returns true, the direction of the next move are placed into 'deltax' and 'deltay'. Then the event is reposted to the queue, intended to fire again after a given number of time units -- which is determined by a call to getMoveDuration(). Note that in this model, we're asking the object being moved where it wants to move, and how fast -- which is very nice from an OO point of view.

"But wait," you cry, "In this model, units will appear to jump from tile to tile, like in those old-fashioned CGA strategy games! I want them to move smoothly like in Starcraft, and I can't do that with this model! Do you want me to be the laughing stock of the RTS community?"

Just hold on, cowpolk -- you can do smooth motion in an event model. Just call upon your old friend, interpolation. Keep track of when you last moved a unit, and when the next move is due. Then when you go to draw that unit, interpolate between the last known location and the current location, using this ratio: 

   ratio = (current_time - last_move_time) / (next_move_time - last_move_time)
On the screen, units will appear to slide nicely from tile to tile, even though at any given moment, they are "officially" sitting squarely upon a single tile in the internal model of the world. The user perceives them as moving continuously because of the interpolation, and for many tile-based games, this is good enough.



What's The Big Deal?


This is all great, but ... why are we supposed to use events? Oh yes, for performance reasons! Now why is it faster than the typical way of doing things ...?

It's faster because the game only computes things that are actually happening. What if you've been playing the game for umpteen hours and there are 1,000's of dead units strewn around the playing field? With an event-based system, you don't have to ask each one "are you alive?" or "are you moving?" every frame. Live units keep on moving and firing, churning out events; dead ones just sit there. This may not be a big issue for a 50-unit game, but it is critical to building next-generation online worlds with millions of objects.

Even if you aren't building the next massively-online game, event modeling can still be useful. Since every interaction in the game takes place in terms of an event, you can just design the entire game in terms of events. It makes sense from a design point of view, and it'll be easier to explain the game to co-developers. Instead of a barely-commented method called "updateSpiralingDeathRayState" in your Spaceship class, you have a totally separate "SpiralingDeathRayEvent" class. How nice!

Also, an event model is a perfect fit for a networked multiplayer game. If everything that happens is an event, it's easy to construct a client/server model for a game.



But... Physics!


"But wait," you wail, "Everything you've been talking about has been applied to tile-based games... But my game ISN'T tile-based at all, it's a space simulation with real orbital mechanics, and it's gotta move on a fixed time step, it CAN'T be event-ized! What are you trying to do, man, destroy me?"

There, there ... you can make an event-driven simulation with accurate physics and collision mechanics, without using a fixed time step. You get the same benefits of scale that we discussed, plus some other benefits -- like not having to choose an arbitrary time step for the entire universe.

But that's a topic for another time. In the meantime, please mail me if you have anything to say about event simulation. I'd especially like to hear of any current games that are event-based -- I have my theories on some. Ciao!





  • 05/14/2001 - Finally, The Project!
  • 10/03/2000 - Whereever I May ROAM
  • 07/08/2000 - Tech File Update
  • 06/12/2000 - Good Vs Evil
  • 05/24/2000 - Ego Surfing
  • 04/24/2000 - Nocturnal Coding
  • 04/12/2000 - Exploding Thought Giblets
  • 04/03/2000 - Event-Driven Games
  • 03/31/2000 - The Housemate Experiment
  • 03/28/2000 - Introduction
    • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]