Rock, Paper, Scissors
aiautomatajavascripthtmlarchivedCellular Automata map and tiles
Cellular Automata are a way to model systems through interactions of 'cells'; individual entities, governed by a set of rules. Cells are updated at a desired rate through a series of steps, and the outcome of their interactions can be viewed and assessed.
In this article, we'll look at a simple Cellular Automata system written in Javascript & HTML, used to model interactions between three types of cells; Rocks, Paper, and Scissors. These cells are governed by these simple rules:
- If there is a "prey" type cell beside me, destroy that cell and create a new cell the same type as me (if there are multiple, choose one at random)
- Otherwise, if there are empty cells around me, move in to one of them at random
For the sake of readability I'll break this content down in to several seperate files. First of all, a map.js file, which will store the data for the tiles on which the cells move, beginning with a Tile class to hold the information about each tile and the cell which occupies it:
class Tile
{
constructor(cx, cy)
{
this.x = cx;
this.y = cy;
this.index = (cy * Map.width) + cx;
this.cell = null;
}
}
Our Map object itself will then store the dimensions of the map we'll be using, as well as an array of tiles which compose the map, and a generate function for creating a new map full of empty tiles:
var Map = {
width : 28,
height : 18,
tiles : [],
generate : function(w, h)
{
this.width = w;
this.height = h;
this.tiles = [];
for(var y = 0; y < h; y++)
{
for(var x = 0; x < w; x++)
{
this.tiles.push(new Tile(x, y));
}
}
}
};
We will also create a html document as the container for our canvas and for loading all of our javascripts:
<!DOCTYPE html>
<html>
<head>
<title>Rock, Paper, Scissors Automata</title>
</head>
<body>
<canvas id="map" width="600" height="400">
This example requires Javascript & Canvas
</canvas>
<script type="text/javascript" src="cell.js"></script>
<script type="text/javascript" src="map.js"></script>
<script type="text/javascript" src="core.js"></script>
</body>
</html>
Cell class
Now we'll create our Cell class and some associated information in the cell.js file. This file begins with two arrays, a list of active cells, and a list of new cells which have been created during this update loop (once the loop is completed, the new cells are added to the allCells list, and the newCells list is cleared):
var allCells = [];
var newCells = [];
We also use a global flag in this example, biasDir, which states whether or not we want cells to prefer to "hunt" by prioritizing their target in a clockwise order. If the value is false, the target of the cell is selected at random from neighbouring cells.
var biasDir = false;
We also create a list of possible cell types. Each type specifies its colour (for vizualisation purposes), and the type of prey it consumes:
var cellTypes = {
"rock" : { "colour" : "#00cc00", "prey" : "scissors" },
"paper" : { "colour" : "#0000cc", "prey" : "rock" },
"scissors" : { "colour" : "#cc0000", "prey" : "paper" }
};
In our cell class itself, we create the constructor for the Cell, which takes the x, y position at which the cell will be created, as well as the cells type (ct) and its prey type (cp). The new cell is added to the newCells list, and the tile at the position where the cell is being created is given a pointer to this cell:
class Cell
{
constructor(cx, cy, ct, cp)
{
this.x = cx;
this.y = cy;
this.tile = (cy * Map.width) + cx;
this.prey = cp;
this.type = ct;
this.alive = true;
newCells.push(this);
Map.tiles[this.tile].cell = this;
}
Our Cell class also has getNeighbours method, which simply gets the tile index of each neighbouring tile to the cell in the cardinal directions, providing the tile is not outside of map bounds:
getNeighbours()
{
var n = [];
if(this.y > 0) { n.push( ((this.y - 1) * Map.width) + this.x ); }
if(this.x > 0) { n.push( (this.y * Map.width) + this.x - 1); }
if(this.y < (Map.height - 1)) { n.push( ((this.y + 1) * Map.width) + this.x ); }
if(this.x < (Map.width - 1)) { n.push( (this.y * Map.width) + this.x + 1); }
return n;
}
The kill method for our Cell sets the alive flag to false, and removes the pointer from the cells tile to the cell itself:
kill()
{
this.alive = false;
Map.tiles[this.tile].cell = null;
}
We'll now begin the update function for the Cell class, that is called for every cell every update tick. The method begins by getting a list of valid neighbouring tiles, n, a flag ate, that keeps track of whether or not the cell has consumed a prey type cell, and a list of possible prey on neighbour tiles to select from at random:
update()
{
var n = this.getNeighbours();
var ate = false;
var prey = [];
We then loop through all of the neighbouring tiles, looking for prey for this cell. If a prey type cell is found and biasDir (directional biasing) is on, we consume the first suitable cell we found. Otherwise, a random suitable prey cell is selected at random. If the cell has eaten, it has completed the update function and we return true:
for(var x in n)
{
if(Map.tiles[n[x]].cell!=null && Map.tiles[n[x]].cell.type == this.prey)
{
if(biasDir)
{
Map.tiles[n[x]].cell.kill();
new Cell(Map.tiles[n[x]].x, Map.tiles[n[x]].y, this.type, this.prey);
ate = true;
break;
}
else { prey.push(n[x]); }
}
}
if(prey.length)
{
var p = prey[Math.floor(Math.random() * prey.length)];
Map.tiles[p].cell.kill();
new Cell(Map.tiles[p].x, Map.tiles[p].y, this.type, this.prey);
ate = true;
}
if(ate) { return true; }
Finally, if the cell hasn't eaten, we select a random empty cell to move in to if one is available:
var open = [];
for(var x in n)
{
if(Map.tiles[n[x]].cell == null)
{
open.push(n[x]);
}
}
if(open.length)
{
var d = open[Math.floor(Math.random() * open.length)];
Map.tiles[this.tile].cell = null;
this.x = Map.tiles[d].x;
this.y = Map.tiles[d].y;
this.tile = d;
Map.tiles[d].cell = this;
return true;
}
return false;
}
};
Finally, after the Cell class, we'll create an update function, which will call the update for each of the cells in turn in the allCells list:
function updateCells()
{
for(var x in allCells)
{
allCells[x].update();
}
After updating, we add all the newCells to the allCells list, clear the newCells list, and remove all cells that have had their alive flag changed to false:
for(var x in newCells) { if(newCells[x].alive) { allCells.push(newCells[x]); } }
newCells.splice(0, newCells.length);
var toRemove = [];
for(var x in allCells)
{
if(!allCells[x].alive) { toRemove.push(allCells[x]); }
}
while(toRemove.length > 0)
{
allCells.splice( allCells.indexOf(toRemove[0]), 1 );
toRemove.shift();
}
}
Rendering to Canvas
Our final file, core.js, manages our rendering, user input, etc. We begin by declaring a number of global variables, including a reference to the Canvas drawing context (ctx), the dimensions we'll draw each map tile & cell, (tileW, tileH), the dimensions of the Canvas we're drawing on (canvasW, canvasH), and variables for calculating framerate & the update rate when the animation is not paused.
var ctx = null;
var tileW = 20, tileH = 20;
var canvasW = 400, canvasH = 400;
var currentSecond = 0, frameCount = 0, framesLastSecond = 0;
var gameTime =
0, lastFrame = 0, lastUpdate = 0, updateDelay = 2000;
We'll also use some global flags to see if the animation is paused, if we want to run a step of the animation on the next frame update, and if we want to reset the animation completely on the next frame:
var paused = false;
var stepFrame = false;
var reset = false;
We also want to build a list of types the user can create, and the index in the list which can currently be created by the user:
var creatableTypes = [];
var createType = 0;
Our final global keeps track of the mouse state; whether or not it is over the canvas element, its position, and the point on the canvas the mouse was last clicked on (or null if there is no unprocessed click):
var mouseState = {
over : false,
x : 0,
y : 0,
click : null
};
Our onload function will begin by setting the canvasW, canvasH based on the actual dimensions of our webpages canvas. We then create a keypress even handler, which, depending on the key pressed, will cycle through the current type the cell type the user creates by clicking on the map (c), toggles the paused state on or off (p), tells the animation we want to animate a single step if the animation is currently paused (s), if we want to toggle a complete system reset (r), toggling directional biasing on or off (b), changing the speed of the automatic update rate (d), and filling in the whole map with random Cells (f):
document.addEventListener('keypress', function(e) {
if(String.fromCharCode(e.which).toLowerCase()=='c')
{
createType++;
if(createType>=creatableTypes.length) { createType = 0; }
}
else if(String.fromCharCode(e.which).toLowerCase()=='p') { paused = !paused; }
else if(String.fromCharCode(e.which).toLowerCase()=='s' && paused) { stepFrame = true; }
else if(String.fromCharCode(e.which).toLowerCase()=='r') { reset = true; }
else if(String.fromCharCode(e.which).toLowerCase()=='b') { biasDir = !biasDir; }
else if(String.fromCharCode(e.which).toLowerCase()=='d')
{
updateDelay+= 200;
if(updateDelay>=2000) { updateDelay = 200; }
}
else if(String.fromCharCode(e.which).toLowerCase()=='f')
{
for(var x in Map.tiles)
{
if(Map.tiles[x].cell!=null) { continue; }
var t = Math.floor(Math.random() * creatableTypes.length);
new Cell(Map.tiles[x].x, Map.tiles[x].y, creatableTypes[t], cellTypes[creatableTypes[t]].prey);
}
}
});
We also create a number of mouse event handlers to update the mouseState global depending on the action performed:
document.getElementById('map').addEventListener('mouseout', function() {
mouseState.over = false;
});
document.getElementById('map').addEventListener('click', function(e) {
if(e.which==1)
{
mouseState.click = [mouseState.x, mouseState.y];
}
});
document.getElementById('map').addEventListener('mousemove', function(e) {
// Get the position of the mouse on the page
var mouseX = e.pageX;
var mouseY = e.pageY;
// Find the offset of the Canvas relative to the document top, left,
// and modify the mouse position to account for this
var p = document.getElementById('map');
do
{
mouseX-= p.offsetLeft;
mouseY-= p.offsetTop;
p = p.offsetParent;
} while(p!=null);
mouseState.over = true;
mouseState.x = mouseX;
mouseState.y = mouseY;
});
The final purposes of our onload function will be to assign the 2D drawing context of the Canvas element to the ctx global, generate a new empty map, fill our creatableTypes global from the list of cellTypes, and then to let the window know it should call our updateMap method when it is ready to render to the Canvas:
ctx = document.getElementById('map').getContext('2d');
Map.generate(28, 18);
for(x in cellTypes) { creatableTypes.push(x); }
requestAnimationFrame(updateMap);
};
Finally, we create a single function, updateMap, which handles our general drawing, update processing, and handling flagged events such as resetting and stepping the animation. First of all, this function updates timers to keep track of update events and framerate:
function updateMap()
{
if(ctx==null) { return; }
// Framerate & game time calculations
var sec = Math.floor(Date.now()/1000);
if(sec!=currentSecond)
{
currentSecond = sec;
framesLastSecond = frameCount;
frameCount = 1;
}
else { frameCount++; }
var now = Date.now();
gameTime+= (now-lastFrame);
lastFrame = now;
Next, if the reset event has been toggled, or if the animation should proceed another step due to the step event being toggled or because enough time has elapsed since the last update, these events are processed accordingly:
if(reset)
{
reset = false;
allCells.splice(0, allCells.length);
newCells.splice(0, newCells.length);
Map.generate(Map.width, Map.height);
}
if((paused && stepFrame) || (!paused && updateDelay!=0 && (gameTime-lastUpdate)>=updateDelay))
{
updateCells();
lastUpdate = gameTime;
stepFrame = false;
}
Additionally, if the mouse has been clicked on the Canvas, and the click event falls on a map tile, check the tile is free of occupying cells; if so, create a new cell here of the currently selected type for creation:
// If there's been a click, attempt to create a new
// cell at the given location:
if(mouseState.click)
{
var x = Math.floor(mouseState.click[0] / tileW);
var y = Math.floor(mouseState.click[1] / tileH);
if(x < Map.width && y < Map.height && Map.tiles[((y*Map.width)+x)].cell==null)
{
new Cell(x, y, creatableTypes[createType], cellTypes[creatableTypes[createType]].prey);
}
mouseState.click = null;
}
We can then begin rendering to our Canvas. We'll start by setting the font, clearing the canvas to a grey, and drawing the map grid:
ctx.font = "bold 10pt sans-serif";
ctx.fillStyle = "#cccccc"
ctx.fillRect(0, 0, canvasW, canvasH);
// Draw grid
ctx.strokeStyle = "#ffffff";
ctx.beginPath();
for(var y = 0; y <= Map.height; y++)
{
ctx.moveTo(0, (y * tileH));
ctx.lineTo((Map.width * tileW), (y * tileH));
}
for(var x = 0; x <= Map.width; x++)
{
ctx.moveTo((x * tileW), 0);
ctx.lineTo((x * tileW), (Map.height * tileH));
}
ctx.stroke();
We'll then draw the cells. Active cells are drawn as a filled block of colour depending on the cells type, whilst newly created cells are drawn as an outlined rectangle:
for(var x in allCells)
{
if(!allCells[x].alive) { continue; }
ctx.fillStyle = cellTypes[allCells[x].type].colour;
ctx.fillRect( (allCells[x].x * tileW), (allCells[x].y * tileH), tileW, tileH);
}
for(var x in newCells)
{
ctx.strokeStyle = cellTypes[newCells[x].type].colour;
ctx.strokeRect( (newCells[x].x * tileW), (newCells[x].y * tileH), tileW, tileH);
}
We'll also draw some text showing the current framerate, animation status, and giving instructions on how to toggle and change settings in the animation:
ctx.fillStyle = "#000000";
ctx.textAlign = "end";
ctx.fillText("Framerate: " + framesLastSecond +
(paused ? " (Paused)" : ""), canvasW-50, 20);
ctx.fillText("Creating: " + creatableTypes[createType] + " (c to change)", canvasW - 50, 35);
ctx.textAlign = "start";
ctx.fillText("Bias direction: " + (biasDir ? "On" : "Off") + " (b to change)", 10, canvasH - 45);
ctx.fillText("s to Step when paused, r to reset, f to random fill", 10, canvasH - 30);
ctx.fillText("Auto step time: " + updateDelay + "ms (d to change)", 10, canvasH - 15);
Finally, we'll let the browser know that when it's ready to animate another frame, it needs to call this function once again:
requestAnimationFrame(updateMap);
}