I wrote my honors application essay for the University of Michigan a few weeks ago, and I really enjoyed writing it, to my surprise. There were a few prompts to choose from, but I chose one that I thought would be interesting to twist in my own way: “**Take a complicated idea or object and make it simple**.” In response to this prompt, I wrote a ~600 word essay on how to make water using cellular automata, in layman’s terms (for the most part). Without further ado, have a read:

One concept that I have found of continuous interest as a programmer has been that of water. It is a fluid and, as such, it has properties that would seem to make it very difficult to realistically simulate in a fast, simplistic way in a video game or program. Making water fall, splash, or spread outward due to celerity in waves, and still settle into available crevices neatly would appear to require a vast amount of calculation and rendering precision in executing it on even a basic level. In the real world, this liquid interacts on a molecular level, which results in these properties of which we are all familiar. But a program would not be able to run with per-molecule level precision at any kind of reasonable rate, if at all. In programming video games, there exists a constant dance of balancing the game experience with the speed at which it is able to run; in essence, finding elegant solutions to complicated concepts is the hallmark of a talented programmer, and simplicity correlates directly with its running speed and its overall quality. In order to solve these kinds of speed problems with water and still give it the capability to form waterfalls, lakes, and varying water levels, from deep to shallow, on entirely randomly-generated terrain where specific-case implementation is impossible, I use a simple technique called “cellular automata.” This technique divides the aquatic region into squares or rectangles to make a grid where each “cell” can hold a possible amount of water. Each cell has a set x/y position, width, height, and percentage of fill. Using only the last value, the fill of the cell, and rules governing these cellular interactions, we can develop a program in which water is able to act in a naturally fluid manner and behave according to all of the tendencies listed above.

In determining how these different cells interact, it simply comes down to deciding how water would act with the different cells around it in reality; if the current cell has more water than the cells to the left or right of it and at least one of them is not obstructed by an impediment of some sort, then this cell must empty water out into that cell to make both have an equivalent fill value. Also, if the cell below the current cell is not blocked by ground or another obstacle and is not completely filled with water, it must fill up with as much water as it can from the current, higher cell until it is completely full. Then, we simply have each cell draw a rectangle whose height is determined by its fill value, and we have a program where water can flow left and right, as well as by gravity. By using these simple, logical rules and executing them for each of the cells that contain water several times a second, a program can easily handle this method and give an effect that will allow for waterfalls, bodies of water with varying depths, and waves. Also, with a little tweaking, pressure calculations can be implemented to show when water is shallower or deeper. Thus, the daunting task of making water adapt in a predictable fashion to a randomly generated environment is quickly turned into a simple case of taking a step back, looking at how water works in the real world, developing rules that fit the natural manner of a liquid, and manipulating a single value, the percentage of fill, to represent that behavior in each cell of a grid.

Hi!

It could be great to see this visualised/animated. The liquid flow in Minecraft seems to have similar behaviour.

I really love everything related to cellular automata. A few years ago I wrote the coloured version of Conway’s Life (in python). Every cell is of one of 6 colors, and the new cell get the colour calculated as the average value of its neighbours. Thinking about posting it to my blog (there’s not much info yet) as soon as video or exe is available.

I haven’t actually heard of the colored version before; I wrote a monochrome version that is on the games page, and the only color is for the age of each cell. If you post it up, definitely link me to it. I’d like to see it!

Your version is really hypnotizing… Rule #6 (2,4/3,6,7,8) produces cave-like(how to say it?) picture over time.

I have to make a videos first, because there’s no user interface to play with properties.

P.S. I just found one screenshot of the same ‘colored Life’, but visualised in 3D (every step as a layer): http://dl.dropbox.com/u/22147262/wolfram_13c_64x48x0.99.jpg

I’m glad you like it I was pretty interested in the rules and wanted to make a few different sets that would make some interesting effects. #6 was also one of my favorites!

That looks really cool; how do you determine what color to make each cell?

Thanks It is not the best picture though (but really the only one I found).

I used 6 colors that form the basic color ring: yellow-red-magenta-blue-aqua-green. I don’t remember all the details. When the new cell is ‘born’, add together all the live cells colors around the current one and then calculate the average color (keeping in mind that the colors are fixed and are on the color ring, it is not just linear average).

http://dl.dropbox.com/u/22147262/color_ring.png

For example, if the cell is surrounded by one green one yellow and one red cells, the resulting color is obviously yellow. There are problems, for example, what color will it be if you add yellow to blue? Or any other two opposite colors. I used random, but now I think it could be better to store the floating point value (position on the color ring).

I wonder what is the algorithm(s) for getting the average value on the numeric ring (closed interval).

P.S. sorry for my English

Hm, that’s an interesting problem with the color. How did you calculate out what colors they should be, exactly? I would think that you’d do something like this, for example (hexadecimal version of the problem you put up):

(FFFF00 + FF0000 + 00FF00)/3 = AAAA00

That will give you a desaturated yellow, which is obviously not what you’d want. Maybe I could put together a version in the near future that uses this method, but I’m not exactly sure how it would turn out (since there’s eight neighbors, and it’d probably become a lot of medium grey in the end).

Also, it might be worthwhile to add white and black to the color palette; there are eight different cells, and that would make eight different colors, which makes a nice bit of continuity for the idea and cleans up issues like yellow + blue: FFFF00 + 0000FF = FFFFFF (white).

If you use the hex. color values and mix them up, you’ll finally see the grid eventually become grey. Looking through the old python code that does the calculations, I can tell how everything works. I used simplified RGB color value structure: every component is 0, 1 or 2. So, for example, red is (2-0-0), yellow is (1-1-0), and purple is (1-0-1). Every color has to have the sum of its components equal to 2. The calculation uses idea of finding ‘distance’ between colors.

To calculate the average of N colors, I did the following steps:

1) sum all the colors (component-wise).

for example, red+yellow+purple = (2-0-0)+(1-1-0)+(1-0-1) = (4,1,1)

2) simplify the sum: divide all components by every component’s multiples (it’s hard to speak English:) I hope you understand)

for example, (8-2-6) turns to (4-1-3), but (4-1-1) remains as it is.

3) calculate the distance squares between that value and every color in the palette. By distance square between colors (r1-g1-b1) and (r2-g2-b2) I mean scalar value sqr(r1-r2)+sqr(g1-g2)+sqr(b1-b2). (This is the same as getting squared distance between 2 points in 3D space)

for example, if the value is (4-1-1), then the distance squares are:

R: sqr(2-4) + sqr(0-1) + sqr(0-1) = 6

Y: sqr(1-4) + sqr(1-1) + sqr(0-1) = 10

G: sqr(0-4) + sqr(2-1) + sqr(0-1) = 18

A: sqr(0-4) + sqr(1-1) + sqr(1-1) = 16

B: sqr(0-4) + sqr(0-1) + sqr(2-1) = 18

P: sqr(1-4) + sqr(0-1) + sqr(1-1) = 10

4) find the minimum of these distances. There can be 1 or 2 of them: get 1 using random() then.

5) get the corresponding color from the palette.

in the example above the minimum is 6, so the result is: red.

I wonder what can it look like if the palette is of 7 (or 5, or any other uneven number) colors.

This is not the best approach, and it is rather slow, but it works and it produces colorful animation or 3D scene. I’m thinking now of porting it to AS3 and make it available online.

Not in the nearest 2 weeks though…

But I really want to make the videos of it working and upload them to youtube as soon as possible. Just need to reinstall the python and a lot of libs.

Very interesting, I can see how that would work; CPU intensive, but still nicely done. I was thinking of a method that would be pretty odd. using an image like the color-wheel picture you showed me, a color could be designated by a certain range of angle values, and the angle value for a particular cell could be found by adding up the angle values of the surrounding cells. I’m not sure exactly how the result would turn out, but I might sit down and put it together to see how things pan out.