Two weeks ago we saw procgen rulesets and that was the alphabet level of procgen. Last week we saw linear procgen and that was like a type of procgen novel. Today we’re taking a look at cellular automata, an experimental grammar of procgen.
If you’ve been interested in procgen or more simply algorithms, you’ve probably already heard of Conway’s Game of Life. This quite famous algorithm consists of having a grid of binary cells and changing the state of each cells after considering the state of its neighbor cells and comparing them with a few simple rules: if there’s too few ‘alive’ neighbors, the cell should be ‘dead’, if there’s too many ‘alive’ neighbors, the cell should also be ‘dead’, but if there’s 3 alive neighbors, then the cell should be ‘alive’ and if there’s 2, ‘alive’ cells remain ‘alive’. This algorithm, while apparently simple, gives impressively complex results and looks effectively alive as its name would suggest, featuring patterns of stability but also looping patterns, moving patterns and patterns that generate other patterns. If you are yet unconvinced, check out this digital clock made entirely in the Game of Life or the Game of Life also made entirely in Game of Life. Conway’s Game of Life is easily the most famous example of cellular automata.
So what is cellular automata? When I talk about cellular automata I generally stretch its definition a bit but here’s a definition that I think works: a cellular automaton (it’s latin) is an algorithm that alters the states of cells on a grid after considering the states of other cells on the grid. The grid doesn’t have to be orthogonal, it can also be hexagonal, triangular or just a total mess. And the cells can have more than two states, in fact they can have an infinity of possible states. Finally, an algorithm doesn’t have to be programmed, much like a music partition, it is easy to simply write cellular automata on a sheet of paper and leave it at that. But let’s be honest, we all want to see our cellular automata in action.
Today we’re gonna see how to make cellular automata in Pico-8 and then a few practical uses!
Let’s start by accepting that Conway’s Game of Life cannot be reproduced at a confortable speed in Pico-8. Or rather that it can be but only with a grid of 32×32. Pico-8’s GPU limitations make it pretty hard to try rulesets as complex as the Game of Life’s, as you have to check the 8 neighbors of each cell at each frame, the numbers go up very quickly. A few people have tried to implement the Game of Life in Pico-8 anyway and if you want to see that, you can check it out on the Pico-8 BBS but I personally think they’re all too slow.
But even though we can’t reproduice Conway’s Game of Life, there’s plenty much simpler cellular automata that exists and let’s start with 1D cellular automata.
What’s great with 1D cellular automata is that you can put your new cellular-automata-generated line just above the previous one and that looks very cool! Here’s an example of 1D 2-state cellular automata with its code right below.
for i=0,127 do pset(i,0,flr(rnd(2))) end --random initial states ^^^ palt(0,false) function _draw() memcpy(0x0,0x6000,0x2000) spr(0,0,1,16,16) line(0,0,127,0,0) for x=0,127 do local k=0 k+=pget(x-1,1) k+=pget(x+1,1) if k==1 then pset(x,0,(k)%2) end end end
(the part with the memcpy() and the spr() makes the scrolling happen)
Each frame, this code looks at the two neighbors of each cell of the previous row and counts the live ones to define the new state of the cell between them. Note that the previous state of the cell being modified is not being considered, this makes for more variable results while considering it could give us boring stationary results (I encourage you to try for yourself). That’s really as simple as cellular automata can get and yet we already have pretty nice results. Let’s make it slightly more interesting.
for i=0,127 do pset(i,0,flr(rnd(2))) end --random initial states ^^^ palt(0,false) function _draw() memcpy(0x0,0x6000,0x2000) spr(0,0,1,16,16) line(0,0,127,0,0) for x=0,127 do local k=0 k+=pget(x-2,1) k+=pget(x-1,1) k+=pget(x+1,1) k+=pget(x+2,1) pset(x,0,(k/2)%4) end end
(on the gif the colors were changed by using the ‘pal(ca,cb,1)’ function)
Here we are looking at neighbors that are slightly further, namely the two previous cells and the two next, for each cell in the row. Moreover, each cell has a grand total of four possible states. The state of each cell is the addition of the states of its four neighbors divided by 2 and modulo 4.
We didn’t really change much, yet the result is very different. Such is the chaotic beauty of cellular automata.
Now I’m not putting the code of this one because it is a bit longer. But here, we have a 2D cellular automaton that considers the four direct neighbors of each cell and has a total of 10 different states possible for each cell, with black being the ‘dead’ state, white being the ‘dying’ state and all the others representing a generation loop.
The rule for this one is that each alive cell with two or less alive neighbors will ‘boom’ with life, staying alive itself but also setting its four neighbors to the next generation state.
Because the operation affects neighbor cells and because the cells are not processed in a random order, this cellular automaton generates a pattern that always moves in the same direction and because my algorithm is actually quite messy, it starts making weird (but interesting) artifacts in the corners.
Here are a few more cellular automata that are more peculiar:
This type of cellular automata is great on its own and can make for super interesting generative art. But how about we make it useful?
Until now we’ve only been considering determinative cellular automata, algorithms that will always give you the same results if you give it the same initial data. That’s nice but it generally requires you to process the whole grid of cells, which can be slow and also maybe we don’t want to have the same results each time. So here comes what I like to call chaotic cellular automata! (also know as “non-determinative”) The only difference is that random will be involved in the algorithm in some way or other.
Cellular automata happens to be one of the many ways to do level generation in video games! Watch!
Here, a bunch of random cells rather than the whole grid are being modified at each frame. This lets you use more complex rulesets regarding the CPU while also being visually interesting and naturally randomized.
This algorithm is really messy and will probably make very different levels each time you run it but maybe that’s what you want!
Here is an island generation algorigthm that is really a stack of 1D cellular automata steps.
Like previously, we’re drawing each step of the cellular automata above the previous one. With only a small amount of randomization, the algorithm makes each step have slightly less alive cells than the previous ones, effectively creating a mountain.
Note that after the generation is done, the mountain is smoothed up by a second algorithm that clears the ugly dead cells in the middle of the mountain. Such algorithms are often required to smooth up cellular automata results as they can turn out a bit messy.
Here is the exact same approach but in voxel 3D and with a 2D cellular automata.
This is actually a toy I made for PROCJAM, you can check it out there, generate lots of islands and even check out the code!
I won’t extend more on level generation but know that the possibilities are pretty much endless and that with practice you’ll get much better control over your randomized algorithms.
And finally there’s the background cellular automata! I already wrote about it on the Doodle Insights #4 with the Procedural Dithering, so read that one if you’re interested, I’ll be more brief here.
Cellular automata can simply be a thing that happens in the background of your creation. Like previously, the ruleset can be pretty much anything, varying the checked tiles, the number of possible states, the grid, the actual state change, etc. Because it’s only happening in the background, we generally don’t want it to take too much GPU, so again we will be checking a bunch of random cells rather than the whole screen each frame.
Each of the game in Pixel Session Vol.1 has a cellular automata background and so does HIGH CLIMB, And All Is Well, One Room Dungeon and my upcoming gardening roguelike. I like using cellular automata in my backgrounds a lot you’ll notice. The reason for this is that it uses the leftover GPU of your game to generate interesting visuals that you can even make more discreet if you choose to. It also lets you set the mood of the game in an original way.
Cellular automata is very interesting to watch on its own but can also prove to be a very useful tool when it comes to generation and alternatively can be used as a background to your other creations. While it can require a lot of tweaking in the beginning, you do get much better at it with practice and then it really doesn’t have any drawbacks unless you really need all the GPU you can get for something else.
I hope you enjoyed these Doodle Insights! As usual, if you have any questions or remarks, please post them on the Patreon post!
All the doodles presented here can be found there on the Pico-8 BBS!
These Doodle Insights are here thanks to the awesome people supporting it on Patreon! Here are their names!
Joseph White, Adam M. Smith, Ryan Malm, Matthew, Tim and Alexandra, Sasha Bilton, berkfrei, Nick Hughes, Christopher Mayfield, Jearl, Dave Hoffman, Thomas Wright, Morgan Jensen, Zach Bracken, Anne Le Clech, Flo Devaux, Emerson Smith, Cathal O’Keeffe, Dan Sanderson, Andrew Reist, vaporstack, Dzozef, Cole Smith, Jared Butowsky, Tony Sarkees and Justin TerAvest!
Next week I’d like to talk about architecture in Pico-8 or ‘what’s worth keeping from OOP and how to implement that’, but maybe I’ll change my mind again!
Have fun with cellular automata!
TRASEVOL_DOG
* TRASEVOL_DOG * 