Spatial-Partitioning-Quadtree

I am Carlos Peña Hernando, student of the Bachelor’s Degree in Video Games by UPC at CITM. This content is generated as a game development research for learning purposes at my free time.

About the project

This project contains a research about spatial partitioning algorithms and its applications in game development, used as an advance to optimize generally problem-solving algorithms when we have to check and order a sizable amount of elements. This research wraps up with a demo application focused on the scope of Region-Point Quadtree as approached method to test its potential optimization comparing it with force brute method when we are checking collisions at run-time.

You can find information about Spatial Partitioning in my website.

You can find the source code at my github repository.

Demo Application

As a little sneak peek, the following gif shows you up the final result of the project demo using my Quadtree code to optimize considerably at collision checking.

Collision system optimized using Quadtree method

XML-based Quadtree configuration

Basic and simple configuration about Quadtree's properties using xml:

• X & Y values
• Width & Height values
• Depth (max depth of quadtree)
• Capacity / Bucket Size (max capacity of quadtree)

Compile-time Quadtree code

Quadtree code works as a multiple data-type container to fit with diferent sort of elements (colliders, entities, particles, tiles, gameobjects, etc) with the same logic. Therefore, it turns out more type safety code capable of doing generalizations for many API's and avoids redundant code and its repetition if we need to work with another data-type elements. Evaluated at compile-time and can increase its performance (as an alternative to polymorphism).

• Template-based Quadtree container generic class
• Easy to integrate (Just 2 Header files)
• Readable & easy to use

Straight-forward steps:

• allocate memory to a Quadtree pointer with a given data type

Quadtree<T>* qtree = new Quadtree<T>(x,y,w,h,capacity,depth);

• Insert elements to Quadtree

qtree->Insert(array<T>);

• Check its relative position every frame querying to found array

qtree->found.clear();
qtree->query(qtree->found(T));

• Clean it up when application run out!

qtree->CleanUp();

more information about my Quadtree code in my website.

Installing

• Download last release from releases tab from the repository
• Unzip Quadtree.zip
• Execute Quadtree.exe

Controls

• F1 - Enable / Disable debug draw colliders

• F2 - Switch between Brute Force & Quadtree optimization methods

• F3 - Enable / Disable debug draw Quadtree

• 1 - Insert one static entity

• 2 - Insert one dynamic entity

• 3 - Insert 1000 dynamic entities (for framerate checking purposes)

Built With

• Visual Studio - IDE
• SDL - Development library
• STL - Development library
• PugiXML - XML processing library
• Brofiler - Profiler
• Tiled - Creating maps

Author

Carlos Peña Hernando - GitHub account: CarlosUPC Contact: charlieph.upc@gmail.com

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Previous learning tests coding a Quadtree

Quadtree Performance Test.

Collision System Performance with Quadtree Test.

Acknowledgements and Webgraphy

Wikipedia.

genbeta.com.

the coding train.

Space Partitioning

Quadtree implementations 1

Quadtree implementations 2

Octree

Quadtree and Octree

Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

K-D Tree Implementation 1

K-D Tree Implementation 2

K-D Tree Implementation 3

K-D Tree VS Quadtree

K-D Tree VS Quadtree

Quadtrees and Hilbert Curves

JavaScript QuadTree Implementation

Pyramid Panic - Feature - QuadTree Optimizations

Examining Quadtrees, k-d Trees, and Tile Arrays

Teoría de colisiones 2D: QuadTree

AABB Trees for Collision Detection

Quadtrees – Hierarchical Grids

jimkang.

GeeksforGeeks.