// LL 2021

const max_iterations = 25   // min = 1, max = 100, step = 1
const m_scale =  65         // min = 10, max = 1000, step = 0.01
const offset_x = 0.7        // min = -10, max = 10, step = 0.001
const offset_y = 0          // min = -10, max = 10, step = 0.001
const min_factor = 0.1      // min = 0, max = 1, step = 0.01
const octree_depth = 9      // min = 1, max = 12, step = 1
const draw_style = 0        // min = 0, max = 1, step = 1, (boxes, hatching)
const hatching_density = 20 // min = 1, max = 100, step = 1


const canvas_size = 190

Canvas.setpenopacity(1)
const turtle = new Turtle()

function dot(x, y, r)
{
    turtle.penup()
    turtle.goto(x + r, y + r)
    turtle.pendown()
    turtle.goto(x + r, y - r)
    turtle.goto(x - r, y - r)
    turtle.goto(x - r, y + r)
    turtle.goto(x + r, y + r)
}

function mandelbrot(x, y)
{
    var cr = x
    var ci = y
    var zr = 0
    var zi = 0
    var iterations = 0
    
    while (zr * zr + zi * zi < 4)
    {
        const new_zr = zr * zr - zi * zi + cr
        const new_zi = 2 * zr * zi + ci
        zr = new_zr
        zi = new_zi
        iterations += 1
        if (iterations >= max_iterations) break;
    }
    
    return iterations
}

// The walk function will be called until it returns false.
function walk(i)
{
    if (i==0 && min_factor==1)
    {
        turtle.penup()
        turtle.goto(canvas_size/2, canvas_size/2)
        turtle.pendown()
        turtle.goto(-canvas_size/2, canvas_size/2)
        turtle.goto(-canvas_size/2, -canvas_size/2)
    }
    
    octree.draw(i)
    
    return (i+1) < octree.total_leaves
}

function Leaf(depth, x, y, size)
{
    this.leaves = []
    this.x = x
    this.y = y
    this.size = size
    this.value = 0
    this.id = -1
    this.min_range = -1
    this.max_range = -1

    var size2 = size / 2

    if (depth > 0)
    {
        for (var yy = 0; yy <2; yy++)
        {
            for (var xx = 0; xx <2; xx++)
            {
                this.leaves.push(new Leaf(depth-1, x + xx * size2, y + yy * size2, size2))
            }
        }
    }
    else
    {
        var center_x = this.x + this.size / 2
        var center_y = this.y + this.size / 2

        const m_x = (center_x) / m_scale - offset_x
        const m_y = (center_y) / m_scale - offset_y

        this.value = mandelbrot(m_x, m_y) / max_iterations
    }
}

function Point(x, y)
{
    this.x = x
    this.y = y
}

function Line(p0, p1)
{
    this.points = []
    this.points.push(p0)
    this.points.push(p1)
}

Line.prototype.draw = function()
{
    turtle.penup()
    turtle.goto(this.points[0].x, this.points[0].y)
    turtle.pendown()
    turtle.goto(this.points[1].x, this.points[1].y)
}

function Box(p0, p1, p2, p3)
{
    this.points = []
    this.points.push(p0)
    this.points.push(p1)
    this.points.push(p2)
    this.points.push(p3)
}

function LineLineIntersection(line1, line2)
{
    var s1x = line1.points[1].x - line1.points[0].x
    var s1y = line1.points[1].y - line1.points[0].y
    var s2x = line2.points[1].x - line2.points[0].x
    var s2y = line2.points[1].y - line2.points[0].y

    var s = (-s1y * (line1.points[0].x - line2.points[0].x) + s1x * (line1.points[0].y - line2.points[0].y)) / (-s2x * s1y + s1x * s2y)
    var t = ( s2x * (line1.points[0].y - line2.points[0].y) - s2y * (line1.points[0].x - line2.points[0].x)) / (-s2x * s1y + s1x * s2y)

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        var x = line1.points[0].x + (t * s1x);
        var y = line1.points[0].y + (t * s1y);
        return new Point(x, y);
    }

    return null
}

function LineBoxIntersection(line, box)
{
    var points = []
    var point
    for (var i=0; i<4 && points.length < 2; i++)
    {
        var line2 = new Line(box.points[i], box.points[(i+1)%4])
        point = LineLineIntersection(line, line2)
        if (point != null) points.push(point)
    }

    if (points.length == 2) return new Line(points[0], points[1])

    return null
}

Leaf.prototype.draw = function(target)
{
    if (target < this.min_range || target > this.max_range) return true
    
    if (this.leaves.length == 0 && this.value > 0 && this.id == target)
    {
        switch (draw_style)
        {
            case 0: // boxes
                var center_x = this.x + this.size / 2
                var center_y = this.y + this.size / 2
                var size = this.size / 2  * (this.value * (1 - min_factor) + min_factor)
                
                turtle.penup()
                turtle.goto(center_x - size, center_y - size)
                turtle.pendown()
                turtle.goto(center_x + size, center_y - size)
                turtle.goto(center_x + size, center_y + size)
                if (min_factor < 1)
                {
                    turtle.goto(center_x - size, center_y + size)
                    turtle.goto(center_x - size, center_y - size)
                }
                break
            case 1: // hatching
                var p0 = new Point(this.x, this.y)
                var p1 = new Point(this.x + this.size, this.y)
                var p2 = new Point(this.x + this.size, this.y + this.size)
                var p3 = new Point(this.x, this.y + this.size)
                var box = new Box(p0, p1, p2, p3);
                var density = (this.value * (1 - min_factor) + min_factor)
                density = Math.floor(density * 10) / 10
                var frequency = Math.ceil(1 / density)
                for (var h=0; h<hatching.length; h++)
                {
                    if ((h%frequency) > 0) continue
                    
                    var line = LineBoxIntersection(hatching[h], box)
                    
                    if (line != null)
                    {
                        line.draw()
                    }
                }
                break
        }

        return false
    }
    else
    {
        for (var l=0; l<this.leaves.length; l++)
        {
            if (!this.leaves[l].draw(target))
                return false
        }
    }
    return true
}

Leaf.prototype.prune = function()
{
    if (this.leaves.length == 0)
        return 1
    
    var leaf_count = 0
    for (var l = 0; l < this.leaves.length; l++)
    {
        leaf_count += this.leaves[l].prune()
    }

    var ok_to_prune = true    
    for (var l = 0; l < this.leaves.length; l++)
    {
        if (this.leaves[l].leaves.length > 0)
            ok_to_prune = false
    }
    
    var value = this.value

    if (ok_to_prune)
    {
        for (var l = 0; l < this.leaves.length; l++)
        {
            if (l==0) value = this.leaves[l].value;
            else if (value != this.leaves[l].value)
                ok_to_prune = false;
        }
    }

    if (ok_to_prune)
    {
        this.leaves = []
        this.value = value
        leaf_count = 1
    }
    
    return leaf_count
}

Leaf.prototype.set_ids = function()
{
    this.min_range = next_id
    if (this.leaves.length == 0)
    {
        this.id = next_id
        next_id += 1
    }
    else
    {
        for (var l = 0; l < this.leaves.length; l++)
        {
            this.leaves[l].set_ids()
        }
    }
    this.max_range = next_id
}

var next_id = 0

function Octree(depth, size)
{
    this.root = new Leaf(depth-1, -size/2, -size/2, size)
    this.total_leaves = this.root.prune()
    console.log("Total leaf count: %d", this.total_leaves)
    
    this.root.set_ids()
}

Octree.prototype.draw = function(target) 
{
    this.root.draw(target)
}

var octree = new Octree(octree_depth, canvas_size)

///

function build_hatching()
{
    list = []
    const steps = hatching_density * 10
    for (var i=0; i<steps; i++)
    {
        {
            var p0 = new Point(-canvas_size / 2 + canvas_size / steps * i, -canvas_size / 2)
            var p1 = new Point(canvas_size / 2, canvas_size / 2 - canvas_size / steps * i)
            var line = new Line(p0, p1)
            list.push(line)
        }
        
        if (i>0)
        {
            var p0 = new Point(-canvas_size / 2, -canvas_size / 2 + canvas_size / steps * i)
            var p1 = new Point(canvas_size / 2 - canvas_size / steps * i, canvas_size / 2)
            var line = new Line(p0, p1)
            list.unshift(line)
        }
    }
    
    const hack = 0.00001
    for (var i=0; i<steps; i++)
    {
        {
            var p0 = new Point(hack+canvas_size / 2 - canvas_size / steps * i, -canvas_size / 2)
            var p1 = new Point(-canvas_size / 2, hack+canvas_size / 2 - canvas_size / steps * i)
            var line = new Line(p0, p1)
            list.push(line)
        }
        
        if (i>0)
        {
            var p0 = new Point(canvas_size / 2, hack-canvas_size / 2 + canvas_size / steps * i)
            var p1 = new Point(hack-canvas_size / 2 + canvas_size / steps * i, canvas_size / 2)
            var line = new Line(p0, p1)
            list.unshift(line)
        }
    }
    
    return list
}

const hatching = build_hatching()