Square tiling

The square grid, square tiling, square tessellation or square lattice is one of the three possible proper Euclidean tilings of 2D space, in which four squares are placed at each vertex.

The square grid is the most familiar of all 2D tilings, with cell positions being easily and uniquely defined via Cartesian coordinates, and is the grid on which cellular automata are simulated most frequently.

Neighbourhoods on the square grid

Range-1 cases

Most of the cellular automata which are investigated are isotropic and use neighbourhoods of range 1. These constraints permit two neighbourhoods of interest; the 4-cell von Neumann neighbourhood, consisting of the four cells orthogonally adjacent to a central cell, and the 8-cell Moore neighbourhood, consisting of the four cells orthogonally adjacent to a central cell as well as the four cells diagonally adjacent to said center cell. (A third neighbourhood, referred to on this wiki as the "saltire" neighbourhood, which consists only of the four cells diagonally adjacent to the central cell, functionally duplicates the von Neumann neighbourhood and is disregarded in this section for the sake of brevity.)

Whether the central cell is counted as being part of the neighbourhood commonly depends on the situation.

von Neumann	Moore	saltire (trivial)

Due to its simplicity, the von Neumann neighbourhood does not lend itself to particularly many interesting 2-state outer-totalistic rules; it does, however, see much more use in more complicated anisotropic rules, and outer-totalistic rules based on it can often be sighted in more complex rules; for example, 2D replicators tend to follow the rule B13/S13V to an extent.

The Moore neighbourhood is the neighbourhood most commonly used in naturalistic rules, with many of the most famous rules such as Life and HighLife being based on it. Its larger size permits a much wider array of rules, many with their own interesting behaviours, in contrast to the more oppressive von Neumann neighbourhood, while not being so large as to include an unthinkably large amount of possibilities which makes finding interesting rules difficult.

Higher ranges

It is entirely possible to extend the aforementioned von Neumann, Moore and even saltire neighbourhoods to higher ranges, such that cells which are not immediately orthogonally or diagonally adjacent to the central cell are also included in the neighbourhood.

There are two immediately obvious ways in which the von Neumann neighbourhood can be extended:

• by counting all of the cells in the von Neumann neighbourhood of the cells which are in turn already in the von Neumann neighbourhood of another cell, or
• by counting all of the cells which are at an orthogonal distance 1 or 2 from a central cell.

The former is usually referred to as the von Neumann neighbourhood of range n (depending on how much this process is repeated), and gives a square shape which is rotated 45 degrees from its constituent cells. The latter is referred to as the cross neighbourhood of range n.

A third, more subtle way in which the range-1 von Neumann neighbourhood can be extended to higher ranges is by considering the grid to be a checkerboard, and only considering the squares of opposite parity to the center cell out to a given distance both orthogonally and diagonally. The resulting neighbourhood is therefore referred to as the checkerboard neighbourhood of range n.

Range \ Type	von Neumann neighbourhood	cross neighbourhood	checkerboard neighbourhood
1
2
3
4
5