Introduction
Conway's Game Of Life is a famous cellular automaton conceived in the early 1970's by mathematician John Conway. While the system is well known as "Conway's Game Of Life", it really isn't a game at all. Conway's system is more like a life simulation. Don't be intimidated. The system is terribly simple and terribly interesting. Math and Computer Science students alike have marvelled over Conway's system for more than 30 years now.
The application represented here is a Swing based implementation of Conway's Game of Life. The rules that govern the system are implemented as business rules using Drools. This document will explain the rules that drive the simulation and discuss the Drools specific parts of the implementation.
Getting Started
Before digging in to how the system works or even what it is really doing you should fire the application up and tinker with it a bit. Start by getting a copy of the source code if you have not already done so. You may download source bundles for milestone releases from the Project Downloads page. See CVS Download Instructions for details on how to retrieve the latest source code from CVS. Once you have a copy of the source code you need to build the system.
D:\java\workspaces\drools-2.0>maven __ __ | \/ |__ _Apache__ ___ | |\/| / _` \ V / -_) ' \ ~ intelligent projects ~ |_| |_\__,_|\_/\___|_||_| v. 1.0.2 build:start: (bunch of output)
Once you have compiled all of the source change to the drools-examples directory and launch the application by executing the "conway-java" maven goal.
D:\java\workspaces\drools-2.0\drools-examples>maven conway-java __ __ | \/ |__ _Apache__ ___ | |\/| / _` \ V / -_) ' \ ~ intelligent projects ~ |_| |_\__,_|\_/\___|_||_| v. 1.0.2 build:start: (bunch of output)
You will now be presented with a Swing gui that looks like this.
The grid represents the area where the life simulation takes place. Initially the grid is empty, meaning that there are no live cells in the system. Use the mouse to click on cells to bring them to life. Live cells are represented with green balls. Add several clusters of live cells to the grid like this.
Don't worry about matching the exact patterns represented in the screen shot. Just get some groups of cells added to the grid. Once you have groups of live cells in the grid click the "Next Generation" button and notice what happens. Some of the live cells are killed (the green ball disappears) and some dead cells come to life (a green ball appears). Cycle through several generations and see if you notice any patterns. If you click on the "Start" button, the system will evolve itself so you don't need to click the "Next Generation" button over and over. Play with the system a little and then come back here for more details. After playing with some free form patterns that you create interactively, notice that there are several predefined patterns in the system that you may activate by selecting them in the drop down list labelled "Pattern:".
The System Rules
Each time the system evolves there are a very simple set of rules that govern what the next evolution will look like.
- If a live cell has fewer than 2 live neighbors, it dies of loneliness
- If a live cell has more than 3 live neighbors, it dies from overcrowding
- If a dead cell has exactly 3 live neighbors, it comes to life
That is all there is to it. Any cell that doesn't meet any of those criteria is left as is for the next generation. With those simple rules in mind, go back and play with the system a little bit more and step through some generations one at a time and notice these rules taking their effect.
 | A Note About Neighbors Neighbors include not only cells to the left, right, top and bottom but also cells that are connected diagonally. Each cell has a total of 8 neighbors except the 4 corner cells and all of the other cells along the 4 edges. Corner cells have 3 neighbors and other edge cells have 5 neighbors. |
Implementation Details
The Java Code
Each time the "Next Generation" button is clicked, the nextGeneration() method is invoked on the CellGrid. When the system is evolving itself after the "Start" button has been clicked, this same method is invoked repeatedly. The first thing that nextGeneration() does is retrieves a Rule Base from a custom RuleBaseFactory and retrieves the Working Memory from the Rule Base.
Next, all of the Cells in the system are asserted to Working Memory. The Cells are stored in a 2 dimensional array.
Once the Cells have all been asserted the rules are fired and the system is transitioned to the next generation.
The complete method looks like this.
| Implementation Note Notice that after the rules are fired there is a call to transitionState(). Each generation of evolution is a 2 phase process. The 1st phase is iterating through the system visiting every cell and defining what that cell's state will be in the next generation. A cell's state (live or dead) is not allowed to change during this phase since changing a cell's state could impact the next cell. This 1st phase is accomplished with the call to fireAllRules(). After the rules have been applied then all of the cells are transitioned to their next state all at once. This 2nd phase is accomplished with the call to transitionState(). |
The Business Rules
The system rules are defined using the Drools Java semantic module.
If a live cell has fewer than 2 live neighbors, it dies of loneliness
If a live cell has more than 3 live neighbors, it dies from overcrowding
If a dead cell has exactly 3 live neighbors, it comes to life
The full drl file looks like this.
Conway's Domain Specific Language
The instructions above called for executing the "conway-java" maven goal to launch the application. The application may be executed in another mode by executing the "conway-dsl" maven goal from the same directory. The "conway-dsl" goal will take advantage of the Domain Specific Languages module to execute rules written in a DSL developed specifically for this application. The user experience will be exactly the same but behind the scenes the rules are implemented differently. The Conway DSL is fairly simple but demonstrates all of the pieces necessary to develop a more complex DSL. More detailed documention on the DSL implementation of Conway's Game Of Life is in development and will be made available soon.
Some Notes About The Application
It turns out that Conway's Game Of Life is a pretty good candidate for using a rule engine like Drools. There are a set of "business rules" that govern the system and using an engine like Drools allows those rules to be defined away from the rest of the application code. All of the rules that control the migration from one generation to the next are clearly defined and easy to maintain. Because of this clean separation it is trivial to play around with the rules and see how they affect the system without making any changes to the application code. For example, what happens if the criteria for being "overcrowded" is changed so that it takes at least 4 live neighbors to qualify? To explore that you need to change the condition spelled out in the rule file, that is it.
Detailed References On Conway's Game Of Life
- http://en.wikipedia.org/wiki/Conway's_Game_of_Life
- http://www.math.com/students/wonders/life/life.html