SAPDivision.h

/* Copyright (C) 2013 Wildfire Games.
 * This file is part of 0 A.D.
 *
 * 0 A.D. is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * 0 A.D. is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef INCLUDED_SAPDIVISION
#define INCLUDED_SAPDIVISION

#include <vector>
#include "Vector234.h"
#include "GuiObject.h"


/**
 * A simulated Entity object for this demo alone. The pyrogenesis Entity is completely different,
 * but its semantics remain the same. Entities have position, size and range.
 */
struct CEntityHandle
{
    Vector2 pos;
    Vector2 size;
    float range;
    GuiText text;
    inline CEntityHandle(const Vector2& pos) : pos(pos), range(10.0f)
    {
        size.x = float((rand() % 20) + 20);
        size.y = float((rand() % 20) + 20);
    }
    inline CEntityHandle(const Vector2& pos, const Vector2& size) : pos(pos), size(size), range(10.0f)
    {
    }
};


/**
 * SAPDivision entity handle
 * Contains X axis index for fast random access
 */
struct SAPHandle
{
    int index;              // index in X axis
    CEntityHandle* entity;  // pointer to the entity object with some data
};


/**
 * SAPDivision entity node
 * Contains entity BOUNDS, POSITION and pointer to SAPHandle that owns the index
 */
struct SAPNode
{
    float x_min, x_max; // ------| object |------> axis : the object BOUNDS
    float z_min, z_max;
    float x_pos, z_pos; // object position X & Z
    union {
    SAPHandle* handle;  // pointer to handle that owns the index
    struct {int a,b;};  // force 32-byte alignment
    };
};




/**
 * A range query structure for fast queries
 */
struct SAPRangeQuery
{
    enum { MAX_COUNT = 2048 };
    struct Result
    {
        float sqrange;      // squared range
        SAPHandle* handle;  // entity handle
    };
    int count;
    Result items[MAX_COUNT];

    inline SAPRangeQuery() : count(0) {}
    inline const Result& operator[](int index) const { return items[index]; } // read-only
    inline int size() const { return count; }
    inline void clear() { count = 0; }
};


/**
 * Sweep and Prune spatial subdivision - Great for rangefinding.
 */
class SAPDivision
{
    std::vector<SAPNode> m_XAxis;       // we only need X axis for sweeping
    std::vector<SAPHandle*> m_LiveHandles;  // currently used handles
    std::vector<SAPHandle*> m_FreeHandles;  // reuse handles if possible
public:
    SAPDivision();
    ~SAPDivision();

    SAPDivision(const SAPDivision& rhs);
    SAPDivision& operator=(const SAPDivision& rhs);

private:
    SAPHandle* AllocHandle();


public:

    /**
     * Clears the current state, but doesn't free any SAPHandle's
     */
    void Clear();

    /**
     * Destroys the current state, deleting all handles
     */
    void Destroy();

    /**
     * @brief Inserts a new entity into the subdivision map as a bounding box.
     * @param entity Entity to insert
     * @param toMin Entity world BOUNDING BOX min
     * @param toMax Entity world BOUNDING BOX max
     */
    SAPHandle* Insert(CEntityHandle* entity, const Vector2& toMin, const Vector2& toMax);

    /**
     * @brief Inserts a new entity into the subdivision map as a point.
     * @param entity Entity to insert
     * @param to Point in world.
     */
    inline SAPHandle* Insert(CEntityHandle* entity, const Vector2& to)
    {
        return Insert(entity, to, to);
    }

    /**
     * @brief Removes an entity from the subdivision map.
     * @param handle SAPEntity handle to erase.
     */
    void Remove(SAPHandle* handle);

    /**
     * @brief Moves an entity by the given amount. Very cheap - simple shift in the Axis.
     * @note For small moves the entity is shifted in the SAP axises. Large moves shift the axis array.
     * @param handle SAPEntity handle to move.
     * @param pos The new position where to move the entity.
     */
    void Move(SAPHandle* handle, const Vector2& pos);

    /**
     * @brief Get entities in range of a BOUNDING BOX.
     * @note This is used by OBSTRUCTION MANAGER.
     * @param inrange [out] The resulting array of entities in range. Sorted from nearest to furthest.
     * @param min Bounding box minimum.
     * @param max Bounding box maximum.
     */
    void GetInBoundingBox(SAPRangeQuery& inrange, const Vector2& min, const Vector2& max);

    /**
     * @brief Get entities in range of a RADII.
     * @note This works differently from GetInBoundingBox and is MUCH FASTER!! Used by RANGE MANAGER.
     * @param inrange [out] The resulting array of entities in range. Sorted from nearest to furthest.
     * @param pos Center of the range query.
     * @param range RADII of the range query.
     */
    int GetInEntityRange(SAPRangeQuery& inrange, SAPHandle* handle, float range);
};


#endif