[022] Spatial Grid

[022] Spatial Grid

[24h] Simple and Fast Query using a Dense Array

[Feb 03] 5h - Spatial Hash Learn
[Feb 04] 2h - Spatial Hash Learn
[Feb 05] 4h - Spatial Hash Learn
[Feb 07] 2h - Flocking Spatial Hash
[Feb 09] 4h - Flocking Spatial Hash
[Feb 10] 7h - Spatial Grid

KISS (Keep it Simple Stupid)
simpler to implement and easier to maintain
no need to implement objects and recursions

var _found: Array[int]
var _unit_count: int = 5000
var _unit_array: Array[Vector2]

var _cell_count: Array[int]                                                     # number of units in cell
var _cell_start: Array[int]                                                     # start_index of cell in dense array
var _dense_array: Array[int]                                                    # compact list of unit index

func _ready() -> void:
    _cell_count.resize(_grid_size)
    _cell_start.resize(_grid_size)
    _dense_array.resize(_unit_array.size())

func _position_to_grid(_position: Vector2) -> Vector2i:
    var pos_x: int = floori(_position.x / _cell_size)
    var pos_y: int = floori(_position.y / _cell_size)
    return Vector2i(pos_x, pos_y)

func _create_spatial_grid() -> void:
    _cell_start.fill(-1)                                                        # -1 if empty
    _cell_count.fill(0)

    var _grid_index: int = 0
    for index in _unit_array.size():                                            # loop vector_array to get _cell_count
        _grid_index = _position_to_grid_index(_unit_array[index])
        _cell_count[_grid_index] += 1

    var cell_sum: int = 0
    for index in _grid_size:                                                    # loop grid_array to get partial sums
        cell_sum += _cell_count[index]
        _cell_start[index] = cell_sum

    for index in _unit_array.size():                                            # loop vector_array to correct _cell_start
        _grid_index = _position_to_grid_index(_unit_array[index])
        _cell_start[_grid_index] -= 1
        _dense_array[_cell_start[_grid_index] = index                           # add point_index to _dense_array