To Implement Extended Moore Neighbourhoods

[Freywa]

At the moment, Golly does not support the extended Moore neighbourhood (two cells around), but I must have that neighbourhood to do a CA I'm interested in. How would I emulate it?

[Freywa]

More specifically, the CA I desire to implement is exactly like Conway's Life, but instead the neighbours of a cell are those cells one knight's move away.

[lukebradford]

You can do this with a rule table, using the neighborhood Moore_radius2: https://code.google.com/p/ruletablerepo ... ki/RoadMap

[Hektor]

You can do this with a rule table, using the neighborhood Moore_radius2: https://code.google.com/p/ruletablerepo ... ki/RoadMap

I don't think it's implemented in the current version of Golly.
It would be interesting to know if, say, Von Neumann with radius 2 could be implemented in the normal Moore neighborhood

[EricG]

Luke,

If I'm not mistaken, the link you provided lists future directions for the rule table format, but they aren't implemented for Golly (or any other commonly used program) at this time.

The good news is that two state rules for Radius 2 neighborhoods can be emulated in Golly, and I'm providing some code to do that below. The bad news is that it takes 16 states to emulate any particular two state rule, and using Golly's RuleTreeGen code, that means it may take hours to generate any particular rule.

Here is some quick-and-dirty C code which implements all of the radius 2 neighborhoods for Golly listed at Luke's link, and it also allows for the implementation of other neighborhoods you'd like to come up with using weights set to zero or one. Of course, it would be more convenient to use python instead of C, but if I recall correctly, the python version took much longer than the C version to run (days instead of hours). Also, I put together the code below some time ago, before Golly switched from RuleTrees to the .Rule format, so the code below needs to be updated. I'm going to post the following as a placeholder for now.

Code: Select all

#include <string.h>     // for strlen
#include <vector>
#include <map>
#include <string>
#include <cstdio>
using namespace std ;


//************************************************************************************************************************
//      Weighted Life Radius 2 In Golly!   Using 16 states!
//         Emulate two state  Weighted Life rules, where each  cell has up to 24 neighbors.
//         Create Larger Than Life rules, Hex Radius 2 rules, and other Radius2 rules.
//
//     The brute force neighborhood code is by Eric Goldstein, eric@goldstein.net
//     The elegant RuleTreeGen code at the bottom of this file was distributed with Golly, by the Golly Gang.
//   
//     Directions for setting a Bnnn/Snnn rule and a neighborhood are below.
//
//     I compiled this file using this command:
//     g++ -O5 -o result_filename_goes_here this_file_filename_goes_here.cpp 
//     
//     Warning:  The compiled code took roughly 4.5 to 6 hours  (depending on the rule) to run 
//                on a Macbook with a 2.4 Ghz Intel Core i5.
//************************************************************************************************************************



//  Set the desired Bnnn/Snnn rule below, using a 1 to indicate a birth or survial condiation and a zero otherwise.
//  Be sure to initizalize birthrule[] and survivalrule[] to a length at least as long as the sum of the values in weights[].

//  Here is B4/S4:
  int birthrule[] =    {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  int survivalrule[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

//  Here is B67/S5678,13,15,16,17,18 (or "B67/S5678dfghi"):
//   const  int birthrule[] =    {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//   const  int survivalrule[] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0};


    
//  Set the desired weights for the cell's 24 neighbors below.  Use positive integers.
//  Here is the Larger Than Life Range 2 neighborhood, in which all 24 neighbors are weighted equally:
    
   const int weights[] = 
              {1, 1, 1, 1, 1,  
               1, 1, 1, 1, 1,   
               1, 1,    1, 1,     
               1, 1, 1, 1, 1,    
               1, 1, 1, 1, 1};


//  Comment out the above weights, and uncomment one of the neighborhoods below, or create your own weighted neighborhood.

        // int weights[] = {0,1,1,1,0,  1,1,1,1,1,  1,1,1,1,  1,1,1,1,1, 0,1,1,1,0};    //     "Disc Radius2 neighborhood"
        // int weights[] = {1,0,1,0,1,  0,1,1,1,0,  1,1,1,1,  0,1,1,1,0, 1,0,1,0,1};    //     "Star Radius2 neighborhood"  
        // int weights[] = {0,0,1,0,0,  0,1,1,1,0,  1,1,1,1,  0,1,1,1,0, 0,0,1,0,0};    //     "Diamond Radius2  neighborhood"
        // int weights[] = {0,1,0,1,0,  1,0,0,0,1,  0,0,0,0,  1,0,0,0,1,  0,1,0,1,0};   //     "Knightlife neighborhood"
        // int weights[] = {1,1,1,1,1,  1,0,0,0,1,  1,0,0,1,  1,0,0,0,1,  1,1,1,1,1};   //     "Perimeter Radius2 neighborhood" 
        // int weights[] = {0,1,0,0,0,  0,1,0,1,1,  0,0,0,0,  1,1,0,1,0,  0,0,0,1,0};   //     "Pinwheel Radius2 neighborhood" 
        // int weights[] = {0,0,1,0,0,  0,0,1,0,0,  1,1,1,1,  0,0,1,0,0,  0,0,1,0,0};   //     "von Neuman Radius2 neighborhood" 

        // int weights[] = {1,1,1,0,0,  1,1,1,1,0,   1,1,1,1,  0,1,1,1,1, 0,0,1,1,1};    //     "Hex Radius2 neighborhood" 
        // int weights[] = {0,1,0,0,0,  1,1,1,1,0,   0,1,1,0,  0,1,1,1,1, 0,0,0,1,0};    //     "Hex Star neighborhood"    
         // ****** WAIT!   George Maydwell's Hex Star neighborhood can be emulated in just 8 states!  
         // ****** See my Golly Tilling Project for a Hex Star neighborhood script!
        // int weights[] = {0,1,0,0,0,  0,1,1,0,0,   0,1,1,0,  0,1,1,1,1, 0,0,0,0,0};    //     "Hex Triangle neighborhood"  
        // int weights[] = {0,0,1,0,0,  0,1,1,0,0,   1,1,1,0,  0,0,1,1,0, 0,0,0,0,1};    //     "Hex BumpyTri neighborhood"   
        // int weights[] = {1,0,1,0,0,  0,1,1,0,0,   1,1,1,1,  0,0,1,1,0, 0,0,1,0,1};    //     "Hex Asterix neighborhood" 
        // int weights[] = {0,0,1,0,0,  0,0,1,0,0,   1,1,0,0,  0,0,0,1,0, 0,0,0,0,1};    //     "Hex Tripod Radius2 neighborhood"  


        // int weights[] = {0,0,1,0,0,  0,1,0,1,0,  1,0,0,1,  0,1,0,1,0,  0,0,1,0,0};   //     "Diagonal Moore neighborhood" 
        // int weights[] = {0,0,0,0,0,  0,1,1,1,0,  0,1,1,0,  0,1,1,1,0, 0,0,0,0,0};    //     "Emulated Radius1 Moore neighborhood"  



const int numStates = 16;
const int numNeighbors = 8;


int f(int *neighbors) {

   int nw = neighbors[0];
   int ne = neighbors[1];
   int sw = neighbors[2];
   int se = neighbors[3];
   int n = neighbors[4];
   int w = neighbors[5];
   int e = neighbors[6];
   int s = neighbors[7];
   int cell = neighbors[8];

/*  
   Subdivide each Golly cell into four parts: a, b, c, and d:
      --------------------------
     |  cell_a    |   cell_b  |
     --------------------------
     |  cell_c    |   cell_d  |
     --------------------------

 So, the cell and its eight neighbors are divided into these 36 sections:

   nw_a  nw_b  n_a     n_b      ne_a  ne_b
   nw_c  nw_d  n_c     n_d      ne_c  ne_d
   w_a   w_b   cell_a  cell_b   e_a   e_b
   w_c   w_d   cell_c  cell_d   e_c   e_d
   sw_a  sw_b  s_a      s_b     se_a  se_b
   sw_c  sw_d  s_c      s_d     se_c  se_d


    
*/


   int cell_a = cell & 1;
   int cell_b = (cell >> 1) & 1;
   int cell_c = (cell >> 2) & 1;
   int cell_d = (cell >> 3) & 1;

   int nw_a = nw & 1;
   int nw_b = (nw >> 1) & 1;
   int nw_c = (nw >> 2) & 1;
   int nw_d = (nw >> 3) & 1;

   int n_a = n & 1;
   int n_b = (n >> 1) & 1;
   int n_c = (n >> 2) & 1;
   int n_d = (n >> 3) & 1;

   int ne_a = ne & 1;
   int ne_b = (ne >> 1) & 1;
   int ne_c = (ne >> 2) & 1;
   int ne_d = (ne >> 3) & 1;

   int e_a = e & 1;
   int e_b = (e >> 1) & 1;
   int e_c = (e >> 2) & 1;
   int e_d = (e >> 3) & 1;

   int w_a = w & 1;
   int w_b = (w >> 1) & 1;
   int w_c = (w >> 2) & 1;
   int w_d = (w >> 3) & 1;

   int sw_a = sw & 1;
   int sw_b = (sw >> 1) & 1;
   int sw_c = (sw >> 2) & 1;
   int sw_d = (sw >> 3) & 1;

   int s_a = s & 1;
   int s_b = (s >> 1) & 1;
   int s_c = (s >> 2) & 1;
   int s_d = (s >> 3) & 1;

   int se_a = se & 1;
   int se_b = (se >> 1) & 1;
   int se_c = (se >> 2) & 1;
   int se_d = (se >> 3) & 1;

/*


 Again, for reference, the cell and its eight neighbors are divided into these 36 sections:

   nw_a  nw_b  n_a     n_b      ne_a  ne_b
   nw_c  nw_d  n_c     n_d      ne_c  ne_d
   w_a   w_b   cell_a  cell_b   e_a   e_b
   w_c   w_d   cell_c  cell_d   e_c   e_d
   sw_a  sw_b  s_a      s_b     se_a  se_b
   sw_c  sw_d  s_c      s_d     se_c  se_d




Neighbor weight indexes (or "indices" if you prefer):
     0,   1,  2,  3,  4,
     5,   6,  7,  8,  9,
     10, 11,     12, 13,
     14, 15, 16, 17, 18,
     19, 20, 21, 22, 23 
    
*/


   int a_count =   nw_a*weights[0] + nw_b*weights[1] + n_a*weights[2] + n_b*weights[3] + ne_a*weights[4] 
                   +  nw_c*weights[5] +  nw_d*weights[6] + n_c*weights[7] + n_d*weights[8] + ne_c*weights[9]
                   +  w_a*weights[10] +  w_b*weights[11] + cell_b*weights[12] + e_a*weights[13]
                   +  w_c*weights[14] +  w_d*weights[15] + cell_c*weights[16] + cell_d*weights[17] +e_c*weights[18]
                   +  sw_a*weights[19] + sw_b*weights[20] + s_a*weights[21] + s_b*weights[22] + se_a*weights[23];

   int b_count = nw_b*weights[0] +   n_a*weights[1] +   n_b*weights[2] +   ne_a*weights[3] +   ne_b*weights[4]   
                + nw_d*weights[5] +   n_c*weights[6] +   n_d*weights[7] +   ne_c*weights[8] +   ne_d*weights[9]  
                + w_b*weights[10] +    cell_a*weights[11] +         e_a*weights[12] +    e_b*weights[13]   
                +  w_d*weights[14] +   cell_c*weights[15] +     cell_d*weights[16] +   e_c*weights[17] +    e_d*weights[18]  
                + sw_b*weights[19] +   s_a*weights[20] +   s_b*weights[21] +   se_a*weights[22] +   se_b*weights[23];

   int c_count = nw_c*weights[0] +   nw_d*weights[1] +   n_c*weights[2] +   n_d*weights[3] +   ne_c*weights[4] 
                 + w_a*weights[5] +    w_b*weights[6] +    cell_a*weights[7] +      cell_b*weights[8] +    e_a*weights[9]   
                 + w_c*weights[10] +    w_d*weights[11] +        cell_d*weights[12] +    e_c*weights[13]  
                 + sw_a*weights[14] +   sw_b*weights[15] +   s_a*weights[16] +   s_b*weights[17] +   se_a*weights[18] 
                 + sw_c*weights[19] +   sw_d*weights[20] +   s_c*weights[21] +   s_d*weights[22] +   se_c*weights[23];

   int d_count = nw_d*weights[0] +    n_c*weights[1] +       n_d*weights[2] +        ne_c*weights[3] +    ne_d*weights[4] 
                + w_b*weights[5] +     cell_a*weights[6] +    cell_b*weights[7] +     e_a*weights[8] +     e_b*weights[9]  
                + w_d*weights[10] +     cell_c*weights[11] +             e_c*weights[12] +     e_d*weights[13]  
                + sw_b*weights[14] +    s_a*weights[15] +        s_b*weights[16] +       se_a*weights[17] +    se_b*weights[18]   
                + sw_d*weights[19] +   s_c*weights[20] +        s_d*weights[21] +       se_c*weights[22] +    se_d*weights[23];

   int newcell_a = 0;
   int newcell_b = 0;
   int newcell_c = 0;
   int newcell_d = 0;

   if (cell_a == 1)
     newcell_a = survivalrule[a_count];
   else newcell_a = birthrule[a_count];

   if (cell_b == 1)
     newcell_b = survivalrule[b_count];
   else newcell_b = birthrule[b_count];

   if (cell_c == 1)
     newcell_c = survivalrule[c_count];
   else newcell_c = birthrule[c_count];

   if (cell_d == 1)
     newcell_d = survivalrule[d_count];
   else newcell_d = birthrule[d_count];


   return newcell_a + (newcell_b << 1) + (newcell_c << 2)  + (newcell_d << 3);

}


//  ************************************************************************
//  The following RuleTreeGen code is distributed with Golly 
//  ************************************************************************

const int numParams = numNeighbors + 1 ;
map<string,int> world ;
vector<string> r ;
int nodeSeq, params[9] ;
int getNode(const string &n) {
   map<string,int>::iterator it = world.find(n) ;
   if (it != world.end())
      return it->second ;
   world[n] = nodeSeq ;
   r.push_back(n) ;
   return nodeSeq++ ;
}
int recur(int at) {
   if (at == 0) {
      return f(params) ;
   } else {
      char buf[256*10] ;
      sprintf(buf, "%d", at) ;
      for (int i=0; i<numStates; i++) {
         params[numParams-at] = i ;
         sprintf(buf+strlen(buf), " %d", recur(at-1)) ;
      }
      return getNode(buf) ;
   }
}
void writestring() {
   printf("num_states=%d\n", numStates) ;
   printf("num_neighbors=%d\n", numNeighbors) ;
   printf("num_nodes=%d\n", r.size()) ;
   for (unsigned int i=0; i<r.size(); i++)
      printf("%s\n", r[i].c_str()) ;
}
int main(int argc, char *argv[]) {
   recur(numParams) ;
   writestring() ;
}

If you want to try out the Larger Than Life rule B4/S4 radius 2 rule, and some related rules, you can download http://www.gohover.com/Radius2_Rules_Example/ B4/S4 was one of the most interesting rules Kellie Evans described in her Larger Than Life thesis.

I have a bit more to post on this subject and on knightlife in particular, but I'll just post this for now. Freywa, what is the knight's move rule you have in mind? Is it a two state rule? I believe I recall you saying, once, that you weren't comfortable with C. If this is still true, I can help you implement your rule, if it is a two state rule.

[EricG]

Oh, I should have said this first: the quickest and easiest way to experiment with the Knight's Move neighborhood using publicly available software is to use Brian Prentice's Square Cell program!

The code I posted above takes so long to run that it isn't practical unless you already have a particular rule in mind that you want to run on Golly. If you want to try out a wide variety of different rules in a radius 2 neighborhood, use Brian's program!

[bprentice]

Carefully read this thread:

viewtopic.php?f=11&t=967&p=7288&

and in particular this post:

viewtopic.php?f=11&t=967&p=7288&#p7288

Brian Prentice

[Freywa]

I actually began this post because Erich Friedman's January 2015 Math Magic deals exactly with a knight move-based version of Conway's Life. Apparently, it is uninteresting.