Game Basic Understanding of Partial Partitioning Algorithm: Quadtree and Octree
Hello everyone
This is Lee Deukwoo from game algorithm
In this lesson, we will talk about factors used for game optimization
which are called quadtree and octree
This spatial partitioning algorithm quadtree lecture
introduces the overview of quadtree and how it works
Let's find out ways to implement quadtree
Overview of Quadtree and How It Works
First, I will introduce the overview of quadtree
and how the operation works
Quadtree isn't a algorithm but instead
a word that describes a general
tree structured data structure with four children
This term of quadtree started in 1974
from a thesis of Raphael Finkel and Jon Louis Bentley
It was first used in the thesis
As you can see from the picture, a quadtree is
always filled up with 4 children
it is a complete form of a tree
This quadtree data structure is
used to divided a 2D plane efficiently
depending on the usage, point quadtree and range quadtree are
the two ways that it can be divided into
Point quadtree is used to control the point data in a plane
through a efficient method
In the early stages of quadtree
there were mostly point quadtree types
It was commonly used to manage information about the location on the map
through an effective way
The closest neighbor from the current location or
Searching for neighbors that are located in a certain classification was
what the point quadtree was mainly used for
Range quadtree was utilized for objects with a defined area
and managing it efficiently
It is often used to determine whether
the objects with defined areas overlap
In games, the second one introduced
which is the range quadtree is used often
For games, it is used to detect collision between two objects
in a 2D plane
In a platformer game
the collision handling between the character and the platform
In a shooter game with a Top Down view
it is used for visibility determination or collision handling
The basic data used for this process
AABB, also known as Axis-Aligned Bounding Box
It uses rectangular data arranged through the world axis
But quadtree itself
does not stand for an algorithm that detects collision
When operating collision detection algorithm
Not every object goes trough census
only the objects near the target objects have to go through census
which is a role played in order to detect collision effectively
by reducing target data
I have prepared a video
This is a video of a program that I have developed
In a wide space, I have placed
15,000 objects randomly
Theses objects and the area on the screen
and as a mean to detect collision
I have utilized quadtree
The numeric value on the bottom which shows rendering object
uses quadtree currently
These are the number of objects that show in the camera viewport
If quadtree isn't used
we would have to compare all 15,000 objects
If we examine through this method for every frame
It would operate very slowly
Therefore, only the objects needed to detect collision
should picked out efficiently
which is why quadtree is being used
Now let's check the video
Next, how the quadtree works
We will take a look at its mechanism
As I mentioned before, quadtree
has a tree structure consisted with nodes
Every node consisting the quadtree
has a unique AABB of the rectangle and
the list of objects
In order to construct a quadree
create a rectangular AABB that encloses the whole area
and refer to this as the root node
And the lower it gets to the child node
The structure of having 4 child nodes
should be maintained as a complete tree structure
Quadtree that is set should fundamentally
implement insertion and query functions
Insertion means adding objects with defined range
into a object list of a
suitable node inside the quadtree
And query allows effective determination
of the AABB region given for performing the check
along with the collision object
First, how the insertion
operates will be explained
When insertion is operating
the root node is the only factor that is set
It searches for objects to insert
and performs division if necessary
For the case of division, the inserting object
has to be completely enclosed
in one of the four regions created by dividing the root node
If it is not completely enclosed and lies on the boundary
add it to the list of the root node and end the insertion
If the inserting object is completely enclosed in one of the four regions
Look back at the region
Take a look at the node and object
that recursively encloses the entire object
If it is entirely enclosed, operate the division again
If it lies on the boundary
Expand the depth of the tree structure while continuing the division
If the depth is set too deep
the memory usage could increase
Generally, the depth is regulated
When dividing the quadtree, length of the divided side
is always the half of the original length of the parent side
In case of a side length of the quadrant with a particular depth
It has a following formula
The W stands for the length of one side of the node
When the depth increases
It decreases by the factor of 2 to the power of the depth
Now let's take a look at the picture
to see the insertion progress of a quadtree
First, including the game map
A giant square region will be set
This is the region of a root node
And I will place the first object on the upper right side
Out of the root node and child node that is divided into four
Whether the inserted object's region is completely enclosed has to be checked
If the inserted object lies on the boundary
It is completely enclosed in the child node on the upper right side
So, we have to operate the division to create four child nodes
and allocate it to the root node
The inserted object is enclosed in the child region on the upper right side
Since it is enclosed in the second child node over here
We will take a look at the second child node
Now for the node on the upper right side
We only have to take a look at the second child node
the process that was carried out recursively
has to be repeated once again
We have to check whether child node that divided the node on the upper right into four
encloses with the object
If you look here now, it's completely contained
within one of the four child node areas
The inserted object is enclosed with the child region on the upper right side
This is where we will take a look
We have came down to depth 2
How it operates from depth 2 will be
the next step that we take a look at
For this depth 2 region
we have checked the region divided into four and the AABB of the object
the result was that it is overlapping
In this case, we don't continue the division
in the object list of the depth 2 node region
add the current object and terminate the insertion process
Now, we will insert one more
This object is completely enclosed with
the region which divided root node into four
For this case, do not go below the depth of the child node
and add to the object list of the root node
We have seen the process of quadtree insertion process
Now let's go over the query process
Query is a function that determines whether the given AABB
collides with the objects controlled by the quadtree
To operate query
First, the quadrant node that AABB used for query belongs in
needs to be observed
When every node that could possibly collide is understood
It is compared with the object list that each node has
This is to operate a collision detection
To learn more about the process
I have prepared an example that already inserted 10 objects
Following the insertion rule that was previously mentioned
We can see that 10 objects are added into
the object list of various nodes
In this situation, let's check the object that
collides with the region colored in red dotted line
From the picture, 3,8, and 7
These three objects are colliding with the current region
To check which object is colliding
We could go through census for all 10 of them
Since it's only 10, it doesn't matter right now
but if this increases to 100, 1000, and 10,000
It will start to slow down
So we have to utilize the tree structure in order to reduce the search volume
Then let's check the nodes
that have the possibility of being searched
First, the root node
If there is a blue object in the object list of the root node
Let's say the blue object has been inserted
The rectangular region that will carry out an assessment
could be overlapped
Therefore, the object list that root node has
there is a possibility of collision
It needs to be added to the list of assessment
Next, going deeper
since it is one of the four child that is enclosed on the upper right side
We should search for the child that is on the upper right side with a depth of 1
In the object list of the upper right side
if there is a blue object like so
this UpperRight
The upper right side should be added to the list of assessment
Going one step below, lower right side
This encloses the lower right side that will be divided into four
We could check the lower right side region
For the case of lower right side
This object could be in the object list of the lower right side
That would lead to overlapping
The object list of the lower right side
should be added to the list of assessment
Moving on to the next dept
Every object list that has been divided into four
should be added to the list of assessment
If the tree structure goes deeper, then we would need to continue
But let's say that this is the final depth
Then the search would end here
To wrap up the process until now
The following nodes are the ones we need to assess
UpperRight of root and the first depth
LowerRight of the second depth
Every child of the LowerRight from the third depth
These are the 7 nodes we could screen out
From the lists that nodes have
When we look at it
it has the overlapping part of the given region
which was 3, 8, and 7
If the quadtree has the depth of 3
A total of 85 nodes will be created
We only need to operate the search for 7 of them
This is called having a logarithmic time complexity
When there are more objects
it is more efficient to determine the overlapping
Next, for the case that is shown on the screen
When the region that should be assessed is overlapped in the middle
When it is overlapped in the middle
As you can see, the root node
and every child enclosed in the root node
counts as an object to be compared
Next, children with a depth of 1
If depth 1 is researched
The upper left side, Upper Left
The child node of lower right encloses the scope
Child node of the lower left for the upper right
Child node of the upper left for the lower right
And child node of the upper right for the lower left
They enclose the given scope
Let's go one step deeper into the next depth
Going in one step deeper on to the next depth
Looking in to the lower right region of depth 2
The two child region encloses the given scope
One child region for the lower left
Two child region for the upper right
They are enclosing the given scope
When operating query like so, it is different from insertion
Including both the overlapping and enclosing region
Every node needs to be identified
Implementing Quadtree
Extract the given sample project
and this project will show up when operating Unity
The Unity version used to run this project is
the 2021.3 version
As you can see, the project is
consisted with multiple scenes
In this lecture, we will take a look at what is assigned as number 1
which is the implementation of a general quadtree
Moving to the first folder, there are insertion and query request
There are two scenes like so
First this insertion scene
I will open up insert scene and explain functions related to it
For this case of insert scene
If you look at the Hierarchy tab on the left
There is a administrator called quadtree manager
In this game object manager
the quadtree spatial partitioning is proceeded
This quadtree manager component is
arranged over here as you can see
In this quadtree manager component
there is an assigned size of a whole map that sets the quadtree
As you can see x and y
64 is set for both vertical and horizontal
And in the bottom of quadtree manager game object
There is an insert
which is placed with a total of 9 objects
Let's take a look at each arrangement
Number 1 on the lower left, number to in the middle
These game objects called insert
As you can see there is a special tag called insert
Through this tag, the objects to be inserted will be chosen
It is designed in code
As you can see in the screen
The scene view and game view is separated
Normally it would be over here but
It is separated intentionally
So that the functions could be operated in the game view
and the result could be seen in the scene view
There is a button created in the game view
Usually a command is made in the game view but
The structure of a quadtree
is designed to be done through scene view
So for the scene view
It is designed that the camera view doesn't show
And the UI area doesn't show as well
Now I will press the play button
If we press the play button, the first on the lower left side
This object called Insert 1
pops up as a rectangle
This is the target rectangle that will proceed with the insertion
If we press the Insert button from the game view on the right
The quadtree to hold the rectangle
it will continue to divide until the node is found
And the rectangle object will be added to the mode object list which is divided
Let's press the button to see the result
As you can see in the bottom left quadrant
And from the top right quadrant
Again in the top left quadrant
The bottom right quadrant, this is the bottom most
It is currently overlapping, right?
The boundary is overlapping
which is why it ends here
Considering the depth, 1 Depth, 2 Depth, 3 Depth, and 4 Depth
We can see that it has proceeded until 4 Depth
So if you look over here
In the 4 Depth area
Do you see the number 1?
If the number is located in the middle of the fourth Depth
One object has been inserted in to the whole node
It means that one object has been inserted
I will press the next button
In the case of this red insertion object that is in the middle
It lies on the boundary of the quadrant that is divided
This means that it doesn't enclose in any child node
So it goes into the root node
It goes into root node if you press the insert button
You can see the number of root node being marked as 1
I will press next
Same as before, top left number 1, 2, 3, 4
It has been divided four times as before
The depth 1 is included but it lies on the boundary
which is why it goes into the lower right node
Like so, if it is continuously added one by one
A total of 9 objects as you can see
A node to store these objects
a node that is divided into 4 will be assigned
A number will be marked on the node
which shows that
spatial partitioning is efficiently done
This is the demo of the prepared program
which included 9 insertions
Now let's take a look at the code ourselves
Go to the script folder
In the first folder, which is quadtree folder
Quadtree manager
The manager component code which has been set to the game object
Let's double click it and take a look
The quadtree manager that we are trying to take a look at
It is included in the last project
which is the quadtree project
So remove everything else
The last quadtree project
The quadtree manager is what we will double click to find out
We will move to the top to take a look
For this quadtree manager
It is a script designed to manage quadtrees directly in Unity
So that it would operate as the Unity component
Inherited from the MonoBehaviour class
This script does not develop actual quadtree operation
It plays the role of controlling communication between
quadtree object that is designed from C Sharp through Unity
and the quadtree object over here
Let's look over the detailed information
First on the top of the class, something that will be dealt later
ways to classify query function and drawing method
A enumeration called Draw Mode has been declared
So that drawing in insert mode and
query mode could be distinguished
It is why this enumeration has been declared
For this enumeration
as you can see, from the quadtree manager
we can assign it like so
It has been pulled out to the interface
The default value is insertion
but it should be replaced when implementing query functions
Next, the size of the whole area that would be controlled from quadtree
has been designed so that it could be assigned manually
Over here, it has been set as 64 for both horizontal and veritcal
Next, the object to operate the actual quadtree
has been declared as member variable _tree
It has been initialized as null value so that it would be created when necessary
In the bottom, operate insertion function
The index variable which shows the list of inserting object list
And every objects with the insert tag
The variable to save this array has been declared
Other variables will be explained later on
when the query function is explained
Next, the initialization function of manager class
Let's take a look at Awake function
When there is no objects
An object called quadtree is created
At this point, you can see that the entire area info is entered as an factor
Next over here, FindGameObjectsWithTag
Using Unity API, a tag has been assigned as an insert
Every game object is brought to the array
and they are assigned here
Using this, the objects that will be inserted
can be searched one at a time as well as being inserted
Now for the insertion function
Let's take a look at Insertion function
For the Insert function, in Unity
There are buttons that say mapping and binding in the UI of Unity
So if you press this Insert button
The Insert function of the quadtree manager is invoked
And if the object list is complete
A defensive code has been declared to prevent additional insertion
If there isn't a problem, object
Invoke the Insert function of an object
which actually controls the quadtree
The index value of the object which we will be inserting
Put it into the Insert function over here
We are adding one more
It is a method of adding one more after being inserted
When every object is finished
The value that is same as the length of the insert object
will be set as an index
Next, we will look at the quad tree class
Quadtree class has rootNode
as a member variable
And it assigned maxDepth as a member variable
It is set as 5
So that it doesn't go below the depth 5
This is why the variable was set
If there isn't a limit
The memory, space, and recursive calls will increase significantly
It is best to regulate it below a certain value
And the constructor of quadtree class
as I mentioned before, takes a size
It starts creating after taking the size of a quadtree
In this case, root node is created right after taking the size
When creating the root node
various arguments need to be inserted
Let's check it out later on
when explaining Node class
This Insert function which quadtree manager invokes
Brings out the Insert function from the root node
It is designed as a structure that passes the argument right away
I will explain other functions later on
The main logic in the quadtree
We will take a look at Node class
The name for this Node class of the quadtree is QNode
Many different operations are done through this node
First, the enumeration called QNodeIndex
has been declared
This enumeration is used for insertion or query
to find out which quadrant the current
area is enclosed in
I specified IntType so that it can be easily converted to Integer type
The enumeration value starts from 0
We have to be cautious of the order
Top left side for number 0
and then top right side
next bottom right side
followed by bottom right side
then bottom left side
These are the order assigned for four
This order doesn't need to be kept but
Later on when you create the partitioned surface
It is easy to code when
you follow the order for the partitioned node
That is why I mentioned the order as a priority
And there are two exceptional cases
There is a case where it isn't enclosed in a quadrant completely
and lies on the boundary
In that case, a enumeration called STRADDING
can be declared
There might be a case when it moves outside the area, right?
This is an exceptional case so
to indicate this exceptional case
an enumeration called OUTOFAREA
an enumeration will be additionally added
Next, this time
we will look over the constructor code of the node
In a node,there is Quadtree,Parent, Bounds,Depth
which are four variables
These are set so that it is directly assigned with each member variable
by the constructor
Now, we will take a look at the member variable
Child of the node
A list that stores the child of a divided quadrant
has been declared
If these children are created
there will always be four
Next, in order to store every list of object
set in the current node
I have created another list called items
And to show the current depth of the node
A Depth member variable has been declared
Next, managing the whole quadtree
meaning the quadtree object
A variable Tree has been declared to save the reference
To find the parent node
I have added another reference called Parent
But it isn't actually used
I made it just in case
Next, in order to assign the area of the current node
AABB area
To save the Bounding Box area
I have added it as a member variable
Then, let's take a look at the process of
adding an item to the node
It is proceeded through an Insert function
The first step for an Insert function
to invoke a function called TestRegion
To check out the condition of the AABB area
of the given item
The output will be put as result
Press F12 for the given code
To enter the function code
This code is invoking a function called GetQuads
This is a function called GetQuads
It is declared right on top when you press F12
The role of this function is to determine
information about the overlapping quadrant with the AABB area
So first, the overlapping output
This index
The value of top left side and top right side as I mentioned
It is designed so that
the lists overlapping the index is returned
To determine this
First, we have to calculate the four separated value
So using minimum and maximum value
We should check which area it overlaps with
And combining these together
The list of quadrant should be added over here
Considering the negative x and positive y, it should be a top left side
Then positive x, positive y will be a top right side
Searching for every area that is overlapping
We make a list and return it
This is how it is returned
It is impossible to have no return value
But I have just inserted it
If there is one returned value
It means that it is enclosed in a certain area
The list has been invoked only one time out of four
In this case, out of the four areas
It means that it is completely enclosed in one
If it isn't the case, it means that
it has to be enclosed in two or more areas
For this instance, it will overlap for sure
At this point, an enumeration value called STRADDLING
will be returned to mark the overlapping
We have taken a look at how the TestRegion function is used
The output is either STRADDLING
or a quadrant value that is completely enclosed will be return
For the case of overlapping
I have mentioned that you can just add to the object list of the current node
So add the object list of the current node
And for cases where it doesn't overlap
Except for the situation of OUTOFAREA
It will be one out of four
It would be one out of four
so we can first operate the partitioning
We will operate the quarter division
I will press F12 to take a look at the division code
If the depth of the current node is
at the maximum depth which was set by the tree
The division is unnecessary
therefore return the false
But if that is not the case
There is a need for additional division
But there is a possibility that this node has already been divided
So I have added a property called IsSplitted
If children
In other words, list that manages the divided node
The value of children isn't null
It will always be four
If the count is bigger than 0, it means it is already divided
In that case, the child node doesn't need to be created
Press Ctrl - to go back to the previous code
If it hasn't been divided
Just operate the division
So if it has not been divided
Create half the size of the current node
Half of each side
Create an AABB area with half the length
Add another value that will move the center of AABB
There will always be four children
List objects with 4 Capacity
Create a list object
Then using the Offset value
Each divided child node's area
has to be assigned
Previously, I said the order needs to be same as the enumeration
I will start creating from the top left side
The top left side has a x value of minus
I will multiply (-2) to the x value in order to convert to a plus
So the root and itself which is a parent node
Then a bounding volume of a new child node
AABB area needs to be assigned
In this case, the center of the current node I have
moved as much as the Offset value will be the center of the child node
And reduced to half the length
Create a node based on the assigned size of the area
but lastly add 1 to the depth value
Next, the top right side
The b Offset value which was used for the
original top left side will be reused
Since we multiplied a minus, it would be -1
So we multiply a minus again to make it into a plus
And assign it in the same way
The top right node is created
Next, to get to the bottom right side
Multiply -1 to the y value and move it to the bottom
and multiply -2 to the x value
and move it to the left
It will lead to a bottom left node
If we have finished everything
Go back to the code before
If the Split is operated, add to the child
Since the output has been produced
The child which has been set as one of the four
will be invoked recursively
to the Insert function
If it meets the limit
goes until maxDepth
It would return the false
Then it could be implemented by
adding to the current object list
We have learned how the insertion function of quadtree
can be implemented
Now we will take a look at drawing functions related to insertion
Double click the quadtree manager
Let's take a look at a function placed in the bottom called onDrawGizmos
This function has ExecuteinEditMode
which is an attribute that has been declared
We don't need to press play
instead, it is set to draw the entire area of the quadtree on the editor
If you look over here, marked with gray
The function is invoked so that it would draw the entire area of the quadtree
And for cases where there is a quadtree
Using a function of quadtree called DrawBounds
The entire area that quadtree has
will be drawn by the function being invoked
If it isn't being operated, the tree value is null
so they won't be drawn
Now let's take a look at the DrawBounds function of quadtree
For the case of DrawBounds function of quadtree
It is simply delivering commands to root node
It invokes the DrawBounds function that root node has
If we take a look at this DrawBounds function that root node has
It is placed in the bottom
First, it draws the Wirecube of itself
In other words, only the boundary
It assigns the center and size to draw only the boundary
Next, mark the object list in the center
The object list which the current node has
Using Label function
Mark the object list in the center of the node
Let's say there is a child to the node
and if it is separated
It gives an order to explore every child
and draw a boundary
But if this is the terminal node
Only for the cases with current item
a crosshair of the x-axis and y-axis
A code that draws the crosshair has been added
If every node has been drawn through this process
Go back to the quadtree manager
First, for the objects that have been inserted
with this sky blue color, a bright blue color
Color the inside through the DrawCube function
and mark it
For the objects that will be inserted later on
A code has been implemented to color it red
We have looked over the insert function of the quadtree
Let's look over the result by implementing it once again
Press play
It being added one by one by dividing
and the procedure of the drawing
We have explained the code
so I believe that you will be able to understand
If you inspect it one step at a time by debugging it on your own
It will be better for you
Let's take a look at the implementation of query function
For the query function, first go over to the scene
Let's double click the quadtree query scene and open it
Open the given scene and play it
The 9 objects that we have set
can be seen and already inserted
The AABB area that is marked red on the screen and
A query button on the game view
I will press this
If you press the query button
The area will be marked yellow
The object that overlaps with the area
will be marked as purple
And to every node that was searched to detect this
The boundary has been colored with purple
And next the area to proceed the query
was marked red
If you press the Query button, to determine the collision detection
between the object that overlaps and the area
The nodes that have been searched
will be colored as purple
This is the three query area that I have prepared
For these query areas, as you can see
It is assign from Query 1, 2, 3
which is a game object
Similar to what I did previously, this game project
has a special tag attached called Query
Then how this query function is implemented
will be taught through looking at the code
Going back to the quadtree manager
For the query function
This variable called DrawMode
was assigned as a Query instead of Insert
If you go to the actual Unity, this DrawMode
can be seen set as a Query
Then, during the initialization process
Every object of the game object which is set as Query
is saved in this place called queryObjects
If the drawing mode is set as Query
It invokes the InsertAll function
It adds every game objects
in this current insert object
Then, we can start from every object being added
when we operate query
After the preparation is finished
We invoke the Query function that is provided
to operate the query
The general mechanism is similar to what I explained
So, it will proceed to a total of three objects
Every time the button is pressed, it will proceed
If you look at the canvas here, the button
You can see the binding to the Query function
You can see it over here
For the case of Query function, the query has to be done now
Every list of node that is possible needs to be brought
Therefore, the ones with possibility
to save the list of nodes
A List object needs to be created
and it is designed to pass as an argument
And the instance of quadtree
which actually executes the quadtree
invokes the Query function
Looking at the Query function, as we did before
It invokes the Query function of root node
bringing in every list of the node that is possible
If the list of every node that is possible is brought in
Every item in the list, every object list
identifies every item that overlaps with the assigned area
Adds to intersects which is a List object
and the code is designed so that it will return
Now, the function that searches for every possible node
We will take a look at the Query function of this node
Let's move over to the node's Query function
Over here, it adds the current self first
It adds the node of itself first
And if it is divided
Every child that is divided will
invoke the Query function again
It will proceed the call recursively
using the GetQuads function that I've mentioned before
Making sure that it will operate on the quadrant area that encloses the given area
The logic was designed so that it could be operated in such effective way
Through this, every node information
that has overlapping possibility was acquired
Now we will take a look at the drawing function
The List that was brought
will be saved to a variable of the manager called intersectObjects
This could help with the drawing
When drawing the queried area first
Mark it with a red color
For the queried area
the logic was designed to mark it as yellow
Next a variable called possibleNodes
It meant every node
that had the possibility of overlapping with the queried area
So every node of that area was colored as purple
Areas that are actually determined to overlap with the queried area
which are called AABB area
It was designed to be drawn with purple coloring
This is it for today's lecture
I appreciate your effort to take the class
Thank you
Quadtree Overview Overview of Quadtree In space partitioning, it refers to a tree-like data structure with four children Always has a complete tree form with all children filled
Point quadtree: Used to find close location in a 2D plane efficiently Range quadtree: Used to find objects with overlapping areasin a 2D plane
Usage of quadtree in games Detects collision handling of two objects in a 2D plane space Used for collision handling in 2D platformer
Used for visibility check and collision handling in Top Down view shooter games Often use AABB bounding volume for collision handling
Primarily used to filter unnecessary objects for detection
Mechanism of Quadtree The basics of Quadtree Every node of quadtree has a unique rectangular AABB area and object list Creates rectangular AABB area that surrounds the area and assigns it as node
The further it moves down to the child, it maintains the complete tree form with four children Object Insertion: Adds object with AABB area to a node's object List
Collision query: Identifies the AABB area given from the object list of the node and the colliding object
Mechanism of Quadtree Mechanism of Insert function Comparison of AABB area to insert the object and the AABB area of a quadtree
Partitioning: Dividing the quadtree area into an even 4 and assigning each as a child node Partitioning is operated when the AABB area of the inserting object is enclosed of the child node's area
When it lies on the boundary of current and child node's area, add to the object list of the current node Repeat recursively from the child node that is completely enclosed
Generally regulated to a certain extent of depth The side length of a quadrant with certain depth Ldepth=W/2depth (W is the side length of root node)
Mechanism of Query function Function to identify if the AABB area collides with the object inside the Quadtree Identifies the Quadrant node that encloses the AABB area which will be queried
Searches for collision in the object list of each quadrant node