// Forked from "Cellular Automata > Voxel Caster" by llemarie
// https://turtletoy.net/turtle/3b6550c0d8

// LL 2021

// 3D Cellular Automata
// Rules: https://softologyblog.wordpress.com/2019/12/28/3d-cellular-automata-3/

// Forked from "Cellular Automata > Voxel Caster" by llemarie
// https://turtletoy.net/turtle/3b6550c0d8

// "Ruud" rule from https://twitter.com/ruuddotorg/status/1405975813703409664

// Declare your own custom rule here in the format: survive/birth/states/neighborhood
const custom_rule = "/1-8/2/M";

const grid_size = 50; // min=1 max=150 step=1
const iterations = 23; // min=0 max=100 step=1
const camera_fov = 3; /// min=0.5 max=5 step=0.05
const camera_distance = 2.4; // min=0.5 max=10 step=0.1
const camera_rotation = 0.125; // min=0 max=1 step=0.01
const camera_height = 0.5; // min=0 max=3 step=0.01
const rule = 4; // min=0 max=4 step=1 (Custom,Lionel 1,Hollow,Clouds 1,Ruud)
const start_cells = 2; // min=0 max=2 step=1 (Full cube, Half cube,Single cell)
const random_threshold = 0.5; // min=0 max=0.99 step=0.01
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)
const cut_out = 0.7; // min=0 max=1 step=0.05

// Lower is more precise but slower - Great quality but very slow: 0.1 - Fast preview: 1.0 - Good compromise: 0.3
const resolution = 0.5; /// min=0.2 max=2 step=0.1

var rule_str_list = [ custom_rule, "/1-2,6-10/5/M", "/1-3/2/M", "13-26/13-14,17-19/2/M", "/1-8/2/M" ];
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 max_state = 1;
var neighborhood_mode = "M";

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;
        //const const camera_rotation_t = camera_rotation;

        const radius = grid_size * camera_distance;
        const xx = radius * Math.cos(camera_rotation_t * Math.PI * 2);
        const yy = radius * camera_height;
        const zz = radius * -Math.sin(camera_rotation_t * Math.PI * 2);
        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
        //const tt = Math.cos(t * Math.PI * 2) * 0.5 + 0.5;
        //iterations_t = Math.floor(iterations * tt);

        reset_random();
        parseRule();
        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, 8 * grid_size, resolution);
    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() {
    grid = Array.from({length: grid_size*grid_size*grid_size}, (v, i) => new Cell(0));
    
    if (start_cells == 0) { 
        for (var z=0; z<grid_size; z++) {
            for (var y=0; y<grid_size; y++) {
                for (var x=0; x<grid_size; x++) {
                    grid[index(x,y,z)].states[current_state] = random() > random_threshold ? 1 : 0;
                }
            }
        }
    } else if (start_cells == 1) { 
        for (var z=0; z<grid_size; z++) {
            for (var y=0; y<grid_size; y++) {
                for (var x=0; x<grid_size; x++) {
                    if ((Math.abs(x - grid_size / 2) < grid_size / 4) && (Math.abs(y - grid_size / 2) < grid_size / 4) && (Math.abs(z - grid_size / 2) < grid_size / 4)) {
                        grid[index(x,y,z)].states[current_state] = random() > random_threshold ? 1 : 0;
                    }
                }
            }
        }
    } else if (start_cells == 2) { 
        const center = Math.round(grid_size / 2);
        grid[index(center,center,center)].states[current_state] = 1;
    }

    for (var i=0; i<iterations_t; i++) {
        current_state = (current_state+1) % 2;
        evolveGrid();
    }
    
    if (cut_out > 0) {
        for (var z=0; z<grid_size; z++) {
            for (var y=0; y<grid_size; y++) {
                for (var x=0; x<grid_size; x++) {
                    if ((grid_size-1-x) < grid_size*cut_out && (grid_size-1-y) < grid_size*cut_out && z < grid_size*cut_out) {
                        grid[index(x,y,z)].states[current_state] = 0;
                    }
                }
            }
        }
    }
}

function parseRule() {
    survive_list = [];
    birth_list = [];
    max_state = 1;
    neighborhood_mode = "M";

    const phases = rule_str.split("/");
    if (phases.length != 4) return;

    survive_list = getList(phases[0]);
    birth_list = getList(phases[1]);
    max_state = parseInt(phases[2]) - 1;
    neighborhood_mode = phases[3];

    turtle.jump(-90,93);
    text.print(turtle, `Rule: ${rule_str} - Iterations: ${iterations_t} - Cut out: ${cut_out}`, .1);
    
    //console.log(`Rule: Survive: ${survive_list} - Birth: ${birth_list} - Max state: ${max_state} - Neighborhood: ${neighborhood_mode}`)
}

function getList(str) {
    const list = [];
    const ranges = str.split(",");
    ranges.forEach(r => getRange(r).forEach(n => list.push(n)));
    return list;
}

function getRange(str) {
    if (str.length < 1) return [];
    const sides = str.split("-");
    if (sides.length == 2) {
        const list = [];
        const min = parseInt(sides[0]);
        const max = parseInt(sides[1]);
        for (var i=min; i<=max; i++) list.push(i);
        return list;
    }
    return [ parseInt(sides[0]) ];
}

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;

    if (neighborhood_mode == "M") { // Moore neighborhood
        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] > 0) count++;
                }
            }
        }
    } else if (neighborhood_mode == "N") { // von Neumann neighborhood
        if (grid[index((x-1+grid_size)%grid_size, y, z)].states[state] > 0) count++;
        if (grid[index((x+1+grid_size)%grid_size, y, z)].states[state] > 0) count++;
        if (grid[index(x, (y-1+grid_size)%grid_size, z)].states[state] > 0) count++;
        if (grid[index(x, (y+1+grid_size)%grid_size, z)].states[state] > 0) count++;
        if (grid[index(x, y, (z-1+grid_size)%grid_size)].states[state] > 0) count++;
        if (grid[index(x, y, (z+1+grid_size)%grid_size)].states[state] > 0) count++;
    }

    return count;
}

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

    if (state > 0 && state + 1 <= max_state) return state + 1;
    
    return 0;
}

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] > 0;
}

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

////////////////////////////////////////////////////////////////
// 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]]}}}

// Cached random for animations
function random() { while (rand_index >= rand_cache.length) rand_cache.push(Math.random()); return rand_cache[rand_index++]; }
function reset_random() { rand_index = 0; }
const rand_cache = [];
var rand_index = 0;