🔨 Spatial partitioning of entities / octree implementation

I affirm:

[x] I understand that if I do not agree to the following points by completing the checkboxes my issue will be ignored.
[x] I have read and understood the Contributing Guide and the Code of Conduct.
[x] I have searched existing issues to see if the issue has already been opened, and I have checked the commit log to see if the issue has been resolved since my server was last updated.

Describe the feature

Currently, we don't really have a proper broad-phase culling phase for looking up "entities near me" or "entities near this point". We either go through the whole entity lists in a zone for mobs/npcs/players etc. or we piggyback on the spawnLists we generate for players - which are built exhaustively I think.

This is fairly easily solved by using linear spatial partitioning, or something like an octree.

// Concept to ensure the class has position methods (CBaseEntity)
template<typename T>
concept HasPositionMethods = requires(T a)
{
    { a.GetXPos() } -> std::convertible_to<float>;
    { a.GetYPos() } -> std::convertible_to<float>;
    { a.GetZPos() } -> std::convertible_to<float>;
};

template<typename TFloatType>
class OctreeNode
children, bounds, payload(s), etc.

template<typename TFloatType = float>
class EntityOctree
{
public:
    template<typename T>
    requires HasPositionMethods<T>
    void insert(T* entity)

    template<typename T>
    requires HasPositionMethods<T>
    std::vector<T*> getNearby(T* entity, TFloatType distance)

Then it's up to the implementer to MEASURE and find out if it makes more sense to rebuild the octree at the start of every tick, or if it should live longer and have entities added and removed from it and then rebalanced. It's important that the octree either never holds pointers to entities that might be gone, or it is able to check and remove them from itself.

I started tinkering with an octree yesterday, and came to the conclusion that the potential cost of constant removal/reinsertion of entities as they move during a tick would trigger too many rebalances, and the cost could get out of hand. So, instead I got the chat-gpt special for linear spatial hashing, which looks to be a good solution.

#include <unordered_map>
#include <vector>
#include <cmath>
#include <iostream>

struct position_t {
    float x = 0.0f;
    float y = 0.0f;
    float z = 0.0f;
};

struct location_t {
    position_t p;
};

class CBaseEntity {
public:
    location_t loc;
    uint32_t   id;
};

struct GridCell {
    std::vector<CBaseEntity*> entities;
};

class SpatialGrid {
public:
    SpatialGrid(float cellSize)
        : cellSize(cellSize) {}

    void AddEntity(CBaseEntity* entity);
    void RemoveEntity(CBaseEntity* entity);
    void UpdateEntity(CBaseEntity* entity);
    std::vector<CBaseEntity*> QueryEntitiesWithinDistance(const position_t& point, float distance);

private:
    std::unordered_map<int64_t, GridCell> grid;
    float cellSize;

    int64_t ComputeCellKey(const position_t& position) const;
    void GetSurroundingCells(const position_t& point, float distance, std::vector<int64_t>& surroundingCells) const;
};

int64_t SpatialGrid::ComputeCellKey(const position_t& position) const {
    int x = static_cast<int>(std::floor(position.x / cellSize));
    int y = static_cast<int>(std::floor(position.y / cellSize));
    int z = static_cast<int>(std::floor(position.z / cellSize));

    // Create a unique key for each cell
    int64_t key = (static_cast<int64_t>(x) << 32) | (static_cast<int64_t>(y) << 16) | static_cast<int64_t>(z);
    return key;
}

void SpatialGrid::AddEntity(CBaseEntity* entity) {
    int64_t cellKey = ComputeCellKey(entity->loc.p);
    grid[cellKey].entities.push_back(entity);
}

void SpatialGrid::RemoveEntity(CBaseEntity* entity) {
    int64_t cellKey = ComputeCellKey(entity->loc.p);
    auto& cell = grid[cellKey].entities;

    // Remove the entity from the cell's vector
    cell.erase(std::remove(cell.begin(), cell.end(), entity), cell.end());
}

void SpatialGrid::UpdateEntity(CBaseEntity* entity)
{
    RemoveEntity(entity);
    AddEntity(entity);
}

std::vector<CBaseEntity*> SpatialGrid::QueryEntitiesWithinDistance(const position_t& point, float distance) {
    std::vector<CBaseEntity*> result;
    std::vector<int64_t> surroundingCells;

    GetSurroundingCells(point, distance, surroundingCells);

    float distanceSquared = distance * distance;

    for (int64_t cellKey : surroundingCells) {
        if (grid.find(cellKey) != grid.end()) {
            for (CBaseEntity* entity : grid[cellKey].entities) {
                float dx = entity->loc.p.x - point.x;
                float dy = entity->loc.p.y - point.y;
                float dz = entity->loc.p.z - point.z;
                float distSq = dx * dx + dy * dy + dz * dz;

                if (distSq <= distanceSquared) {
                    result.push_back(entity);
                }
            }
        }
    }

    return result;
}

void SpatialGrid::GetSurroundingCells(const position_t& point, float distance, std::vector<int64_t>& surroundingCells) const {
    int minX = static_cast<int>(std::floor((point.x - distance) / cellSize));
    int minY = static_cast<int>(std::floor((point.y - distance) / cellSize));
    int minZ = static_cast<int>(std::floor((point.z - distance) / cellSize));

    int maxX = static_cast<int>(std::floor((point.x + distance) / cellSize));
    int maxY = static_cast<int>(std::floor((point.y + distance) / cellSize));
    int maxZ = static_cast<int>(std::floor((point.z + distance) / cellSize));

    for (int x = minX; x <= maxX; ++x) {
        for (int y = minY; y <= maxY; ++y) {
            for (int z = minZ; z <= maxZ; ++z) {
                int64_t key = (static_cast<int64_t>(x) << 32) | (static_cast<int64_t>(y) << 16) | static_cast<int64_t>(z);
                surroundingCells.push_back(key);
            }
        }
    }
}

int main() {
    SpatialGrid grid(10.0f);

    // Create and add entities
    CBaseEntity* entity1 = new CBaseEntity();
    entity1->loc.p = {10.0f, 20.0f, 30.0f};
    grid.AddEntity(entity1);

    CBaseEntity* entity2 = new CBaseEntity();
    entity2->loc.p = {15.0f, 25.0f, 35.0f};
    grid.AddEntity(entity2);

    // Query entities within 50 units of a point
    position_t queryPoint = {12.0f, 22.0f, 32.0f};
    float queryDistance = 50.0f;
    auto entities = grid.QueryEntitiesWithinDistance(queryPoint, queryDistance);

    // Things happen
    grid.UpdateEntity(entity1);
    grid.UpdateEntity(entity2);

    // Output results
    for (CBaseEntity* entity : entities) {
        std::cout << "Entity ID: " << entity->id << " at (" 
                  << entity->loc.p.x << ", " 
                  << entity->loc.p.y << ", " 
                  << entity->loc.p.z << ")" << std::endl;
    }

    // Clean up
    delete entity1;
    delete entity2;

    return 0;
}

LandSandBoat / server

🔨 Spatial partitioning of entities / octree implementation #5196

Describe the feature