here is the quad tree code. this is off the top of my head and it may not be outstanding and i would love you guys to give me some tips on making it better or fixing it all together lol
- Code: Select all
#ifndef _QUAD_TREE_H_
#define _QUAD_TREE_H_
#include <SFML/System.hpp>
#include "EntityManager.h"
#include <vector>
/// hope to increase collision decetion speed with this one!!
// need to figure out how im going to do this...
struct NodeRect
{
int x, y, w, h;
NodeRect()
{
x = y = w = h = 0;
}
NodeRect(int setX, int setY, int setW, int setH)
:
x(setX),
y(setY),
w(setW),
h(setH)
{
}
};
struct Node
{
Node* child[4];
NodeRect area;
std::vector<cell::Entity*> entity;
~Node()
{
if(child[0]) delete child[0];
if(child[1]) delete child[1];
if(child[2]) delete child[2];
if(child[3]) delete child[3]; // becomes a recursive deallocation
}
Node()
{
child[0] = child[1] = child[2] = child[3] = NULL;
}
Node(int x, int y, int w, int h):
area(x, y, w, h)
{
child[0] = child[1] = child[2] = child[3] = NULL;
}
Node(const NodeRect &setArea):
area(area)
{
child[0] = child[1] = child[2] = child[3] = NULL;
}
void AddEntity(cell::Entity* _entity)
{
entity.push_back(_entity);
}
};
// in the entity class create an OnCollision method
class QuadTree
{
public:
QuadTree(int levels);
~QuadTree();
void Setup(Node* node, int levels = 2); // zero = 1x1 one = 4x4 two = 16x16 exc...
void Update(EntityManager*);
void CheckCollisions();
void FindCell(Node* node, cell::Entity* entity);
Node* GetNode(){ return m_node; }
private:
int m_levels;
Node* m_node;
public:
/// just for now
std::vector<Node*> leafNodes; // for collision checking and stuff
std::vector<Node*> collisionNodes;
};
#endif
- Code: Select all
#include "QuadTree.h"
#include <fstream>
#include <iostream>
#include "Player.h"
QuadTree::QuadTree(int levels)
:
m_levels(levels)
{
m_node = new Node(0, 0, 640, 480);
Setup(m_node, levels);
}
QuadTree::~QuadTree()
{
if(m_node != NULL)
{
delete m_node;
}
}
void QuadTree::Setup(Node* node, int levels)
{
levels -= 1;
if(levels >= 0)
{
node->child[0] = new Node(node->area.x, node->area.y, node->area.w/2, node->area.h/2);
node->child[1] = new Node(node->area.x + node->area.w/2, node->area.y, node->area.w/2, node->area.h/2);
node->child[2] = new Node(node->area.x, node->area.y + node->area.h/2, node->area.w/2, node->area.h/2);
node->child[3] = new Node(node->area.x + node->area.w/2, node->area.y + node->area.h/2, node->area.w/2, node->area.h/2);
for(int i = 0; i < 4; i++)
{
Setup(node->child[i], levels); // recursive method lol
}
}
else
{
this->leafNodes.push_back(node); // its a leaf node !!
}
}
void QuadTree::CheckCollisions()
{
for(unsigned int i = 0; i < collisionNodes.size(); i++)
{
for(unsigned int n = 0; n < collisionNodes[i]->entity.size(); n++)
{
cell::Entity* entity = collisionNodes[i]->entity[n];
for(unsigned int z = 0; z < collisionNodes[i]->entity.size(); z++)
{
if(z != n)
{
if(entity->Collision(collisionNodes[i]->entity[z]))
{
collisionNodes[i]->entity[n]->OnCollision();
}
}
}
}
}
}
void QuadTree::Update(EntityManager* mgr)
{
for(unsigned int i = 0; i < leafNodes.size(); i++)
{
leafNodes[i]->entity.clear();
}
collisionNodes.clear();
for(unsigned int i = 0; i< mgr->GetVector().size(); i++)
{
FindCell(m_node, mgr->GetEntity(i));
}
}
void QuadTree::FindCell(Node* node, cell::Entity* entity)
{
if(node->child[0])
{
if(entity->GetX() < node->child[1]->area.x)
{
if(entity->GetY() < node->child[2]->area.y)
{
FindCell(node->child[0], entity);
}
else
{
FindCell(node->child[2], entity);
}
}
else
{
if(entity->GetY() < node->child[2]->area.y)
{
FindCell(node->child[1], entity);
}
else
{
FindCell(node->child[3], entity);
}
}
}
else
{
node->AddEntity(entity);
collisionNodes.push_back(node); // if it has an entity check it for collision
}
}
