I remember discovering Michael Abrash in the early 90s and being amazed with both his writing style and the crazy amount of speed he produced from “slow” machines. When I started researching this project, I was quite excited to remember he had written two chapters (17 and 18) in Graphics Programming Black Book on the Game of Life.
(… an hour later)
Damn you, Wikipedia! I just spent ages reading about American McGee, Graeme Devine, 7th Guest, 11th Hour, Clandestiny, George “Fat Man” Sander, Wing Commander, Prophecy, Privateer, and Freelancer. Sigh. Back to this post.*
My first goal is to discover whether starting with the naive algorithm for the game using vector graphics under Metro (Windows 8) leads to the same optimization path as the book. The second goal will be to take a “reasonable” performing version of the algorithm and wrap a Metro (are we allowed to use that term still?) game around it, taking advantage of what the platform has to offer.
The Rules
Rather than having to flip back and forth between this page and the Wikipedia entry, here are the rules of the game:
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Simple enough :) Let’s get coding under Metro Windows 8 Store-style application.
Start with File > New Project > (Installed > Templates >) Visual C# > Windows Store > Blank App (XAML)
I’m calling my project “LifeInMetro” as a tribute to “Life in Mono” – you get five points if you recognize the reference. The code is on GitHub if you’d rather not type it in yourself :). We’ll use a simple MVVM pattern for now (i.e. no frameworks).
Add a LifeViewModel class with a single integer property named Generation and implement INotifyPropertyChanged.
using System.ComponentModel;
namespace LifeInMetro
{
class LifeViewModel : INotifyPropertyChanged
{
private int generation;
public event PropertyChangedEventHandler PropertyChanged;
public int Generation
{
get
{
return generation;
}
set
{
generation = value;
if (PropertyChanged != null)
{
PropertyChanged(this, new PropertyChangedEventArgs("Generation"));
}
}
}
}
}
Assign the DataContext in MainPage and add some needed constants.
private const int MapWidth = 96;
private const int MapHeight = 96;
private const int CellSize = 5;
private readonly LifeViewModel viewModel;
public MainPage()
{
this.InitializeComponent();
viewModel = new LifeViewModel();
DataContext = viewModel;
}
Add a TextBlock (to display the generation) and Canvas to MainWindow. The Canvas will need a name for later (mine is called LifeCanvas).
<Page
x:Class="LifeInMetro.MainPage"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:local="using:LifeInMetro"
xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
mc:Ignorable="d">
<Grid Background="{StaticResource ApplicationPageBackgroundThemeBrush}">
<Grid.RowDefinitions>
<RowDefinition Height="Auto"></RowDefinition>
<RowDefinition></RowDefinition>
</Grid.RowDefinitions>
<Grid>
<Grid.ColumnDefinitions>
<ColumnDefinition Width="Auto"></ColumnDefinition>
<ColumnDefinition></ColumnDefinition>
</Grid.ColumnDefinitions>
<TextBlock FontSize="24">Current Frame:</TextBlock>
<TextBlock FontSize="24" Margin="10 0 0 0" Grid.Column="1" Text="{Binding Generation}"/>
</Grid>
<Canvas Grid.Row="1" x:Name="LifeCanvas" Width="480" Height="480"/>
</Grid>
</Page>
The Canvas is the first departure from Chapter 17: I am hoping that we can ignore pixels and bitmaps and use Metro’s vector capabilities intead.
Create a CellMapDisplay (equivalent of all the drawing routines) and add an instance to MainWindow
public class CellMapDisplay
{
private readonly Canvas canvas;
private readonly int numberCellsAcross;
private readonly int numberCellsDown;
public CellMapDisplay(Canvas canvas, int numberCellsAcross, int numberCellsDown, int cellSize)
{
this.canvas = canvas;
this.numberCellsAcross = numberCellsAcross;
this.numberCellsDown = numberCellsDown;
for (int y = 0; y < numberCellsDown; y++)
{
for (int x = 0; x < numberCellsAcross; x++)
{
var cell = new Rectangle();
cell.Width = cellSize;
cell.Height = cellSize;
cell.Fill = new SolidColorBrush(Colors.Black);
Canvas.SetLeft(cell, x * cellSize);
Canvas.SetTop(cell, y * cellSize);
canvas.Children.Add(cell);
}
}
}
public void DrawCell(int x, int y, bool on)
{
var cellRectangle = canvas.Children[y * numberCellsAcross + x] as Rectangle;
cellRectangle.Fill = on ? new SolidColorBrush(Colors.White) : new SolidColorBrush(Colors.Black);
}
}
Create a CellMap class and implement the code from listing 17-1. Add two instances (currentMap and nextMap) to MainWindow.
public class CellMap
{
private byte[] cells;
private int width;
private int height;
public CellMap(int height, int width)
{
this.width = width;
this.height = height;
cells = new byte[width * height];
}
public void CopyCells(CellMap sourcemap)
{
Array.Copy(sourcemap.cells, cells, sourcemap.cells.Length);
}
public void SetCell(int x, int y)
{
cells[width * x + y] = 1;
}
public void ClearCell(int x, int y)
{
cells[width * x + y] = 0;
}
public int GetCellState(int x, int y)
{
while (x < 0) x += width;
while (x >= width) x -= width;
while (y < 0) y += height;
while (y >= height) y -= height;
return cells[width * x + y];
}
public void NextGeneration(CellMap destination, CellMapDisplay display)
{
for (var y = 0; y < height; y++)
{
for (var x = 0; x < height; x++)
{
// Figure out how many neighbours this cell has
var neighbourCount = GetCellState(x - 1, y - 1) + GetCellState(x, y - 1) +
GetCellState(x + 1, y - 1) + GetCellState(x - 1, y) +
GetCellState(x + 1, y) + GetCellState(x - 1, y + 1) +
GetCellState(x, y + 1) + GetCellState(x + 1, y + 1);
if (GetCellState(x, y) == 1)
{
// The cell is on; does it stay on?
if (neighbourCount != 2 && neighbourCount != 3)
{
destination.ClearCell(x, y);
display.DrawCell(x, y, false);
}
}
else
{
// The cell is off; does it turn on?
if (neighbourCount == 3)
{
destination.SetCell(x, y);
display.DrawCell(x, y, true);
}
}
}
}
}
}
Add a timer to MainWindow that draws 18.2 times times / second
timer = new DispatcherTimer();
timer.Interval = TimeSpan.FromMilliseconds(1000 / 18.2);
timer.Tick += timer_Tick;
protected override void OnNavigatedTo(NavigationEventArgs e)
{
timer.Start();
}
private void timer_Tick(object sender, object e)
{
viewModel.Generation += 1;
currentMap.NextGeneration(nextMap, cellMapDisplay);
currentMap.CopyCells(nextMap);
}
And that should do it! Running the app will produce something like this:
All seems well, except that if you take a look at CPU usage, it’s a tad on the high side. On a 4-core machine, we peak at around 20% and gradually drop down to 8%. While this may not seem like a lot, keep in mind that since it’s not a multi-threaded application, we’re using 30 to 80% of one core! Surely something can be done…
* For any Black Books fans, you will remember Bernard’s line in S01E01: “Right, that’s all of my socks paired. Back to the accounts.” It seems appropriate here.
Comments