Le voisinage 2D complet (voisinage de Moore) sur la grille rectangulaire est le voisinage de base. Tous les autres voisinages sont incomplets et constituent des sous-ensembles du voisinage complet. Par conséquent les automates cellulaires basés sur un voisinage incomplet constituent un sous-ensemble d'une famille (k, r).
|
|
| FIG 1: Correspondance entre les voisinages d'une cellule sur une grille hexagonale et sur une grille rectangulaire |
Le voisinage hexagonal comprend 6 cellules voisines d'un hexagone (et la cellule elle-même). Pour retrouver ce voisinage sur la grille rectangulaire il suffit d'observer la transformation de la grille hexagonale vers la grille rectangulaire (FIG 1 ).
|
| FIG 2: Correspondance entre les voisinages d'une cellule sur une grille hexagonale ajustée et sur une grille rectangulaire |
Le voisinage de la grille hexagonale ajustée (au rectangle), quant à lui, n'est pas homogène. Il diffère selon la parité de la ligne 10 (FIG 2 ).
Les cellules de la grille triangulaire peuvent avoir deux positions. La cellule triangulaire peut être placée base vers le haut ou base vers le bas. Les triangles dont la base est tournée vers le haut correspondent aux cellules rectangles des lignes impaires (FIG.3).
|
| FIG 3: Correspondance entre la grille triangulaire et la grille rectangulaire |
Ceux dont la base est tournée vers le bas correspondent aux cellules des lignes paires. Ainsi la grille se «tasse»: deux lignes de la grille rectangulaire sont remplacées par une seule ligne de la grille triangulaire qui contient deux fois plus de cellules (pour le réseau fini). Ces cellules sont de deux genres différents (les deux orientations du triangle) et leur voisinage n'est pas le même pour ces deux genres.
|
| FIG 4: Correspondance entre la grille triangulaire ajustée et la grille rectangulaire |
Le voisinage n'est donc plus homogène déjà sur la grille triangulaire la plus simple, celle en parallélogramme (FIG.3). Après l'opération d'ajustement de la grille au rectangle cette différence ne s'annule pas. Au contraire, les choses se compliquent. On a maintenant quatre genres de voisinage qui varient selon l'orientation des triangles et, en plus, selon la parité de la ligne triangulaire (FIG.4).
Il existe une manière simple d'obtenir les versions de tous les voisinages incomplets étendus. On part d'un voisinage incomplet le plus proche (par exemple hexagonal simple). Autour de chaque cellule de ce voisinage on dessine un voisinage précédemment choisi. On répète cette opération r-1 fois FIG.5).
|
| FIG.5: Production du voisinage de rayon 2 |
Ce procédé correspond à un automate cellulaire (2,1), qui allume la cellule dès que dans son voisinage se trouve au moins une cellule allumée. On le fait tourner pendant r-1 étapes. On peut obtenir ainsi les versions étendues (pour r entier) de tous les voisinages incomplets (FIG. 5-10).
Les solutions pour étendre les voisinages décrites ci-dessus sont valables pour un r entier. Il faudra inventer un système plus élaboré pour étendre les voisinages incomplets pour 2r+1 pair. On peut aussi se contenter de couper tout simplement un rang ce cellules de chaque coté.
Le cardinal de l'ensemble des cellules d'un voisinage complet est donné par la formule suivante :
Il s'agit bien du cardinal d'un voisinage complet et dans toutes les dimensions il existe des sous-espaces de ce voisinage. Un automate cellulaire unidimensionnel peut être défini sur un voisinage comportant uniquement 2 cellules (la cellule elle-même et sa voisine) ou bien 4, 6 ou un autre nombre pair de cellules. On considère que le rayon d'un voisinage comportant 2 cellules est égal à 1/2. Cette notation généralise le calcul du nombre de cellules du voisinage à partir du rayon du voisinage (Équation (4.1)): (1+2r)1, donc r=1/2. Le rayon d'un voisinage constitué de 4 cellules est égal à (4-1)/2 = 3/2 etc. Par un raisonnement analogue le nombre de cellules de la famille (2;1/2) en 2D égale (1+2 x 1/2)^2 = 4 (un carré 2x2) et en 3D égale (1+2 x 1/2)^3=8 (un cube 2x2x2). Selon le même calcul le nombre de cellules du voisinage de la famille (2,1) en 1D (automates élémentaires) égale 3, en 2D (le jeu de la vie) égale 9 et en 3D égale 27... En 2D le voisinage complet est appelé le voisinage de Moore. Le cardinal du voisinage de Von Neuman est calculé selon l'équation:
 |
(4.2) |
Le cardinal du voisinage hexagonal selon:
Les mêmes voisinages ne comportant pas de cellule centrale peuvent avoir plusieurs variétés. Si on génère le voisinage étendu à partir du voisinage le plus proche comportant une celluledu centre, puis on enlève la cellule du centre, il suffit de compter le cardinal selon les règles indiquées ci-dessus, puis de le diminuer de 1. Le cardinal du voisinage augmente exponentiellement:
