/// Quadtree

function initTree(max_nodes) {
    global.nodes = array_create(max_nodes)
    for (var i = 0; i < max_nodes; i++) {
        global.nodes[i] = {
            x: 0,
            y: 0,
            width: 0,
            height: 0,
            divided: false,
            bodies: [],
            mass: 0,
            center_x: 0,
            center_y: 0,
            northwest_index: -1,
            northeast_index: -1,
            southwest_index: -1,
            southeast_index: -1
        };
    }
    global.node_index = 0
}

function createNode(_x, _y, _width, _height) {
    if (global.node_index >= array_length(global.nodes)) {
        show_error("Превышено количество узлов дерева: " + string(global.node_index), true);
    }
    var node = global.nodes[global.node_index];
    global.node_index += 1;

    node.x = _x;
    node.y = _y;
    node.width = _width;
    node.height = _height;
    resetNode(node);

    return node;
}

function insertNode(node, body) {
    if (!containsNode(node, body)) {
        return false;
    }

    if (!node.divided && array_length(node.bodies) < 1) {
        array_push(node.bodies, body);
        return true;
    }

    if (!node.divided) {
        subdivideNode(node);
    }

    if (insertNode(global.nodes[node.northwest_index], body)) return true;
    if (insertNode(global.nodes[node.northeast_index], body)) return true;
    if (insertNode(global.nodes[node.southwest_index], body)) return true;
    if (insertNode(global.nodes[node.southeast_index], body)) return true;

    return false;
}

function resetTree() {
    for (var i = 0; i < global.node_index; i++) {
        resetNode(global.nodes[i]);
    }
    global.node_index = 1;
}

function resetNode(node) {
    node.bodies = [];
    node.mass = 0;
    node.center_x = 0;
    node.center_y = 0;
    node.divided = false;
    node.northwest_index = -1;
    node.northeast_index = -1;
    node.southwest_index = -1;
    node.southeast_index = -1;
}

function computeMassDistribution(node) {
    if (!node.divided) {
        if (array_length(node.bodies) == 1) {
            var body = node.bodies[0];
            node.mass = body.mass;
            node.center_x = body.x;
            node.center_y = body.y;
        } else {
            node.mass = 0;
            node.center_x = node.x + node.width / 2;
            node.center_y = node.y + node.height / 2;
        }
    } else {
        computeMassDistribution(global.nodes[node.northwest_index]);
        computeMassDistribution(global.nodes[node.northeast_index]);
        computeMassDistribution(global.nodes[node.southwest_index]);
        computeMassDistribution(global.nodes[node.southeast_index]);

        var nw = global.nodes[node.northwest_index];
        var ne = global.nodes[node.northeast_index];
        var sw = global.nodes[node.southwest_index];
        var se = global.nodes[node.southeast_index];

        node.mass = nw.mass + ne.mass + sw.mass + se.mass;
        if (node.mass > 0) {
            node.center_x = (nw.center_x * nw.mass +
                                ne.center_x * ne.mass +
                                sw.center_x * sw.mass +
                                se.center_x * se.mass) / node.mass;
            node.center_y = (nw.center_y * nw.mass +
                                ne.center_y * ne.mass +
                                sw.center_y * sw.mass +
                                se.center_y * se.mass) / node.mass;
        }
    }
}

function containsNode(node, body) {
    return (body.x >= node.x) && (body.x < node.x + node.width) &&
            (body.y >= node.y) && (body.y < node.y + node.height);
}

function subdivideNode(node) {
    static tempBodies = [];

    var half_width = node.width / 2;
    var half_height = node.height / 2;

    node.northwest_index = global.node_index;
    createNode(node.x, node.y, half_width, half_height);

    node.northeast_index = global.node_index;
    createNode(node.x + half_width, node.y, half_width, half_height);

    node.southwest_index = global.node_index;
    createNode(node.x, node.y + half_height, half_width, half_height);

    node.southeast_index = global.node_index;
    createNode(node.x + half_width, node.y + half_height, half_width, half_height);

    node.divided = true;

    tempBodies = node.bodies;
    node.bodies = [];

    for (var i = 0; i < array_length(tempBodies); i++) {
        var body = tempBodies[i];
        if (insertNode(global.nodes[node.northwest_index], body)) continue;
        if (insertNode(global.nodes[node.northeast_index], body)) continue;
        if (insertNode(global.nodes[node.southwest_index], body)) continue;
        if (insertNode(global.nodes[node.southeast_index], body)) continue;
    }
}

// slower?
function calculateForce(node, body, theta) {
    if (!node.divided && array_length(node.bodies) == 1 && node.bodies[0] == body) {
        return;
    }

    if (node.mass == 0) {
        return;
    }

    var dx = node.center_x - body.x;
    var dy = node.center_y - body.y;
    var distance = sqrt(dx * dx + dy * dy) + 0.0001;

    if (distance == 0) {
        return;
    }

    var s = node.width;
    var d = distance;

    if (!node.divided || (s / d) < theta) {
        var force = (obj_controller.G * node.mass * body.mass) / (distance * distance);
        var fx = force * (dx / distance);
        var fy = force * (dy / distance);
        body.force_x += fx;
        body.force_y += fy;
    } else {
        calculateForce(global.nodes[node.northwest_index], body, theta);
        calculateForce(global.nodes[node.northeast_index], body, theta);
        calculateForce(global.nodes[node.southwest_index], body, theta);
        calculateForce(global.nodes[node.southeast_index], body, theta);
    }

}

// faster?
function calculateForceIterative(node, body, theta) {
    var stack = [];
    array_push(stack, node);

    while (array_length(stack) > 0) {
        var current = array_pop(stack);

        if (!current.divided && array_length(current.bodies) == 1 && current.bodies[0] == body) {
            continue;
        }

        if (current.mass == 0) {
            continue;
        }

        var dx = current.center_x - body.x;
        var dy = current.center_y - body.y;
        var distance = sqrt(dx * dx + dy * dy) + 0.0001;

        if (distance == 0) {
            continue;
        }

        var s = current.width;
        var d = distance;

        if (!current.divided || (s / d) < theta) {
            var force = (obj_controller.G * current.mass * body.mass) / (distance * distance);
            var fx = force * (dx / distance);
            var fy = force * (dy / distance);
            body.force_x += fx;
            body.force_y += fy;
        } else {
            array_push(stack, global.nodes[current.northwest_index]);
            array_push(stack, global.nodes[current.northeast_index]);
            array_push(stack, global.nodes[current.southwest_index]);
            array_push(stack, global.nodes[current.southeast_index]);
        }
    }
}

function applyForce(body) {
    body.velocity_x += (body.force_x / body.mass);
    body.velocity_y += (body.force_y / body.mass);
    body.x += body.velocity_x;
    body.y += body.velocity_y;
}

function drawTree(node) {
    with (node) {
        draw_set_color(c_green);
        draw_line(x, y, x + width, y)
        draw_line(x + width, y, x + width, y + height)
        draw_line(x + width, y + height, x, y + height)
        draw_line(x, y + height, x, y)
        if (divided) {
            drawTree(global.nodes[node.northwest_index]);
            drawTree(global.nodes[node.northeast_index]);
            drawTree(global.nodes[node.southwest_index]);
            drawTree(global.nodes[node.southeast_index]);
        }
    }

}