空洞武士笔记3
1.位运算管理物理碰撞层级
1.确定每个层的位掩码
当我们使用枚举类来实现碰撞层级时，是因为我们只有一对一的碰撞，当我们遇到一对多的碰撞。就需要新的解决方案。于是我们选择使位运算，将每个层级映射为位掩码。
以int为例，正常有32个bit位，即代表32个可用层级。每个物理层（collision layer）可以分配一个唯一的位标识（bit）。例如：
Layer 1：0001 (1)
Layer 2：0010 (2)
Layer 3：0100 (4)
Layer 4：1000 (8)
那么我们就可以使用一个int型来代表一个对象的层级。
enum class CollisionLayer
{
None = 0,
Player = 1 << 1,
Enemy = 1 << 2
};
现在我们来聊一聊enum和enum class的简单区别
1. 作用域（Scoping）
- **
enum**：传统的枚举成员是全局可见的，也就是说，枚举值会暴露在外部作用域中，可能与其他变量名发生冲突。enum Colors { Red, // Red 是全局的 }; int Red = 5; // 会与 Colors::Red 冲突
- **
enum class**：枚举成员位于枚举类的作用域内，必须使用枚举类型的名称来访问，不会与外部作用域中的其他标识符冲突2.类型安全（Type Safety）
- **
enum**：传统的枚举类型会隐式转换为整数类型，枚举成员可以与整数值自由混用。这种隐式转换可能导致类型不安全的操作。enum Colors { Red, Green, Blue }; int color = Red; // 可以隐式转换为 int
- **
enum class**：枚举类不会隐式转换为整数类型，必须显式进行转换。这增强了类型安全，防止意外的类型转换或不合法的比较。// int color = Colors::Red; // 编译错误：不能隐式转换 int color = static_cast<int>(Colors::Red); // 必须显式转换为整数3. 底层类型
**
enum**：默认情况下，传统的enum使用int作为底层类型（也可以通过enum指定底层类型，类似于enum class）。**
enum class**：默认情况下，enum class使用int作为底层类型，但你可以显式指定其他类型，如unsigned int、char等。enum class Colors : unsigned int { Red = 1, };顺便提一下几个不同的强制转换
static_cast的特点
- 编译时检查：
static_cast在编译时进行类型检查，确保类型安全。如果转换不合法，编译器会报错。- 类型转换：
- 可以将基本数据类型之间（如
int、float、double等）进行转换。- 可以将指针类型之间进行转换（如基类指针和派生类指针之间）。
- 可以将枚举类型转换为整型，反之亦然。
- 不能进行所有转换：不能用于进行类型层次结构中不安全的转换，如将基类指针直接转换为派生类指针，而不进行检查。
- 使用场景：适用于常见的类型转换，不需要动态类型检查的情况。
**
dynamic_cast**：
主要用于安全地进行类层次结构中的向下转型（即将基类指针或引用转换为派生类指针或引用）。
运行时检查类型安全。如果转换不合法，返回
nullptr（对于指针）或抛出std::bad_cast（对于引用）。适用于多态类型（需要有虚函数）。
示例：
class Base { virtual void func() {} }; class Derived : public Base { void func() override {} }; Base* b = new Derived(); Derived* d = dynamic_cast<Derived*>(b); // 安全的向下转型 if (d) { // 转换成功 }**
const_cast**：
用于添加或移除对象的
const限定符。可以将
const对象转换为非const对象，或者反向转换。使用时要小心，修改原本为
const的对象可能会导致未定义行为。示例：
const int a = 10; int* p = const_cast<int*>(&a); // 移除 const 限定符 *p = 20; // 未定义行为**
reinterpret_cast**：
用于在几乎任何类型之间进行转换，包括指针和整数之间的转换。
通常用于底层编程，如操作系统或硬件接口。
不会进行任何类型检查,表明任何错误自己承担,计算机不考虑任何后果，使用时非常小心，因为它可能导致未定义行为。
示例：
long p = 0x12345678; int* ptr = reinterpret_cast<int*>(p); // 将长整型地址转换为整型指针
2.确定层级的设置方式
然后就是使用问题,我们如何对一个物体设置多个目标层级
void set_layer_src(CollisionLayer layer)
{
layer_src = static_cast<int>(layer)|layer_src;
}
很简单,就是我们默认int层级一开始都为0,我们只要设置层级,将对应的层级强制转换为int,然后与自己取或运算,这样自己对应的bit位上的也变成了1,这样的操作可以执行多次.
3.层级判定
其实也不难,只需要将目标层级与自己的所在层级取&和运算,这样只要层级对应必定为1
(受击只能在一个层级,攻击可以对应多个层级)
bool CanCollideWith(int layer1, int layer2)
{
if ((layer1 & layer2) != 0)
return true;
else return false;
}
4. 额外的启用和关闭对应的碰撞层
lay_dst &= ~(static_cast<int> Layer::Enemy);
思路也很简单,只要将对应的层级取反然后和自己进行和运算即可,这样就能将对应的位掩码变为0.
2.简单的四叉树管理空间
使用四叉树（Quadtree）进行碰撞管理是一种常见的空间分割技术，能够有效地减少需要进行碰撞检测的物体数量。四叉树特别适用于二维空间中的碰撞检测，因为它能够将空间划分为更小的区域，使得只需检查在同一区域内的物体之间的碰撞。
四叉树的基本结构
- 节点：四叉树的每个节点表示一个矩形区域，并包含以下信息：
- 矩形区域的边界（通常用最小和最大坐标表示）。
- 子节点的指针（最多有四个子节点）。
- 存储在该区域内的物体列表。
- 分割：当一个节点中的物体超过一定数量时（例如，4个物体），该节点会被分割为四个子节点，每个子节点代表原节点区域的四分之一。
- 插入：物体的边界（碰撞箱）会被插入到合适的节点中，树会向下查找适当的区域。
- 查询：在进行碰撞检测时，查询四叉树可以快速找到可能碰撞的物体。
- 删除: 删除对应的不需要的碰撞箱和无用的节点
- 动态空间管理: 在删除四叉树内的碰撞箱时,要实时检测删除空节点或者向上融合,保证空间的利用率.
我目前只能插入,但是在动态空间规划shape还是有问题,所以只是简单说一下实现
int GetIndex(const shape& shape) const
传入对应的形状,确定当前的形状所在子节点划分的对应序号区域.
void Insert(shape* shape）
- 首先检查当前节点是否无子节点,若无则直接插入.
- 若有节点,则用上CPP面获取对应的子节点划分区域,然后递归插入.
- 上面俩个逻辑完成后,则检查是否超过每个节点的限制,是否需要分裂子节点,将对象的往下分配
- 注意,刚好卡在划分线上的就放在当前的节点,不再向下分配
void remove(shape* object)
- 因为我们是指针列表存放对应的shape,实际的shape在对象的碰撞箱子里,我们有需要删除对应的shape的时候,我们就需要从上到下递归寻找.
- 删除后我们还要从下网上检查是否有的节点全空,是否需要删除,保证空间的利用率,这里我一直没做好,但大体逻辑就是检查对象列表,检查节点是否为空,来选择是否删除,但是在检查节点是否位空,是指没对象没子节点的空,一CPP直有问题,暂且我就不说了.
void Retrieve(std::vector<shape*>& result, const shape& shape) const
- 通过引用列表获取与对应碰撞箱子的所在区域所有可能的碰撞箱子,供碰撞检测用,在存在大量的碰撞箱子时优化性能
void Split()
- 就是为子节点创建新的四叉树,平均的分配空间.
以下时供参考的但有问题的例子:
#ifndef _QUADTREE_H_
#define _QUADTREE_H_
#include "rectangle.h"
#include <iostream>
#include "vector2.h"
#include <graphics.h>
#include <vector>
// 矩形结构
// 四叉树类
class Quadtree {
public:
static const int MAX_OBJECTS = 4;
static const int MAX_LEVELS = 5;
Quadtree(int level, const rectangle_my& bounds)
: level(level), bounds(bounds) {}
// 插入对象
void Insert(rectangle_my* rect) {
if (!nodes.empty()) {
int index = GetIndex(*rect);
if (index != -1) {
nodes[index]->Insert(rect);
return;
}
}
objects.push_back(rect);
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS)
{
if (nodes.empty())
{
Split();
}
auto it = objects.begin();
while (it != objects.end())
{
int index = GetIndex(**it);
if (index != -1)
{
nodes[index]->Insert(*it);
it = objects.erase(it);
}
else
{
++it;
}
}
}
}
void remove(rectangle_my* object)
{
auto it = std::find(objects.begin(), objects.end(), object);
if (it != objects.end())
{
objects.erase(it);
}
else if (hasChildren)
{
removeFromChildren(object);
}
// 动态管理：如果没有对象且子节点为空，释放子节点
if (hasChildren)
{
bool shouldDeleteChildren = true;
for (int i = 0; i < 4; ++i)
{
if (!nodes[i]->isEmpty())
{
shouldDeleteChildren = false;
break;
}
}
if (shouldDeleteChildren)
{
std::cout << "delete" << level<< std::endl;
clearChildren();
}
}
}
// 检索与给定区域可能相交的所有对象
void Retrieve(std::vector<rectangle_my*>& result, const rectangle_my& range) const
{
int index = GetIndex(range);
if (index != -1 && !nodes.empty()) {
nodes[index]->Retrieve(result, range);
}
for (const auto& obj : objects) {
if (obj->Intersects(range)) {
result.push_back(obj);
}
}
if (index == -1 && !nodes.empty()) {
for (int i = 0; i < 4; ++i) {
nodes[i]->Retrieve(result, range);
}
}
}
// 清除所有节点和对象
void Clear() {
objects.clear();
for (int i = 0; i < nodes.size(); ++i) {
nodes[i]->Clear();
delete nodes[i];
}
nodes.clear();
}
void on_render(Quadtree* tree)
{
if (tree == nullptr)return;
if (!tree->nodes.empty())
{
for (int i = 0; i < 4; i++)
tree->on_render(tree->nodes[i]);
}
for (auto& it : tree->objects)
{
setlinecolor(RGB(255, 195, 195));
rectangle((int)(it->position.x- it->size.x/2),
(int)(it->position.y- it->size.y/2),
(int)(it->position.x + it->size.x/2),
(int)(it->position.y + it->size.y/2));
}
setlinecolor(RGB(255, 255, 255));
//std::cout << it->position.x << std::endl;
rectangle((int)(tree->bounds.position.x),
(int)(tree->bounds.position.y),
(int)(tree->bounds.position.x + tree->bounds.size.x),
(int)(tree->bounds.position.y + tree->bounds.size.y));
}
public:
int level;
rectangle_my bounds;
std::vector<rectangle_my*> objects; // 存储指向对象的指针
std::vector<Quadtree*> nodes;
bool hasChildren = false; // 标记是否有子节点
// 将当前节点分裂为四个子节点
void Split() {
hasChildren = true;
float subWidth = bounds.size.x / 2.0;
float subHeight = bounds.size.y / 2.0;
float x = bounds.position.x;
float y = bounds.position.y;
nodes.push_back(new Quadtree(level + 1, rectangle_my{ Vector2(x, y), Vector2(subWidth, subHeight) }));
nodes.push_back(new Quadtree(level + 1, rectangle_my{ Vector2(x + subWidth, y), Vector2(subWidth, subHeight) }));
nodes.push_back(new Quadtree(level + 1, rectangle_my{ Vector2(x, y + subHeight), Vector2(subWidth, subHeight)}));
nodes.push_back(new Quadtree(level + 1, rectangle_my{ Vector2(x + subWidth, y + subHeight), Vector2(subWidth, subHeight) }));
}
// 获取对象应该插入的子节点索引
int GetIndex(const rectangle_my& rect) const {
int index = -1;
float verticalMidpoint = bounds.position.x + bounds.size.x / 2.0;
float horizontalMidpoint = bounds.position.y + bounds.size.y / 2.0;
bool topQuadrant = (rect.position.y-rect.size.y/2) < horizontalMidpoint && (rect.position.y + rect.size.y/2) < horizontalMidpoint;
bool bottomQuadrant = (rect.position.y + rect.size.y/2) > horizontalMidpoint;
bool leftQuadrant = (rect.position.x-rect.size.x/2) < verticalMidpoint && (rect.position.x + rect.size.x/2) < verticalMidpoint;
bool rightQuadrant = (rect.position.x-rect.size.x/2) > verticalMidpoint;
if (leftQuadrant) {
if (topQuadrant) {
index = 0;
}
else if (bottomQuadrant) {
index = 2;
}
}
else if (rightQuadrant) {
if (topQuadrant) {
index = 1;
}
else if (bottomQuadrant) {
index = 3;
}
}
return index;
}
bool isEmpty() const
{
if (!objects.empty()）
return false;
if (!hasChildren)
return true;
for (int i = 0; i < 4; ++i)
{
if (nodes[i] && !nodes[i]->isEmpty())
return false;
}
return true;
}
void removeFromChildren(rectangle_my* object)
{
int index = GetIndex(*object);
if (index != -1)
{
nodes[index]->remove(object);
}
}
void clearChildren()
{
for (int i = 0; i < 4; ++i)
{
nodes[i]->Clear(); // 清理子节点中的所有对象
delete nodes[i];
nodes[i] = nullptr;
}
nodes.clear();
hasChildren = false;
}
};
#endif // !_QUADTREE_H_