 |
Author |
Topic: uberfast cellular automata (java) (Read 1239 times) |
|
rgovostes
|
uberfast cellular automata (java)
« on: Mar 16th, 2004, 10:08pm » |
|
I found this neat page, which has a Java applet which does the 'Game of Life' (it also can do any other pattern - you just supply it with two integer "rule" values). The amazing thing about it is that it runs extremely quickly.
Luckily, the Java source is available here (scroll to the bottom). I think it would be great if someone could port this to Processing, but alas I do not have the skill to do so myself.
(P.S: My favorite pattern is '1234/16' - try it out!)
|
| « Last Edit: Mar 16th, 2004, 11:49pm by rgovostes » |
|
|
|
|
arielm
|
Re: uberfast cellular automata (java)
« Reply #1 on: Mar 16th, 2004, 10:28pm » |
|
i'm seeing a lot of Cellular Automata stuff these days and i have to tell you that this example is one of the slowest ones i remember 
well, i'm exagerating a bit, but still, i can't say this stuff is extremly quick.
a classic cellular automata is generally a matter of analysing n times per frame a relatively few bits of information, so it's something quite fast for c/c++ and even java.
also, for the kind of CAs used in the given example:
they're operating on a very limited number of bits so it's possible to use a 64k (or so) "pre-computed table" and then: it's really super fast.
didn't check the source code, but i think pre-computed tables is the technique used here, but i suspect that what makes the simulation look "slow" to me here is the way scren-update is handled (the use of a grid + probably the use of standard java drawing functions)
these days, i'm using a custom non-orthodox CA for simulating sand pouring... one implementation of it is viewable in that (purposely silly) applet:
http://www.chronotext.org/toys/Ssshh.htm
|
Ariel Malka | www.chronotext.org
|
|
|
rgovostes
|
Re: uberfast cellular automata (java)
« Reply #2 on: Mar 16th, 2004, 11:57pm » |
|
That is a pretty neat sand applet... Nice work!
Still, the Life applet is pretty quick, considering the window sizes. My machine does about 93 frames per second at full size.
|
| « Last Edit: Mar 17th, 2004, 12:11am by rgovostes » |
|
|
|
|
gll
|
Re: uberfast cellular automata (java)
« Reply #3 on: Apr 16th, 2004, 7:14pm » |
|
Hi rgovostes, arielm,
Here is sample of a project done with POVray: [.http://www.vif.com/users/goo/VDO/gPov00.avi] [it use DivX]
I worked on a project based on cellular automatas. It was in C++ and OpenGL. We are working with really huge matrices (1600x1600x1600 with 256 states). We were looking to find a way to reduce time of calculations.
The applet proposed by rgovostes is one of the most rapid have seen too. The problem with Cellular automatas is that you cannont loose information when you try to compress information.
This applet is based on tables but is not pre-computed tables (maybe a part for case table). First, if I remember correctly, it divide the matrice like a Divide an Conquer algorithm to have cells of same type. Each sub regions recursivly done have three states based of the way they change :
0- Stable (Total stability - Active or Empty)
1- UnStable (that have to be calculated - A mix)
2- Borders (wich could be unstable for the next step)
In life32 (http://psoup.math.wisc.edu/Life32.html), I guess they add cycles considerations. Some cycles (oscillations over a period) could be considerated as Stable state and is then not processed. But they didn't publish the source. I guess that I saw similar code. It's based on Pascal - or assembly operations wich is complex to understand because it's not represented as an Array[x][y].
With this paradigm, focusing on how the matrice change, rather than the state of the matrice, you don't have restrictions about the scale of the model (million by million cells matrices). And it doesn't take too much space in memory. For example, a square of 1000x1000 active cells is considered as 1 UnStable cell in the Table for active region, 9 Stable Cells for empty parts, and many boder cells.
|
| « Last Edit: Apr 17th, 2004, 3:51am by gll » |
|
guillaume LaBelle
|
|
|
gll
|
Re: uberfast cellular automata (java)
« Reply #4 on: Jun 5th, 2004, 6:45am » |
|
I've found this website which talk about the optimization with Cellular Automatas.
http://cell-auto.com/optimisation/index.html
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. - Donald Knuth"
|
guillaume LaBelle
|
|
|
|
