Comment compter les voisins d'une cellule dans un automate cellulaire avec wraparound

Question

Je crée donc un programme qui simule des automates cellulaires de type Life, mais j'ai des problèmes avec la méthode utilisée pour compter les voisins vivants d'une cellule. Le problème est que je veux être en mesure de changer la façon dont la grille s'enroule autour - à savoir, si elle s'enroule autour de gauche à droite (c.-à-cylindrique), de haut en bas et gauche à droite (c'est-à-dire, toroïdal), ou pas du tout (c'est à dire, plat) - et je ne peux pas comprendre comment rendre ma méthode compte pour cela. Voici ce que j'ai jusqu'à présent:

public int getLiveNeighbors(int row, int col) 
{ 
    int count = 0; 

    // "topology" is an int that represents wraparound: 
    // 0 = flat; 1 = cylindrical; 2 = toroidal 
    int top = topology != 2 ? row - 1 : (row + ROWS - 1) % ROWS; 
    int bottom = topology != 2 ? row + 1 : (row + 1) % ROWS; 
    int left = topology != 0 ? (col + COLS - 1) % COLS : col - 1; 
    int right = topology != 0 ? (col + 1) % COLS : col + 1; 

    for (int r = top; r < bottom + 1; r++) 
     for (int c = left; c < right + 1; c++) 
      if (!(r == row && c == col) && getCell(r, c).equals(LIVE)) 
       count++; 
} 

La clé, je pense, est le if -Déclaration dans le for -loop - il doit y avoir un moyen de vérifier si r et c sont dans les limites de la grille, tout en gardant à l'esprit que la définition de "bounds" variera en fonction de l'enroulement de la grille. Dans le passé, j'ai contourné cela en ayant trois ensembles différents (un pour chaque paramètre enveloppant) de huit états différents if pour vérifier individuellement chacune des huit cellules composant le voisinage de la cellule d'origine; Comme vous pouvez l'imaginer, ce n'était pas très joli, mais au moins cela a fonctionné. Je ne suis pas très douée pour expliquer mon propre code, alors j'espère que ce n'était pas trop déroutant - je me sens un peu bouclé moi-même (ha). Si vous avez des questions, n'hésitez pas à demander!

Answer 1

Vous avez probablement déjà une classe comme Board avec une méthode comme getCell(x, y) (au moins une méthode de ce type est présente dans votre code).

Je venais de rendre cette méthode clémente dans un sens qu'il accepterait négatif x et y ou x et y supérieure ou égale à COLS et ROWS. Ainsi, vous pouvez simplement parcourir col - 1 à col + 1 et row - 1 à row + 1 (moins col et row) et ne pas se soucier que ces coordonnées vont "sur le tableau". C'est la tâche du Board de faire les recherches de coordonnées correctement.

Ce qui rend votre code plus difficile, c'est aussi de gérer différentes topologies en un seul endroit. C'est assez difficile à suivre.

Vous pouvez le rendre plus simple en implémentant différentes sous-classes de Board comme CylindricalBoard, ToroidalBoard et FlatBoard. Chacune des sous-classes implémenterait getCell différemment, mais dans le contexte de la sous-classe, elle sera clairement compréhensible.

Answer 2

Vous recherchez le Strategy Pattern:

Il y a des situations communes lorsque les cours ne diffèrent que par leur comportement. Dans ce cas, il est judicieux d'isoler les algorithmes dans des classes séparées afin de pouvoir sélectionner différents algorithmes lors de l'exécution.

Dans ce cas, vous voudriez quelque chose comme ça (en abrégé pour plus de clarté):

class Point { 
    int x; 
    int y; 
} 

interface WrapStrategy { 
    Point moveUp(Point p); 
    Point moveDown(Point p); 
    Point moveLeft(Point p); 
    Point moveRight(Point p); 
} 

class CylinderWrapping implements WrapStrategy { 
    int height; 
    int circumference; 
    Point moveUp(Point p) { 
     if (p.y <= 0) 
      return null; // cannot move up 
     return new Point(p.x, p.y - 1); 
    } 
    Point moveDown(Point p) { 
     if (p.y >= height - 1) 
      return null; // cannot move down 
     return new Point(p.x, p.y + 1); 
    } 
    Point moveLeft(Point p) { 
     if (p.x <= 0) 
      return new Point(circumference - 1, p.y); 
     return new Point(p.x - 1, p.y); 
    } 
    Point moveRight(Point p) { 
     if (p.x >= circumference - 1) 
      return new Point(0, p.y); 
     return new Point(p.x + 1, p.y); 
    } 
} 

Answer 3

Essayez ceci:

import java.awt.Point; 

public class Neighbours { 

    public static void main(String[] args) { 
     Neighbours inst=new Neighbours(); 
     int r=3;//<ROWS 
     int c=3;//<COLS 
     for(int i :new int[]{0,1,2}){ 
      inst.type=i; 
      System.out.format("There are %d neighbours of point (%d,%d), topography type %d\n", inst.countLiveNeighbours(r, c), c, r,i); 
     } 
    } 

    int ROWS=4; 
    int COLS=4; 
    int type=0;//0=flat, 1=cylinder, 2=toroid 

    /** 
    * Is x,y a neighbour of r,c? 
    * @return coordinates of neighbour or null 
    */ 
    Point neighbour(int x, int y, int r, int c){ 
     if((x==c)&&(y==r)) 
      return null; 
     switch (type){ 
/*this is wrong for the reasons explained below 
     case 0: return ((x<COLS)&&(y<ROWS)) ? new Point (x,y) : null; 
     case 1: return y<ROWS ? new Point(x%COLS,y) : null; 
     case 2: return new Point(x%COLS,y%ROWS); 
*/ 
//replacement statements produce the correct behaviour 
    case 0: return ((x<COLS)&&(x>-1)&&(y<ROWS)&&(y>-1)) ? new Point (x,y) : null; 
    case 1: return ((y<ROWS)&&(y>-1)) ? new Point(Math.floorMod(x,COLS),y) : null; 
    case 2: return new Point(Math.floorMod(x,COLS),Math.floorMod(y,ROWS)); 
     } 
     return null; 
    } 

    int countLiveNeighbours(int r, int c){ 
     int result=0; 
     for(int x=c-1; x<c+2; x++) 
      for(int y=r-1; y<r+2; y++){ 
       Point p=neighbour(x,y,r,c); 
       if(live(p)){ 
        System.out.format("\tpoint (%d,%d)\n",(int)p.getX(),(int)p.getY()); 
        result++; 
       } 
      } 
     return result; 
    } 

    boolean live(Point p){ 
     boolean result=true; 
     if(p==null) 
      return false; 
     //perform tests for liveness here and set result 
     return result; 
    } 
}