Table of Contents
Building off a Godot official RPG Demo, I used a quadtree data structure to implement a simple search and reveal positional system. This takes the form of a yellow slime you control, that as you move him forward, utilizes this quadtree to search the immediate area to find enemy slimes and reveals them.
The goal of this was to do a from scratch implmentation of an effecient way to locate objects via organizing and storing them by their positions.
You can think about a quadtree visually, which goes well with my usecase for a quadtree using positional data. A quadtree can be a representation of space divided into 4 rectangles or quadrants, each of those quadrants can cotain 4 children or contain another reactangle with 4 quadrants itself. This is an effecient way to store the spatial position of data, based on what quadrant they are in.
For example, we have a bunch of positional points and we want to query if some point p is range. We could compare every point in space to p, the brute force method that would take a long time. Or we could use the quadtree, which find the correct quadrant using time effecient recursive methods, by finding each of the ancestor quadrants until the correct quadrant is found and the children can check if the point is a child of the quadrant (found) or deemed not in range.
Why use a quadtree:
- A quadtree can take in spatial positioning data and offers good performance for insertion, removal and lookup.
- In a game, spatial data is constantly changing, you need fast performing structures to handle the retreival and processes of this data.
- Tha alternative would be a brute force approach of checking all intersections.
- Great for sparse data sets.
See more about quadtrees and spatial partitioning here:
Spatial Partition - Game Programming Patterns
Please refer to QT.cs and PlayerQT.cs for my personal code.
- Godot
- C#
This project was written with Godot Engine .NET v4.2.2 in compatibility mode.
Import project via Godot Build via Godot .NET builder
Use Godot editor play button. Use WASD to move.
Distributed under the MIT License. See LICENSE.txt for more information.