Thursday, June 25, 2020

[iknyszfk] Generalized Moore neighborhood

Each cell is the root of a tree of squares; orthogonal neighbors are children, labeled by the square edge traversed to reach them.  To get to a diagonal neighbor, go one step orthogonally, turn 90 degress, and go one more step orthogonally.

We need to avoid backtracking, but that seems easy: don't go backward.  Returning to a cell without going backward, i.e., traveling a loop, is permitted.

A node may appear multiple times as a descendent of another node.  For example, on a Euclidean plane, there are two ways to get to a diagonally adjacent cell as a grandchild.  With a totalistic cellular automaton such as Conway's Game of Life, diagonal neighbors would get counted twice when using this tree view.  Compensate for this by giving them half weight.

Treating neighbors as a tree allows evaluating a cellular automaton rule on any manifold consisting of square cells glued at edges, for example, on a hyperbolic plane.  The Moore neighborhood can be treated as an extension of the von Neumann neighborhood.

No comments :