QuadTree

From Wikipedia:Quadtree:

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".

In our case nodes are cells and the internal cells of an quadtree are squares with a specified center and span.Also, the terms splitting and subdividing will be used interchangeably.

This section will be a quick-start on how to create, subdivide an QuadTree according to custom conditions and then display the result. In order to have a more in-depth explanation of some concepts and learn how to give your quadrants custom data please refer to the sidebar.

We will doing this inside of a _ready() function of any Redot Node.

Before creating an QuadTree structure we need to create it's root which is of the type QuadTreeQuadrant:

func _ready() -> void:
	var quadtree_root : QuadTreeQuadrant = QuadTreeQuadrant.new()
	quadtree_root.center = Vector2.ZERO
	quadtree_root.span = 500

Here we've created an QuadTreeQuadrant with a position at the world origin and a span of 500. A span of any cell is it's distance from it's center. The position and span of the root will matter when displaying the QuadTree and of course when we want to spatially query it or it's children. It's immediate children will be affected as they will be a subdivision of root, and in turn their children will be affected by the resulting center and span, until finally the maximum depth is reached.

Now we will create an QuadTree and make it's root the quadrant we've just created.

func _ready() -> void:
	(...)
	var quadtree : QuadTree = QuadTree.new()
	quadtree.root = quadtree_root
	quadtree.maximum_depth = 5

This extra property we've assigned, maximum_depth, is the amount of subdivision that is allowed of any splitting operation done by the QuadTree. This will help preserve memory if you're not entirely sure what the result of your splitting operation will look like. There is currently no limit on this property so be careful and start from small numbers.

There are two splitting operations of an QuadTree:

1. split_on_condition(condition : Callable) -> void
2. split_on_cell(condition_on_cell : Callable) -> void

Each operation is to be only called once. The both iterate first the root and if any children nodes are created then those children are iterated and may be split.

split_on_condition(condition : Callable) -> void takes as an argument a Callable that takes no arguments and returns a bool. The QuadTree will call the Callable and each time that the condition returns true the QuadTree subdivides the QuadTreeQuadrant it is currently iterated on.

split_on_cell(condition_on_cell : Callable) -> void takes as an argument a Callable that takes one argument of type QuadTreeQuadrant and returns a bool. The QuadTree will call the Callable and pass in the QuadTreeQuadrant it is iterated upon as the argument. Each time that the condition returns true the QuadTree subdivides the QuadTreeQuadrant it is currently iterated on.

These operations will recurse onto the children cells until the conditions return false or until the maximum_depth is reached.

A simple example of split_on_condition:

func _ready() -> void:
	(...)
	quadtree.split_on_condition(func() -> bool: return true)

As the Callable always returns true the QuadTree will subdivide until the maximum depth is reached.

For split_on_cell we will retrieve the Callable from a created function quadrant_contains_color(quadrant : QuadTreeQuadrant) -> bool.

func quadrant_contains_color(quadrant : QuadTreeQuadrant) -> bool:
	var chosen_color : Color = Color.ORANGE_RED
	
	var color_diff_tolerance : float = .2
	var viewport : Viewport = get_viewport()
	#Get screen result of main Camera2D
	var screen_texture : ViewportTexture = viewport.get_texture()
	var screen_image : Image = screen_texture.get_image()
	var screen_width : int = screen_image.get_width()
	var screen_height : int = screen_image.get_height()
	var world_origin_screen_coords : Vector2 = -viewport.get_camera_2d().global_position + Vector2(screen_width/2, screen_height/2)
	#if quadrant is entirely below camera view
	if(quadrant.center.y - quadrant.span >= viewport.get_camera_2d().global_position.y + screen_height/2):
		return false
	#if quadrant is entirely above camera view
	if(quadrant.center.y + quadrant.span <= viewport.get_camera_2d().global_position.y - screen_height/2):
		return false
	#if quadrant is entirely to the left of camera view
	if(quadrant.center.x + quadrant.span <= viewport.get_camera_2d().global_position.x - screen_width/2):
		return false
	#if quadrant is entirely to the right of camera view
	if(quadrant.center.x - quadrant.span >= viewport.get_camera_2d().global_position.x + screen_width/2):
		return false
	var quadrant_corner : Vector2 = quadrant.center - Vector2(quadrant.span, quadrant.span)
	#interpolate across quadrant
	for i : int in (quadrant.span*2 as int):
		for j : int in (quadrant.span*2 as int):
			#convert interpolant to screen space
			var qc_screen_coords : Vector2 = world_origin_screen_coords + (quadrant_corner + Vector2(i, j))
			var pixel_color : Color = screen_image.get_pixel(qc_screen_coords.x, qc_screen_coords.y)
			var color_diff = color_difference(pixel_color, chosen_color)
			if(color_diff <= color_diff_tolerance):
				return true
	return false

func color_difference(c1 : Color, c2 : Color) -> float:
	return abs(c1.r - c2.r) + abs(c1.g - c2.g) + abs(c1.b - c2.b)

A function like this showcases the amount of complexity you can put into your conditions of subdivision

This function returns true if the quadrant contains a pixel with a color within a tolerance of difference towards chosen_color. For this you will need to add any image to your scene in the bounds of the main Camera2D and update chosen_color appropriately.

In our ready function, now

func _ready() -> void:
	(...)
	#Wait until RenderingServer has sent data to the cameras
	await RenderingServer.frame_post_draw
	quadtree.split_on_cell(quadrant_contains_color)

Now the QuadTree will only split if the current quadrant contains a similar color to chosen_color within it's bounds.

In each case you can call quadtree.cell_count() to return the number of cells that the QuadTree now has.
As well, you can call quadtree.find_depth() to see the deepest level that the QuadTree has reached.

But for a more visual understanding you will want to display your QuadTree. QuadTrees are displayed by adding a Sprite2D to the scene that has a function which draws each line of the tree connected to it's draw signal. To retrieve the points of these lines we call gen_lines():

func _ready() -> void:
	(...)
	var quadtree_line_points : PackedVector2Array = quadtree.gen_lines()
	var quadtree_sprite : Sprite2D = Sprite2D.new()
	quadtree_sprite.draw.connect(func() -> void: \
		for i : int in quadtree_line_points.size()/2:
			quadtree_sprite.draw_line(quadtree_line_points[i*2], quadtree_line_points[i*2 + 1], Color.DEEP_SKY_BLUE))
	#Display tree on top
	quadtree_sprite.z_index = 1
	add_child(quadtree_sprite)

The result of split on condition with a maximum depth of 5

The result of split on cell with a maximum depth of 5

The result of split on cell with a maximum depth of 8

Redot Engine Logo by Asrorul Irsyad

The relevant code of this page:

func _ready() -> void:
	var quadtree_root : QuadTreeQuadrant = QuadTreeQuadrant.new()
	quadtree_root.center = Vector2.ZERO
	quadtree_root.span = 500
	var quadtree : QuadTree = QuadTree.new()
	quadtree.root = quadtree_root
	quadtree.maximum_depth = 5
	
	quadtree.split_on_condition(func() -> bool: return true)
	
	##Wait until RenderingServer has sent data to the cameras
	#await RenderingServer.frame_post_draw
	#quadtree.split_on_cell(quadrant_contains_color)
	
	var quadtree_line_points : PackedVector2Array = quadtree.gen_lines()
	var quadtree_sprite : Sprite2D = Sprite2D.new()
	quadtree_sprite.draw.connect(func() -> void: \
		for i : int in quadtree_line_points.size()/2:
			quadtree_sprite.draw_line(quadtree_line_points[i*2], quadtree_line_points[i*2 + 1], Color.DEEP_SKY_BLUE))
	#Display tree on top
	quadtree_sprite.z_index = 1
	add_child(quadtree_sprite)

func quadrant_contains_color(quadrant : QuadTreeQuadrant) -> bool:
	var chosen_color : Color = Color.ORANGE_RED
	
	var color_diff_tolerance : float = .2
	var viewport : Viewport = get_viewport()
	#Get screen result of main Camera2D
	var screen_texture : ViewportTexture = viewport.get_texture()
	var screen_image : Image = screen_texture.get_image()
	var screen_width : int = screen_image.get_width()
	var screen_height : int = screen_image.get_height()
	var world_origin_screen_coords : Vector2 = -viewport.get_camera_2d().global_position + Vector2(screen_width/2, screen_height/2)
	#if quadrant is entirely below camera view
	if(quadrant.center.y - quadrant.span >= viewport.get_camera_2d().global_position.y + screen_height/2):
		return false
	#if quadrant is entirely above camera view
	if(quadrant.center.y + quadrant.span <= viewport.get_camera_2d().global_position.y - screen_height/2):
		return false
	#if quadrant is entirely to the left of camera view
	if(quadrant.center.x + quadrant.span <= viewport.get_camera_2d().global_position.x - screen_width/2):
		return false
	#if quadrant is entirely to the right of camera view
	if(quadrant.center.x - quadrant.span >= viewport.get_camera_2d().global_position.x + screen_width/2):
		return false
	var quadrant_corner : Vector2 = quadrant.center - Vector2(quadrant.span, quadrant.span)
	#interpolate across quadrant
	for i : int in (quadrant.span*2 as int):
		for j : int in (quadrant.span*2 as int):
			#convert interpolant to screen space
			var qc_screen_coords : Vector2 = world_origin_screen_coords + (quadrant_corner + Vector2(i, j))
			var pixel_color : Color = screen_image.get_pixel(qc_screen_coords.x, qc_screen_coords.y)
			var color_diff = color_difference(pixel_color, chosen_color)
			if(color_diff <= color_diff_tolerance):
				return true
	return false

func color_difference(c1 : Color, c2 : Color) -> float:
	return abs(c1.r - c2.r) + abs(c1.g - c2.g) + abs(c1.b - c2.b)