QuadTree

GitHub

Goal:

• To be able to stand up a quad tree in the time it takes to write the code
• To structure the code to be easily implemented in differing situations.

Exploring a QuadTree in Unity.

• test case is 1000 balls, each checking the other 999 for collision
• using GlobalClass as singleton
• graphic representation of quad rectangles (on/off)
• compare cntSearch between n*n vs nLOGn search counts
• compare frame rate
• uses circle range to request nearest ball

Classes & Structs

• GlobalClass: global switches and data such as balls data
• QTRectStruct: used by quad tree
• QTCircleStruct: used to select from quad tree (since ball data is round)
• QTDataStruct: used for ball data (pos and dataIndex)
• QTQuadClass: creates quads, selects and inserts data

QuadTreeDemo

GlobalClass

QTQuadClass

BallStruct

QTDataStruct

QTRectStruct

QTCircleStruct

UI

Benchmarks

Quad Tree Based Collision Avoidance

Using a quad tree with capacity = 1, one quad is created for each ball, as the quad tree is re-initialized each frame. As each ball is inserted into the quad tree, the order of insertion determines the quad tree level and the size of the quad. The top level quad is initialized to "screen size", empty with capacity = 1. The first ball matches the top level quad, and is added to it. The second ball first matches the top level quad (all balls will). It finds that it's at capacity (1), and creates a quarter size quad in the quadrant that it matches at second quad level. The third ball, depending on its location, will match the top level quad finding it full, tests the quadrant that it matches. If a sub-quad already exists, the ball tries to join it. If the matching sub-quad doesn't exist, one is created for that quadrant and joined.

Quads

A new quad is created empty with no points joined to it. With capacity = 1, each quad can only hold one ball. Therefore, 1000 balls will create 1000 quads, with capacity = 1. Each quad is created by a "parent" quad, is one quarter its parent's size. Each quad can have up to four children or sub-quads. Each quad can also be associated with one ball (capacity = 1).

Collision Avoidance

If we associate quad level with height, we see capacity = 1 means that there will be only one ball per quad level. The height can be the safe vertical distance between balls at speed.