Dictionary value comparisons seem to cause a lot of lag

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Rikri

I have a dictionary with a few hundred keys in it, and a function which searches every key in the dictionary to find one with a value that lies in a particular range. This function is then run around 100 times on certain frames. During these frames, my game lags substantially: a single frame sometimes takes an upwards of an entire second (and I wouldn’t consider my specs particularly bad, either). Does running this many comparisons tend to cause Godot to lag a lot, or did I do something else inefficiently?

The following is an excerpt from my code:

var object_dict = {
        0: {"Type": "FGTile", "Position": [0,0]}, # this dict has ~300ish objects in it when the game is run
    }

func point_is_between(p0, p1, p2):
    return (p1 >= p0 && p0 >= p2) || (p2 >= p0 && p0 >= p1)

func overlap_between_ranges(x1, y1, x2, y2, x3, y3, x4, y4):
    if point_is_between(x1, x3, x4) || point_is_between(x2, x3, x4) || point_is_between(x3, x1, x2):
        if point_is_between(y1, y3, y4) || point_is_between(y2, y3, y4) || point_is_between(y3, y1, y2):
            return true
    return false

func is_range_empty(x1, y1, x2, y2): # this is the function which is run ~100 times
    for i in range(0, object_dict.size()):
        if object_dict[i]["Type"] == "FGTile":
            if overlap_between_ranges(x1, y1, x2, y2, object_dict[i]["Position"][0]-2, object_dict[i]["Position"][1]-2, object_dict[i]["Position"][0]+1, object_dict[i]["Position"][1]+1):
                return false

    return true
2
:bust_in_silhouette: Reply From: dewcked

It’s problem about how you implement this algorithm.

Make new Arrays

bool x_pos = []
bool y_pos = []
bool x_y_map = []

Initialize Arrays with false (coordinate limits)

for i in range(x_limit+1):
    x_pos.append(false)
    for j in range(y_limit+1):
        x_y_map.append(false)
for i in range(y_limit+1):
    y_pos.append(false)

Iterate every elements in object_dict’s position. Save the result to x_pos and y_pos. also x_y_map

for i in dictionary: # Fix references
    var x = dictionary.posx
    var y = dictionary.posy
    x_pos[x] = true
    y_pos[y] = true
    x_y_map[x][y] = true

Now you can search by x_pos or y_pos.
given search range (x0, y0, x1, y1) # here, x0 < x1 and y0 < y1

if x1 - x0 < y1 - y0:
    for i in range(y0, y1+1):
        if y_pos[i] == true:
        for j in range(x0, x1+1):
            if x_y_map[i][j] == true:
                # do something you want here if not empty and return
else:
    for i in range(x0, x1+1):
        if x_pos[i] == true:
        for j in range(y0, y1+1):
            if x_y_map[j][i] == true:
                # do something you want here if not empty and return
# here, given range is empty

+++ Fixed logic error in last code block

if you want to change position, you should update those Arrays (which will cost less).