const allowGaps = 0;//min=0 max=1 step=1 (No, Yes)
const size = 20;//min=2 max=30 step=.5
const padding = 30;//min=-20 max=50 step=5
const hatching = 1;//min=0 max=1 step=1 (No, Yes)
const plotPenThickness = .15 //min=.01 max=2 step=.01

// Define the turtle
const turtle = new Turtle();
const polygons = new Polygons();

// Define the size of the tiles
const GOLDEN_RATIO = (1 + 5**.5) / 2;

// Set the pen opacity of the canvas
Canvas.setpenopacity(1);

const KITE_LONG_LEFT = 0;
const KITE_LONG_RIGHT = 1;
const KITE_SHORT_LEFT = 2;
const KITE_SHORT_RIGHT = 3;
const ARROW_LONG_LEFT = 4;
const ARROW_LONG_RIGHT = 5;
const ARROW_SHORT_LEFT = 6;
const ARROW_SHORT_RIGHT = 7;

const EDGEMAP = [
    [KITE_LONG_RIGHT, ARROW_LONG_LEFT],
    [KITE_LONG_LEFT, ARROW_LONG_RIGHT],
    [KITE_SHORT_RIGHT, ARROW_SHORT_LEFT],
    [KITE_SHORT_LEFT, ARROW_SHORT_RIGHT],
    [ARROW_LONG_RIGHT, KITE_LONG_LEFT],
    [ARROW_LONG_LEFT, KITE_LONG_RIGHT],
    [KITE_SHORT_LEFT],
    [KITE_SHORT_RIGHT]
];
const TYPEPOLYGONS = {'kite': [.9, 6 * plotPenThickness], 'arrow': [1.1, 4 * plotPenThickness]};
const TILECANDIDATES = Array.from({length: EDGEMAP.length}).map((v, i) => i < 6? ['arrow', 'kite']: ['kite']);

const container = 100 - padding;

const tileBlueprints = getTiles(size);

const edgesToProcess = [];
const edgesAll = [];
const polygonsAll = [];

const checkpoints = [];
let revert = false;

const startRotation = (Math.random()-.5)*2*Math.PI;
const startType = Object.keys(TYPEPOLYGONS).sort((a,b) => Math.random() -.5).pop();
let [tile, rott] = getTileEdges(tileBlueprints[startType], (Math.random() * 4) | 0, [Math.random() * size,Math.random() * size], startRotation);
addTile(turtle, tile, [startType, startRotation-rott]);

function walk(run) {
    if(edgesToProcess.length == 0) {
        if(hatching === 1) {
            [polygonsAll.shift()].forEach(pts => {
                const p = polygons.create();
                p.addPoints(...pts[1]);
                p.addHatching(pts[0][1] - Math.PI*TYPEPOLYGONS[pts[0][0]][0], TYPEPOLYGONS[pts[0][0]][1]);
                polygons.draw(turtle, p);
            });
        }
        if(hatching === 0 || polygonsAll.length == 0) {
            edgesAll.forEach(edge => drawPath(turtle, [edge[0], edge[1]]));
        }
        return polygonsAll.length > 0 && hatching === 1;
    }

    let tries = null;
    if(allowGaps == 0 && revert) {
        const cp = checkpoints.pop();
        tries = cp[0];
        edgesToProcess.splice(0, edgesToProcess.length, ...cp[1]);
        edgesAll.splice(0, edgesAll.length, ...cp[2]);
        polygonsAll.splice(0, polygonsAll.length, ...cp[3]);
        revert = false;
    }

    let processEdge = edgesToProcess.shift();

    if(!edgeContained([-container, -container], [container, container], processEdge)) {
        return true;
    }

    if(tries === null) {
        tries = TILECANDIDATES[processEdge[2]].map(a=>a).sort((a,b) => Math.random() < .5? 1: -1);
    }

    let placedSomething = false;
    for(let tryIndex = 0; tryIndex < tries.length; tryIndex++) {
        const _try = tries[tryIndex];

        const linkedEdge = tileBlueprints[_try].map((v, i) => [i, v[2]]).filter(v => EDGEMAP[processEdge[2]].includes(v[1])).map(v => v[0]).pop();
        if(linkedEdge == undefined) {
            continue;
        }
        const direction = sub2(processEdge[1], processEdge[0]);
        const rotation = Math.atan2(...direction);
        
        const [tile, rott] = getTileEdges(tileBlueprints[_try], linkedEdge, processEdge[1], rotation+Math.PI);
        
        const proximityLimits = tile.reduce((p, edge) => [
            Math.min(p[0], edge[0][0] - size),
            Math.max(p[1], edge[0][0] + size),
            Math.min(p[0], edge[0][1] - size),
            Math.max(p[1], edge[0][1] + size),
        ], [2000, -2000, 2000, -2000]);
        const nearEdges = edgesAll.filter(edge => 
            ((
                proximityLimits[0] <= edge[0][0] && edge[0][0] <= proximityLimits[1] &&
                proximityLimits[2] <= edge[0][1] && edge[0][1] <= proximityLimits[3]
            ) ||
            (
                proximityLimits[0] <= edge[1][0] && edge[1][0] <= proximityLimits[1] &&
                proximityLimits[2] <= edge[1][1] && edge[1][1] <= proximityLimits[3]
            )) && edge != processEdge
        );
        
        let cancelBecauseOverlappingEdgesNotMatching = false;
        for(let i = 1; i < tile.length; i++) { //for all test edges which are all but the connecting first edge
            const myDir = Math.atan2(...sub2(tile[i][1], tile[i][0])); //get the direction

            //then for all near edges, filter the edges that end near the location the test edge starts
            const matchedEdges = nearEdges.filter(e => nearSq2(e[1], tile[i][0], .01)).filter(e => {
                //and only get the edges that have approximately the same direction
                return approx1(Math.atan2(...sub2(e[0], e[1])), myDir);
            });
            //also for all near edges, filter the edges that start near the location the test edge ends
            const otherMatchedEdges = nearEdges.filter(e => nearSq2(e[0], tile[i][1], .01)).filter(e => {
                //and only get the edges that have approximately the same direction
                return approx1(Math.atan2(...sub2(e[0], e[1])), myDir);
            })
            
            if(matchedEdges.length === 0 && otherMatchedEdges.length === 0) { // if none are found we can continue test the next one
                continue;
            }
            if(matchedEdges.length > 0) {
                if(!EDGEMAP[tile[i][2]].includes(matchedEdges[0][2])) { // otherwise, if the type of the matching edge does not match the test edge type
                    cancelBecauseOverlappingEdgesNotMatching = true; // (ie a short overlaps a long) cancel this candidate
                    break; //and stop testing
                }
            } else {
                if(!EDGEMAP[tile[i][2]].includes(otherMatchedEdges[0][2])) { // otherwise, if the type of the matching edge does not match the test edge type
                    cancelBecauseOverlappingEdgesNotMatching = true; // (ie a short overlaps a long) cancel this candidate
                    break; //and stop testing
                }
            }
        }
        
        const shouldCancelPlacementBecauseIntersectionsWithOtherEdges = tile.some((edge, i) => {
            if (i === 0) { return false; }

            return nearEdges.some(e => !nearSq2(e[0], edge[0], .01) && !nearSq2(e[0], edge[1], .01)
                                && 
                                !nearSq2(e[1], edge[0], .01) && !nearSq2(e[1], edge[1], .01) 
                                && 
                                segment_intersect2(edge[0], edge[1], e[0], e[1]) !== false
            );

        });

        if(cancelBecauseOverlappingEdgesNotMatching || shouldCancelPlacementBecauseIntersectionsWithOtherEdges) {
            continue;
        }

        if(tryIndex < tries.length - 1) {
            //make checkpoint for later revert
            checkpoints.push([
                tries.filter((v, i) => i > tryIndex),
                cloneEdges(edgesToProcess),
                cloneEdges(edgesAll),
                polygonsAll.map(pts => pts.map(pt => [...pt]))
            ]);
            checkpoints[checkpoints.length - 1][1].push(cloneEdge(processEdge));
            //end make checkpoint
        }

        addTile(turtle, tile, [_try, rotation-rott]);
        placedSomething = true;
        break;
    }
    
    if(!placedSomething) {
        revert = true;
    }

    return true;
}

function cloneEdge(edge) {
    return [[...edge[0]], [...edge[1]], edge[2]];
}

function cloneEdges(edges) {
    return edges.map(e => cloneEdge(e));
}

function addTile(turtle, tile, typeRotation) {
    polygonsAll.push([typeRotation, tile.map(edge => edge[0])]);
    const add = cloneEdges(tile);
    if(edgesAll.length > 0) {
        add.shift();

        for(let i = 0; i < edgesAll.length; i++) {
            for(let j = 0; j < add.length; j++) {
                if(
                    //same start and same end (== same edge in same direction) will never happen
                    //(nearSq2(edgesAll[i][0], add[j][0]) && nearSq2(edgesAll[i][1], add[j][1])) ||
                    (nearSq2(add[j][1], edgesAll[i][0]) && nearSq2(add[j][0], edgesAll[i][1]))
                ) {
                    for(let k = 0; k < edgesToProcess.length; k++) {
                        if(
                            //same start and same end (== same edge in same direction) will never happen
                            //(nearSq2(edgesAll[i][0], add[j][0]) && nearSq2(edgesAll[i][1], add[j][1])) ||
                            (nearSq2(add[j][1], edgesToProcess[k][0]) && nearSq2(add[j][0], edgesToProcess[k][1]))
                        ) {
                            edgesToProcess.splice(k, 1);
                            break;
                        }
                    }
                    add.splice(j, 1);
                    break;
                }
            }
        }
/*// THIS IS THE CODE TO SUBSTITUTE DE LOOP ABOVE (over edgesAll) WHEN REVERTING IS IMPLEMENTED
        for(let i = 0; i < edgesToProcess.length; i++) {
            for(let j = 0; j < add.length; j++) {
                if(
                    //same start and same end (== same edge in same direction) will never happen
                    //(nearSq2(edgesAll[i][0], add[j][0]) && nearSq2(edgesAll[i][1], add[j][1])) ||
                    (nearSq2(add[j][1], edgesToProcess[i][0]) && nearSq2(add[j][0], edgesToProcess[i][1]))
                ) {
                    
                    add.splice(j, 1);
                    edgesToProcess.splice(i, 1);
                    i--;
                    //j--;
                    break;
                }
            }
        }
/// THIS IS THE CODE TO SUBSTITUTE DE LOOP ABOVE (over edgesAll) WHEN REVERTING IS IMPLEMENTED */
    }

    add.forEach(edge => {
        edgesToProcess.push(edge);
        edgesAll.push(edge);
    });
}

function edgeContained(leftTop, bottomRight, edge) {
    return (leftTop[0] <= edge[0][0] && edge[0][0] <= bottomRight[0] && leftTop[1] <= edge[0][1] && edge[0][1] <= bottomRight[1])
    ||
    (leftTop[0] <= edge[1][0] && edge[1][0] <= bottomRight[0] && leftTop[1] <= edge[1][1] && edge[1][1] <= bottomRight[1]);
}

function getTileEdges(tilePathDefinition, side, location, rotation) {
    const startRotation = tilePathDefinition.reduce((p, v, i) => p + (i < side? v[1]: 0), 0);
    return [
        tilePathDefinition.map((v, i, a) => a[(i+side)%a.length])
            .reduce((p, v, i, a) => {
                const cp = p.length == 0? location: p[p.length-1][1];
                const result = [cp, add2(cp, trans2(rot2(rotation - Math.PI/2), v[0])), v[2]];
                rotation += v[1];
                return p.concat([result]);
        }, []),
        startRotation
    ];
}

// Helper function to draw a kite tile
function getTiles(size) {
    const short = [size/GOLDEN_RATIO, 0];
    const long = [size, 0];
    const pi2 = Math.PI * 2;
    return {
        kite: [
            [short, 1.4*Math.PI, KITE_SHORT_LEFT],  //-108 = 1.4*2*pi
            [long,  1.4*Math.PI, KITE_LONG_LEFT],     //-108 = 1.4*2*pi
            [long,  1.4*Math.PI, KITE_LONG_RIGHT],    //-108 = 1.4*2*pi
            [short, 1.8*Math.PI, KITE_SHORT_RIGHT],   //-36 = 1.8*2*pi
        ],
        arrow: [
            [short, 1.2*Math.PI, ARROW_SHORT_LEFT],   //-144 = -0.4*2*pi
            [long,  1.4*Math.PI, ARROW_LONG_LEFT],    //-108 = 1.4*2*pi
            [long,  1.2*Math.PI, ARROW_LONG_RIGHT],     //-144 = -0.4*2*pi
            [short, 0.2*Math.PI, ARROW_SHORT_RIGHT],   //-324 = -0.9*2*pi
        ]
    }
}

function approx1(a,b,delta=0.0001) { return -delta < a-b && a-b < delta }

////////////////////////////////////////////////////////////////
// 2D Vector Math utility code - Created by several Turtletoy users
////////////////////////////////////////////////////////////////
function norm2(a) { return scale2(a, 1/len2(a)); }
function add2(a, b) { return [a[0]+b[0], a[1]+b[1]]; }
function sub2(a, b) { return [a[0]-b[0], a[1]-b[1]]; }
function mul2(a, b) { return [a[0]*b[0], a[1]*b[1]]; }
function scale2(a, s) { return mul2(a, [s,s]); }
function lerp2(a,b,t) { return [a[0]*(1-t) + b[0]*t, a[1]*(1-t) + b[1]*t]; }
function lenSq2(a) { return a[0]**2+a[1]**2; }
function len2(a) { return Math.sqrt(lenSq2(a)); }
function rot2(a) { return [Math.cos(a), -Math.sin(a), Math.sin(a), Math.cos(a)]; }
function trans2(m, a) { return [m[0]*a[0]+m[2]*a[1], m[1]*a[0]+m[3]*a[1]]; } //Matrix(2x1) x Matrix(2x2)
function dist2(a,b) { return Math.hypot(...sub2(a,b)); }
function dot2(a,b) { return a[0]*b[0]+a[1]*b[1]; }
function cross2(a,b) { return a[0]*b[1] - a[1]*b[0]; }
function multiply2(a2x2, a) { return [(a[0]*a2x2[0])+(a[1]*a2x2[1]),(a[0]*a2x2[2])+(a[1]*a2x2[3])]; } //Matrix(2x2) x Matrix(1x2)
function intersect_info2(as, ad, bs, bd) {
    const d = [bs[0] - as[0], bs[1] - as[1]];
    const det = bd[0] * ad[1] - bd[1] * ad[0];
    if(det === 0) return false;
    const res = [(d[1] * bd[0] - d[0] * bd[1]) / det, (d[1] * ad[0] - d[0] * ad[1]) / det];
    return [...res, add2(as, scale2(ad, res[0]))];
}
function intersect_ray2(a, b, c, d) {
    const i = intersect_info2(a, b, c, d);
    return i === false? i: i[2];
}
function segment_intersect2(a,b,c,d, inclusive = true) {
    const i = intersect_info2(a, sub2(b, a), c, sub2(d, c));
    if(i === false) return false;
    const t = inclusive? 0<=i[0]&&i[0]<=1&&0<=i[1]&&i[1]<=1: 0<i[0]&&i[0]<1&&0<i[1]&&i[1]<1;
    return t?i[2]:false;
}
function approx2(a,b,delta=0.0001) { return len2(sub2(a,b)) < delta }
function eq2(a,b) { return a[0]==b[0]&&a[1]==b[1]; }
function clamp2(a, tl, br) { return [Math.max(Math.min(br[0], a[0]), tl[0]), Math.max(Math.min(br[1], a[1]), tl[1])]; }
function nearSq2(test, near, delta = .0001) {
    return near[0] - delta < test[0] && test[0] < near[0] + delta &&
           near[1] - delta < test[1] && test[1] < near[1] + delta;
}

////////////////////////////////////////////////////////////////
// Start of some path utility code - Created by Jurgen Westerhof 2023
////////////////////////////////////////////////////////////////
function circlePoints(radius, extend = 2 * Math.PI, clockWiseStart = 0, steps = null, includeLast = false) { return [steps == null? (radius*extend+1)|0: steps].map(steps => Array.from({length: steps}).map((v, i, a) => [radius * Math.cos(clockWiseStart + extend*i/(a.length-(includeLast?1:0))), radius * Math.sin(clockWiseStart + extend*i/(a.length-(includeLast?1:0)))])).pop(); }
function pts2Edges(pts) { return pts.map((v, i, a) => [v, a[(i+1)%a.length]]); }
function drawPath(turtle, pts) { return pts.forEach((pt, i) => turtle[i == 0? 'jump':'goto'](pt)); }
function drawTour(turtle, pts) { return drawPath(turtle, pts.concat([pts[0]])); }
function drawPoint(turtle, pt) { return drawTour(turtle, circlePoints(.5).map(p => add2(p, pt))); }
function isInPolygon(edges, pt) { return edges.map(edge => intersect_info2(edge[0], sub2(edge[1], edge[0]), pt, [0, 300])).filter(ii => ii !== false && 0 <= ii[0] && ii[0] <= 1 && 0 < ii[1]).length % 2 == 1; }

////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// (Polygon binning by Lionel Lemarie 2021)
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){const t=[],s=25,e=Array.from({length:s**2},t=>[]),n=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,n=1e5,h=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),n=Math.min(n,t[1]),h=Math.max(h,t[1])}),this.aabb=[s,n,e,h]}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,s){const e=new n;e.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const h=Math.sin(t)*s,o=Math.cos(t)*s,a=200*Math.sin(t),i=200*Math.cos(t);for(let t=.5;t<150/s;t++)e.dp.push([h*t+i,o*t-a],[h*t-i,o*t+a]),e.dp.push([-h*t+i,-o*t-a],[-h*t-i,-o*t+a]);e.boolean(this,!1),this.dp=[...this.dp,...e.dp]}inside(t){let s=0;for(let e=0,n=this.cp.length;e<n;e++)this.segment_intersect(t,[.1,-1e3],this.cp[e],this.cp[(e+1)%n])&&s++;return 1&s}boolean(t,s=!0){const e=[];for(let n=0,h=this.dp.length;n<h;n+=2){const h=this.dp[n],o=this.dp[n+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const n=this.segment_intersect(h,o,t.cp[s],t.cp[(s+1)%e]);!1!==n&&a.push(n)}if(0===a.length)s===!t.inside(h)&&e.push(h,o);else{a.push(h,o);const n=o[0]-h[0],i=o[1]-h[1];a.sort((t,s)=>(t[0]-h[0])*n+(t[1]-h[1])*i-(s[0]-h[0])*n-(s[1]-h[1])*i);for(let n=0;n<a.length-1;n++)(a[n][0]-a[n+1][0])**2+(a[n][1]-a[n+1][1])**2>=.001&&s===!t.inside([(a[n][0]+a[n+1][0])/2,(a[n][1]+a[n+1][1])/2])&&e.push(a[n],a[n+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,n){const h=(n[1]-e[1])*(s[0]-t[0])-(n[0]-e[0])*(s[1]-t[1]);if(0===h)return!1;const o=((n[0]-e[0])*(t[1]-e[1])-(n[1]-e[1])*(t[0]-e[0]))/h,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/h;return o>=0&&o<=1&&a>=0&&a<=1&&[t[0]+o*(s[0]-t[0]),t[1]+o*(s[1]-t[1])]}};return{list:()=>t,create:()=>new n,draw:(n,h,o=!0)=>{reducedPolygonList=function(n){const h={},o=200/s;for(var a=0;a<s;a++){const c=a*o-100,r=[0,c,200,c+o];if(!(n[3]<r[1]||n[1]>r[3]))for(var i=0;i<s;i++){const c=i*o-100;r[0]=c,r[2]=c+o,n[0]>r[2]||n[2]<r[0]||e[i+a*s].forEach(s=>{const e=t[s];n[3]<e.aabb[1]||n[1]>e.aabb[3]||n[0]>e.aabb[2]||n[2]<e.aabb[0]||(h[s]=1)})}}return Array.from(Object.keys(h),s=>t[s])}(h.aabb);for(let t=0;t<reducedPolygonList.length&&h.boolean(reducedPolygonList[t]);t++);h.draw(n),o&&function(n){t.push(n);const h=t.length-1,o=200/s;e.forEach((t,e)=>{const a=e%s*o-100,i=(e/s|0)*o-100,c=[a,i,a+o,i+o];c[3]<n.aabb[1]||c[1]>n.aabb[3]||c[0]>n.aabb[2]||c[2]<n.aabb[0]||t.push(h)})}(h)}}}