Tuesday, 11 October 2011

Cellular automata in Minecraft

Besides being on of the best games I've ever played, Minecraft, is also a superbe resource for learning how game development works. First of all, the game is still in development - you get to see with each update what elements are added and how bugs appear. You don't have this privilege with most games out there - you don't get to see how an idea evolves into a great game. You can also read the full version history on the official wiki to see what were the very first steps in developing this wonderful game.

In this post I want to underline some cellular automata-like behaviour that can be observed in the Minecraft universe.

Cellular automata
The simplest example I can give is how grass spreads. A block of dirt will have grass grow on it if one of its neighbours has grass on it (some lighting conditions must also be met).
In other words the rule needed to describe this as a cellular automata looks like this:
Dirt -> Grass if at least one of the neighbouring blocks are Grass and light conditions are met

There are 2 types of water blocks: sources and flowing. Flowing water comes in 7 levels or so, and can't be picked up with a bucket (water sources can).
Rules (roughly):
Air/Water -> Water, Flowing of level Max(neighbours)-1
Air/Water -> Water, Source if it has at least 2 neighbours who are Water Sources themselvs
Air -> Water, Flowing, if the block above is water

Water will spread on a flat surface, if there are no gaps in the way. Otherwise it will be drawn to the nearest gaps. Gap seaching only occurs when placing a water source. Notice, in the screenshots below, the uneven spread of water due to gaps.


It behaves mostly like water except it spreads slower and the rule regarding Sources doesn't apply - you can't create infinite lava pools.
Lava, Source -> Obsidian if the above block is Water
Lava, Flowing -> Stone if one of the neighbouring blocks is Water

Propagates just like water on a flat surface except it's in three dimensions.
Realistic shadows wouldn't have blended with the overall blocky aspect of the game and it would have required a more powerful GPU.

Below is a demo showing how light could have been implemented using cellular automata. Click on the canvas to add and remove obstacles.

Redstone circuits
The signal in a restone circuit propagates just like water on a flat surface.

Redstone -> Redstone, powered of level Max(neighbours)-1
Repeater, inactive -> Repeater, active, level 2 if its input is powered
Repeater, active, level 2 -> Repeater, active, level 1
Repeater, active, level 1 -> Repeater, inactive
Redstone, unpowered -> Redstone, powered if there is a neighbouring Repeater, level 1 or another source

Redstone signal propagates from one elevation to another only if the block above the lower redstone is transparent.

Crops have a very simple set of rules. The rate of growth is influenced by light level and irrigation.
Seed -> Crops, level 1
Crops, level 1 -> Crops, level 2
Crops, level 6 -> Crops, level 7
Crops, level 7 -> Crops, fully grown

Placed cactus block is "Cactus, level 1"
Air -> Cactus, level 2, if the block below is Cactus, level 1
Air -> Cactus, level 3, if the block below is Cactus, level 2
Air -> Cactus, level 4, if the block below is Cactus, level 3

The decaying of leaves behaves much like grass: Leaves -> Air if there is no Wood block around.
Currently, trees grow in minecraft instantly. It would be much nicer to see them growing gradually. With enough rules the growing of trees could be simulated using cellular auomata.
Sample rules:
Sapling -> Trunk, level 1
Air -> Trunk, level 2 if the block below is Trunk, level 1
Air -> Trunk, level 3 if the block below is Trunk, level 2
Air -> Branch, level 1 if there is a neighbouring Trunk, level 3 block
Air -> Branch, level 2 if there is a neighbouring Branch, level 1 block
Air -> Leaves if there is a neighbouring Branch, level 2 block
Leaves -> Branch, level 2 if there is a neighbouring Branch, level 1 block

Minecart mechanics could be simulated (up to a certain extent) using an altered version of Wireworld. Minecarts would be electrons and the track would be the conductor. Additional rules may be needed to prevent the minecart from splitting like electrons do when the track splits.
Minecarts could also be implemented as turmites. The closest thing to a turmite is the snow golem because it leaves a trail of snow wherever it goes. If it had changed its behaviour based on whether it stood on snow or not it would have been a fully capable turmite.
Every minecart knows its direction and energy level.

The rules for a turmite-minecart would look like this:
on ground: decrease energy by 5
on horizontal tracks: decrease energy by 1
on ascending tracks: decrease energy by 4
on descending tracks: increase energy by 3
on cornering tracks: adjust direction, descrease energy by 1
on booster: increase energy by 10

in all cases advance if there is enough energy left.

No comments:

Post a Comment