// LL 2021

// 3D Cellular Automata
// Basics: https://en.wikipedia.org/wiki/Life-like_cellular_automaton 

// Forked from "Menger Sponge" by reinder
// https://turtletoy.net/turtle/79240332e3

// Declare your own custom rule here in the format: Bnnn/Snnn
const custom_rule = "B12/S2";

// Thumbnail settings:
// https://turtletoy.net/turtle/3b6550c0d8#grid_size=50,iterations=24,camera_distance=46.9,camera_rotation=0.14,camera_height=0.33,rule=2,add_hatching=1,draw_cube_edges=0

const grid_size = 50; // min=1 max=150 step=1
const iterations = 24; // min=0 max=50 step=1
const camera_fov = 3; /// min=0.5 max=5 step=0.05
const camera_distance = 50; // min=.1 max=100 step=0.1
const camera_rotation = 0.1; // min=0 max=1 step=0.01
const camera_height = 0.4; // min=0 max=3 step=0.01
const rule = 1; // min=0 max=3 step=1 (Custom,B124567/S,B123/S,B135/S246)
const add_hatching = 1; // min=0 max=1 step=1 (No, Yes)
const draw_cube_edges = 0; // min=0 max=1 step=1 (No, Yes)

var rule_str_list = [ custom_rule, "B124567/S", "B123/S", "B135/S246" ];
var rule_str = rule_str_list[rule];

const turtle = new Turtle();
const text = new Text();

var grid = [];
var current_state = 0;
var survive_list = [];
var birth_list = [];
var iterations_t = iterations;

var voxelRayCaster;

function walk(i, t) {
    if (i==0) {
        // Animate GIF by rotating camero
        const camera_rotation_t = camera_rotation + (t-1);
        //const camera_rotation_t = camera_rotation;

        const radius = Math.pow(1.02, grid_size) * camera_distance;
        const xx = radius * Math.cos(camera_rotation_t * Math.PI);
        const yy = radius * camera_height;
        const zz = radius * -Math.sin(camera_rotation_t * Math.PI);
        const ro = [xx+.5, yy+.5, zz+.5]; 
        const ta = [.5, .5, .5];
        voxelRayCaster = new VoxelRayCaster(ro, ta, 0, camera_fov);

        // Animate GIF by stepping through iterations
        //iterations_t = iterations * t;

        initGrid();
    }
    
    const tiles = 5;
    const x = i % tiles, y = (i/tiles)|0;
    
    const lt = [x*200/tiles-100, y*200/tiles-100];           // Left top of tile
    const rb = [(x+1)*200/tiles-100, (y+1)*200/tiles-100];   // Right bottom of tile
    
    // Draw tile
    //turtle.jump(lt[0], lt[1]); turtle.goto(rb[0], lt[1]); turtle.goto(rb[0], rb[1]); turtle.goto(lt[0], rb[1]); turtle.goto(lt[0], lt[1]);
    
    const faces = voxelRayCaster.collectFaces(map, lt, rb, 400, 0.25);
    const polys = new Polygons();
    
    // Create a polygon for this tile to clip all faces
    const viewPort = polys.create();    
    viewPort.addPoints(lt, [lt[0], rb[1]], rb, [rb[0], lt[1]]);
    
    faces.forEach(face => {
        const p = polys.create();
        p.addPoints(...face.points);

        if (draw_cube_edges) {
            p.addOutline();
        } else {
            face.edges.forEach((e, i) => e && p.addSegments(p.cp[i], p.cp[(i+1)%4]));
        }
        
        if (add_hatching && Math.abs(face.normal[2]) > .5) {
            p.addHatching(-Math.PI/3, .5);
        }
        
        p.boolean(viewPort, false);
        
        polys.draw(turtle, p);
    });

    return i < tiles*tiles - 1;
}

function initGrid() {
    parseRule();
    
    grid = Array.from({length: grid_size*grid_size*grid_size}, (v, i) => new Cell(false));
    
    // Start with single cell in the center.
    const center = Math.round(grid_size / 2);
    grid[index(center,center,center)].states[current_state] = true;

    for (var i=0; i<iterations_t; i++) {
        current_state = (current_state+1) % 2;
        evolveGrid();
    }
}

function parseRule() {
    const lists = { "B": [], "S": [] };
    var current_list = "B";
    
    for (var i=0; i<rule_str.length; i++) {
        const c = rule_str.charAt(i);
        const a = rule_str.charCodeAt(i);
        if (c == "B" || c == "S") {
            current_list = c;
        } else if (a >= 48 && a <= 57) {
            lists[current_list].push(a - 48);
        }
    }
    
    birth_list = lists["B"];
    survive_list = lists["S"];
    
    var rule_log = "B";
    birth_list.forEach(b => rule_log += b.toString());
    rule_log += "/S";
    survive_list.forEach(s => rule_log += s.toString());
    
    turtle.jump(-90,93);
    text.print(turtle, `Rule: ${rule_log} - Iterations: ${iterations_t}`, .1);
}

function evolveGrid() {
    const previous_state = (current_state+1) % 2;
    for (var z=0; z<grid_size; z++) {
        for (var y=0; y<grid_size; y++) {
            for (var x=0; x<grid_size; x++) {
                const count = countNeighbors(x, y, z, previous_state);
                grid[index(x, y, z)].states[current_state] = applyRule(grid[index(x, y, z)].states[previous_state], count);
            }
        }
    }
}

function countNeighbors(x, y, z, state) {
    var count = 0;

    for (var dz=-1; dz<=1; dz++) {
        for (var dy=-1; dy<=1; dy++) {
            for (var dx=-1; dx<=1; dx++) {
                if (dx==0 && dy==0 && dz==0) continue;
                const xx = (x+dx+grid_size)%grid_size;
                const yy = (y+dy+grid_size)%grid_size;
                const zz = (z+dz+grid_size)%grid_size;
                if ( grid[index(xx, yy, zz)].states[state] ) count++;
            }
        }
    }

    return count;
}

function applyRule(enabled, count) {
    if (enabled) {
        for (var i=0; i<survive_list.length; i++) {
            if (count == survive_list[i]) return true;
        }
    } else {
        for (var i=0; i<birth_list.length; i++) {
            if (count == birth_list[i]) return true;
        }
    }

    return false;
}

function index(x, y, z) {
    return x + y * grid_size + z * grid_size * grid_size;
}

// The voxel caster will cast rays into a scene that is defined by a function that 
// returns true for all solid cells ([x,y,z]):
function map(p) {
    const x = Math.floor(p[0] + grid_size / 2);
    const y = Math.floor(p[1] + grid_size / 2);
    const z = Math.floor(p[2] + grid_size / 2);
    
    if (x < 0 || x >= grid_size || y < 0 || y >= grid_size || z < 0 || z >= grid_size) {
        return false;
    }
    
    return grid[index(x, y, z)].states[current_state];
}

class Cell {
    constructor(enabled) {
        this.states = [enabled, enabled];
    }
}

////////////////////////////////////////////////////////////////
// Voxel Ray Caster utility code. Created by Reinder Nijhoff 2020
// https://turtletoy.net/turtle/d9ae1fb0bd
////////////////////////////////////////////////////////////////
function VoxelRayCaster(t,s,i=0,e=1.5){const o=(t,s)=>t[0].toFixed(0)+"_"+t[1].toFixed(0)+"_"+t[2].toFixed(0)+s[0].toFixed(0)+"_"+s[1].toFixed(0)+"_"+s[2].toFixed(0),a=t=>[-t[0],-t[1],-t[2]],r=(t,s)=>[t[0]*s,t[1]*s,t[2]*s],c=t=>Math.sqrt(t[0]**2+t[1]**2+t[2]**2),h=t=>r(t,1/c(t)),n=(t,s)=>[t[0]+s[0],t[1]+s[1],t[2]+s[2]],p=(t,s)=>[t[0]-s[0],t[1]-s[1],t[2]-s[2]],l=(t,s)=>[t[1]*s[2]-t[2]*s[1],t[2]*s[0]-t[0]*s[2],t[0]*s[1]-t[1]*s[0]],d=(t,s)=>t.map((i,e)=>s[e]*t[0]+s[e+3]*t[1]+s[e+6]*t[2]),m=(t,s)=>t.map((i,e)=>s[3*e+0]*t[0]+s[3*e+1]*t[1]+s[3*e+2]*t[2]);class u{constructor(t,s,i,e){this.id=o(t,s),this.pos=t,this.normal=s,this.b=[s[1],s[2],s[0]],this.t=l(this.normal,this.b),this.dist=i,this.center=n(this.pos,[.5,.5,.5])}projectVertex(t,s){const i=m(t,s),o=100*e/i[2];return[i[0]*o,i[1]*-o]}projectVertices(t,s){const i=r(this.normal,.5),e=r(this.t,.5),o=r(this.b,.5);this.points=[n(a(e),a(o)),n(e,a(o)),n(e,o),n(a(e),o)].map(e=>this.projectVertex(p(n(n(e,i),this.center),t),s))}calculateEdges(t){const s=this.t,i=this.b,e=this.pos,o=this.normal;this.edges=[a(i),s,i,a(s)].map(s=>!t(n(e,s))||t(n(n(e,s),o)))}}return new class{constructor(t,s,i=0,e=1.5){this.ro=t,this.ta=s,this.w=e,this.ca=this.setupCamera(t,s,i)}setupCamera(t,s,i){const e=h(p(s,t)),o=[Math.sin(i),Math.cos(i),0],a=h(l(e,o)),r=l(a,e);return[...a,...r,...e]}castRay(t,s,i,e){const o=t.map(t=>Math.floor(t)),a=s.map(t=>Math.abs(t)>1e-16?1/t:1e32),r=a.map(t=>Math.sign(t)),c=a.map(t=>Math.abs(t)),h=o.map((s,i)=>(s-t[i]+.5+.5*r[i])*a[i]);for(let t=0;t<e;t++){const t=h[0]<=h[1]&&h[0]<=h[2]?0:h[1]<=h[0]&&h[1]<=h[2]?1:2;if(h[t]+=c[t],o[t]+=r[t],i(o)){const s=[0,0,0];return s[t]=-r[t],[o,s]}}return!1}collectFaces(s,i=[-100,-100],e=[100,100],a=200,r=.25){const n=[];for(let l=i[0];l<=e[0];l+=r)for(let m=i[1];m<=e[1];m+=r){const i=d(h([l/100,-m/100,this.w]),this.ca),e=this.castRay(t,i,s,a);if(e){const t=o(e[0],e[1]);if(!n.find(s=>s.id===t)){const t=new u(e[0],e[1],c(p(e[0],this.ro)));t.projectVertices(this.ro,this.ca),t.calculateEdges(s),n.push(t)}}}return n.sort((t,s)=>t.dist-s.dist)}}(t,s,i,e)}

////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){let t=[];const s=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,h=1e5,i=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),h=Math.min(h,t[1]),i=Math.max(i,t[1])}),this.aabb=[(s+e)/2,(h+i)/2,(e-s)/2,(i-h)/2]}addSegments(...t){t.forEach(t=>this.dp.push(t))}addOutline(){for(let t=0,s=this.cp.length;t<s;t++)this.dp.push(this.cp[t],this.cp[(t+1)%s])}draw(t){for(let s=0,e=this.dp.length;s<e;s+=2)t.jump(this.dp[s]),t.goto(this.dp[s+1])}addHatching(t,e){const h=new s;h.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const i=Math.sin(t)*e,n=Math.cos(t)*e,a=200*Math.sin(t),p=200*Math.cos(t);for(let t=.5;t<150/e;t++)h.dp.push([i*t+p,n*t-a],[i*t-p,n*t+a]),h.dp.push([-i*t+p,-n*t-a],[-i*t-p,-n*t+a]);h.boolean(this,!1),this.dp=[...this.dp,...h.dp]}inside(t){let s=0;for(let e=0,h=this.cp.length;e<h;e++)this.segment_intersect(t,[.13,-1e3],this.cp[e],this.cp[(e+1)%h])&&s++;return 1&s}boolean(t,s=!0){if(s&&Math.abs(this.aabb[0]-t.aabb[0])-(t.aabb[2]+this.aabb[2])>=0&&Math.abs(this.aabb[1]-t.aabb[1])-(t.aabb[3]+this.aabb[3])>=0)return this.dp.length>0;const e=[];for(let h=0,i=this.dp.length;h<i;h+=2){const i=this.dp[h],n=this.dp[h+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const h=this.segment_intersect(i,n,t.cp[s],t.cp[(s+1)%e]);!1!==h&&a.push(h)}if(0===a.length)s===!t.inside(i)&&e.push(i,n);else{a.push(i,n);const h=n[0]-i[0],p=n[1]-i[1];a.sort((t,s)=>(t[0]-i[0])*h+(t[1]-i[1])*p-(s[0]-i[0])*h-(s[1]-i[1])*p);for(let h=0;h<a.length-1;h++)(a[h][0]-a[h+1][0])**2+(a[h][1]-a[h+1][1])**2>=.001&&s===!t.inside([(a[h][0]+a[h+1][0])/2,(a[h][1]+a[h+1][1])/2])&&e.push(a[h],a[h+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,h){const i=(h[1]-e[1])*(s[0]-t[0])-(h[0]-e[0])*(s[1]-t[1]);if(0===i)return!1;const n=((h[0]-e[0])*(t[1]-e[1])-(h[1]-e[1])*(t[0]-e[0]))/i,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/i;return n>=0&&n<=1&&a>=0&&a<=1&&[t[0]+n*(s[0]-t[0]),t[1]+n*(s[1]-t[1])]}};return{list:()=>t,create:()=>new s,draw:(s,e,h=!0)=>{for(let s=0;s<t.length&&e.boolean(t[s]);s++);e.draw(s),h&&t.push(e)}}}

////////////////////////////////////////////////////////////////
// Text utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/1713ddbe99
////////////////////////////////////////////////////////////////
function Text(){const s="br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefggmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfphnmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>cqfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrkshserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlpingkfjfggeidl>`tq^gs<c^q^>`th^e_dadceegfkgnhpjqlqopqorlshserdqcocldjfhigmfoepcpao_l^h^>`tpeohmjjkikfjdhcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wagsg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmhn<ocnknmpnrntluiugtdsbq`o_l^i^f_d`bbad`g`jambodqfrislsorqqrp<pcokompn>asj^bs<j^rs<elol>_tc^cs<c^l^o_p`qbqdpfoglh<chlhoipjqlqopqorlscs>`urcqao_m^i^g_eadccfckdnepgrismsorqprn>_tc^cs<c^j^m_oapcqfqkpnopmrjscs>`sd^ds<d^q^<dhlh<dsqs>`rd^ds<d^q^<dhlh>`urcqao_m^i^g_eadccfckdnepgrismsorqprnrk<mkrk>_uc^cs<q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqporlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkcieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfehdkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_jbjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofpips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkdmepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsksmrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj[i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjcieigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhillnmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs".split(">").map(s=>[s.charCodeAt(0)-106,s.charCodeAt(1)-106,s.substr(2).split("<").map(s=>{const e=[];for(let p=0;p<s.length;p+=2)e.push(s.substr(p,2).split("").map(s=>s.charCodeAt(0)-106));return e})]);return new class{print(e,p,j=1,h=0,r=1){e.radians();let f=[e.x(),e.y()],o=e.h(),i=f;p.split("").map(p=>{const c=p.charCodeAt(0)-32;if(c<0)f=i=this.rotAdd([0,48*j],i,o);else if(c>96)f=this.rotAdd([16*j,0],i,o);else{const p=s[c],i=p[0]*j,d=p[1]*j;p[2].map(s=>{e.up(),s.map(s=>{e.goto(this.rotAdd([(s[0]-s[1]*h)*j-i,s[1]*j],f,o)),e.down()})}),f=this.rotAdd([(d-i)*r,0],f,o)}})}rotAdd(s,e,p){return[Math.cos(p)*s[0]-Math.sin(p)*s[1]+e[0],Math.cos(p)*s[1]+Math.sin(p)*s[0]+e[1]]}}}