Programatically finding areas of interest
Xerol
again, finishing up the original feature list and adding some new
ones. Since the program is primarily for entertainment rather than
study purposes, I'd like to have the program able to "focus" on areas
of interest.
Of course, the first problem is defining an area of interest. In this
case it would just be something that comes up but isn't one of the
usual patterns. The likelihood of this happening in a small region of
random soup is pretty low, so when it does happen I want the user's
attention to be brought to it. Since one of the program's main
features will be the ability to move backwards and forwards in time,
the user would be able to rewind the simulation a bit and see how the
pattern formed.
The real question here is how to figure out a way to find these areas
without taking too much of a performance hit. The graphics are going
to be low enough quality that they won't need a super-fast computer to
run, but they still take up a significant amount of CPU time so the
resources available for other aspects of the program are limited. This
is especially going to be an issue if the user wants to run the
simulation at high speed (which, incidentally, looks pretty neat,
especially with a lot of gliders: http://www.youtube.com/watch?v=F92PyKA2ASA),
but since this feature will be toggleable it's not too much of an
issue.
The only reasonable method I can think of that accomplishes both goals
(finding unique structures, and running fairly fast) would be to
generate hashes of regions of cells and compare them to hashes of
known familiar patterns, and if it finds something "new", it can slow/
stop the simulation and focus the camera at the region. This is still
somewhat of a problem because random soup passing through might set it
off more often than not. I think I can make use of the history
function here, however, by comparing hashes of regions in different
generations, and finding stable patterns and cycles this way. This
seems like a simple and easy way to get started, but there's probably
some other, better, and more obvious way that I'm overlooking.
Frank Buss
> The real question here is how to figure out a way to find these areas
> without taking too much of a performance hit. The graphics are going
> to be low enough quality that they won't need a super-fast computer to
> run, but they still take up a significant amount of CPU time so the
> resources available for other aspects of the program are limited. This
> is especially going to be an issue if the user wants to run the
> simulation at high speed (which, incidentally, looks pretty neat,
> especially with a lot of gliders: http://www.youtube.com/watch?v=F92PyKA2ASA),
> but since this feature will be toggleable it's not too much of an
> issue.
You are right, Generations CAs can looks nice. I've implemented one in
assembler some time ago:
http://www.youtube.com/watch?v=iA1XGM0CGnU
> The only reasonable method I can think of that accomplishes both goals
> (finding unique structures, and running fairly fast) would be to
> generate hashes of regions of cells and compare them to hashes of
> known familiar patterns, and if it finds something "new", it can slow/
> stop the simulation and focus the camera at the region. This is still
> somewhat of a problem because random soup passing through might set it
> off more often than not. I think I can make use of the history
> function here, however, by comparing hashes of regions in different
> generations, and finding stable patterns and cycles this way. This
> seems like a simple and easy way to get started, but there's probably
> some other, better, and more obvious way that I'm overlooking.
Using hashes and caches sounds like a good idea, but I don't know if it
works with generations CAs. Maybe it helps to take a look at Hashlife:
http://en.wikipedia.org/wiki/Hashlife
--
Frank Buss, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Ilmari Karonen
> Xerol wrote:
>>
>> The only reasonable method I can think of that accomplishes both goals
>> (finding unique structures, and running fairly fast) would be to
>> generate hashes of regions of cells and compare them to hashes of
>
> works with generations CAs. Maybe it helps to take a look at Hashlife:
I don't see any reason the hashlife algorithm wouldn't work with any
deterministic cellular automaton.
Indeed, this follows from the fact that it works for Life b3/s23,
since that rule allows the construction of macrocells capable of
emulating any deterministic cellular automaton, and hashlife can run
such macrocell patterns efficiently. :)
Of course, the efficiency of hashlife depends significantly on the
pattern being simulated: regular, repetitive patterns run very fast,
while high-entropy noise slows things down. Many "generations" rules
seem to have features of both: they produce highly repetitive features
on small scales, but the interactions of those features tend to become
chaotic on larger scales unless carefully controlled. Even so, I
suspect a hashlife-style algorithm could be reasonably competitive for
them, even if the speed gain over a naive simulator might be only by a
constant factor.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Andrew Trevorrow
> I don't see any reason the hashlife algorithm wouldn't work with any
> deterministic cellular automaton.
In the Golly 2.0 release (http://golly.sourceforge.net/) Tom Rokicki
has extended the hashlife algorithm to support arbitrary rules in
universes with up to 256 states. See ghashbase.h and .cpp in the
source distribution. Other algorithms use this base class -- see
for example generationsalgo.h and .cpp which implement the
Generations algorithm.
Golly 2.0 makes it easy to add new hashlife-based algorithms, with
only a couple of trivial changes to the GUI code (in wxalgos.cpp).
Even better, the new RuleTree and RuleTable algos (also hashlife-based)
allow you to plug in new CA rules without writing any code -- you just
need to create suitably formatted .tree or .table files.
See Help > File Formats.
> Of course, the efficiency of hashlife depends significantly on the
> pattern being simulated: regular, repetitive patterns run very fast,
> while high-entropy noise slows things down. Many "generations" rules
> seem to have features of both: they produce highly repetitive features
> on small scales, but the interactions of those features tend to become
> chaotic on larger scales unless carefully controlled. Even so, I
> suspect a hashlife-style algorithm could be reasonably competitive for
> them, even if the speed gain over a naive simulator might be only by a
> constant factor.
I haven't bothered to do any speed comparisons between Golly and MCell.
This will probably only be a fair comparison after we add support
for bounded universes (torii, Klein bottles, etc).
Andrew