四叉树在碰撞检测中的应用

ACM算法日常

发布于 2020-08-20 10:18:38

2.4K0

缘起

《你被追尾了》中预告了加速碰撞检测的算法——四叉树（for 2D），所以本文就来学习一下.

分析

首先是为什么要使用四叉树进行优化，其实《你被追尾了》中已经说了，这里简单复习一下，碰撞检测是一种比较昂贵的操作. 假设有100个对象需要进行碰撞检测，那么两两进行碰撞检测需要进行 100 x 100 = 10000 次碰撞检测，检测的次数实在太多，消耗大量CPU资源而引起游戏卡帧。一种优化途径是减少非必要的碰撞检测的次数。比如两个物体位于屏幕的左上角和右下角，显然是不可能发生碰撞的，因此不需要检测它们之间是否会发生碰撞。这正是四叉树发挥作用的地方。

什么是四叉树（Quadtree）

四叉树是一种将一块2D矩形区域（理解为游戏沙盒）分割为更易于管理的子区域的数据结构.

四叉树是二叉树的扩展——将2个子节点变为4个子节点. 四叉树的根节点是初始的尚未被划分的一整块2D区域.

在下面所有的图中，红色的小方块代表物体（例如赛车）.

然后，我们将一个物体放入初始的2D区域（即四叉树的根节点）

当越来越多的物体被放入该区域（记做 R，region）的时候，就会导致该区域（节点）的分裂（split）. 具体多到什么程度开始分裂，你可以在程序中进行自定义. 例如我设定为1，则表示只要有物体放入，我就对R 进行分裂. 显然，这个数字的大小代表四叉树算法的惰性.

该节点将最终分裂为4（因为是四叉树嘛~）个子节点（子节点记做SR，sub region）. 然后每个物体都将根据它们所处的坐标被划分进某个SR. 如果一个物体不能完全放入任何一个SR的话，将被归入 R

例如上图中，物体 A 将归入 R，而除了 A 之外的所有物体都被归入了相应的 SR

然后，随着越来越多的物体加入，SR 可能也会分裂. 就像下图这样, 左上角的 SR 继续分裂为了4个子节点.

正如你所见，A、B、C、D 四个物体处在不同的象限，所以绝逼不可能发生碰撞. 这就不需要对这四个物体之间进行昂贵的碰撞检测，从而优化了游戏的性能.

知道了四叉树的思想之后，我们不难给出如下实现. 首先，我先说一下我想做出什么效果? 就是如下图所示

就是能实时（其实是每一帧）展示出四叉树的样子，以及填充发生碰撞的小球对（ball pair）. 框中的小球和边界都是弹性碰撞，小球碰撞时彼此互相穿过.

网上有使用 js 实现的版本，我这里使用 Win 32 API 实现 UI 界面.

以下代码在 vs2010 下调试通过

Object.h

#include "Rectangle.h"
#include <graphics.h>

#define OBJECT_WIDTH 20 
#define OBJECT_HEIGHT 20 

class Object : public Bound 
{
    double vx, vy; 
    int color; 
    int id;
public:
    Object(double x = 0, double y = 0)
    {
        this->x = x;
        this->y = y;
        this->w = rand() % OBJECT_WIDTH + 1;
        this->h = this->w;
        this->vx = (rand() % 10 + 1) * (rand() & 1 ? 1 : -1); 
        this->vy = (rand() % 10 + 1) * (rand() & 1 ? 1 : -1);
        color = YELLOW; 
    }

    ~Object() {}

    friend bool collisionWithBound(Object object);

    friend void reflect(Object &object); 

    void setId(int id) 
    {
        this->id = id;
    }

    void setColor(int color) 
    {
        this->color = color;
    }

    void paint()
    {
        setfillcolor(color);
        solidrectangle(x, y, x + w, y + h);
    }

    bool collision(Object &o) 
    {
        bool ans = x < o.x + o.w && o.x < x + w && y < o.y + o.h && o.y < y + h;
        if (ans) 
        {
            o.color = color = RED;
        }
        return ans;
    }

    void move()
    {
        x += vx;
        y += vy;
    }

    bool operator == (const Object &o)
    {
        return id == o.id;
    }

};

QuadTree.h

#include <list>
using namespace std;
#include "Object.h"
typedef list<Object>::iterator LIT;

class QuadTreeNode
{
public:
    void clear();
    void insert(Object); 
    list<Object> retrieve(Object &); 
    void setLevel(int level) { this->level = level; }
    void setBound(Bound bound) { this->bound = bound; }
    QuadTreeNode();
    QuadTreeNode(int, Bound);
    ~QuadTreeNode();
private:
    int level; 
    list<Object> objects; 
    Bound bound; 
    QuadTreeNode *nodes[4];

    const static int MAX_OBJECTS = 5; 
    const static int MAX_LEVELS = 5; 

    void split(); 
    int getIndex(Object &); 
};

struct Line 
{
    double sx, sy, ex, ey; 
    Line(double sx = 0, double sy = 0, double ex = 0, double ey = 0):sx(sx), sy(sy), ex(ex), ey(ey){}
    void paint(); 
};

Rectangle.h

class Bound
{
protected:
    double x, y, w, h; 
public:
    Bound(double x = 0, double y = 0, double w = 0, double h = 0):x(x), y(y), w(w), h(h){}
    
    double getx()
    {
        return x;
    }

    double gety()
    {
        return y;
    }

    double getw()
    {
        return w;
    }

    double geth()
    {
        return h;
    }

};

QuadTree.cpp

#include "QuadTree.h"
#include <string.h>

Line lines[10005];
int top; 

QuadTreeNode::QuadTreeNode()
{
    memset(nodes, 0, sizeof(nodes));
}

QuadTreeNode::QuadTreeNode(int level, Bound bound)
{
    this->level = level;
    this->bound = bound;
    memset(nodes, 0, sizeof(nodes));
}

QuadTreeNode::~QuadTreeNode()
{
    clear();
}

void QuadTreeNode::clear()
{
    objects.clear();
    if (nodes[0])
    {
        for (int i = 0; i < 4; i++)
        {
            nodes[i]->clear();
            nodes[i] = 0;
        }
    }
}

void QuadTreeNode::split()
{
    double w = bound.getw() / 2.0;
    double h = bound.geth() / 2.0;
    double x = bound.getx();
    double y = bound.gety();
    nodes[0] = new QuadTreeNode(level + 1, Bound(x + w, y, w, h)); 
    nodes[1] = new QuadTreeNode(level + 1, Bound(x, y, w, h)); 
    nodes[2] = new QuadTreeNode(level + 1, Bound(x, y + h, w, h)); 
    nodes[3] = new QuadTreeNode(level + 1, Bound(x + w, y + h, w, h)); 
    lines[top].sx = bound.getx() + bound.getw() / 2.0; lines[top].sy = bound.gety(); lines[top].ex = bound.getx() + bound.getw() / 2.0; lines[top].ey = bound.gety() + bound.geth();
    lines[top + 1].sx = bound.getx(); lines[top + 1].sy = bound.gety() + bound.geth() / 2.0; lines[top + 1].ex = bound.getx() + bound.getw(); lines[top + 1].ey = bound.gety() + bound.geth() / 2.0;
    lines[top + 2].sx = bound.getx(); lines[top + 2].sy = bound.gety(); lines[top + 2].ex = bound.getx() + bound.getw(); lines[top + 2].ey = bound.gety();
    lines[top + 3].sx = bound.getx(); lines[top + 3].sy = bound.gety() + bound.geth(); lines[top + 3].ex = bound.getx() + bound.getw(); lines[top + 3].ey = bound.gety() + bound.geth();
    lines[top + 4].sx = bound.getx(); lines[top + 4].sy = bound.gety(); lines[top + 4].ex = bound.getx(); lines[top + 4].ey = bound.gety() + bound.geth();
    lines[top + 5].sx = bound.getx() + bound.getw(); lines[top + 5].sy = bound.gety(); lines[top + 5].ex = bound.getx() + bound.getw(); lines[top + 5].ey = bound.gety() + bound.geth();
    top += 6;
}

int QuadTreeNode::getIndex(Object &object)
{
    int ans = -1; 
    double hmid = bound.getx() + bound.getw() / 2.0, vmid = bound.gety() + bound.geth() / 2.0; 
    if (object.getx() + object.getw() < hmid) 
    {
        if (object.gety() + object.geth() / 2.0 < vmid)
        {
            return 1;
        }
        else if (object.gety() > vmid)
        {
            return 2;
        }
    }
    else if (object.getx() > hmid) 
    {
        if (object.gety() + object.geth() / 2.0 < vmid)
        {
            return 0;
        }
        else if (object.gety() > vmid)
        {
            return 3;
        }
    }
    return ans; 
}

void QuadTreeNode::insert(Object object)
{
    if (nodes[0])
    {
        int index = getIndex(object);
        if (~index) 
        {
            nodes[index]->insert(object);
            return;
        }
    }
    objects.push_back(object); 
    if (objects.size() > QuadTreeNode::MAX_OBJECTS && level < QuadTreeNode::MAX_LEVELS) 
    {
        if (!nodes[0]) 
        {
            split();
        }
        for (LIT lit = objects.begin(); lit != objects.end();)
        {
            int index = getIndex(*lit);
            if (~index)
            {
                nodes[index]->insert(*lit);
                lit = objects.erase(lit);
            }
            else
            {
                ++lit;
            }
        }
    }
}

list<Object> QuadTreeNode::retrieve(Object &object)
{
    list<Object> ans;
    int index;
    if (nodes[0] && ~(index = getIndex(object)))
    {
        ans = nodes[index]->retrieve(object);
    }
    for (LIT lit = objects.begin(); lit != objects.end(); lit++)
    {
        ans.push_back(*lit);
    }
    return ans;
}

四叉树Demo.cpp

#include <stdio.h>
#include <graphics.h>
#include <time.h>
#include <MMSystem.h>
#pragma comment(lib, "winmm.lib")
#include "QuadTree.h"

#define WIDTH 600 
#define HEIGHT 800 
#define OBJECT_NUM 20 
Object objects[OBJECT_NUM];
QuadTreeNode quad;
extern int top;
extern Line lines[];

HWND hWnd;

void initGame(); 

void _move();

void drawGame();

int main()
{
    // 秋华の恋
    mciSendString("open 1.mp3 alias start", NULL, NULL, NULL); 
    mciSendString("play start repeat", NULL, NULL, NULL);
    initGame();
    SetTimer(hWnd, 666, 50, (TIMERPROC)_move);
    while (1)
    {
        drawGame();
    }
    return 0;
}

void initGame()
{
    srand(time(0));
    hWnd = initgraph(WIDTH, HEIGHT);
    setbkcolor(RGB(0, 255, 255));
    cleardevice();
    for (int i = 0; i < OBJECT_NUM; i++)
    {
        objects[i] = Object(rand() % (WIDTH - OBJECT_WIDTH), rand() % (HEIGHT - OBJECT_HEIGHT));
        objects[i].setId(i);
    }
    quad.setLevel(0);
    quad.setBound(Bound(0, 0, WIDTH, HEIGHT));
}

bool collisionWithBound(Object object)
{
    return object.x <= 0 || object.x + object.w >= WIDTH || object.y <= 0 || object.y + object.h >= HEIGHT;
}

void reflect(Object &object)
{
    if (object.x < 0)
    {
        object.x = 0;
        object.vx = -object.vx;
    }
    else if (object.x + object.w > WIDTH)
    {
        object.x = WIDTH - object.w;
        object.vx = -object.vx;
    }
    if (object.y < 0)
    {
        object.y = 0;
        object.vy = -object.vy;
    }
    else if (object.y + object.h > HEIGHT)
    {
        object.y = HEIGHT - object.h;
        object.vy = -object.vy;
    }
}

void _move()
{
    for (int i = 0; i < OBJECT_NUM; i++)
    {
        objects[i].move();
        if (collisionWithBound(objects[i])) 
        {
            reflect(objects[i]); 
        }
    }
}

void Line::paint()
{
    setlinecolor(BLUE);
    setlinestyle(PS_DASH);
    line((int) sx, (int) sy, (int) ex, (int) ey);
}

void drawGame()
{
    BeginBatchDraw();
    cleardevice();
    quad.clear();
    top = 0;
    for (int i = 0; i < OBJECT_NUM; i++) 
    {
        quad.insert(objects[i]);
    }
    for (int i = 0; i < OBJECT_NUM; i++)
    {
        objects[i].setColor(YELLOW); 
        list<Object> candidate = quad.retrieve(objects[i]); 
        for (LIT lit = candidate.begin(); lit != candidate.end(); lit++)
        {
            if (objects[i] == *lit) 
            {
                continue;
            }
            objects[i].collision(*lit); 
        }
    }
    for (int i = 0; i < OBJECT_NUM; i++) 
    {
        objects[i].paint();
    }
    for (int i = 0; i < top; i++) 
    {
        lines[i].paint();
    }
    EndBatchDraw();
}

运行效果