I watched the video “Godot 4 C# Tilemap World 3 Ways - No Chunking, Millions of Tiles” and attempted to replicate tile generation within the view. As I zoom out, the rendering time increases significantly (potentially by O(N^2) or similar). Are there any optimizations I can apply to my code, or is multithreading my only viable option for improvement?
The main function looks like that:
func render_tiles(tile_pos: Vector2i) -> void:
var time:= Time.get_ticks_msec()
var tiles: Array[Vector2i] = []
var del_tiles = _prev_target_tiles.duplicate()
var old_tiles: Array[Vector2i] = []
var view_range = get_range(tile_pos)
for i in range(tile_pos.x - view_range.x, tile_pos.x + view_range.x + 1):
for j in range(tile_pos.y - view_range.y, tile_pos.y + view_range.y + 1):
var tile = Vector2i(i, j)
tiles.append(tile)
if tile in _prev_target_tiles:
del_tiles.erase(tile)
old_tiles.append(tile)
var n = 0
for tile in del_tiles:
self.erase_cell(tile)
for tile in tiles:
if tile in old_tiles:
old_tiles.erase(tile)
continue
self.set_cell(tile, 0, Vector2i.ZERO)
n += 1
print(n)
_prev_target_tiles = tiles
print("rendered by %s" % [Time.get_ticks_msec() - time])
The idea of video was to not make chunks, make the view of player one big chunk. I have one project where i was playing with chunk system, but this idea was inspirational for me, so i wonder is there i can do for optimization without chunks.
In the video one million was the size of world, but he was rendering only 450 tiles around the player. But for my hex map 500 tiles seems to small, so i think only way is to optimize somehow the code or just limit the zoom out.
removing and adding tiles every frame sounds like a bad solution, chunks are good because of their low granularity. I recommend trying out such a system.
OMG i did it, its so much faster!! I was thinking for a while and understood, that the bottle neck is all those for loops. I tried to draw 2 rectangles and try to solve how to get only the area that i need using math. But there is already a Rect2 & Rect2i types in godot so i used it and now it is a lot and a LOT faster.
The new code:
func get_view_rect(target_pos: Vector2i) -> Rect2i:
var view_range = get_range(target_pos)
return Rect2i(
target_pos.x - view_range.x,
target_pos.y - view_range.y,
2 * view_range.x + 1,
2 * view_range.y + 1
)
func render_tiles(tile_pos: Vector2i) -> void:
var n = 0
var time:= Time.get_ticks_msec()
var tiles: Array[Vector2i] = []
var del_tiles = _prev_target_tiles.duplicate()
var old_tiles: Array[Vector2i] = []
var rect = get_view_rect(tile_pos)
if rect == _prev_rect2i:
return
var crossover: Rect2i = rect.intersection(_prev_rect2i)
if crossover.size == Vector2i.ZERO:
for i in range(_prev_rect2i.position.x, _prev_rect2i.end.x + 1):
for j in range(_prev_rect2i.position.y, _prev_rect2i.end.y + 1):
self.erase_cell(Vector2i(i, j))
for i in range(rect.position.x, rect.end.x + 1):
for j in range(rect.position.y, rect.end.y + 1):
self.set_cell(Vector2i(i, j), 0, Vector2i.ZERO)
n += 1
else:
for i in range(_prev_rect2i.position.x, _prev_rect2i.end.x + 1):
for j in range(_prev_rect2i.position.y, _prev_rect2i.end.y + 1):
if crossover.has_point(Vector2i(i, j)):
continue
self.erase_cell(Vector2i(i, j))
for i in range(rect.position.x, rect.end.x + 1):
for j in range(rect.position.y, rect.end.y + 1):
if crossover.has_point(Vector2i(i, j)):
continue
self.set_cell(Vector2i(i, j), 0, Vector2i.ZERO)
n += 1
print(n)
_prev_target_tiles = tiles
_prev_rect2i = rect
print("rendered by %s" % [Time.get_ticks_msec() - time])
new results look like this:
780
rendered by 2
642
rendered by 2
303
rendered by 2
800
rendered by 2
350
rendered by 1
old ones:
1945
rendered by 41
1574
rendered by 42
1974
rendered by 41
658
rendered by 41
719
rendered by 42
Also i checked speed between different for loops using code like this:
var time = Time.get_ticks_msec()
for i in range(10_000):
for j in range(10_000):
continue
print(Time.get_ticks_msec() - time)
var l = []
for i in range(10_000):
for j in range(10_000):
l.append(Vector2i(i, j))
time = Time.get_ticks_msec()
for _l in l:
continue
print(Time.get_ticks_msec() - time)
#results
691
2092