// LL 2021

const pad_count = 100; // min=2 max=5000 step=1
const iterations = 10000; /// min=0 max=10000 step=1
const pad_size = 3; // min=0.1 max=10 step=0.1
const clearance = 0; // min=0 max=1 step=0.1
const alignment = 1.5; // min=0.1 max=10 step=0.1
const show_pads = 1; // min=0 max=1 step=1 (No,Yes)
const seed = 0; // min=0 max=100 step=1

const precision = 30; // min=2 max=100 step=1
const thickness = 2; // min=1 max=5 step=1

const hole_size = pad_size / 2;
const trace_size = pad_size / 3;

Canvas.setpenopacity(1);

const turtle = new Turtle();
var rng;
var full_pad_list;
var lone_pad_list, used_pad_list;
var forbidden_trace_list;
var trace_list;

var outliner, outliner2;

console.clear();

var phase;

function walk(i, t) {
    if (i==0) phase = 0;
    
    if (phase==0) {
        rng = new RNG(seed);
        outliner = new Outliner(turtle, precision, thickness);
        outliner2 = new Outliner(turtle, precision, thickness, true);
        init_pads();
        init_traces();
        full_pad_list.forEach(p => p.draw());

        var ii = 0;
        while (ii++ < iterations && trace_list.length < (full_pad_list.length-1)) {
            do_iteration();
        }

        outliner2.build();
        
        phase++;
        return true;
    }
    
    if (phase == 1) {
        if (!outliner2.drawNext()) phase++;
        return true;
    }
    
    if (phase == 2) {
        outliner.build();
        phase++;
        return true;
    }
    
    if (!outliner.drawNext()) return false;

    return true;
}

function do_iteration() {
    var i1 = -1, i2 = -1;
    if (trace_list.length < 1) {
        i1 = (rng.nextFloat() * full_pad_list.length) | 0;
        i2 = findClosest(i1);
    } else if (used_pad_list.length > 0 && lone_pad_list.length > 0) {
        var min_dist = 10000;
        for (var i=0; i<used_pad_list.length; i++) {
            if (full_pad_list[used_pad_list[i]].closest_index >= 0 && lone_pad_list.indexOf(full_pad_list[used_pad_list[i]].closest_index) >= 0) {
                i1 = used_pad_list[i];
                i2 = full_pad_list[used_pad_list[i]].closest_index;
                const dist = distance(i1, i2);
                min_dist = dist;
            } else {
                for (var j=0; j<lone_pad_list.length; j++) {
                    if (trace_key(used_pad_list[i], lone_pad_list[j]) in forbidden_trace_list) continue;
                    const dist = distance(used_pad_list[i], lone_pad_list[j]);
                    if (min_dist > dist) {
                        i1 = used_pad_list[i];
                        i2 = lone_pad_list[j];
                        full_pad_list[i1].closest_index = i2;
                        min_dist = dist;
                    }
                }
            }
        }
    }
    if (i1 >= 0 && i2 >= 0) {
        const new_trace = new Trace(i1, i2);
        new_trace.draw();
        trace_list.push(new_trace);

        i = lone_pad_list.indexOf(i1);
        if (i > -1) { lone_pad_list.splice(i, 1); }
        i = lone_pad_list.indexOf(i2);
        if (i > -1) { lone_pad_list.splice(i, 1); }
        i = used_pad_list.indexOf(i1);
        if (i == -1) { used_pad_list.push(i1); }
        i = used_pad_list.indexOf(i2);
        if (i == -1) { used_pad_list.push(i2); }
    }
}

function findClosest(i1) {
    var i2 = 0;
    var min_dist = distance(i1, i2);
    for (var i=1; i<full_pad_list.length; i++) {
        if (i == i1) continue;
        var dist = distance(i1, i);
        if (min_dist > dist) {
            min_dist = dist;
            i2 = i;
        }
    }
    return i2;
}

function init_traces() {
    trace_list = [];
    lone_pad_list = Array.from({length: full_pad_list.length}, (_,id) => id);
    used_pad_list = [];
}

function addForbiddenTraces(pad_list) {
    for (var i=0; i<pad_list.length; i++) {
        for (var j=i+1; j<pad_list.length; j++) {
            forbidden_trace_list[trace_key(pad_list[i], pad_list[j])] = 1;
        }
    }
}

function trace_key(i1, i2) {
    return Math.min(i1, i2) + Math.max(i1, i2) * pad_count;
}

function newComponent() {
    return [ [ (rng.nextFloat() - 0.5) * 200, (rng.nextFloat() - 0.5) * 200 ] ];
    
    // Proof of concept for a potential future version
    
    const list = [];
    
    const rotate = rng.nextFloat() < 0.5;
    
    const components = [
        // Chance, rows, cols
        [ 1, 1, 1 ],
        [ 0, 2, 1 ],
        [ 0, 2, 2 ],
        [ 0, 2, 6 ]
        ];
    
    var total_chance = 0;
    components.forEach(c => total_chance += c[0]);
    
    var chance = (rng.nextFloat() * total_chance) | 0;
    
    components.forEach(c => {
        const pitch = pad_size * 3;
        if (chance >= 0 && chance < c[0]) {
            var x = (rng.nextFloat() - 0.5) * 200;
            var y = (rng.nextFloat() - 0.5) * 200;
            for (var row=0; row<c[1]; row++) {
                const oy = row * pitch;
                for (var col=0; col<c[2]; col++) {
                    const ox = col * pitch;
                    if (rotate) {
                        list.push([y + oy, x + ox]);
                    } else {
                        list.push([x + ox, y + oy]);
                    }
                }
            }
            chance = -1;
        }
        chance -= c[0];
    });
    
    return list;
}

function init_pads() {
    full_pad_list = [];
    forbidden_trace_list = {};

    var attempts = pad_count * 10;
    while (attempts-- > 0 && full_pad_list.length < pad_count) {
        const newly_added = [];
        const pad_list = newComponent();
        for (var pi=0; pi<pad_list.length && full_pad_list.length < pad_count; pi++) {
            var x = pad_list[pi][0];
            var y = pad_list[pi][1];
            
            x = Math.round(x / (pad_size * alignment * 2)) * pad_size * alignment * 2;
            y = Math.round(y / (pad_size * alignment * 2)) * pad_size * alignment * 2;
            
            if (Math.abs(x) > 100 - pad_size * 1.5) continue;
            if (Math.abs(y) > 100 - pad_size * 1.5) continue;
            
            if (Math.hypot(x, y) > 100) continue;
            
            const new_p = new Pad(x, y);
            
            var collision = false;
            for (var i=0; i<full_pad_list.length && !collision; i++) {
                const dist = distance_p(full_pad_list[i], new_p);
                if (dist < pad_size * (clearance + 1) * 2) collision = true;
            }
            if (collision) continue;
            
            full_pad_list.push(new_p);
            newly_added.push(full_pad_list.length - 1);
        }
        addForbiddenTraces(newly_added);
    }
}

function distance(i1, i2) {
    return distance_p(full_pad_list[i1], full_pad_list[i2]);
}

function distance_p(p1, p2) {
    return Math.hypot(p1.x - p2.x, p1.y - p2.y);
}

class Pad {
    constructor(x, y) {
        this.x = x;
        this.y = y;
        this.closest_index = -1;
    }
    
    draw() {
        const p1 = outliner.addPoint([this.x, this.y], pad_size);
        const p2 = outliner2.addPoint([this.x, this.y], hole_size);
    }
}

function rotX(x, y, a) { return Math.cos(a) * x - Math.sin(a) * y; }
function rotY(x, y, a) { return Math.sin(a) * x + Math.cos(a) * y; }

class Trace {
    constructor(i1, i2) {
        this.i1 = i1;
        this.i2 = i2;
    }
    
    length() {
        return distance(this.i1, this.i2);
    }
    
    split() {
        const list = [];
        const dx = full_pad_list[this.i2].x - full_pad_list[this.i1].x;
        const dy = full_pad_list[this.i2].y - full_pad_list[this.i1].y;
        const EPS = 0.001;
        if ((Math.abs(dx) > EPS) && (Math.abs(dy) > EPS) && (Math.abs(dx-dy) > EPS)) 
        {
            const x1 = full_pad_list[this.i1].x;
            const y1 = full_pad_list[this.i1].y;
            const x3 = full_pad_list[this.i2].x;
            const y3 = full_pad_list[this.i2].y;

            const adx = Math.abs(dx);
            const ady = Math.abs(dy);
            const dir = Math.sign(dx) *  Math.sign(dy);
            const x2 = (adx > ady) ? (x1 + dy * dir) : (x3);            
            const y2 = (ady > adx) ? (y1 + dx * dir) : (y3);            

            if (Math.hypot(x1-x2, y1-y2) > hole_size && Math.hypot(x2-x3, y2-y3) > hole_size) {
                list.push([x1, y1, x2, y2]);
                list.push([x2, y2, x3, y3]);
            }
        }

        if (list.length < 1) {
            list.push([full_pad_list[this.i1].x, full_pad_list[this.i1].y, full_pad_list[this.i2].x, full_pad_list[this.i2].y]);
        }

        return list;
    }
    
    draw() {
        const lines = this.split();

        for (var i=0; i<lines.length; i++) {
            const len = Math.hypot(lines[i][0]-lines[i][2], lines[i][1]-lines[i][3]);
            const EPS = 0.0001;
            if (len < EPS) continue;

            const factor = (show_pads && len > 0.001) ? (len - hole_size) / len : 1;
            const x1 = (i==0) ? (lines[i][2] + (lines[i][0] - lines[i][2]) * factor) : lines[i][0];
            const y1 = (i==0) ? (lines[i][3] + (lines[i][1] - lines[i][3]) * factor) : lines[i][1];
            const x2 = (i==lines.length-1) ? (lines[i][0] + (lines[i][2] - lines[i][0]) * factor) : lines[i][2];
            const y2 = (i==lines.length-1) ? (lines[i][1] + (lines[i][3] - lines[i][1]) * factor) : lines[i][3];
            
            const len2 = Math.hypot(x1 - x2, y1 - y2);
            if (len2 < EPS) continue;
            const a = -Math.PI / 2;
            const rx = rotX((x1 - x2) / len2, (y1 - y2) / len2, a);
            const ry = rotY((x1 - x2) / len2, (y1 - y2) / len2, a);

            const p1 = outliner.addPoint([x1, y1], trace_size);
            const p2 = outliner.addPoint([x2, y2], trace_size);
            outliner.addSegment(p1, p2);
        }
    }
    
    sameAs(e) {
        return (this.i1 == e.i1 && this.i2 == e.i2) || (this.i1 == e.i2 && this.i2 == e.i1);
    }
}

// Random with seed
function RNG(t){return new class{constructor(t){this.m=2147483648,this.a=1103515245,this.c=12345,this.state=t||Math.floor(Math.random()*(this.m-1))}nextFloat(){return this.state=(this.a*this.state+this.c)%this.m,this.state/(this.m-1)}}(t)}

/////////////////////////////////////////////////////////////////
// Outliner utility code v03 - minimized Created by Lionel Lemarie 2021
// https://turtletoy.net/turtle/a206296e80
/////////////////////////////////////////////////////////////////
function Outliner(n=turtle,r=20,o=1,e=!1){const a={},i=[];function f(n){const t=performance.now();n in a?(a[n][0]++,a[n][1]-=t):(a[n]=[1,-t],i.push(n))}function s(n){const t=performance.now();n in a&&(a[n][1]+=t)}f("Total time");const c=[],h=[],u=[],l=1e-4;function g(n){const t=1/r;for(var o=0;o<1;o+=t){x([[n[0]+n[2]*Math.cos(o*Math.PI*2),n[1]+n[2]*Math.sin(o*Math.PI*2)],[n[0]+n[2]*Math.cos((o+t)*Math.PI*2),n[1]+n[2]*Math.sin((o+t)*Math.PI*2)]])}}function d(n,t,r){return Math.cos(r)*n-Math.sin(r)*t}function v(n,t,r){return Math.sin(r)*n+Math.cos(r)*t}function p(n){const t=Math.hypot(n[1][0]-n[0][0],n[1][1]-n[0][1]);if(t<l)return[];var r=n[0][0]+n[0][2]*d(n[0][0]-n[1][0],n[0][1]-n[1][1],-.5*Math.PI)/t,o=n[0][1]+n[0][2]*v(n[0][0]-n[1][0],n[0][1]-n[1][1],-.5*Math.PI)/t,e=n[0][0]+n[0][2]*d(n[0][0]-n[1][0],n[0][1]-n[1][1],.5*Math.PI)/t,a=n[0][1]+n[0][2]*v(n[0][0]-n[1][0],n[0][1]-n[1][1],.5*Math.PI)/t,i=n[1][0]+n[1][2]*d(n[1][0]-n[0][0],n[1][1]-n[0][1],-.5*Math.PI)/t,f=n[1][1]+n[1][2]*v(n[1][0]-n[0][0],n[1][1]-n[0][1],-.5*Math.PI)/t;M([[r,o],[n[1][0]+n[1][2]*d(n[1][0]-n[0][0],n[1][1]-n[0][1],.5*Math.PI)/t,n[1][1]+n[1][2]*v(n[1][0]-n[0][0],n[1][1]-n[0][1],.5*Math.PI)/t]]),M([[e,a],[i,f]])}function M(n){const o=1/r;for(t=0;t<1-l;t+=o){x([[n[0][0]+(n[1][0]-n[0][0])*t,n[0][1]+(n[1][1]-n[0][1])*t],[n[0][0]+(n[1][0]-n[0][0])*(t+o),n[0][1]+(n[1][1]-n[0][1])*(t+o)]])}}const N=1,m={};function L(n){return 1e5*Math.floor(n[1]/N)+Math.floor(n[0]/N)}function P(n){var t=[];const r=L(n);r in m&&t.push(m[r]);var o=!1;if(t.forEach(n=>n.forEach(n=>o|=!_(n))),!o){t=[];const r=2;for(var e=-r;e<=r+.1;e+=1)for(var a=-r;a<=r+.1;a+=1){if(0==a&&0==e)continue;const r=L([n[0]+a*N,n[1]+e*N]);r in m&&t.push(m[r])}}return t}function w(n,t){for(var r=0;r<2;r++){const o=L(n[r]);o in m||(m[o]=[]),m[o].push(t)}}function I(n,t){const r=E(n[0],t[0]),o=E(n[0],t[1]),e=E(n[1],t[0]),a=E(n[1],t[1]);return!((r>l||a>l)&&(o>l||e>l))}function x(n){f("addLine");var t=!0;if(!e){f(`addLine - figure_points ${h.length}`);for(var r=0;r<h.length&&t;r++){const o=E(n[0],h[r])*(1+l),e=E(n[1],h[r])*(1+l);t&=o>h[r][2]**2,t&=e>h[r][2]**2}s(`addLine - figure_points ${h.length}`),f(`addLine - figure_segments ${u.length}`);for(r=0;r<u.length&&t;r++){const o=[0,1].map(n=>h[u[r][n]]);t&=!$(n[0],o)&&!$(n[1],o)}s(`addLine - figure_segments ${u.length}`),function(n){const t=[],r=L(n[0]);r in m&&t.push(m[r]);const o=L(n[1]);return o in m&&t.push(m[o]),t}(n).forEach(r=>{for(var o=0;o<r.length&&t;o++)t&=!I(n,c[r[o]])})}t&&(w(n,c.length),c.push(n)),s("addLine")}function E(n,t){return(n[0]-t[0])*(n[0]-t[0])+(n[1]-t[1])*(n[1]-t[1])}function $(n,t){const r=function(n,t){var r=E(t[0],t[1]);if(r<l)return 0;var o=((n[0]-t[0][0])*(t[1][0]-t[0][0])+(n[1]-t[0][1])*(t[1][1]-t[0][1]))/r;return o=Math.max(0,Math.min(1,o))}(n,t),o=t[0][2]*(1-r)+t[1][2]*r;return function(n,t,r){return E(n,[t[0][0]+r*(t[1][0]-t[0][0]),t[0][1]+r*(t[1][1]-t[0][1])])}(n,t,r)<o*o*(1-l)}const b=[];var O=0;function _(n){for(;b.length<=n;)b.push(!1);return b[n]}function S(){if(f("drawNextLine"),0==c.length)return!1;const t=n.position();var r=1e6,o=-1,h=-1;if(!e&&(f("drawNextLine - bins"),P(t).forEach(n=>{for(var e=0;e<n.length;e++)if(!_(n[e]))for(var a=0;a<2;a++){const i=E(t,c[n[e]][a]);(o<0||i<r)&&(r=i,o=n[e],h=a)}}),s("drawNextLine - bins"),o<0)){f("drawNextLine - all");for(var u=0;u<c.length&&r>1;u++)if(!_(u))for(var l=0;l<2;l++){const n=E(t,c[u][l]);(o<0||n<r)&&(r=n,o=u,h=l)}s("drawNextLine - all")}if(o<0){for(f("drawNextLine - last restort"),o=0,h=0,r=1;_(o);)o++;s("drawNextLine - last restort")}o<c.length&&h<c[o].length&&(r>.01&&n.jump(c[o][h]),n.down(),n.goto(c[o][1-h])),e?c.splice(o,1):function(n){for(;b.length<=n;)b.push(!1);b[n]=!0,O++}(o),s("drawNextLine");const g=c.length-O>0;return g||(s("Total time"),console.log(""),i.forEach(n=>{var t=a[n][1],r=a[n][0],o="ms";t>1e3&&(o="sec",(t/=1e3)>60&&(o="min",t/=60)),console.log(`Outliner: ${n} - calls: ${function(n){return n.toString().replace(/\B(?=(\d{3})+(?!\d))/g,",")}(r)} - total: ${t.toFixed(1)} ${o}`)})),g}function k(){f("buildOutline");for(var n=0;n<h.length;n++)g(h[n]);for(n=0;n<u.length;n++){p([0,1].map(t=>h[u[n][t]]))}!function(){if(e)return;const n=[];for(var t=0;t<c.length;t++)for(var r=0;r<2;r++){var o=!1;P(c[t][r]).forEach(n=>{for(var e=NaN,a=0;a<n.length;a++)if(!I(c[t],c[n[a]]))for(var i=0;i<2;i++){const o=E(c[t][r],c[n[a]][i]);(isNaN(e)||o<e)&&(e=o,c[n[a]][i])}!isNaN(e)&&e<l&&(o=!0)}),o||n.push(c[t][r])}const a=[];for(;n.length>1;){const t=n.shift();for(var i=-1,f=NaN,s=0;s<n.length;s++){const r=E(n[s],t);(i<0||r<f)&&(f=r,i=s)}if(i>=0&&f<10){const r=n[i];n.splice(i,1),a.push([t,r])}}a.forEach(n=>{w(n,c.length),c.push(n)})}(),function(){const n=c.length;for(var t=0;t<thickness;t++)for(var r=0;r<thickness;r++)if(0!=r||0!=t)for(var o=0;o<n;o++){const n=c[o].map(n=>[n[0]-.2*r,n[1]-.2*t,n[2]]);w(n,c.length),c.push(n)}}(),s("buildOutline")}function T(n,t){return h.push([n[0],n[1],t]),h.length-1}function j(n,t){return u.push([n,t]),u.length-1}return{addPoint:(n,t)=>T(n,t),addSegment:(n,t)=>j(n,t),addPoints:n=>n.forEach(n=>T(n[0],n[1])),addSegments:n=>n.forEach(n=>j(n[0],n[1])),build:()=>k(),drawNext:()=>S(),unsortedLines:c}}