Most Diffused Reaction

Someone Anonymous
Twitter: @hirekoke

Yusuke Endoh
https://github.com/mame/
Twitter: @mametter

Judges' comments:

To use:

make

<tbd-tool-rubl-perl-python?>

Try:

Connect to port http://localhost:10333 with your browser

Selected Judges Remarks:

How did the leopard get its spots? Why are a zebra’s stripes unique?

In case you didn’t recognise the portrait of Alan Turing, there are some pointers to his features like eyes with “stdeye-o” and “<–mouth”. Can you find any other tributes?

Author’s comments:

What does “Alan Turing” remind you of? Cryptanalysis of the Enigma? Turing machine? Turing test? This program is also based on his work.

Whirlwind tour

Compile the program as follows:

$ clang -O3 -std=c99 \
    -Wall -Wextra -pedantic -o prog prog.c \
    -Delta_u="Du*laplacian(u)-u*v*v+F*(1-u)" \
    -Delta_v="Dv*laplacian(v)+u*v*v-v*(F+K)" \
    -DF=0.040 -DK=0.060 -DDu=0.200 -DDv=0.100 \
    -DUV_BACKGROUND=1,0 -DUV_DROP=-0.5,0.5 \
    -DTIMESTEP=1.0 -DSPEED=2 -DRGB=255:128:192

Then, run it under tcpserver command in ucspi-tcp package, which was created by Daniel J. Bernstein, IOCCC 1989 “Best of Show” winner.

$ tcpserver -v 127.0.0.1 10333 ./prog ioccc.txt

Finally, open http://127.0.0.1:10333/ by a modern browser supporting HTML5. You can use the mouse cursor to place drops into the Petri dish interactively.

Description

This is a simulator of reaction-diffusion systems.

Reaction-diffusion systems, proposed by Alan Turing in [1], are mathematical models in which two chemical substances are transformed into each other (local chemical reactions) and spread out (diffusion). Their interactions sometimes form non-trivial patterns, such as spots, spiral, dappling, and labyrinths.

The systems are generally formulated as follows:

du/dt = F(u, v) + Du * laplacian(u)
dv/dt = G(u, v) + Dv * laplacian(v)

The functions F(u, v) and G(u, v) represent reactions of each substance, and the parameters Du and Dv are diffusion coefficients. By changing the functions and parameters, you can see a wide range of behaviors.

See the Wikipedia article of “Reaction-diffusion system” in detail.

This program simulates the systems. The field consists of 128 x 128 cells. Each cell includes infomration of an amount of the two substances, and interacts with neighbor cells (in terms of von Neumann neighborhood) in each frame.

Configuration

You can change the model, initial pattern, simulation speed, and color via macro definition.

Model: -Delta_u=<expression> -Delta_v=<expression>

The definitions represent the equations of reaction-diffusion system. For example, the following is the Gray-Scott model in TeX notation.

\frac{\partial u}{\partial t} = D_u \Delta u - u v^2 + F (1 - u)
\frac{\partial v}{\partial t} = D_v \Delta v + u v^2 - v (F + K)

You can specify this model as follows:

-Delta_u="Du*laplacian(u)-u*v*v+F*(1-u)" \
-Delta_v="Dv*laplacian(v)+u*v*v-v*(F+K)"

Du, Dv, F, and K are parameters of that model.

Initial pattern: -DUV_BACKGROUND=<u0>,<v0> -DUV_DROP=<u1>,<v1>

The definitions specifies the initial amount of the two substances u and v. All cells have (u0, v0) by default.

You can specify a pattern file when the executable is invoked (not compile-time). The file should include a sequence of points, see ioccc.txt, center.txt, or line.txt as examples. Each amount in cells near to the point included in the file, will be added by (u1, v1).

Simulation speed: -DTIMESTEP=ts -DSPEED=spd

The definitions are for changing the simulation speed.

TIMESTEP is a simulation time step. The bigger, the faster but more unstable.

SPEED is a frameskip parameter. The bigger, the faster but more sluggish.

Rendering color: -DRGB=r:g:b

This specifies a color used for rendering.

Examples

Some interesting parameters are included in Makefile. Do one of the following command and open http://127.0.0.1:10333.

$ make gray-scott-1 && tcpserver -v 127.0.0.1 10333 ./gray-scott-1 ioccc.txt
$ make gray-scott-1 && tcpserver -v 127.0.0.1 10333 ./gray-scott-1 center.txt
$ make gray-scott-1 && tcpserver -v 127.0.0.1 10333 ./gray-scott-1 line.txt
$ make gray-scott-2 && tcpserver -v 127.0.0.1 10333 ./gray-scott-2 ioccc.txt
$ make gray-scott-3 && tcpserver -v 127.0.0.1 10333 ./gray-scott-3 ioccc.txt
$ make gray-scott-4 && tcpserver -v 127.0.0.1 10333 ./gray-scott-4 ioccc.txt
$ make fitzhugh-nagumo-1 && tcpserver -v 127.0.0.1 10333 ./fitzhugh-nagumo-1 ioccc.txt
$ make fitzhugh-nagumo-2 && tcpserver -v 127.0.0.1 10333 ./fitzhugh-nagumo-2 ioccc.txt
$ make oregonator && tcpserver -v 127.0.0.1 10333 ./oregonator ioccc.txt

These examples are created by drawing (and modifying) the pattern files of Ready, a cross-platform implementation of various reaction-diffusion systems [2].

Compatibility

C part

This program compiles clean with no warnings under -std=c99 -Wall -Wextra -pedantic. Since it uses long long for 64bit integers, C99 is required.

Browser part

You must use a modern browser that supports the latest specification of WebSocket [3]. All the following browsers worked for me:

I think Safari 6 will work but I haven’t tested. (I have no recent os x.)

tcpserver alternatives

I think you may use inetd and xinetd instead of tcpserver. Here is an example of inetd configuration.

10333 stream tcp nowait nobody /path/to/prog /path/to/prog /path/to/initial-pattern.txt

But note that I didn’t test well.

Internal

  1. The C program accepts HTTP connection from the browser, and sends a HTML document.
  2. The browser tries to upgrade the connection to WebSocket.
  3. The C program accepts WebSocket upgrade. This negotiation process requires SHA1 hash [4] and Base64 encoding [5]. The C program calculates them without the aid of any external libraries.
  4. The C program simulates the reaction-diffusion system, and then send the field data to the browser on each frame.
  5. The browser receives and renders the field data onto the HTML5 canvas.

References

Creative Commons License

© Copyright 1984-2016, Leo Broukhis, Simon Cooper, Landon Curt Noll - All rights reserved
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.