// Forked from "KD Tree 🌲" by markknol
// https://turtletoy.net/turtle/182d91df0d

const turtle = new Turtle();
const seed = 1.0; // min=1, max=1000, step=1

const balance1 = 1.0; /// min=0.0, max=1.0, step=0.01  
const balance2 = 0.75; // min=0, max=1, step=0.01  
const balance3 = 0.0; // min=0, max=1, step=0.01  

const sizeX = 185; // min=50, max=200, step=5 
const sizeY = 185; // min=50, max=200, step=5

const minSize = 1.5; // min=1, max=50, step=0.5  
const spacing = 1.5; // min=0, max=10, step=0.5  

const optimizations = 3; // min=0, max=6, step=1
const shuffleBeforeOptimize = 0 // min=0, max=1, step=1 (no,yes)

const startPos = [-sizeX/2, -sizeY/2];

const areas = [
    [0, 0, sizeX, sizeY],
];

let rects = [];

function walk(i) {
    if (i === 0) {
        for (const area of areas.slice()) {
            subdivide(area);
        }
    }
    
    let area = areas.shift();
    const a = [area[0], area[1]];
    const b = [(area[0] + area[2]), (area[1] + area[3])];
    
    let s = spacing*.5;
    add2(a, startPos);
    add2(b, startPos);
    add2(a, [s,s]);
    add2(b, [-s,-s]);
    
    s = spacing * 2/3;
    rects.push([a[0],a[1], b[0]-a[0], b[1]-a[1]]);
    
    if (!areas.length) {
        for(let ii=0;ii<optimizations;ii++) {
            rects = optimizeRects(rects);
        }
        rects.forEach(rect=>drawRect(rect));
    }
    return areas.length;
}


let rseed = seed;
function rand() {
    let r = 1103515245 * (((rseed) >> 1) ^ (rseed++));
    r = 1103515245 * (r ^ (r>>3));
    r = r ^ (r >> 16);
    return r / 1103515245 % 1;	
}

function optimizeRects(rects) {
    if (shuffleBeforeOptimize) shuffle(rects);
    for (let rect1 of rects) {
         for (let rect2 of rects) {
            if (rect1 !== rect2) {
                if (rand() > 0.25 && rect1[1]==rect2[1] && rect1[3]==rect2[3] && rect1[0]+rect1[2]+spacing == rect2[0] ) {
                    // next with same height
                    rects.remove(rect2);
                    rect1[2] += spacing + rect2[2];
                    continue;
                } else if (rand() > 0.25 && rect1[0]==rect2[0] && rect1[2]==rect2[2] && rect1[1]+rect1[3]+spacing == rect2[1] ) {
                    // below with same width
                    rects.remove(rect2);
                    rect1[3] += spacing + rect2[3];
                } else if (rand() > 0.25 && rect1[0]==rect2[0] && rect1[2]==rect2[2] && rect1[1]-spacing == rect2[1]+rect2[3]  ) {
                    // up with same width
                    rects.remove(rect2);
                    rect1[3] += spacing + rect2[3];
                    rect1[1] -= spacing + rect2[3];
                    continue;
                } else if (rand() > 0.25 && rect1[1]==rect2[1] && rect1[3]==rect2[3] && rect1[0]-spacing == rect2[0]+rect2[2]  ) {
                    // up with same width
                    rects.remove(rect2);
                    rect1[2] += spacing + rect2[2];
                    rect1[0] -= spacing + rect2[2];
                    continue;
                }
            }
        }
    }
    return rects;
}

function drawRect(rect) {
    let [x,y,w,h] = rect;
    turtle.jump(x,y)
    turtle.goto(x+w,y)
    turtle.goto(x+w,y+h)
    turtle.goto(x,y+h)
    turtle.goto(x,y)
}

Array.prototype.remove = function(item) {
    var idx;
    while ((idx = this.indexOf(item)) !== -1) {
        this.splice(idx, 1);
    }
    return this;
}

function subdivide(area) {
    const b1 = 1 - balance1;
    let r = 0.5 - (b1 / 2) + rand() * b1 / 2;
    let verticalSplit = rand() > 0.5;
    if (rand() < balance2) verticalSplit = area[2] < area[3]
    const area1 = verticalSplit ?
                    [area[0], area[1], area[2], area[3]*r]
                : 
                    [area[0], area[1], area[2]*r, area[3]];
                    
    const area2 = !verticalSplit ?
                    [area[0] + area[2]*r, area[1], area[2]*(1-r), area[3]]
                :
                    [area[0], area[1] + area[3]*r, area[2], area[3]*(1-r)];

    areas.remove(area);
    areas.push(area1);
    areas.push(area2);
    
    const minWidth = Math.max(minSize + spacing, spacing);
    const minHeight = Math.max(minSize + spacing, spacing)
    if ((area1[2] > minWidth) && (area1[3] > minHeight)) {
        if (rand() > Math.pow(balance3, 3)) subdivide(area1);
    }
    if ((area2[2] > minWidth) && (area2[3] > minHeight)) {
        if (rand() > Math.pow(balance3, 3)) subdivide(area2);
    }
}

function add2(p, v) { p[0] += v[0]; p[1] += v[1]; return p }

function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(rand() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}