Chapter 2:

A Case Study:
Designing a Discrete Event Simulation

David Blackledge

This chapter presents a case study in the design of a Discrete Event Simulation of primitive life. We'll see how design patterns capture solutions to design problems in the simulation and applications like it.

This particular Discrete Event Simulation (DES) of life gives each life a goal, usually to get to a particular position, but these goals can be overridden by more pressing needs or desires such as hunger and procreation. They can also be altered by changes in the life's condition including disease and pregnancy. The "world" is littered with objects for the life forms to interact with including food, obstacles and dangers. The DES will maintain a display of one or more views of the world as well as some readouts of statistics on the life forms. The Discrete Event part of this simulation indicates that "events" will be generated by the world and acted upon discretely by each life. This means each event will be acted upon somewhat independently and more or less in parallel by each life.

2.1 Design Problems

We will examine several problems in the Discrete Event Simulation design.

  1. Event Queueing. We would like multiple types of events to occur, but we need our events queued in a simple, easy to understand, and easy to process manner.
  2. Multiple Views of Simulation Data Beyond simply seeing a display of all our life forms and where they are at the moment, which we may want in more than one window, we would like to see some statistics information updated with each event as well. All of these views must share the data from the individual watched lives.
  3. Choice of Action Based on Condition and Event Our life forms are not one simple stimulus-response pair. They will choose the appropriate action that is best for them at the particular time depending on their condition and what is going on around them.
  4. Actions Done independently of Condition and Event Even with the above, the life forms will have some particular behaviors that affect actions independently of the current conditions, yet may differ between sub-life forms.
  5. Allowing Apparent Parallel Action on Events One major issue with this kind of DES is that results from one life's actions may have bearing on what another life decides to do, so we want to have all life forms act only based on what was true at the end of the last event even though by the time a particular life gets its turn to act on the new event, many other life forms have already acted, changing the current environment.

"We discuss these problems in the sections that follow. Each problem has an associated set of goals plus constraints on how we achieve those goals. We explain the goals and constraints in detail before proposing a specific solution. The problem and its solution will illustrate one or more design patterns. The discussion for each problem will culminate in a brief introduction to the relevant patterns."

2.2 Event Queueing

The backbone of the simulation is the Event Generator. It will create a stream of events that shape how and when the life forms act. Each event, however, will require significant processing to occur before it is complete, so we would like to queue the generated events to be processed later. Also, we would like to have multiple kinds of events rather than simple step execution. We would like the queueing to work simply and independently of what events we have in the queue and have it be general enough that we can decide to add more kinds of events to the simulation later on without having to change a lot of code. The way to do this is to allow the queue to work with a generic event object so it does not need to know what kind of event it is, and new events would be of the same super-class, so the queue would automatically work with them as well.

We can solve this issue with the Command pattern which objectifies code, allowing it to effectively be passed around at will. The Event Generator will generate, somewhat at random, different events from the list of commands it has available, and place them in a queue. A separate function will de-queue and execute the commands when processing of previous commands has completed. We might, for instance, have a NormalEvent concrete command that simply allows each life to go about its business for another step. We might also have a DisasterEvent concrete command that, depending what subclass of disaster it is, chooses particular life forms to affect negatively, and contrastingly, we could have a BlessedEvent that affects life forms positively.

Sample Code

Here is what the code for the Event Generator might look like

class NormalEvent : Command { //... } class DisasterEvent : Command { //... } class BlessedEvent : Command { //... } void EventGenerator() { Queue<Command> eventQueue; int r = rand(); if(r > NORMAL_PROBABILITY) eventQueue.insert(new NormalEvent); else if (r > DISASTER_PROBABILITY) eventQueue.insert(new DisasterEvent); else if (r > BLESSED_PROBABILITY) eventQueue.insert(new BlessedEvent); }
This also allows us to use threading or multiple processes at once: one queueing events, another extracting and executing them.

2.3 Multiple Views of Simulation Data

To make the simulation interesting, we would like to watch it as it progresses, viewing areas of the "world" and all of the life forms in it. We would also like a list of running statistics to give an overall view of the system. All of these will need to share the data from any given life form, but will only be interested in a change in that data. They will commonly only be interested in certain life forms at a time as well such as those within the current area of the world, or health statistics only on life forms over 40 years of age.

Each of our views need to be updated when a life form they are watching changes. However, since many life forms will affect the data of other life forms around them, many changes may take place for the same life form during the same event. These complex interactions are such that we would like to only update the views when all changes have taken place to a particular life form rather than repeatedly updating the view every time the same life form changes.

Three patterns make their way into the solution of these problems. The Observer pattern Is used by each of the views and statistics. It allows a simple interface for the subjects being watched to notify the list of observers that a change has taken place so they may update themselves. Because of the complex interactions causing us to not want to update until all changes have taken place, the Mediator pattern can be used to strategize the decision of when the update actually gets called for the observers. It would be a man-in-the-middle of sorts for attempts by subjects to request an update from observers. Finally, we only want one of these Mediators, and we want it to be available globally by all of the appropriate objects. The pattern that facilitates this is the Singleton pattern.

See page 300 of the Design Patterns book for a diagram of this exact setup.

2.4 Choice of Action Based on Condition and Event

Each life has a mind of its own, so to speak. Each individual one decides what it will do next based on its own condition, goals, and perceptions of the "world" around it. We would like to have changes in what the life decides is more important to do next to be transparent to the rest of the program. This allows requests for the life to do its work, such as moving and acting upon what is available within its grasp, to look the same to the requester, no matter what the life's current condition and plans are.

We will solve this problem two-fold using the patterns State and Strategy. The State pattern will allow the life to change its entire function set, maintaining the same interface, by simply changing what State object it currently contains. The State object contains functions oriented towards whatever goal is most appropriate for that state. A Starving state will contain movements that have the short-term goal of finding food, and actions of eating anything nearby that is edible. A Satisfied state would move towards the greater goal, ignoring food, and acting only on objects that would prevent or assist the reaching of that goal.

The second level of the solution, the Strategy Pattern, allows the life to, within the current State, choose different methods of meeting the goals. If one method of getting from point A to point B isn't working, it can change its Strategy for the next try. Thus we may have movement strategies of AsTheBirdFlies, AvoidOtherLifeForms, and AvoidInanimateObstacles for instance. Different strategies may be appropriate for different Events as well.

Life Object Diagram
 / Life      \         ___________
|_____________|       / Hungry    \          ______________
|  state   *--+----->|_____________|        /AsTheBirdFlies\
 \___________/       | strategy *--+------>|________________|
                      \___________/        | ...            |

The final result is a life form that chooses its destination based on how it feels, then chooses how it gets there based on what's working.

2.5 Actions Done Independently of Condition and Event

Each life form can have its own, independent "ideals" that it feels it must act on no matter what condition it is in or what is going on around it. For example, a life with a "propensity towards violence" may feel it necessary that it attack every other life around itself before going on for every event. We would, however, like the life forms to have a general form that does not have to cater directly to those ideals. What we would like is to allow the sub-classes of the life forms to decide what to do before and after the requests for them to move or act or whatever else is requested of them without directly affecting the code of the super-life.

The perfect solution to this problem is the Template Method pattern. Using this pattern says that when you write the main function, you have it execute some otherwise empty operations prior to and/or following (or even in the middle of) the main function's execution. You then allow sub-classes to re-define those two functions, adding any additional personal behaviors they like without changing the definitions of the base functions of movement and action. An example might look like the following.

class Life { //... void Move() { BeforeMove(); // ... do move AfterMove(); } void BeforeMove() {} //Empty Template Function void AfterMove() {} //Empty Template Function } class MeanLife : Life { //... void BeforeMove() { BeMeanToNeighbors(); } void AfterMove() { GlareAtNewNeighbors(); } }

2.6 Allowing Apparent Parallel Action on Events

During the invocation of an event in the simulation, we would like to keep a copy of the current state of each life form because the next life form that does its work for the same event needs to base its choices on what was true for the first life form when the event began rather than the "future" state of the first life form. The problem is that we do not want to violate encapsulation when we keep that copy. We shouldn't look at the internal "organs" of the life form, but we do need to keep the information that is stored there without knowing what the information is for.

This is a complex problem, but it can be solved with the Memento pattern. With this pattern, we will ask the life form to give us a copy of itself. The life form itself will decide what data it needs to keep track of so it may reinstate itself in the current form. It then places all of that data in a structure that nobody else knows how to examine. When the life has finished its actions for the current event, we get another memento so we may give the life form its new state when the entire event has ended. Finally we give the life form the first memento so it is returned to its pre-event state, allowing the proper actions to be performed by all of the life forms that still need to execute for this event. When all life forms have done their work, they are all restored with the saved mementos of their newly calculated states and the event execution has completed.

Life Memento Interaction Diagram
                      aLife            PreMemento AftMemento
                        |                    :       :
                        |                    :       :
CreateMemento()        ---                   :       :
---------------------->| |new Memento(state)---      :
                       | |.................>| |      :
                       | |                  ---      :
DoEvent(event)         | |                   |       :
---------------------->| |                   |       :
                       |/                    /       /
                        /|                   /       /
CreateMemento()        | |                   |       :
---------------------->| |new Memento(state) |      ---
                       | |.........................>| |
SetMemento(PreMemento) | |                   |      ---
---------------------->| |                   |       |
                       | |GetState()        ---      |
                       | |----------------->| |      |
                       ---                  ---      |
                        |                    |       |
                        /                    /       /
                        /                    /       /
                        |                    |       |
SetMemento(AftMemento) ---                   |       |
---------------------->| |GetState()         |      ---
                       | |------------------------->| |
                       ---                   |      ---
                        |                    |       |

2.8 Summary

We've applied eight different patterns to the DES design:

  1. Command to allow different and easily queueable events,
  2. Observer to allow multiple views of the same information,
  3. Mediator to prevent excessive updates of Observers,
  4. Singleton to assure a single, global Mediator,
  5. State to allow actions based on the current state,
  6. Strategy to allow different options to perform an action,
  7. Template Method to allow independent behavior attached to actions, and
  8. Memento to allow apparent parallel actions.

There are many, many aspects to the Discrete Event Simulation, and all parts included could incorporate even more design patterns. Many of the ideas applied in this example are also easily applied to numerous other applications. This was only meant as an overview of the kinds of uses one can make of design patterns.