Hello all,
2D game,
i need to find if there is any enemy around another enemy but, using lenght and collision detection with 200 npcs it's equivalent to winVista as server on WiFi.
Is there any other way to find any enemy near another enemy ?
And sys look like this:
entity:
struct gameEntity_NPC
entity manager:
map<string, unique_ptr<gameEntity_NPC>>
// QuadtreeSimple.cpp : Demonstrates the use of Quadtree using SFML
//
#include "Quadtree.h"
#include "Object.h"
#include <SFML/Graphics/RenderWindow.hpp>
#include <SFML/Window/Event.hpp>
#include <SFML/Graphics/Font.hpp>
#include <iostream>
int main()
{
using namespace std;
sf::RenderWindow app( sf::VideoMode( 800, 600, 32 ), "Quadtree" );
app.setFramerateLimit( 60 );
sf::Font font;
font.loadFromFile( "DroidSans.ttf" );
Quadtree quadtree( 0.0f, 0.0f, 800.0f, 600.0f, 0, 3 );
quadtree.SetFont( font );
vector<Object> objects;
while( app.isOpen() ) {
sf::Event event;
sf::Vector2i mousePosition = sf::Mouse::getPosition( app );
while( app.pollEvent( event ) ) {
if ( event.type == sf::Event::KeyPressed ) {
if ( event.key.code == sf::Keyboard::Escape ) {
app.close();
}
}
if ( event.type == sf::Event::MouseButtonPressed ) {
objects.push_back( Object( mousePosition.x, mousePosition.y, 32, 32 ) );
}
}
app.clear();
for ( int n = 0; n < objects.size(); ++n ) {
quadtree.AddObject( &objects[n] );
objects[n].Draw( app );
}
quadtree.Draw( app );
vector<Object*> returnObjects = quadtree.GetObjectsAt( mousePosition.x, mousePosition.y );
cout << returnObjects.size() << endl;
quadtree.Clear();
app.display();
}
return 0;
}
#ifndef __QUADTREE_H__
#define __QUADTREE_H__
#include <vector>
#include <SFML/Graphics/RenderTarget.hpp>
#include <SFML/Graphics/RectangleShape.hpp>
#include <SFML/Graphics/Text.hpp>
using namespace std;
class Quadtree;
class Object;
class Quadtree {
public:
Quadtree(float x, float y, float width, float height, int level, int maxLevel);
~Quadtree();
void AddObject(Object *object);
vector<Object*> GetObjectsAt(float x, float y);
void Clear();
void SetFont(const sf::Font &font);
void Draw(sf::RenderTarget &canvas);
private:
float x;
float y;
float width;
float height;
int level;
int maxLevel;
vector<Object*> objects;
Quadtree * parent;
Quadtree * NW;
Quadtree * NE;
Quadtree * SW;
Quadtree * SE;
sf::RectangleShape shape;
sf::Text text;
bool contains(Quadtree *child, Object *object);
};
#endif
quadtree.cpp
#include "Quadtree.h"
#include "Object.h"
#include <iostream>
#include <sstream>
using namespace std;
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)
{
shape.setPosition(x, y);
shape.setSize(sf::Vector2f(width, height));
shape.setFillColor(sf::Color(0, 0, 0, 0));
shape.setOutlineThickness(1.0f);
shape.setOutlineColor(sf::Color(64, 128, 255));
text.setPosition(x, y + level * 16);
text.setCharacterSize(12);
if (level == maxLevel) {
return;
}
NW = new Quadtree(x, y, width / 2.0f, height / 2.0f, level+1, maxLevel);
NE = new Quadtree(x + width / 2.0f, y, width / 2.0f, height / 2.0f, level+1, maxLevel);
SW = new Quadtree(x, y + height / 2.0f, width / 2.0f, height / 2.0f, level+1, maxLevel);
SE = new Quadtree(x + width / 2.0f, y + height / 2.0f, width / 2.0f, height / 2.0f, level+1, maxLevel);
}
Quadtree::~Quadtree()
{
if (level == maxLevel)
return;
delete NW;
delete NE;
delete SW;
delete SE;
}
void Quadtree::AddObject(Object *object) {
if (level == maxLevel) {
objects.push_back(object);
return;
}
if (contains(NW, object)) {
NW->AddObject(object); return;
} else if (contains(NE, object)) {
NE->AddObject(object); return;
} else if (contains(SW, object)) {
SW->AddObject(object); return;
} else if (contains(SE, object)) {
SE->AddObject(object); return;
}
if (contains(this, object)) {
objects.push_back(object);
}
}
vector<Object*> Quadtree::GetObjectsAt(float _x, float _y) {
if (level == maxLevel) {
return objects;
}
vector<Object*> returnObjects, childReturnObjects;
if (!objects.empty()) {
returnObjects = objects;
}
if (_x > x + width / 2.0f && _x < x + width) {
if (_y > y + height / 2.0f && _y < y + height) {
childReturnObjects = SE->GetObjectsAt(_x, _y);
returnObjects.insert(returnObjects.end(), childReturnObjects.begin(), childReturnObjects.end());
return returnObjects;
} else if (_y > y && _y <= y + height / 2.0f) {
childReturnObjects = NE->GetObjectsAt(_x, _y);
returnObjects.insert(returnObjects.end(), childReturnObjects.begin(), childReturnObjects.end());
return returnObjects;
}
} else if (_x > x && _x <= x + width / 2.0f) {
if (_y > y + height / 2.0f && _y < y + height) {
childReturnObjects = SW->GetObjectsAt(_x, _y);
returnObjects.insert(returnObjects.end(), childReturnObjects.begin(), childReturnObjects.end());
return returnObjects;
} else if (_y > y && _y <= y + height / 2.0f) {
childReturnObjects = NW->GetObjectsAt(_x, _y);
returnObjects.insert(returnObjects.end(), childReturnObjects.begin(), childReturnObjects.end());
return returnObjects;
}
}
return returnObjects;
}
void Quadtree::Clear() {
if (level == maxLevel) {
objects.clear();
return;
} else {
NW->Clear();
NE->Clear();
SW->Clear();
SE->Clear();
}
if (!objects.empty()) {
objects.clear();
}
}
void Quadtree::SetFont(const sf::Font &font) {
text.setFont(font);
if (level != maxLevel) {
NW->SetFont(font);
NE->SetFont(font);
SW->SetFont(font);
SE->SetFont(font);
}
}
void Quadtree::Draw(sf::RenderTarget &canvas) {
stringstream ss;
ss << objects.size();
string numObjectsStr = ss.str();
text.setString(numObjectsStr);
canvas.draw(shape);
canvas.draw(text);
if (level != maxLevel) {
NW->Draw(canvas);
NE->Draw(canvas);
SW->Draw(canvas);
SE->Draw(canvas);
}
}
bool Quadtree::contains(Quadtree *child, Object *object) {
return !(object->x < child->x ||
object->y < child->y ||
object->x > child->x + child->width ||
object->y > child->y + child->height ||
object->x + object->width < child->x ||
object->y + object->height < child->y ||
object->x + object->width > child->x + child->width ||
object->y + object->height > child->y + child->height);
}