Request for information: Discrete Events Simulation

[Kai Backman]

I just got a basic DES engine working for ShortHike the other day. When I finally got down to the actual implementation there wasn't that much material on the subject available so I decided to write an article series (as a set of blog posts) on the subject. You can find the intro: here (http://www.kaibackman.com/development/2005/08/discrete_event_.html).

This is a request for information for that series (like the intro says). If you have implemented a DES yourself, know someone who has done so, know an article on the subject or if nothing else, know someone researching into it, please post/PM/email me so I can collect all the background information.

Here is a quick summary for those who are new to discrete events simulation:
In a traditional continuous simulation engine (what most people do) you loop through all your simulation objects and update them based on past values (like position) and trends (like velocity). In a DES you update based on when interesting things happen. Here are some benefits of a DES compared to traditional approaches:
- The time to converge is based on amount of change, vs. number of objects traditionally
- Usually less processing to reach the same fidelity
- Easy to limit workload per frame and still have usable intermediate results
- Processing effort better focused on interesting events, fast forwarding has higher fidelity
- Great capacity for distributed processing (I'm not going to explore this specifically)
- In short: it's faster and more accurate.

For rigid body physics you are better off using specific libraries (or existing algorithms), for general purpose simulation a DES is very practical.

BTW. If you have any general comments on what you would like to see me write about, I'm open for suggestions! (plenty of practical details to be sure) :)

Edit: Thank you in advance for anyone providing information! :D

[Kai Backman]

Not much info then.. :)

I'll just (finally) posted the first installment of the article series here (http://www.kaibackman.com/development/2005/08/discrete_event__1.html). It's a basic overview of what DES is all about. Feel free to comment either here or on the blog.

[cliffski]

I think for most people, the level of simulation they code is sufficiently simple that a continous simulation is no big deal, or they code a turn based sim (like democracy) where processing time is also not an issue. Aside from indie dev, the Movies (lionhead game) does have a lot to simulate, but its done just by objects taking their turn to update each frame, rather than waiting for discrete events.
I think most people would agree that an events based system is better and more efficient, but its probably a bit harder to code.

[Rod Hyde]

I enjoy these articles even though I freely admit that I am still struggling to get my head around the concept. In my attempt to figure it out, I rediscovered hierarchical state machines, for which I'm more than grateful.

Btw, your link to Wikipedia refers to "timsteps" rather than timesteps.

--- Rod

[soniCron]

Btw, your link to Wikipedia refers to "timsteps" rather than timesteps. Hmmm... I figured he was trying to link to this (http://upload.wikimedia.org/wikipedia/en/a/a2/Tiny_tim_tiptoe_thru_the_tulips.ogg). (Please, tell me somebody gets it! :))

[Kai Backman]

... but its probably a bit harder to code.

And this is the part I hope to mend. :) Once you know the basics is pretty much the same as any other system around. I think part of the reason why DES has the image of being a complex is the fact that it's used in military and aviation simulations. Those guys spend 98% of the time proving that the simulation provides high fidelity in respect to the original model. Games don't have such strict requirements so it's much easier for us. It's just a loop in the end ..

Thanks Rob, fixed.

[Kai Backman]

Ok. Discrete event simulation for games, Part 2 (http://www.kaibackman.com/development/2005/09/discrete_event_.html) posted with source code and one answer to Adrians riddle about the data structure where to keep the list of next updates. Enjoy! :)

[Mark Currie]

I do something like this for my game. It can really cut down on the processing. For example, instead of updating a unit's position every tick, I update the position when important--when it moves to a new tile. If the unit is on screen, then the graphics engine will do extra work to see exactly where the unit is at, so that is looks like it's moving smoothly to the next tile. The smoothness is perfect--equal to your frame rate, it's not based on the number of game updates per second.

I'm not sure if this is exactly what Kai is talking about, but it can REALLY cut down on processing--to only process objects when they really need to be processed, instead of every game tick.