This tutorial will show you how to configure, display and interact with a cellular automaton using DrAutomaton by the example of Gosper's glider gun (see below). The impatient may skip right ahead to Creating a cellular automaton.
A 2D cellular automaton (CA) operates on an underlying two-dimensional space, divided into rectangular cells. Each cell has a current state state. According to a set of rules defined by the cellular automaton, the cells change their state in the next generation.
For example, Conway's Game of Life uses two states, dead and alive, and the cells change depending on the number of dead and live cells in their neighborhood. For details, see Wikipedia: Conway's Game of Life
The underlying space is represented by the Space class.
Every Space object
has a limited width() and height(),
unlike its mathematical counterpart.
Each of its cells may be acquired
by virtue of its cell coordinates,
(x, y),
where 0 <= x < width() and 0 <= y < height().
The top-left cell is (0, 0),
and the indexing is column-major.
The space may or may not be equipped with a geometry.
By default, the cellular automaton operates on a rectangular space in a plane,
but Space may also represent
A geometry defines the states of cells outside of the finite bounds of the space,
effectively either extending the space infinitely using default values,
or glueing the sides of the space together,
creating such geometries as a torus
(Wikipedia: Torus)
or the real projective plane
(Wikipedia: Real projective plane).
More on that in Geometries.
The Cellular class template is in charge of all asynchronous computations on the space
(call doUpdate to compute the next generation of cells).
Computations are done on the CPU,
although much higher framerates could be reached when parallelizing on the GPU).
It's template parameter Rule specifies a class which
implements the interface IRule and defines the exact way
(for details, see Implementing rules).
Every Cellular class holds an underlying Space object
(created upon construction),
which it exposes to the Model
(more of that later).
Although the user is in charge of creating the Cellular object,
they should never use it beyond specifying the Rule parameter
and (optionally) setting the geometry via
void setGeometry(std::shared_ptr<AbstractGeometry>);(for details, see Geometries).
Instead,
the Cellular object should always be driven by a model.
DrAutomaton uses the typical Model/View pattern for displaying
Cellular objects.
Model is a class template,
the template parameter is the Rule.
The model's job is to convert every
generation of the cellular automaton into
vertices (type std::vector<int>).
Every vertex represents a cell of the CA.
The View uses these vertices as keys for the coloring map.
But the model only renders its viewport,
not the entire CA.
The viewport is a rectangle inside the underlying space
(by default,
the viewport is equal to the underlying space).
In particular,
the width() and height() of the model
aren't always equal to the width() and height() of the underlying space.
Every Model is driven by a View,
which inherits QQuickItem.
Furthermore,
View controls the framerate,
start/stop toggles and key/click events.
All of these can be configured using QML.
An important point is the conversion from state to vertex.
This is done by static_cast.
Therefore,
the state type of every rule must implement operator int().
For details,
see Implementing rules.
Note that View is not a QQuickView itself,
but a QQuickItem.
As such,
it can be registered to QML and used in .qml to create scenes.
A QQuickView is only required to render the scene
that is defined in the .qml file.
This tutorial is based on the example samples/glider,
in which we define a cellular automaton for displaying Gosper's glider gun.
Checkout Glider.cpp.
Start off by registering the View class to QML:
qmlRegisterType<View>("DrAutomaton", 0, 0, "CellularView");(We don't care about version numbers...)
Next, we create the Cellular object.
Unfortunately,
this is not a QML object and must be configured in the .cpp.
auto cellular = std::make_shared<Cellular<GameOfLife>>(70, 70);The template parameter is GameOfLife
(Conway's Game of Life, the set of rules we're using).
The arguments are width and height of the underlying space
(70 by 70).
The space will automatically be filled with the default state
(the result of default constructing T = GameOfLife::State),
in this case GameOfLife::State::dead.
We fill the space with live cells by using the fill method
of the underlying Space object:
cellular->space().fill(
1, 1,
{{".", GameOfLife::State::dead},
{"O", GameOfLife::State::live}},
// Gosper's glider gun, created by Bill Gosper in 1970.
{".......................O",
".....................O.O",
"............O.......O.O...........OO",
"...........OO......O..O...........OO",
"OO........OO....OO..O.O",
"OO.......OOO....OO...O.O",
"..........OO....OO.....O",
"...........OO",
"............O"}
);The last parameter is a std::vector<std::string>.
Every element of the vector represents one row of the underlying space.
Dead cells are represented by ., live cells by O
(this is the notation popularized by www.conwaylife.com).
This encoding is passed to the fill method
using the std::unordered_map<std::string, T> in the third parameter.
The fill method maps this pattern into the space.
The upper-left character corresponds to the cell with coordinates
equal to the first two parameters.
The geometry of the space is defined as Border,
with default value equal to GameOfLife::State::dead:
auto geometry = std::make_shared<geometry::Border<GameOfLife>>();
geometry->setDefault(GameOfLife::State::dead);
cellular->setGeometry(std::move(geometry));This means that when the GameOfLife rules access
a cell that is outside the bounds of the underlying space,
asy (-1, 23),
then this cell will count as dead.
(This will happen,
for example,
every time the Moore neighborhood of a cell at the boundary
of the underlying space is accessed,
say (0, 23).)
The geometry should always be set via Cellular::setGeometry,
not Space::setGeometry.1
The viewport of the model is configured to only show a 4:3 rectange wedged in the upper-left corner of the space:
auto model = std::make_shared<Model<GameOfLife>>(std::move(cellular));
model->setViewport(0, 0, 52, 39);This will create the illusion that the CA operates on an infinite space, when actually the gliders crash into an invisible wall right outside the viewport.
Next up is QML configuration, which is quite straightforward:
QQuickView view;
view.setSource(QUrl{"qrc:/glider.qml"});This is the usual pattern
(there's a .qrc file which points to glider.qml, which configures the QML scene).
Let's take a look at glider.qml!
When defining a CA without any keyboard or mouse interaction, it would be perfectly reasonable to do this:
CellularView
{
id: root
width: 800
height: 800
}(Cf. samples/cyclic.)
Let's skip over the width and height parameters
(these don't have to have anything relationship with the width() and height() of the model,
although they should yield the same aspect ratio if you want square cells).
If you want keyboard or mouse interaction,
extra source code is required.
For mouse input,
we place a MouseArea together with CellularView into a root Item,
then connect the onPressed/onPositionChanged to the onClicked handler of View.
Clicking a cell will call the rule's increment method,
which will increment the clicked cell's state:
// Forward mouse events.
MouseArea
{
anchors.fill: parent
acceptedButtons: Qt.LeftButton
onPressed:
{
view.onClicked(mouse.x, mouse.y)
mouse.accepted = true
}
onPositionChanged:
{
view.onClicked(mouse.x, mouse.y)
mouse.accepted = true
}
}For keyboard input,
the root object requires focus.
Our typical setup is to map 1 to 4 to different framerates,
space bar to start/stop toggle and return to showNextGeneration.
The last one allows you to advance the CA by one generation
without toggleing the CA on/off:
// Key mapping.
focus: true
Keys.onPressed:
{
switch(event.key)
{
case Qt.Key_1: { view.setFramerate( 3); break; }
case Qt.Key_2: { view.setFramerate( 8); break; }
case Qt.Key_3: { view.setFramerate(20); break; }
case Qt.Key_4: { view.setFramerate(60); break; }
case Qt.Key_Space: { view.toggle(); break; }
case Qt.Key_Return: { view.showNextGeneration(); break; }
}
}The configuration of the View object itself can be done in QML
using the Component.onCompleted slot.
You can set the color using
void setColor(int vertex, int r, int g, int b);
which sets the RGB values of the color of vertex,
or the framerate (in fps/Hz).
Using start() or toggle(),
the CA may be started upon creation.
CellularView
{
id: view
objectName: "view"
anchors.fill: parent
anchors.margins: 0
Component.onCompleted:
{
setColor(0, 255, 255, 255)
setColor(1, 0, 0, 0)
setFramerate(8)
start()
}
}Here, we're mapping dead cells (0) to white (255, 255, 255)
and live cells (1) to black (0, 0, 0).
Finally, we need to go back to the C++ side.
In fact,
we have to set the model of the View object that was created on the QML side:
auto automaton_view = view.rootObject()->findChild<View*>("view");
automaton_view->setModel(std::move(model));(This is why we need the objectName field in CellularView.)
If you'd rather use C++ for configuring the Cellular object,
this can be done by calling the same methods as in the Component.onCompleted slot
on the C++ side:
automaton_view->setColor(0, 255, 255, 255);
automaton_view->setColor(1, 0, 0, 0);
automaton_view->setFramerate(8);
automaton_view->start();1
Cellular actually holds two instances of Space,
the one exposed to Model,
and a temporary for computations
(obviously, the computations cannot be done in place).
Following the computation,
the temporary is moved onto the exposed instance
and then replaced with a new copy.
Thus,
the effects of setting the geometry via space().geometry(/* ... */)
will last for only one frame,
followed most likely by a segfault when rule_ dereferences a nullptr.
The role of geometries is to allow any int to be used as coordinates
for a cell using modulo operations or default values.
This changes the geometry of the underlying space from a rectangle in a plane
to that of a torus, a projective plane, a Möbius strip, a Klein bottle, a Cylinder, etc.
The problem a programmer faces when implementing rules
such as Conway's Game of Life is that at the boundaries of the space
the notions of neighborhood (Moore, (extended) von Neumann, etc.) fails
due to the finiteness of the underlying space:
If the space has dimensions 20x30,
then what are the cells in the Moore neighborhood of the cell at (0, 17)?
Does it contain (-1, 17)? If yes, which cell is it?
Geometries provide a convenient and unified way for implementations of rules
to apply the notion of neighborhood,
even on a computer.
The idea is to somehow provide a value,
even if the space doesn't have a cell at coordinates (-1, 17).
In case of the torus geometry,
instead of the out-of-bounds coordinates (-1, 17),
the coordinates are replaced by their unique representatives mod. width (resp. height)
in the interval [0, width) (resp. [0, height)).
This amounts to glueing the horizontal and vertical edges of the rectangle together,
forming a donut-shaped space (called a flat torus).
Other geometries use default values,
such as geometry::Border,
which returns a default value on all out-of-bounds coordinates,
effectively creating a wall of cells with uniform state.
The geometry is only used when calling Space::geometricCell,
not used when calling Space::cells (const and non-const).
As it returns references to default values,
only a const-version of geometricCell exists.
It would be a good rule to only use geometricCell in rule implementations,
and let the user worry about space bounds everywhere else.
Geometry classes are contained in the namespace geometry.
The rules are injected into the Cellular object using templates.
To create new rules, you must implement a class that satisfies the
interface specified in src/IRule.h:
/* Interface for rules --- not to be included in any code! */
class IRule
{
public:
using State = T; // Where T is a type with operator int();
// Compute the state of the cell at the coords `(x, y)` of `space` in
// the next generation.
T transition(int x, int y, const Space<T>& space);
// Return the state obtained by incrementing the state of `t` by one.
T increment(const T& t);
};(Once C++20 is commonplace, we will define a Rule concept.)
Note that the State type must be equipped with a conversion
operator int(),
as we rely on static_casting the states.
In most cases, an enum is sufficient as state class
(Cyclic, whose CyclicStates require the isSucceededBy method,
is an exception to this).
It may be helpful to take a look at already implemented rules under
src/rules.
If you've implemented a well-known rule or something really cool, we'd
be happy if you made it a contribution to DrAutomaton.
Let us know!