Discussion: neighbourhoods
Gerard Vriens
neighbourhoods: the von Neumann neighbourhood and the Moore neighbourhood.
+--+ +--+--+--+
| | | | | |
+--+--+--+ +--+--+--+
| | | | | | | |
+--+--+--+ +--+--+--+
| | | | | |
+--+ +--+--+--+
von Neumann Moore
Obviously the von Neumann is "just" a subset of the Moore. So why is it
usually considered a neighbourhood in its own right?
Theoretically, because the geometrical properties of the whole lattice are
different. For instance, it gives rise to a different distance function.
Practically, because it gets mighty tiresome to have to spell out the
rules for 8 cells when only 4 would suffice.
I'd like to draw some attention to the following two neighbourhoods:
1. The hexagonal neighbourhood:
+--+--+ +--+--+
| | | | | |
+--+--+--+ +--+--+--+
| | | | or | | | |
+--+--+--+ +--+--+--+
| | | | | |
+--+--+ +--+--+
Though there seems to be some awareness that rules which leave two
opposite diagonal cells out of the Moore are capable of simulating a
hexagonal CA on a rectangular grid, I haven't yet seen any mention of it
as a neighbourhood on a par with the von Neumann and the Moore.
2. The knight's neighbourhood. This one fascinates me no end. It is a
subset of the "extended Moore", consisting of all squares that the chess
knight can jump to:
+--+ +--+
| | | |
+--+--+ +--+--+
| | | |
+--+ +--+ +--+
| |
+--+ +--+ +--+
| | | |
+--+--+ +--+--+
| | | |
+--+ +--+
Though each cell has 8 "neighbours", just as in the "ordinary" Moore, once
again the lattice properties are subtly but fundamentally different. For
instance: in the Moore, if two cells are neighbours, they have neighbours
in common. Not so in the knight's neighbourhood. (Neither in the von
Neumann. Could it be the knight's is related to a 4d von Neumann?)
It would be very interesting to see the rules of Conway's Game of Life
applied to a knight's neighbourhood. Since Life is totalistic on 8
neighbours, this requires no extra assumptions.
Perhaps a challenge for the programmers among us?
Gerard.
George Maydwell
<ger...@localhost.localdomain> wrote:
>It would be very interesting to see the rules of Conway's Game of Life
>applied to a knight's neighbourhood. Since Life is totalistic on 8
>neighbours, this requires no extra assumptions.
>
>Perhaps a challenge for the programmers among us?
>
>Gerard.
SARCASim is capable of simulating your "knight's" neighborhood, the
simple hexagonal neighborhood which you describe, and more complex
hexagonal neighborhoods to boot. Its available at:
www.bayarea.net/~maydwell/htdoc/ca
Changing the neighborhood is trivial in ARCAL, SARCASim's programming
language. Better yet, your knight's neighborhood CA should run at
nearly the same speed as GOL on SARCASim (i.e. - fast). The challenge
is one of finding rules which result in visually interesting CA's for
this neighborhood. I have found it easier to construct interesting
CA's using dense rather than sparse neighborhoods, so your task may be
a difficult one even using SARCASim.
Regards,
George Maydwell
Tim Tyler
: I'd like to draw some attention to the following two neighbourhoods:
: 1. The hexagonal neighbourhood: [snip diagram]
: Though there seems to be some awareness that rules which leave two
: opposite diagonal cells out of the Moore are capable of simulating a
: hexagonal CA on a rectangular grid, I haven't yet seen any mention of it
: as a neighbourhood on a par with the von Neumann and the Moore.
No? Check out some of the hexagonal cellular automata links at the top of
http://hex.org.uk/links/
There's an example of a few simple hexagonal automata in a Java applet at:
http://hex.org.uk/totalhex/ - and many of the automata at
http://hex.org.uk/diffusion/ are based on a hexagonal geometry.
: 2. The knight's neighbourhood. This one fascinates me no end. [...]
By way of contrast, my interest in cellular automata is closely connected
with getting high speed operation in hardware. For this to happen
neighbours should be as close as reasonably possible, in order to
reduce signal propagation delays, and minimise the volume of wiring.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler t...@cryogen.com http://hex.org.uk/ http://atoms.org.uk/
Gordon D. Pusch
> SARCASim is capable of simulating your "knight's" neighborhood, the
> simple hexagonal neighborhood which you describe, and more complex
> hexagonal neighborhoods to boot. Its available at:
> www.bayarea.net/~maydwell/htdoc/ca
I find your paper quite interesting, and would have very much have liked to
have experimented with your simulator, but I am deeply disappointed to find
that you only distribute a Micro$chlock Windoze .EXE; this pretty much
leaves all serious scientific users out in the cold, unless they run it
on an emulator (which sort of defeats the point of a fast CA simulator... :-(
Do you plan to someday port your simulator to a scientific OS, like LINUX
or Solaris ???
-- Gordon D. Pusch
perl -e '$_ = "gdpusch\@NO.xnet.SPAM.com\n"; s/NO\.//; s/SPAM\.//; print;'
Erik Max Francis
> Obviously the von Neumann is "just" a subset of the Moore.
Right, for suitable meanings of _just_.
> So why is it
> usually considered a neighbourhood in its own right?
Because in cellular automata, "neighborhood" means, effectively, the
information on other cells' states that a given cell has available to it
in order to make a transition. The von Neumann neighborhood is
definitely distinct from the Moore neighborhood in this respect.
Certainly one could have a Moore-based cellular automaton that did not
ever use the corner squares, but a rule set that does not use that
information is different from one that _cannot_.
> It would be very interesting to see the rules of Conway's Game of Life
> applied to a knight's neighbourhood. Since Life is totalistic on 8
> neighbours, this requires no extra assumptions.
>
> Perhaps a challenge for the programmers among us?
Do you have a cellular automata package available to you? Programming
up such a thing in a dedicated environment should be a breeze.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ Chastity the most unnatural of the sexual perversions.
\__/ Aldous Huxley
Interstelen / http://www.interstelen.com/
A multiplayer, strategic, turn-based Web game on an interstellar scale.
Gerard Vriens
GV> Obviously the von Neumann is "just" a subset of the Moore.
EMF> Right, for suitable meanings of _just_.
Which, of course, is why I put the quotes around the word.
GV> So why is it usually considered a neighbourhood in its own right?
EMF> Because in cellular automata, "neighborhood" means, effectively, the
EMF> information on other cells' states that a given cell has available to
EMF> it in order to make a transition.
Let's supplement this with another definition:
effective neighbourhood := the information on other cell's states that a
given cell _uses_ in order to make a
transition.
EMF> Certainly one could have a Moore-based cellular automaton that did
EMF> not ever use the corner squares, but a rule set that does not use
EMF> that information is different from one that _cannot_.
If you're interested in analyzing CA _behaviour_ (like I am), then what
matters is the _effective_ neighbourhood.
You can't tell, just by watching its transitions, a von Neumann CA from a
Moore whose effective neighbourhood is von Neumann.
So, however different a Moore-based CA may _factually_ be from a von
Neumann-based (as evident in capabilities and meters of wiring/bytes of
code), to me they're in the same class if they have the same effective
neighbourhood.
Thank you for helping me realize this distinction.
Gerard.
Gerard Vriens
GV> 1. The hexagonal neighbourhood: [snip diagram]
GV> [...] I haven't yet seen any mention of it as a neighbourhood on a par
GV> with the von Neumann and the Moore.
TT> No? Check out some of the hexagonal cellular automata links at the
TT> top of http://hex.org.uk/links/
There's certainly a lot about hexagonal CA there. It'll take me some
time to go through it completely and thoroughly.
But I meant something different. I meant that I never saw my diagram
(which you thoughtfully snipped) as a neighbourhood on a _rectangular_ CA,
mentioned along with the von Neumann and the Moore neighbourhoods; and
with the annotation that (apart from the appearance of the tiles) it is
exactly the same as what you call a honeycomb neighbourhood on a hexagonal
tiling.
The page of Charles Herring, which you link to, being a case in point:
he explicitly presents his "uniform" neighbourhood as a neighbourhood on a
_hexagonal_ tiling, while it is equally possible to implement and just as
valid to see it as a neighbourhood on a square tiling.
Of course, the fact that I haven't yet seen such a mention does not
mean that there ain't one... ;-)
GV> 2. The knight's neighbourhood. This one fascinates me no end. [...]
TT> By way of contrast, my interest in cellular automata is closely
TT> connected with getting high speed operation in hardware. For this to
TT> happen neighbours should be as close as reasonably possible, in order
TT> to reduce signal propagation delays, and minimise the volume of
TT> wiring.
Since the lattice resulting from a knight's neighbourhood on a square
tiling is non-planar, it may be able to perform some "tricks" that a
"closer" planar neighbourhood is uncapable of. Or it may do them more
efficiently.
So unless you want to go 3-D, the knight's may _be_ "as close as
reasonably possible".
Gerard.
Erik Max Francis
> So, however different a Moore-based CA may _factually_ be from a von
> Neumann-based (as evident in capabilities and meters of wiring/bytes
> of
> code), to me they're in the same class if they have the same effective
> neighbourhood.
>
> Thank you for helping me realize this distinction.
Right. With that distinction, your statement because true. If a Moore
neighborhood based cellular automaton only uses the neighbors associated
with its von Neumann subset, then it could be trivially implemented with
a von Neumann neighborhood.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ What a crime to waste [youth] on children.
\__/ George Bernard Shaw
Product's Quake III Arena Tips / http://www.bosskey.net/
Tips, tricks, and hints from an Arena Eternal Master.
Tim Tyler
: I meant that I never saw my diagram (which you thoughtfully snipped) as
: a neighbourhood on a _rectangular_ CA, mentioned along with the von
: Neumann and the Moore neighbourhoods; and with the annotation that
: (apart from the appearance of the tiles) it is exactly the same as what
: you call a honeycomb neighbourhood on a hexagonal tiling.
Missing oppositte corner cells is a well-known way of implementing
that hexagonal neighbourhood. I don't think it should be classified
differently, since there's an exact isomorphism between them.
IIRC, I first encountered the "Moore with missing corners" idea for
hexagonal cellular automata on p. 179 of "Cellular Automata Machines".
For a web reference, http://excite.math.wisc.edu/mcell/rullex_wlif.html -
"One can also define hexagonal rules by defining NE and SW neigbours as 0."