[HELP] Enemy Around

[StDH]

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>>

[Nexus]

Use spatial partition. For example a simple grid, a quadtree, or an R-tree (Boost.Geometry).

There have also been several threads about this problem, you could search the forum.

[StDH]

Use spatial partition. For example a simple grid, a quadtree, or an R-tree (Boost.Geometry).

There have also been several threads about this problem, you could search the forum.

thanks.
It looks like i will implement QuadTree.

[Nexus]

By the way, isn't there a useful and generic Quadtree implementation out there? Everybody reinvents the wheel, although this data structure has certainly existed for decades and been used thousands of times. And I'm sure a lot of people reinvent it wrongly, even if it ends up working somehow. Almost every game engine uses quadtrees, but nobody seems to care about reusability or genericity, let alone independence of the engine.

[StDH]

As far i know QuadTree has an official website, but i forgot its name.
i have quadtree from github, downloaded about 6 months back.

[StDH]

// 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);
}