the main issues are two.
-> first off , not all objects (entities ) are added in the quadtree and i have no clue why ( the objects that are not added are part of the "boundaries" of each zone.
-> to check for the collision side i've divided it into 2 steps, first i'm checking if the position of the bullet is inside the entity ( wall in this case ) and then i'm tracing a ray from the previous position to the new position and check which side it intersects. I've been debugging it for a while, and the "ray tracing" is not a problem.
The implementation is not entitrely completed, i'll polish it and improve it later.
The Entities in the quadtree are divided into fixed ( will neve be removed ) and not fixed ( will implement them later, don't need them now : i've removed their code )
here's the header
p.s. the code might seem long, but it's really easy to understand. Thank you in advance
Quadtree header
class QuadTree
{
public :
QuadTree(){};
QuadTree(float,float,float,float,int,int);
~QuadTree();
void Clear();
void AddEntity(Entity*);
void AddFixedEntity(Entity*);
std::vector<Entity*> GetEntitiesAt(float,float);
std::vector<Entity*> GetFixedEntitiesAt(float,float);
private :
float X_;
float Y_;
float Width_;
float Height_;
int Level_;
int MaxLevel_;
QuadTree* Parent_;
QuadTree* RightUp_;
QuadTree* LeftUp_;
QuadTree* RightDown_;
QuadTree* LeftDown_;
bool Contains(QuadTree*,Entity*);
std::vector<Entity*> Entities_;
std::vector<Entity*> FixedEntities_;
};
Quadtree source
/**=============================
QuadTree::QuadTree
=============================**/
QuadTree::QuadTree(float x,float y,float width,float height,int level,int maxLevel):
X_(x),
Y_(y),
Width_(width),
Height_(height),
Level_(level),
MaxLevel_(maxLevel)
{
if (Level_ == MaxLevel_)
return;
LeftUp_ = new QuadTree(X_,Y_,Width_ / 2.0f , Height_ / 2.0f, Level_ +1,MaxLevel_);
RightUp_ = new QuadTree(X_ + Width_ / 2.0f,Y_, Width_ / 2.0f,Height_ /2.0f,Level_ +1,MaxLevel_);
LeftDown_ = new QuadTree(X_, Y_ + Height_ / 2.0f,Width_ / 2.0f,Height_ / 2.0f,Level_ +1,MaxLevel_);
RightDown_ = new QuadTree(X_ + Width_ / 2.0f,Y_ + Height_ / 2.0f,Width_ / 2.0f,Height_ / 2.0f,Level_ +1,MaxLevel_);
}
/**=============================
QuadTree::~QuadTree
=============================**/
QuadTree::~QuadTree()
{
if (Level_ != MaxLevel_)
{
delete LeftUp_;
delete LeftDown_;
delete RightUp_;
delete RightDown_;
}
}
/**=============================
QuadTree::AddFixedEntity
=============================**/
void QuadTree::AddFixedEntity(Entity* entity)
{
if (Level_ == MaxLevel_)
{
FixedEntities_.push_back(entity);
return;
}
if (Contains(LeftUp_,entity))
{
LeftUp_->AddFixedEntity(entity);
return;
}
else if (Contains(RightUp_,entity))
{
RightUp_->AddFixedEntity(entity);
return;
}
else if (Contains(LeftDown_,entity))
{
LeftDown_->AddFixedEntity(entity);
return;
}
else if (Contains(RightDown_,entity))
{
RightDown_->AddFixedEntity(entity);
return;
}
if (Contains(this,entity))
{
FixedEntities_.push_back(entity);
}
}
/**=============================
QuadTree::GetFixedEntitiesAt
=============================**/
std::vector<Entity*> QuadTree::GetFixedEntitiesAt(float x,float y)
{
if (Level_ == MaxLevel_)
{
return FixedEntities_;
}
std::vector<Entity*> returnOne,returnTwo;
if (!Entities_.empty())
{
returnOne = FixedEntities_;
}
if (x >= X_ && x <= X_ + Width_ / 2.0f)
{
if ( y >= Y_ && y <= Y_ + Height_ / 2.0f)
{
returnTwo = LeftUp_->GetFixedEntitiesAt(x,y);
returnOne.insert(returnOne.end(),returnTwo.begin(),returnTwo.end());
return returnOne;
}
else if (y >= Y_ + Height_ / 2.0f && y <= Y_ + Height_)
{
returnTwo = LeftDown_->GetFixedEntitiesAt(x,y);
returnOne.insert(returnOne.end(),returnTwo.begin(),returnTwo.end());
return returnOne;
}
}
else if (x >= X_ + Width_ / 2.0f && x <= X_ + Width_)
{
if ( y >= Y_ && y <= Y_ + Height_ / 2.0f)
{
returnTwo = RightUp_->GetFixedEntitiesAt(x,y);
returnOne.insert(returnOne.end(),returnTwo.begin(),returnTwo.end());
return returnOne;
}
else if (y >= Y_ + Height_ / 2.0f && y <= Y_ + Height_)
{
returnTwo = RightDown_->GetFixedEntitiesAt(x,y);
returnOne.insert(returnOne.end(),returnTwo.begin(),returnTwo.end());
return returnOne;
}
}
return returnOne;
}
/**=============================
QuadTree::Contains
=============================**/
bool QuadTree::Contains(QuadTree* child,Entity* entity)
{
if (entity->Position_.x < child->X_ ||
entity->Position_.y < child->Y_ ||
entity->Position_.x > child->X_ + child->Width_ ||
entity->Position_.y > child->Y_ + child->Height_ ||
entity->Position_.x + entity->Width_ < child->X_ ||
entity->Position_.y + entity->Height_ < child->Y_ ||
entity->Position_.x + entity->Width_ > child->X_ + child->Width_||
entity->Position_.y + entity->Height_ > child->Y_ + child->Height_ )
return false;
return true;
}
/**=============================
QuadTree::Clear
=============================**/
void QuadTree::Clear()
{
if (!Entities_.empty())
Entities_.clear();
if (Level_ != MaxLevel_)
{
LeftDown_->Clear();
LeftUp_->Clear();
RightUp_->Clear();
RightDown_->Clear();
}
else
{
Entities_.clear();
return;
}
}
Here's the bullet to wall collision
/**=============================
CollisionHandler::BulletToWall
=============================**/
int CollisionHandler::BulletToWall(Bullet& bullet,sf::RenderWindow& window)
{
// getting data from quadtree
std::vector<Entity*> walls = QuadTree_->GetFixedEntitiesAt(bullet.GetPosition().x,bullet.GetPosition().y);
// creating ray from old position to new one
sf::Vector2f startVertex = bullet.GetPosition();
sf::Vector2f endVertex = bullet.GetPreviousPosition();
std::size_t s = walls.size();
for (int i = 0; i < s; ++i)
{
// checking if it is inside first
if (IsInside(bullet.GetPosition(),walls[i]))
{
sf::Vector2f topLeft = walls[i]->Position_;
sf::Vector2f topRight = sf::Vector2f(walls[i]->Position_.x + walls[i]->Width_,walls[i]->Position_.y);
sf::Vector2f downRight = sf::Vector2f(walls[i]->Position_.x + walls[i]->Width_,walls[i]->Position_.y + walls[i]->Height_);
sf::Vector2f downLeft = sf::Vector2f(walls[i]->Position_.x,walls[i]->Position_.y + walls[i]->Height_);
// if it inside i'm gonna check the angle by tracing a ray from the previous position to the new position and check on which side it intersects
if (AreIntersecting(endVertex,startVertex,topLeft,topRight))
return COLLISION_TOP;
else if (AreIntersecting(endVertex,startVertex,topRight,downRight))
return COLLISION_RIGHT;
else if (AreIntersecting(endVertex,startVertex,downRight,downLeft))
return COLLISION_DOWN;
else if (AreIntersecting(endVertex,startVertex,downLeft,topLeft))
return COLLISION_LEFT;
else
return COLLISION_TRUE;
}
sf::ConvexShape s(4);
s.setPoint(0,walls[i]->Position_);
s.setPoint(1,sf::Vector2f(walls[i]->Position_.x + walls[i]->Width_,walls[i]->Position_.y));
s.setPoint(2,sf::Vector2f(walls[i]->Position_.x + walls[i]->Width_,walls[i]->Position_.y + walls[i]->Height_));
s.setPoint(3,sf::Vector2f(walls[i]->Position_.x,walls[i]->Position_.y + walls[i]->Height_));
s.setFillColor(sf::Color(0,255,0));
window.draw(s);
}
return COLLISION_FALSE;
}