[020] K-dimension Tree

[020] K-dimension Tree

[42h] Binary Tree Algorithm for Quick Searching

[Jan 24] 02h - Nearest Neighbor Search
[Jan 25] 06h - 8 Letter Seed / Naive Search
[Jan 26] 05h - Binary Search Tree
[Jan 27] 11h - Tree Data Structures
[Jan 28] 04h - K-d Tree Search
[Jan 29] 04h - K-d Tree Review
[Jan 30] 04h - K-d Tree UI
[Jan 31] 05h - K-d Tree Upload
[Feb 02] 01h - K-d Tree Fix

- learned how to generate and load RNG seed

- K-d Tree is good searching static positions
- requires to be rebuild if things moved
- building is expensive due to sorting and finding the middle
- it's a trade-off based on the number of points
- naive searching is quicker in lower number of points
- K-d Tree is better in higher number of points

Pseudocode:
    # youtu.be/Glp7THUpGow
    var _root_node: TreeNode
    var _nearest_node: TreeNode
    var _k_dimention: int = 2
    
    class TreeNode:
        var data: Vector2
        var parent: TreeNode
        var left: TreeNode
        var right: TreeNode
        
    func _ready() -> void:
        _root_node = _build_kd_tree_helper(_root_node, _tree_node_array)
        _nearest_node = _nearest_neighbor(_root_node, get_global_mouse_position())
        
    func _build_kd_tree_helper(parent: TreeNode, tree_node_array: Array[TreeNode], depth: int = 0) -> TreeNode:
        var current_axis: int = depth % _k_dimention
        var sorted_array: Array[TreeNode]

        if current_axis == 0:
            sorted_array = _array_insertion_sort_x(tree_node_array)
        elif current_axis == 1:
            sorted_array = _array_insertion_sort_y(tree_node_array)

        var middle_index: int = (int)(sorted_array.size() / 2)
        var left_array: Array[TreeNode] = sorted_array.slice(0, middle_index)
        var right_array: Array[TreeNode] = sorted_array.slice(middle_index + 1)

        if parent != null:
            sorted_array[middle_index].parent = parent

        if left_array.size() != 0:
            sorted_array[middle_index].left = _build_kd_tree_helper(sorted_array[middle_index], left_array, depth + 1)

        if right_array.size() != 0:
            sorted_array[middle_index].right = _build_kd_tree_helper(sorted_array[middle_index], right_array, depth + 1)

        return sorted_array[middle_index]

    func _array_insertion_sort_x(tree_node_array: Array[TreeNode]) -> Array[TreeNode]: # insertion sort
        var index_i: int = 1
        var index_j: int = 0
        var temp: TreeNode

        for i in tree_node_array.size() - 1:            # loop, skip first item
            temp = tree_node_array[index_i]
            index_j = index_i - 1

            while index_j >= 0 && tree_node_array[index_j].data.x > temp.data.x:
                tree_node_array[index_j + 1] = tree_node_array[index_j]
                index_j -= 1

            tree_node_array[index_j + 1] = temp

            index_i += 1

        return tree_node_array

    func _array_insertion_sort_y(tree_node_array: Array[TreeNode]) -> Array[TreeNode]: # insertion sort
        var index_i: int = 1
        var index_j: int = 0
        var temp: TreeNode

        for i in tree_node_array.size() - 1:             # loop, skip first item
            temp = tree_node_array[index_i]
            index_j = index_i - 1

            while index_j >= 0 && tree_node_array[index_j].data.y > temp.data.y:
                tree_node_array[index_j + 1] = tree_node_array[index_j]
                index_j -= 1

            tree_node_array[index_j + 1] = temp

            index_i += 1

        return tree_node_array

    func _nearest_neighbor(parent: TreeNode, target: Vector2, depth: int) -> TreeNode:
        if parent == null:
            return null
            
        var current_axis: int = depth % _k_dimention
        var next_node: TreeNode
        var other_node: TreeNode

        if current_axis == 0:                            # x-axis
            if target.x < parent.data.x:
                next_node = parent.left
                other_node = parent.right
            else:
                next_node = parent.right
                other_node = parent.left
        else:                                            # y-axis
            if target.y < parent.data.y:
                next_node = parent.left
                other_node = parent.right
            else:
                next_node = parent.right
                other_node = parent.left
                
        var temp: TreeNode = _nearest_neighbor(next_node, target, depth + 1)
        var best: TreeNode = _closer_node(target, temp, parent)
        
        var best_distance: float = target.distance_to(best)
        var parent_distance: float
        
        if current_axis == 0:
            parent_distance = absf(target.x - parent.data.x)
        else:
            parent_distance = absf(target.y - parent.data.y)
            
        if best_distance >= parent_distance * parent_distance:
            temp = _nearest_neighbor(other_node, target, depth + 1)
            best = _closer_node(target, temp, parent)
            
        return best
        
    func _closer_node(target: Vector2, node_a: TreeNode, node_b: TreeNode) -> TreeNode:
        if node_a == null:
            return node_b
            
        if node_b == null:
            return node_a
            
        var distance_a: float = target.distance_to(node_a)
        var distance_b: float = target.distance_to(node_b)
        
        if distance_a < distance_b:
            return node_a
        else:
            return node_b