Store objects in 3 dimensional grid

@max_godot @Loxyrak I made a quick benchmark.

I tested three different methods of creating and iterating through a 3-dimensional int array of size 10x10x10. I chose integers for simplicity.

What we measure in each test is creating the array and then iterating through it 1000 times and increasing each value by one. For testing I had a couple of asserts at the end of each test but those were for size 3 x 3 x 3 but I left them in here to show how to access the array values. I did not measure the asserts.

const size_x := 10
const size_y := 10
const size_z := 10


func value(x: int, y: int, z: int) -> int:
    return size_z * size_y * z + size_x * y + x

The value() helper function returns the initial value at position x/y/z.

Method 1: Multidimensional array

Access values with data[z][y][x].

func bench01(iterations: int):
    var data := []

    for z in size_z:
        var grid := []
        for y in size_y:
            var row: Array[int] = []
            for x in size_x:
                row.append(value(x, y, z))
            grid.append(row)
        data.append(grid)

    for i in iterations:
        for z in size_z:
            for y in size_y:
                for x in size_x:
                    data[z][y][x] += 1

    # assert(data[0][0][0] == 1000)
    # assert(data[0][0][2] == 1002)
    # assert(data[1][0][1] == 1010)
    # assert(data[1][1][1] == 1013)
    # assert(data[2][1][0] == 1021)
    # assert(data[2][2][2] == 1026)

Method 2: Dictionary with Vector3i keys

Access values with data[Vector3i(x, y, z)].

func bench02(iterations: int):
    var data := {}

    for x in size_x:
        for y in size_y:
            for z in size_z:
                data[Vector3i(x, y, z)] = value(x, y, z)

    for i in iterations:
        for x in size_x:
            for y in size_y:
                for z in size_z:
                    data[Vector3i(x, y, z)] += 1

    # assert(data[Vector3i(0, 0, 0)] == 1000)
    # assert(data[Vector3i(2, 0, 0)] == 1002)
    # assert(data[Vector3i(1, 0, 1)] == 1010)
    # assert(data[Vector3i(1, 1, 1)] == 1013)
    # assert(data[Vector3i(0, 1, 2)] == 1021)
    # assert(data[Vector3i(2, 2, 2)] == 1026)

Method 3: Linear array and we calculate the index by hand

Access values with data[size_z * size_y * z + size_x * y + x].

func bench03(iterations: int):
    var data: Array[int] = []
    data.resize(size_z * size_y * size_x)

    for z in size_z:
        for y in size_y:
            for x in size_x:
                data[size_z * size_y * z + size_x * y + x] = value(x, y, z)

    for i in iterations:
        for z in size_z:
            for y in size_y:
                for x in size_x:
                    data[size_z * size_y * z + size_x * y + x] += 1

    # assert(data[size_z * size_y * 0 + size_x * 0 + 0] == 1000)
    # assert(data[size_z * size_y * 0 + size_x * 0 + 2] == 1002)
    # assert(data[size_z * size_y * 1 + size_x * 0 + 1] == 1010)
    # assert(data[size_z * size_y * 1 + size_x * 1 + 1] == 1013)
    # assert(data[size_z * size_y * 2 + size_x * 1 + 0] == 1021)
    # assert(data[size_z * size_y * 2 + size_x * 2 + 2] == 1026)

Results

• Method 1: 191 ms
• Method 2: 122 ms
• Method 3: 90 ms

Method 3 (one linear array) is the fastest which isn't surprising but only under the condition that we always calculate the index on the spot by hand and don't use some kind of index(x, y, z) function that returns the array index as one would usually do to reduce errors. This would completely kill performance because every function call in GDScript is expensive. Calculating the index by hand makes this method faster but also more clunky.

I was surprised to see that using a dictionary with Vector3i as keys is faster than using a multidimensional array. So in this case this might actually be the best tradeoff between usability and performance.

Using a 3-dimensional array was surprisingly slow but on the other hand we access the array three times whereas the other three methods only make one array access and each [] operator is probably a function call which as I said are slow in GDScript.

BTW I know that we can optimize the loops (or use only one for method 3) but I wanted to check the most common use case which would probably be calling some kind of please_get_me_my_array_value_at(x, y, z).