Difference between revisions of "Moore neighbourhood"

From LifeWiki
Jump to: navigation, search
m (Corrected Wikipedia page name)
Line 19: Line 19:
 
|-
 
|-
 
! c<br/><small style="font-weight: normal;">(corner)</small>
 
! c<br/><small style="font-weight: normal;">(corner)</small>
| || [[File:Neighborhood 1c.png]] || [[File:Neighborhood 2c.png]] || [[File:Neighborhood 3c.png]] || [[File:Neighborhood 4c.png]] || [[File:Neighborhood 5c.png]] || [[File:Neighborhood 6c.png]] || [[File:Neighborhood 7c.png]] ||  
+
| || [[File:Neighborhood 1c.png]] || [[File:Neighborhood 2c.png]] || [[File:Neighborhood 3c.png]] || [[File:Neighborhood 4c.png]] || [[File:Neighborhood 5c.png|64px]] || [[File:Neighborhood 6c.png]] || [[File:Neighborhood 7c.png]] ||  
 
|-
 
|-
 
! e<br/><small style="font-weight: normal;">(edge)</small>
 
! e<br/><small style="font-weight: normal;">(edge)</small>

Revision as of 00:01, 18 August 2019

File:Mooreneighbourhood 1cell.png
The Moore neighbourhood (in green) 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 OEISicon light 11px.pngA024023).

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

Generalizations

Main article: Isotropic non-totalistic Life-like 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)
Neighborhood 0.png Neighborhood 8.png
c
(corner)
Neighborhood 1c.png Neighborhood 2c.png Neighborhood 3c.png Neighborhood 4c.png Neighborhood 5c.png Neighborhood 6c.png Neighborhood 7c.png
e
(edge)
Neighborhood 1e.png Neighborhood 2e.png Neighborhood 3e.png Neighborhood 4e.png Neighborhood 5e.png Neighborhood 6e.png Neighborhood 7e.png
k
(knight)
Neighborhood 2k.png Neighborhood 3k.png Neighborhood 4k.png Neighborhood 5k.png Neighborhood 6k.png
a
(adjacent)
Neighborhood 2a.png Neighborhood 3a.png Neighborhood 4a.png Neighborhood 5a.png Neighborhood 6a.png
i Neighborhood 2i.png Neighborhood 3i.png Neighborhood 4i.png Neighborhood 5i.png Neighborhood 6i.png
n Neighborhood 2n.png Neighborhood 3n.png Neighborhood 4n.png Neighborhood 5n.png Neighborhood 6n.png
y Neighborhood 3y.png Neighborhood 4y.png Neighborhood 5y.png
q Neighborhood 3q.png Neighborhood 4q.png Neighborhood 5q.png
j Neighborhood 3j.png Neighborhood 4j.png Neighborhood 5j.png
r Neighborhood 3r.png Neighborhood 4r.png Neighborhood 5r.png
t Neighborhood 4t.png
w Neighborhood 4w.png
z Neighborhood 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.

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)2-1 (Sloane's OEISicon light 11px.pngA033996).

Symmetries

Main article: 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

Image gallery

The Moore neighbourhood (in green) of an eater 1
File:Mooreneighbourhood range2.png
The Moore neighbourhood of range 2 of a single cell
File:Mooreneighbourhood range3.png
The Moore neighbourhood of range 3 of a single cell

See also

References

  1. Tim Tyler. "The Moore neighbourhood". Retrieved on June 13, 2009.

External links