325 lines
8.1 KiB
C++
325 lines
8.1 KiB
C++
#pragma once
|
|
|
|
#include "UnrealProject.h"
|
|
#include <unordered_set>
|
|
using namespace std;
|
|
|
|
|
|
class ACharacterBase;
|
|
namespace MiniMap
|
|
{
|
|
struct Rect
|
|
{
|
|
Rect() = default;
|
|
Rect(float x, float y, float width, float height) : x(x), y(y), width(width), height(height) {}
|
|
Rect(const FVector2D& position, const FVector2D& size) : x(position.X), y(position.Y), width(size.X), height(size.Y) {}
|
|
float x;
|
|
float y;
|
|
float width;
|
|
float height;
|
|
|
|
inline FVector2D position() const
|
|
{
|
|
return FVector2D(x, y);
|
|
}
|
|
inline FVector2D size() const
|
|
{
|
|
return FVector2D(width, height);
|
|
}
|
|
inline bool contains(const FVector2D& pos) const
|
|
{
|
|
return pos.X >= x && pos.X <= (x + width) && pos.Y >= y && pos.Y <= (y + height);
|
|
}
|
|
};
|
|
|
|
|
|
inline Rect GetSubArea(const Rect& area, size_t idx)
|
|
{
|
|
const FVector2D half_size = area.size() / 2;
|
|
const FVector2D position = area.position();
|
|
switch (idx)
|
|
{
|
|
case 0: return Rect(position, half_size);
|
|
case 1: return Rect(position + FVector2D(half_size.X, 0), half_size);
|
|
case 2: return Rect(position + half_size, half_size);
|
|
case 3: return Rect(position + FVector2D(0, half_size.Y), half_size);
|
|
}
|
|
return area;
|
|
}
|
|
inline bool RectCircleOverlapSquared(const Rect& area, const FVector2D& position, float radius_sqr)
|
|
{
|
|
const FVector2D pos = area.position();
|
|
const float left = area.x;
|
|
const float bottom = area.y;
|
|
const float right = area.x + area.width;
|
|
const float top = area.y + area.height;
|
|
|
|
const float x = position.X > right ? right : position.X < left ? left : position.X;
|
|
const float y = position.Y > top ? top : position.Y < bottom ? bottom : position.Y;
|
|
|
|
return FVector2D::DistSquared(position, FVector2D(x, y)) <= radius_sqr;
|
|
}
|
|
|
|
class NonCopyable
|
|
{
|
|
public:
|
|
NonCopyable() = default;
|
|
NonCopyable(const NonCopyable& other) = delete;
|
|
NonCopyable& operator=(const NonCopyable& other) = delete;
|
|
};
|
|
|
|
class MinimapHandle;
|
|
class NodeBase : private NonCopyable
|
|
{
|
|
protected:
|
|
NodeBase(const Rect& area, NodeBase* parent) : area(area), parent(parent) {}
|
|
|
|
public:
|
|
virtual void AddObject(MinimapHandle& obj) = 0;
|
|
virtual void RemoveObject(MinimapHandle& obj) = 0;
|
|
virtual void ClearRecursive()
|
|
{
|
|
objects.clear();
|
|
}
|
|
virtual void ResizeRecursive(const Rect& area)
|
|
{
|
|
this->area = area;
|
|
}
|
|
|
|
virtual void CircleOverlap(const FVector2D& position, float radius_sqr, TArray<MinimapHandle*>& out_objects);
|
|
|
|
unordered_set<MinimapHandle*> objects;
|
|
Rect area;
|
|
NodeBase* parent;
|
|
};
|
|
|
|
class MinimapHandle : private NonCopyable
|
|
{
|
|
public:
|
|
MinimapHandle() : character(nullptr), node(nullptr), root(nullptr) {}
|
|
MinimapHandle(const FVector2D& position) : character(nullptr), position(position), node(nullptr), root(nullptr) {}
|
|
~MinimapHandle()
|
|
{
|
|
|
|
}
|
|
|
|
FVector2D position;
|
|
class ::ACharacterBase* character;
|
|
NodeBase* node;
|
|
NodeBase* root;
|
|
};
|
|
|
|
template<size_t level> class TreeNode : public NodeBase
|
|
{
|
|
public:
|
|
TreeNode(const Rect& area, NodeBase* parent) : NodeBase(area, parent), child0(GetSubArea(area, 0), this), child1(GetSubArea(area, 1), this), child2(GetSubArea(area, 2), this), child3(GetSubArea(area, 3), this) {}
|
|
|
|
typedef TreeNode<level - 1> child_type;
|
|
child_type child0;
|
|
child_type child1;
|
|
child_type child2;
|
|
child_type child3;
|
|
unordered_set<MinimapHandle*> child_objects;
|
|
|
|
virtual void AddObject(MinimapHandle& obj) override
|
|
{
|
|
child_type* children = &child0;
|
|
for (size_t i = 0; i < 4; i++)
|
|
{
|
|
if (children[i].area.contains(obj.position))
|
|
{
|
|
// Register to child
|
|
child_objects.emplace(&obj);
|
|
children[i].AddObject(obj);
|
|
return;
|
|
}
|
|
}
|
|
|
|
// Register to this node
|
|
objects.emplace(&obj);
|
|
obj.node = this;
|
|
}
|
|
virtual void RemoveObject(MinimapHandle& obj) override
|
|
{
|
|
// Check if present in children
|
|
auto find_child = child_objects.find(&obj);
|
|
if (find_child != child_objects.end())
|
|
{
|
|
child_type* children = &child0;
|
|
for (size_t i = 0; i < 4; i++)
|
|
children[i].RemoveObject(obj);
|
|
|
|
child_objects.erase(find_child);
|
|
}
|
|
else
|
|
{
|
|
// Remove from node
|
|
auto find = objects.find(&obj);
|
|
if (find != objects.end())
|
|
objects.erase(find);
|
|
}
|
|
}
|
|
virtual void ClearRecursive() override
|
|
{
|
|
child_type* children = &child0;
|
|
for (size_t i = 0; i < 4; i++)
|
|
children[i].ClearRecursive();
|
|
|
|
NodeBase::ClearRecursive();
|
|
child_objects.clear();
|
|
}
|
|
virtual void ResizeRecursive(const Rect& area) override
|
|
{
|
|
child_type* children = &child0;
|
|
for (size_t i = 0; i < 4; i++)
|
|
children[i].ResizeRecursive(GetSubArea(area, i));
|
|
|
|
NodeBase::ResizeRecursive(area);
|
|
}
|
|
|
|
virtual void CircleOverlap(const FVector2D& position, float radius_sqr, TArray<MinimapHandle*>& out_objects) override
|
|
{
|
|
if (!child_objects.empty())
|
|
{
|
|
child_type* children = &child0;
|
|
for (size_t i = 0; i < 4; i++)
|
|
{
|
|
child_type& child = children[i];
|
|
if (RectCircleOverlapSquared(child.area, position, radius_sqr))
|
|
child.CircleOverlap(position, radius_sqr, out_objects);
|
|
}
|
|
}
|
|
|
|
NodeBase::CircleOverlap(position, radius_sqr, out_objects);
|
|
}
|
|
};
|
|
template<size_t level> class RootNode : public TreeNode<level>
|
|
{
|
|
public:
|
|
RootNode(const Rect& area, NodeBase* parent) : TreeNode<level>(area, parent)
|
|
{
|
|
|
|
}
|
|
|
|
virtual void AddObject(MinimapHandle& obj) override
|
|
{
|
|
TreeNode<level>::AddObject(obj);
|
|
all_objects.emplace(&obj);
|
|
}
|
|
virtual void RemoveObject(MinimapHandle& obj) override
|
|
{
|
|
TreeNode<level>::RemoveObject(obj);
|
|
auto find = all_objects.find(&obj);
|
|
if (find != all_objects.end())
|
|
all_objects.erase(find);
|
|
}
|
|
virtual void ClearRecursive() override
|
|
{
|
|
for (auto iter = all_objects.begin(); iter != all_objects.end(); iter++)
|
|
{
|
|
(*iter)->node = nullptr;
|
|
(*iter)->root = nullptr;
|
|
}
|
|
all_objects.clear();
|
|
|
|
TreeNode<level>::ClearRecursive();
|
|
}
|
|
|
|
void Reparent(MinimapHandle& obj)
|
|
{
|
|
TreeNode<level>::RemoveObject(obj);
|
|
TreeNode<level>::AddObject(obj);
|
|
}
|
|
|
|
unordered_set<MinimapHandle*> all_objects;
|
|
};
|
|
template<> class TreeNode<0> : public NodeBase
|
|
{
|
|
public:
|
|
TreeNode(const Rect& area, NodeBase* parent) : NodeBase(area, parent)
|
|
{
|
|
|
|
}
|
|
|
|
void AddObject(MinimapHandle& obj) override
|
|
{
|
|
objects.emplace(&obj);
|
|
obj.node = this;
|
|
}
|
|
void RemoveObject(MinimapHandle& obj) override
|
|
{
|
|
auto find = objects.find(&obj);
|
|
if (find != objects.end())
|
|
objects.erase(find);
|
|
}
|
|
};
|
|
|
|
template<size_t depth> class QuadTree : private NonCopyable
|
|
{
|
|
public:
|
|
QuadTree() : m_root_node(Rect(0, 0, 1, 1), nullptr) {}
|
|
QuadTree(const Rect& area) : m_root_node(area, nullptr) {}
|
|
~QuadTree()
|
|
{
|
|
m_root_node.ClearRecursive();
|
|
}
|
|
|
|
void AddObject(MinimapHandle& obj)
|
|
{
|
|
if (obj.root == &m_root_node)
|
|
return;
|
|
if (obj.root != nullptr)
|
|
obj.root->RemoveObject(obj);
|
|
|
|
// Add object to root
|
|
m_root_node.AddObject(obj);
|
|
obj.root = &m_root_node;
|
|
}
|
|
void RemoveObject(MinimapHandle& obj)
|
|
{
|
|
if (obj.root == nullptr)
|
|
return;
|
|
if (obj.root != &m_root_node)
|
|
return;
|
|
|
|
// Remove from root
|
|
m_root_node.RemoveObject(obj);
|
|
obj.node = nullptr;
|
|
obj.root = nullptr;
|
|
}
|
|
|
|
void Update()
|
|
{
|
|
// Update positioning
|
|
for (auto iter = m_root_node.all_objects.begin(); iter != m_root_node.all_objects.end(); iter++)
|
|
{
|
|
MinimapHandle& obj = **iter;
|
|
|
|
if (!obj.node->area.contains(obj.position) && obj.node->parent)
|
|
m_root_node.Reparent(obj);
|
|
}
|
|
}
|
|
void Clear()
|
|
{
|
|
m_root_node->ClearRecursive();
|
|
}
|
|
void Resize(const Rect& area)
|
|
{
|
|
m_root_node.ResizeRecursive(area);
|
|
}
|
|
|
|
int32 Num() const
|
|
{
|
|
return int32(m_root_node.all_objects.size());
|
|
}
|
|
|
|
bool CircleOverlap(const FVector2D& position, float radius, TArray<MinimapHandle*>& out_objects)
|
|
{
|
|
out_objects.SetNum(0);
|
|
m_root_node.CircleOverlap(position, radius * radius, out_objects);
|
|
return out_objects.Num() > 0;
|
|
}
|
|
|
|
RootNode<depth> m_root_node;
|
|
};
|
|
} |