top of page
  • Foto do escritorYves "Jack" Albuquerque

The Ultimate Guide for Spatial Structures

version: 0.01 (draft)

Spatial structures are the unsung heroes in gaming, orchestrating seamless gameplay by managing spatial data efficiently. From detecting collisions to creating vast virtual worlds, these data structures are integral to a game's performance. Let’s delve into these spatial structures by splitting them into two main families: hierarchical and non-hierarchical.


1. Non-Hierarchical Structures: Simplicity Meets Speed

These structures excel at straightforward spatial division, prioritizing ease of use and efficiency.


Grid-Based Structures

Uniform Grid


Description: Imagine dividing your entire game world into neat squares (2D) or cubes (3D), where each cell is a part of a consistent grid system.


Function: Every object is neatly placed into a cell based on its coordinates, enabling rapid searches by checking neighbouring cells.


Usage: Ideal for collision detection in 2D platformers or unit tracking in simple strategy games.


Sparse Grid


Description: Takes the concept of the uniform grid but optimizes it by storing only non-empty grid cells, eliminating wasteful empty space.


Function: Dynamically creates and stores grid cells only when they contain objects, reducing unnecessary memory usage.


Usage: Perfect for vast, open-world games where objects are sparsely distributed, keeping the data footprint light.


Spatial Hashing Structures

Spatial Hash Table


Description: Instead of relying on grids, it uses a hash function to map spatial coordinates to unique identifiers in a hash table, quickly finding which "bucket" contains an object.


Function: When an object moves, its coordinates are hashed into a bucket for fast, near-instant lookups of neighbouring objects.


Usage: Tailored for collision detection and physics in fast-paced fighting games or RTS titles where immediate neighbourhood checks are critical.


Closing Thoughts

Non-hierarchical structures are your go-to for straightforward spatial organization in games where simplicity and quick data access are essential. Whether managing a grid-based world or hashing coordinates into buckets, these structures offer swift performance boosts for efficient spatial queries.


Step Further

As we can see, each of the solutions above have their pros and cons. Uniform Grids are simple to implement, Sparse Grids avoid useless memory allocation and Spatial Hash table it's easier and faster to access specific parts of the grid. What about put it all together and make a Grid that only allocates where is needed and that can be accessed as a Spatial Hash Table?


Hybrid Non-Hierarchical Grid

Description: Imagine a grid that adapts, an intelligent structure that only allocates space when needed and allows for hashing-style quick access. This concept brings together the best aspects of the uniform and sparse grids with the rapid access of spatial hashing tables, creating a supercharged spatial structure for complex game environments.


  • Dynamic Allocation: By integrating the concept of a sparse grid, this hybrid grid allocates cells only when they contain objects. This adaptability saves memory and boosts efficiency, particularly useful in large, open-world games where player interactions and environmental elements are unpredictably scattered.

  • Quick Access: By employing a hashing mechanism within the grid structure, each cell or bucket can be accessed in constant time. This method is essential for games that require instantaneous data retrieval, such as high-speed multiplayer shooters or real-time simulations.


In the example below we used a dictionary and mapped each hash position using a Vector3Int. We also are able to convert world position to this hash key:


public class Grid<T>
{
    private Dictionary<Vector3Int, List<T>> grid;
    private float cellSize;
    public Bounds Bounds { get; private set; }
    public Grid(Bounds bounds, float cellSize = 1)
    {
        this.Bounds = bounds;
        this.cellSize = Mathf.Max(0.01f, cellSize);
        this.grid = new Dictionary<Vector3Int, List<T>>();
    }
    public void Add(Vector3Int index, T item)
    {
        if (!grid.ContainsKey(index))
        {
            grid[index] = new List<T>();
        }
        grid[index].Add(item);
    }
    public void Add(Vector3 position, T item)
    {
        Vector3Int cellIndex = WorldToCell(position);
        Add(cellIndex, item);
    }
    public bool Remove(Vector3Int index, T item)
    {
        if (grid.ContainsKey(index))
        {
            return grid[index].Remove(item);
        }
        return false;
    }
    public bool Remove(Vector3 position, T item)
    {
        Vector3Int cellIndex = WorldToCell(position);
        return Remove(cellIndex, item);
    }
    public List<T> GetItems(Vector3Int index)
    {
        if (grid.ContainsKey(index))
        {
            return grid[index];
        }
        return new List<T>();
    }
    public List<T> GetItems(Vector3 position)
    {
        Vector3Int cellIndex = WorldToCell(position);
        return GetItems(cellIndex);
    }
    private Vector3Int WorldToCell(Vector3 position)
    {
        return new Vector3Int(
            Mathf.FloorToInt((position.x - Bounds.min.x) / cellSize),
            Mathf.FloorToInt((position.y - Bounds.min.y) / cellSize),
            Mathf.FloorToInt((position.z - Bounds.min.z) / cellSize));
    }

}

2. Non-Hierarchical Structures: Simplicity Meets Speed

Hierarchical spatial structures are pivotal for managing complex spatial data in gaming. These structures facilitate efficient querying and manipulation of data by organizing it into nested, multi-level formats. These structures are especially crucial in games with intricate environments or variable object distributions. Here’s a structured look at these key hierarchical structures, grouped by their core partitioning approaches.


1. Tree-Based Partitioning Structures

These structures rely on a tree-like hierarchy where each node represents a spatial region, and its children represent further subdivisions. This method is versatile, supporting different dimensions and levels of complexity.


Quadtree

Description: Divides 2D space into four quadrants at each node, with further subdivisions as necessary, optimizing storage and querying in two-dimensional environments.


Octree

Description: Applies the quadtree concept to three dimensions, splitting space into eight cubic regions at each node, ideal for 3D spatial management.


KD-Tree (K-Dimensional Tree)

Description: Splits space along k dimensions, using planes perpendicular to the axis of the dataset’s dimensions, adaptable to the complexities of the data.


R-Tree

Description: Uses bounding rectangles to organize spatial data, with each node containing the minimum bounding rectangle that encloses all child nodes, streamlining range queries and searches.


2. Binary Space Partitioning Structures

Binary Space Partitioning (BSP) uses planes to divide space, facilitating dynamic scene management and rendering optimizations.


BSP Tree

Description: Employs arbitrary planes for dividing space, crucial in graphics for rendering order and managing object visibility in complex scenes. This flexibility in plane selection allows for highly tailored spatial partitioning.


3. Bounding Volume Hierarchies (BVH)

Bounding Volume Hierarchies organize objects using bounding volumes as tree nodes, which encase single or multiple objects. This structure is fundamental for reducing the computational overhead in collision detection and ray tracing by enabling quick exclusion of non-intersecting objects.


BVH Tree

Description: Organizes objects within bounding volumes such as spheres, boxes, or capsules. Each node in the tree represents a volume that contains all child volumes, streamlining intersection tests and spatial queries by eliminating large swathes of non-intersecting objects efficiently.

1 visualização0 comentário

Posts recentes

Ver tudo

Comments


bottom of page