AvalonLife’s Architecture
Most of this article is about the new GUI technologies in Windows Presentation Foundation, but I think it is worth devoting a few free web column-inches to the nature of the model and controller. I’ve always enjoyed simulation programming, and although this is a very simple simulation it does illustrate some interesting techniques. Some of the decisions made in the design of the model and controller are driven by the needs of the interface, however they have been implemented in a way that preserves layer autonomy and avoids creating couplings, so I hope to be forgiven this minor breech of architect-iquette. Since the heart of any simulation is its model of the world, let’s start with that.
The model for AvalonLife is implemented in the file LifeModel.cs. You can refer to it in listing 1. This file adds two classes to the AvalonLife namespace. The first is LifeCell, which is a simple representation of the state of a single cell in the life grid. That state is represented by the boolean property IsAlive, with the ‘on’ state corresponding to a value of ‘true’ for this member. Why implement a cell in this way? Isn’t there a much more compact representation of the Life grid, say, an array of bit flags? The answer is yes, but recall that our aim here is to demonstrate the power of the WPF. Just why the grid is implemented as a collection of LifeCell objects will become clear when we look at the GUI, but you can get a hint by examining the class definition a little more closely. You’ll note that LifeCell implements INotifyPropertyChanged, one of the interfaces that classes can implement if they wish to alert data-bound UI elements of changes in their state. You’ll also notice that the set{} clause for the IsAlive property implements change notifications through a call to the INotifyPropertyChanged.PropertyChangedEventHandler delegate. I’ll talk more about how this is used when we look at wiring up the layers to the UI.
The second class implemented in LifeModel.cs is the actual model itself, which is contained in the definition of the LifeModel class. The role of the model in the sample program is to create and manage the state of a grid of LifeCells. LifeModel also implements INotifyPropertyChanged, so that it can support binding for a couple of properties I’ll discuss later, as well as ISerializable so that we can stream the model to disk. I’m not going to talk in detail here about the design or implementation of this class, or the controller class either, but I do want to hit a couple of the high points. The first thing to note is that in addition to the main grid of LifeCells, stored in the _cellGrid private member, there are three other two dimensional arrays being maintained by LifeModel. Two of these are arrays of bools that simply capture the state of the grid at two points in time: startup, and the result of the last evaluation. The first is used to revert the model back to its initial state, while the second is used in comparisons to see if the model has stopped evolving, as many Life models do eventually. The fourth array is another grid of LifeCells called _workGrid, and what this does is pretty important to the overall operation of the model. The problem to be solved is how to treat cells that live on the edges of the grid.
Conway’s original mathematical universe for Life models was infinite, but the actual models he evaluated ran on graph paper that certainly had some physical limitations. There are similar limitations on the world of a computer simulation too. The model can’t just keep growing in all directions as cells propagate. There has to be some defined way to limit the size of the grid. The simplest solution is just to treat it as a finite space. When you get to a cell on an edge it doesn’t have eight neighbors; it has five. This dramatically effects what happens to models at the edges, but it is one valid approach to the problem. Another way is to treat the grid as a torus: each edge wraps to the opposing edge. Modifications to this idea treat the grid as a cylinder: the Y edge wraps, for example, but the X edge does not. AvalonLife supports switching back and forth between all these approaches at will, and it does so using the work grid. The work grid is created after the initial model is constructed, and is two cells larger than the model grid on both axes. The program treats the model grid as centered in the working grid, so the working grid provides a one cell-wide border all around the model grid. The working grid is built in a function called BuildWorkGrid(). This function initializes all of the cells in the work grid that correspond to cells in the model grid with object references to those cells. So you can think of each cell in the center of the work grid as “pointing to” the corresponding cell in the model grid. The edge cells are treated differently. If an edge wraps then the work grid cell is pointed to a cell on the other edge of the grid. If the edge does not wrap then the work grid cell gets a LifeCell that will always be off. In this way any edge can be set to wrap or be treated as finite, while the function that applies the rules to cells can simply ignore the limitations of a finite grid, making for simpler, faster code. You can change the grid type in the Settings | Grid Type submenu at any time. You’ll see that the program displays thick gray bars on impassable (finite) edges.
Experienced .Net programmers may cringe to see that I have used multidimensional arrays for all of the structures just discussed. It seems to make sense, doesn’t it? C# has a nice syntax for multidimensional array access, and after all, the grids clearly are multidimensional arrays. In fact this practice turns out to be so bad that the fxcop utility complains about it. A better alternative in .NET is to use so-called ‘jagged’ arrays, or arrays of arrays. How can this be better? It can be better because the implementation of multidimensional arrays in the CLR is so horrid that it is actually more efficient to have an array of arrays. I wasn’t aware of this when I started, and plan to go back and change the grids to jagged arrays at some point to see how much performance improves. For various reasons I don’t think array access is any kind of bottleneck in this program. If you’re interested in the reasons for the persona non grata status of multidimensional arrays in .NET, see Ming Chen’s post on the topic at thescripts.com.
A couple of other quick points on the model, and then I’ll get into the controller briefly before finally moving on to the UI stuff, which is what I meant to talk about in the first place. The model is responsible for two other big chunks of the program behavior: saving itself to and from streams, and applying the game rules to cells. The first responsibility is discharged in two different ways. First, LifeModel supports ISerializable, and implements the appropriate constructor and GetObjectData() method. This is how the native .AVL format save file is created. I had to implement ISerializable, rather than getting it on the cheap with the [Serializable] attribute, because I needed to skip serialization of the delegate types that are used in property binding. I’ll talk more about that later. The other way that LifeModel supports saving and restoring itself is through the LifeModel(Stream) constructor, and the LifeModel.StreamCells() method. These methods understand a stream of data in the .CELLS format supported by the Life Lexicon website, and are used to support drag-n-drop loading of Lexicon models, as well as saving them to and from disk. The .CELLS format is very sparse, and loads very quickly, but it does not save as much of the model’s state as the .AVL format does, and so I recommend using that when saving and loading models from disk.
The last interesting thing about LifeModel is the Evaluate() function. This where the rules of the Game of Life are applied to the cells in the grid. Evaluate is responsible for applying the rules once. It takes an existing state and transforms it into a new state. One trick in doing this is that you cannot change the cells as you go, because you would be changing the way the rules apply to other cells. You need to first calculate the new state from the existing grid atomically, and then apply the changes. I do this using a temporary grid to hold the new state until I get to the end. For each cell the Evaluate function calls CountAdjacent(), which uses the work grid to count the neighbors of the cell being evaluated. It returns an integer between 0 and 8 for the count of live neighbor cells. Based on this count the current cell is turned on or off according to the rules. Evaluate has two other responsibilities: it saves the starting grid the first time through, so the model can be restored, and it also retains the previous state and uses it at the end to check for stability in the model. If it detects that the model is stable it sets a property to true that will trigger behavior in the controller. And speaking of that, this is a good time to take a look at the C part of AvalonLife’s MVC architecture.
The simulation controller is implemented in the LifeSim class, in file LifeSim.cs. You can refer to it in listing 2. The controller has three primary responsibilities: first, it manages the creation of the model; second, it provides the entry point for serialization of a model; and third it provides some UI thread time for running the model. I’ll look at each of these responsibilities briefly. LifeSim owns an instance of LifeModel. In the default case it constructs this model when it constructs itself. Two other methods are provided, versions of LifeSim.NewModel() that cause the controller to ditch its current model and create a new one. These are used for loading from streams of .CELLS data, as well as creating a new model from the game menu. LifeSim exposes its LifeModel through the Model property, and as you’ll see later this is used by the UI to get at the model for various properties, and to wire up certain data bindings. Some of this makes architectural sense, while other parts will stand out as being contrived for the example. While I haven’t labored here to keep the MVC model pure, I don’t think there are too many ill-advised couplings between layers. The LifeModel doesn’t know anything about the UI or the LifeSim class. The LifeSim class doesn’t know anything about the UI. The UI knows about the LifeSim and the LifeModel classes. So both the model and controller are independent of the UI. The one place where this conclusion might be called into question is in the case of data binding. Data binding through INotifyPropertyChanged is clearly there to support the UI’s presentation needs, but since it is a third-party contract that is passive from the perspective of the data source, I can’t get too worked up about it. I think data binding and how it should be used presents other challenges, and I don’t care for binding directly from the UI into a database, but I don’t necessarily think it increases semantic connections between publishers and consumers.
LifeSim’s role in construction is thus pretty straightforward: the UI creates an instance of a LifeSim, and the LifeSim creates an instance of the model. If the UI wants a new model it tells the LifeSim to make a new one. If it needs to read the model directly it uses LifeSim’s Model property. The role of the controller in serialization is similarly straightforward. When the UI wants to save or load a model it creates the appropriate stream and hands it off to the LifeSim, which serializes itself and then serializes the model. Like the model class LifeSim implements ISerializable and the proper constructor and GetObjectData() method. Also like the model class it implements the serialization interface to get around serialization of delegates, in this case not only the data binding event notification delegates, but also one callback delegate whose operation I will discuss in the next section. LifeSim is also similar to LifeModel in how it handles streams from the Life Lexicon site. When the UI gets a link to a .CELLS file it opens a stream using HttpWebRequest() and then hands it off to LifeSim.NewModel(Stream). This function creates a new LifeModel from the stream, and the LifeModel does most of the decoding work as described above.
The last part of LifeSim that I want to talk about is how it gets thread time for running the model. Windows Forms, and the whole .Net platform, is an event-driven framework throughout. The main thread of an application is typically looping somewhere off in the framework (in Application.Main() to be specific), processing events, and calling down into your code when something happens that you have asked to be notified about. You request notification of events by registering event handlers using the delegate type. It’s as easy as calling MyUIElement.MouseLeave += new MouseEventHandler(MyMouseEventHandler). When the mouse pointer leaves MyUIElement your method gets called. It’s a beautiful thing, but it falls somewhat short when you want to have a simulation running all the time, whether there is user input or not. There are a couple of ways to do this. The hardest, and most error prone, is to create your own worker thread to run the model. I thought deeply about this for 2.5 seconds before rejecting it. I think creating your own threads is a major-league last resort for problems where a workload must be decomposed across multiple processing units, or you need to keep the UI responsive in the presence of a heavy background workload. Another technique is to overload Main() in your Application-derived class and run a while() loop that calls into your simulation on idle. This is a fine approach but requires more management than the technique I chose, which is to have the LifeSim class create a timer during construction.
The nice thing about a timer is that you can get control over simulation speed by setting the timer interval. If you run an idle loop you need to count time and run your sim at defined intervals. Nothing too hard about that, but why do it if you don’t need to? Instead I used System.Windows.Forms.Timer to periodically execute the model. There are several other timer classes in .Net that might have been used for this task, but the nice thing about System.Windows.Forms.Timer is that it uses the UI thread, meaning that the UI stays responsive, and your timer event handler won’t get called if the UI is doing something important. In other scenarios that might be a bad thing, but AvalonLife doesn’t need to adhere to any notion of realtime. As long as we get regular chances to run the model that’s good enough. The default period established for this timer is 1000 milliseconds. It can be adjusted in 100 ms increments down to 100 ms using the slider control on the right side of the status bar. When the timer fires it calls a static method named TimerEvent() in LifeSim. Why is this static? That’s just the way this timer is designed. If it were going to know enough about my LifeSim class to call a method on an instance then my class would have to derive from some base that the timer knows about. Instead it requires a static method, and I shove the instance reference into the Tag property of the timer, where it is easy to get at in the event handler. Useful little things, Tags. The event handler does four things: first, it checks the LifeSim.IsPaused property and exits if it is true. The timer is always running in the background, but if the sim is paused the handler doesn’t do anything. If the sim isn’t paused then the handler runs the model by calling LifeModel.Evaluate(). It then checks the LifeModel.EvoHalted property to see if the model has entered stability. If it has, and the UI has registered a callback function, and the settings say that the model should be halted when stable, then control is passed to the callback so that the UI can do whatever it wants to with the event.
That’s enough detail on these two classes, I think. You should have an idea at this point of the roles that they play in the program. There are a number of other classes in the program that play supporting roles, and which won’t get a detailed treatment here either. If you want to look at them in more detail you’ll find the source pretty liberally commented, and there’s nothing like stepping through it for getting a sense of what’s happening. In the next section I’ll dive into what really sets .NET 3.0 and the WPF apart from previous ways of building Windows applications: XAML.
Introduction
Part 1 – The Game of Life
Part 2 – AvalonLife’s Architecture
Part 3 – XAML and the User Interface
Part 4 – Resources and Styles
Part 5 – Drawing the Grid
Part 6 – Conclusion