Moore neighbourhood: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
← Older edit
Muzik (talk | contribs)
Trusted users
24,382 edits
Confocal (talk | contribs)
9,118 edits
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
[[File:Moore neighbourhood (range 1).png|framed|right|The Moore neighbourhood (blue) of a single cell]]
[[File:Moore neighbourhood (range 1).png|framed|right|The Moore neighbourhood (blue) of a single cell]]
The '''Moore neighbourhood''' is the set of all [[cell]]s that are orthogonally or diagonally-adjacent to the region of interest (the region of interest itself may or may not be considered part of the Moore neighbourhood, depending on context). For example, the Moore neighbourhood of a single cell consists of the eight cells immediately surrounding it. This [[neighbourhood]] is named after Edward F. Moore, one of the pioneers of [[cellular automata]] theory.<ref>{{Cite web|url=http://cell-auto.com/neighbourhood/moore/|title=The Moore neighbourhood|author=Tim Tyler|accessdate=June 13, 2009}}</ref> The Moore neighborhood is the neighbourhood of interest in [[Conway's Game of Life]] and all [[Life-like cellular automata]], though there are cellular automata that use other neighbourhoods such as the 4-cell [[von Neumann neighborhood]].
The '''Moore neighbourhood''' is the set of all [[cell]]s that are orthogonally or diagonally-adjacent to the region of interest (the region of interest itself may or may not be considered part of the Moore neighbourhood, depending on context). For example, the Moore neighbourhood of a single cell consists of the eight cells immediately surrounding it. This [[neighbourhood]] is named after [[Edward F. Moore]], one of the pioneers of [[cellular automata]] theory.<ref>{{Cite web|url=http://cell-auto.com/neighbourhood/moore/|title=The Moore neighbourhood|author=Tim Tyler|accessdate=June 13, 2009}}</ref> The Moore neighborhood is the neighbourhood of interest in [[Conway's Game of Life]] and all [[Life-like cellular automata]], though there are cellular automata that use other neighbourhoods such as the 4-cell [[von Neumann neighborhood]].


The Moore neighbourhood naturally extends to cellular automata in higher dimensions, for example forming a 26-cell cubic neighborhood for a cellular automaton in three dimensions. The number of cells in the Moore neighbourhood of a single cell in an n-dimensional cellular automaton is 3<sup>n</sup>-1 (Sloane's {{OEIS|A024023}}).
The Moore neighbourhood naturally extends to cellular automata in higher dimensions, for example forming a 26-cell cubic neighborhood for a cellular automaton [[Three-dimensional cellular automaton|in three dimensions]]. The number of cells in the Moore neighbourhood of a single cell in an n-dimensional cellular automaton is {{nowrap|3<sup>n</sup> - 1}} (Sloane's {{OEIS|A024023}}).


The Moore neighbourhood of a cell can be thought of as the points at a Chebyshev distance of 1 from that cell.
The Moore neighbourhood of a cell can be thought of as the points at a Chebyshev distance of 1 from that cell.


== Generalizations ==
== Generalizations ==
{{main|Isotropic non-totalistic cellular automaton}}
{{related|Isotropic non-totalistic cellular automaton}}
Like in the [[hexagonal neighborhood]], [[isotropic]] cellular automata using the Moore neighbourhood can be defined using [[Hensel notation]], which was devised by [[Alan Hensel]] and represents the relative permutations of the cells using letters.
Like in the [[hexagonal neighborhood]], [[isotropic]] cellular automata using the Moore neighbourhood can be defined using [[Hensel notation]], which was devised by [[Alan Hensel]] and represents the relative permutations of the cells using letters.


{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
{{Isotropic non-totalistic transitions (square grid)}}
| style="border: none; background: #fff;" |
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8
|-
! —<small style="font-weight: normal;"> (no<br/>letter)</small>
| [[File:INT Moore R1 0.png]] || || || || || || || || [[File:INT Moore R1 8.png]]
|-
! c<br/><small style="font-weight: normal;">(corner)</small>
| || [[File:INT Moore R1 1c.png]] || [[File:INT Moore R1 2c.png]] || [[File:INT Moore R1 3c.png]] || [[File:INT Moore R1 4c.png]] || [[File:INT Moore R1 5c.png]] || [[File:INT Moore R1 6c.png]] || [[File:INT Moore R1 7c.png]] ||
|-
! e<br/><small style="font-weight: normal;">(edge)</small>
| || [[File:INT Moore R1 1e.png]] || [[File:INT Moore R1 2e.png]] || [[File:INT Moore R1 3e.png]] || [[File:INT Moore R1 4e.png]] || [[File:INT Moore R1 5e.png]] || [[File:INT Moore R1 6e.png]] || [[File:INT Moore R1 7e.png]] ||
|-
! k<br/><small style="font-weight: normal;">(knight)</small>
| || || [[File:INT Moore R1 2k.png]] || [[File:INT Moore R1 3k.png]] || [[File:INT Moore R1 4k.png]] || [[File:INT Moore R1 5k.png]] || [[File:INT Moore R1 6k.png]] || ||
|-
! a<br/><small style="font-weight: normal;">(adjacent)</small>
| || || [[File:INT Moore R1 2a.png]] || [[File:INT Moore R1 3a.png]] || [[File:INT Moore R1 4a.png]] || [[File:INT Moore R1 5a.png]] || [[File:INT Moore R1 6a.png]] || ||
|-
! i
| || || [[File:INT Moore R1 2i.png]] || [[File:INT Moore R1 3i.png]] || [[File:INT Moore R1 4i.png]] || [[File:INT Moore R1 5i.png]] || [[File:INT Moore R1 6i.png]] || ||
|-
! n
| || || [[File:INT Moore R1 2n.png]] || [[File:INT Moore R1 3n.png]] || [[File:INT Moore R1 4n.png]] || [[File:INT Moore R1 5n.png]] || [[File:INT Moore R1 6n.png]] || ||
|-
! y
| || || || [[File:INT Moore R1 3y.png]] || [[File:INT Moore R1 4y.png]] || [[File:INT Moore R1 5y.png]] || || ||
|-
! q
| || || || [[File:INT Moore R1 3q.png]] || [[File:INT Moore R1 4q.png]] || [[File:INT Moore R1 5q.png]] || || ||
|-
! j
| || || || [[File:INT Moore R1 3j.png]] || [[File:INT Moore R1 4j.png]] || [[File:INT Moore R1 5j.png]] || || ||
|-
! r
| || || || [[File:INT Moore R1 3r.png]] || [[File:INT Moore R1 4r.png]] || [[File:INT Moore R1 5r.png]] || || ||
|-
! t
| || || || || [[File:INT Moore R1 4t.png]] || || || ||
|-
! w
| || || || || [[File:INT Moore R1 4w.png]] || || || ||
|-
! z
| || || || || [[File:INT Moore R1 4z.png]] || || || ||
|}


For instance, B2-a/S12 (the [[Just Friends]] rule) indicates that a dead cell will be born with 2 neighbors, except when they are adjacent, and that a live cell will survive with 1 or 2 neighbors in any configuration.
For instance, B2-a/S12 (the [[Just Friends]] rule) indicates that a dead cell will be born with 2 neighbors, except when they are adjacent, and that a live cell will survive with 1 or 2 neighbors in any configuration.


==Higher ranges==
==Higher ranges==
The Moore neighbourhood can also be defined with a higher ''range''; that is, so that it captures cells that are further than one cell away from the region of interest. The standard Moore neighbourhood has range 1. The Moore neighbourhood of range 2 is the set of all cells that are orthogonally or diagonally-adjacent to the Moore neighbourhood itself. The Moore neighbourhood of range n can be defined recursively as the set of all cells that are orthogonally or diagonally-adjacent to the Moore neighbourhood of range n-1. The number of cells in the Moore neighbourhood of range n is given by (2n+1)<sup>2</sup>-1 (Sloane's {{OEIS|A033996}}).
The Moore neighbourhood can also be defined with a higher ''range''; that is, so that it captures cells that are further than one cell away from the region of interest. The standard Moore neighbourhood has range 1. The Moore neighbourhood of range 2 is the set of all cells that are orthogonally or diagonally adjacent to the Moore neighbourhood (of range 1). The Moore neighbourhood of range n can be defined recursively as the set of all cells that are orthogonally or diagonally adjacent to the Moore neighbourhood of range {{nowrap|n - 1}}. The number of cells in the Moore neighbourhood of range n is given by {{nowrap|(2 n + 1)<sup>2</sup> - 1}} (Sloane's {{OEIS|A033996}}).


== Symmetries ==
== Symmetries ==
Line 84: Line 39:


== Gallery ==
== Gallery ==
{|
<gallery widths=160px style="text-align:center;">
|-
File:Mooreneighbourhood eater1.png|The Moore neighbourhood (blue) of an [[eater 1]]
|[[File:Mooreneighbourhood eater1.png|framed|left|The Moore neighbourhood (blue) of an [[eater 1]]]]
File:Moore neighbourhood (range 2).png|The Moore neighbourhood of range 2 of a single cell
|[[File:Moore neighbourhood (range 2).png|framed|left|The Moore neighbourhood of range 2 of a single cell]]
File:Moore neighbourhood (range 3).png|The Moore neighbourhood of range 3 of a single cell
|[[File:Moore neighbourhood (range 3).png|framed|left|The Moore neighbourhood of range 3 of a single cell]]
</gallery>
|}


== See also ==
== See also ==
Line 108: Line 62:
* {{LinkMathworld|MooreNeighborhood.html|pagename=Moore neighborhood}}
* {{LinkMathworld|MooreNeighborhood.html|pagename=Moore neighborhood}}


[[Category:Neighbourhoods]]
__NOTOC__
__NOTOC__

Latest revision as of 20:16, 26 August 2024

The Moore neighbourhood (blue) of a single cell

The Moore neighbourhood is the set of all cells that are orthogonally or diagonally-adjacent to the region of interest (the region of interest itself may or may not be considered part of the Moore neighbourhood, depending on context). For example, the Moore neighbourhood of a single cell consists of the eight cells immediately surrounding it. This neighbourhood is named after Edward F. Moore, one of the pioneers of cellular automata theory.[1] The Moore neighborhood is the neighbourhood of interest in Conway's Game of Life and all Life-like cellular automata, though there are cellular automata that use other neighbourhoods such as the 4-cell von Neumann neighborhood.

The Moore neighbourhood naturally extends to cellular automata in higher dimensions, for example forming a 26-cell cubic neighborhood for a cellular automaton in three dimensions. The number of cells in the Moore neighbourhood of a single cell in an n-dimensional cellular automaton is 3n - 1 (Sloane's  A024023).

The Moore neighbourhood of a cell can be thought of as the points at a Chebyshev distance of 1 from that cell.

Generalizations

See also: Isotropic non-totalistic cellular automaton

Like in the hexagonal neighborhood, isotropic cellular automata using the Moore neighbourhood can be defined using Hensel notation, which was devised by Alan Hensel and represents the relative permutations of the cells using letters.

0 1 2 3 4 5 6 7 8
—
(no letter)
c
(corner)
e
(edge)
k
(knight)
a
(adjacent)
i
n
y
q
j
r
t
w
z

For instance, B2-a/S12 (the Just Friends rule) indicates that a dead cell will be born with 2 neighbors, except when they are adjacent, and that a live cell will survive with 1 or 2 neighbors in any configuration.

Higher ranges

The Moore neighbourhood can also be defined with a higher range; that is, so that it captures cells that are further than one cell away from the region of interest. The standard Moore neighbourhood has range 1. The Moore neighbourhood of range 2 is the set of all cells that are orthogonally or diagonally adjacent to the Moore neighbourhood (of range 1). The Moore neighbourhood of range n can be defined recursively as the set of all cells that are orthogonally or diagonally adjacent to the Moore neighbourhood of range n - 1. The number of cells in the Moore neighbourhood of range n is given by (2 n + 1)2 - 1 (Sloane's  A033996).

Symmetries

Main article: Static symmetry

The Moore and von Neumann neighbourhoods rely on a different grid than the hexagonal neighbourhood and thus features a different set of inherent symmetries when dealing with isotropic rules:

  • C2_1
  • C2_2
  • C2_4
  • C4_1
  • C4_4
  • D2_+1
  • D2_+2
  • D2_x
  • D4_+1
  • D4_+2
  • D4_+4
  • D4_x1
  • D4_x4
  • D8_1
  • D8_2 (only occasionally preserved)
  • D8_4
  • The Moore neighbourhood (blue) of an eater 1
    The Moore neighbourhood (blue) of an eater 1
  • The Moore neighbourhood of range 2 of a single cell
    The Moore neighbourhood of range 2 of a single cell
  • The Moore neighbourhood of range 3 of a single cell
    The Moore neighbourhood of range 3 of a single cell

See also

References

  1. ↑ Tim Tyler. "The Moore neighbourhood". Retrieved on June 13, 2009.
Retrieved from "https://conwaylife.com/w/index.php?title=Moore_neighbourhood&oldid=154930"