// 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 thick = 1; // min=0 max=1 step=1 (No,Yes)
const seed = 0; // min=0 max=100 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;

console.clear();

function walk(i, t) {
    if (i==0) {
        rng = new RNG(seed);
        init_pads();
        init_traces();
        full_pad_list.forEach(p => p.draw());
    } else {
        do_iteration();
    }
    
    const keep_going = i < iterations * t && trace_list.length < (full_pad_list.length-1);
    return keep_going;
}

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) continue;
            if (Math.abs(y) > 100 - pad_size) 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() {
        if (thick) {
            const min_radius = show_pads ? hole_size : 0;
            const max_radius = show_pads ? pad_size : trace_size;
            const rstep = 0.1;
            const astep = Math.PI * 2 / 20;
            turtle.jump(this.x + max_radius, this.y);
            for (var r = max_radius; r >= min_radius; r -= rstep) {
                for (var a = astep; a <= Math.PI * 2; a += astep) {
                    turtle.goto(this.x + r * Math.cos(a), this.y + r * Math.sin(a));
                }
            }
        } else if (show_pads) {
            turtle.jump(this.x, this.y - hole_size);
            turtle.circle(hole_size);
            // turtle.jump(this.x, this.y - pad_size);
            // turtle.circle(pad_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();

        const mint = thick ? -trace_size : 0;
        const maxt = thick ?  trace_size : 0;
        const tstep = trace_size * 0.1;
        
        for (var t=mint; t<=maxt + tstep/2; t+=tstep) {
            turtle.up();
            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);

                turtle.goto(x1 + rx * t, y1 + ry * t); turtle.down();
                turtle.goto(x2 + rx * t, y2 + ry * t);
            }
        }
    }
    
    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)}