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

// LL 2021

const grid_size = 50; // min=1 max=150 step=1
const steps = 15000; // min=0 max=250000 step=100
const random_step = 0; // min=0 max=1 step=0.01
const max_move = 20; // min=0 max=100 step=1
const proximity = 3; // min=0 max=10 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 add_hatching = 1; // min=0 max=1 step=1 (No, Yes)
const draw_cube_edges = 0; // min=0 max=1 step=1 (No, Yes)

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

const turtle = new Turtle();

var steps_t = steps;

var grid = [];

var voxelRayCaster;

function walk(i, t) {
    if (i==0) {
        // Animate GIF by rotating camera
        //const camera_rotation_t = camera_rotation + t;
        const camera_rotation_t = camera_rotation;
        
        // Animate GIF by adding steps
        steps_t = steps * (Math.cos(t**0.5 * Math.PI * 2) * 0.5 + 0.5);

        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, -3.5, .5];
        voxelRayCaster = new VoxelRayCaster(ro, ta, 0, camera_fov);

        reset_random();
        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;
}

let current_pos;

function initGrid() {
    grid = Array.from({length: grid_size*grid_size*grid_size}, (v, i) => new Cell(0));
    
    // for (var t=0; t<steps_t; t++) {
    //     const size = [];
    //     size[0] = Math.floor(random() * grid_size);
    //     size[1] = 1+Math.floor(random() * 5);
    //     size[2] = 1+Math.floor(random() * 5);

    //     const chance = Math.floor(random() * 3);

    //     const x1 = Math.floor(random() * grid_size);
    //     const y1 = Math.floor(random() * grid_size);
    //     const z1 = Math.floor(random() * grid_size);
        
    //     const x2 = x1 + size[chance];
    //     const y2 = y1 + size[(chance+1)%3];
    //     const z2 = z1 + size[(chance+2)%3];

    //     const x_start = Math.max(0, Math.min(x1, x2)), x_end = Math.min(grid_size, Math.max(x1, x2));
    //     const y_start = Math.max(0, Math.min(y1, y2)), y_end = Math.min(grid_size, Math.max(y1, y2));
    //     const z_start = Math.max(0, Math.min(z1, z2)), z_end = Math.min(grid_size, Math.max(z1, z2));

    //     for (var z=z_start; z<z_end; z++) {
    //         for (var y=y_start; y<y_end; y++) {
    //             for (var x=x_start; x<x_end; x++) {
    //                 grid[index(x,y,z)].state = true;
    //             }
    //         }
    //     }
    // }
    
    reset_current_pos();
    const length = 1 + random() * max_move;
    for (var t=0; t<steps_t; t++) {
        var retries = 50;
        while (retries > 0) {
            retries--;
            if (retries < 1) {
                // Stuck, move somewhere else
                reset_current_pos();
                break;
            };
            var l = 0;
            const chance = Math.floor(random() * 6);
            switch (chance) {
                case 0: while (l++ < length && move( 1,  0,  0)) retries = 0; break;
                case 1: while (l++ < length && move(-1,  0,  0)) retries = 0; break;
                case 2: while (l++ < length && move( 0,  1,  0)) retries = 0; break;
                case 3: while (l++ < length && move( 0, -1,  0)) retries = 0; break;
                case 4: while (l++ < length && move( 0,  0,  1)) retries = 0; break;
                case 5: while (l++ < length && move( 0,  0, -1)) retries = 0; break;
            }
        }
    }
}

function reset_current_pos() {
    current_pos = [ Math.round(grid_size * random()), Math.round(grid_size * random()), Math.round(grid_size * random()) ];
}

function move(dx, dy, dz) {
    if (current_pos[0] + dx < 0) return false;
    if (current_pos[0] + dx >= grid_size) return false;
    if (current_pos[1] + dy < 0) return false;
    if (current_pos[1] + dy >= grid_size) return false;
    if (current_pos[2] + dz < 0) return false;
    if (current_pos[2] + dz >= grid_size) return false;
    
    const i = index(current_pos[0] + dx, current_pos[1] + dy, current_pos[2] + dz);
    if (grid[i].state == true) return false;
    
    var neighbor_count = 0;
    for (var dz2 = -proximity; dz2 <= proximity; dz2++) {
        for (var dy2 = -proximity; dy2 <= proximity; dy2++) {
            for (var dx2 = -proximity; dx2 <= proximity; dx2++) {
                if ((Math.abs(dx2) + Math.abs(dy2) + Math.abs(dz2)) != proximity) continue;
                if (current_pos[0] + dx + dx2 < 0) continue;
                if (current_pos[0] + dx + dx2 >= grid_size) continue;
                if (current_pos[1] + dy + dy2 < 0) continue;
                if (current_pos[1] + dy + dy2 >= grid_size) continue;
                if (current_pos[2] + dz + dz2 < 0) continue;
                if (current_pos[2] + dz + dz2 >= grid_size) continue;
                if (grid[index(current_pos[0] + dx + dx2, current_pos[1] + dy + dy2, current_pos[2] + dz + dz2)].state == true) {
                    neighbor_count++;
                }
            }
        }
    }
    if (neighbor_count > 1) return false;
    
    current_pos[0] += dx;
    current_pos[1] += dy;
    current_pos[2] += dz;
    grid[i].state = true;
    
    return true;
}

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

class Cell {
    constructor(state) {
        this.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)}}}


var mseed = Math.random();
function mrandom() { 
    if (random_step == 0) return Math.random();
    mseed = ((mseed + 1 + random_step)**1) % 1.0; 
    return mseed;
}
//function mrandom() { return Math.random(); }

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