[Resolu][C++] Instance la plus proche

Bonjour à tous, je me triture l'esprit depuis un bout de temps à essayer de résoudre ce problème mais j'ai vraiment du mal à trouver une solution efficace.
J'ai deux types d'objets différents: Player et Astre
Chacun de ses types possèdes les attributs x et y qui déterminent leur position à l'écran.
J'ai un objet de type Player, et un nombre non défini d'objets de type Astre.
Ce que je souhaiterais avoir c'est une fonction du style nearestAstre() qui renverrait un pointeur vers l'objet de type Astre le plus proche de mon objet Player en fonction de leurs coordonnées.

Je sais comment calculer une distance entre mon objet Player et un Astre en particulier, jusque la ça va.
Par contre pour le faire avec un nombre variables d'Astres je ne sais pas trop. J'ai pensé à placer tout mes Astres dans un vector et le passer en paramètre de ma fonction nearestAstre mais je ne sais pas si c'est la meilleur solution...

Salut Ancestral,

Tu as pensé à juste faire une recherche du minimum dans une boucle ?
Tu stock l'ensemble des instances des astres créés dans une list.

Code:

Astre* nearestAstre(const Container<Astre*>& astre)  {

    Astre nearest = nullptr;
    double best = 400.0 // rayon de recherche
    for(auto i : astre) {
         float d = distance(*i);
         if (d < best) {
               best = d;
               nearest = d;
         }
    }
    return d;
}

Ensuite ça s'est très basique, mais ça devrait te suffire.
Tu peux optimiser en prenant en compte la cohérence spatiale/temporel de tes astres.
Si tu a plusieurs player et plusieurs astres du peux faire traitement de lot plus rapide que la somme des traitements individuelles.

Bonne chance pour la suite.

Alors, y a plusieurs façons de faire.
La version GM like, ou tu crées un objet Object, qui contiens tes coordonnées, et autres attributs partagés entre toutes les instances, plus les fonctions virtuelles step et draw.

Code:

class Object {
static std::vector< std::vector<Object*> * > objects;
public:
float x, y;
Object(float x, float y, int object_index);
~Object();
virtual void step(float dt) {}
virtual void draw() const {}

static std::vector<Object*> & getInstancesOf(int object_index);

static void updateInstances(float dt);
static void drawInstances();

};

Dans le constructeur d'Object, tu ajoutes ton pointeur dans le vector objects (vector 2d [index, ptr]).
Dans updateInstances tu loops juste sur tous les pointeurs pour leur faire faire la methode step, de même avec draw.
getInstancesOf te donnes toutes les instances d'un type d'objet.

Pour la creation d'index auto, histoire de pas se prendre la tête, tu crées une classe template qui te fait ça toute seule:

Code:

int object_ptr = 0;
template<class T> class ObjectIndex : public Object
{
public:
    ObjectIndex(float x, float y): Object(x, y, object_index) {}
    static const int object_index;
};
template<class T> const int ObjectIndex<T>::object_index = object_ptr++;

Et ensuite t'utilise ça en dérivant ta classe:

Code:

class A : public ObjectIndex<A>
{
public:
    A(float x, float y) : ObjectIndex<A>(x, y) {}
    void step(float dt);
    void draw() const;
};

Et du coup la pour récupérer tes instances d'un type d'objet spécial, tu fais juste un:
getInstancesOf(A::object_index);

arthuro a écrit:

Salut Ancestral,
Tu as pensé à juste faire une recherche du minimum dans une boucle ?

Oui, en réalité c'est exactement ce à quoi je pensais implicitement quand je parlais de passer un vector en paramètre de ma fonction nearestAstre().
Ce qui m'embêtais plus c'était de devoir faire un push_back a chaque fois que je cree un Astre. Et puis, je sais pas pourquoi mais le fait de passer un vector en parametre de la fonction je trouves pas ca sexy   .
N'empêche qu'en effet ca marche tres bien et en plus ca à le mérite de pas être trop compliqué.

Pour ce qui est de ta solution onilink je crois que c'est exactement ce que je cherchais.
Surtout que je ne l'ai pas précisé mais mes classes Astre et Player héritent bien d'une classe Objet (qui contient les attributs x et y entre autre). Du coup je vais essayer de faire comme ça.

Merci beaucoup  

J'ai un peu répondu à côté de la question ^^.

Ancestral a écrit:

Pour ce qui est de ta solution onilink je crois que c'est exactement ce que je cherchais.
Surtout que je ne l'ai pas précisé mais mes classes Astre et Player héritent bien d'une classe Objet (qui contient les attributs x et y entre autre). Du coup je vais essayer de faire comme ça.

Merci beaucoup  

Perso j'ai basé tout mon game engine sur une structure similaire, c'est très efficace pour la gestion des collisions.
Par la suite tu peux ajouter a chaque instance un masque, et pour les masques t'utilises un visitor pattern afin qu'ils puissent profiter du double dispatching (en gros si tu fais mask->collision(otherMask) ça sera capable d'appeler la bonne methode sans que t'ais a mettre des conditions dégueulasses dans chacun de tes type de masque), mais aussi un identifiant, que t'ajoutes ensuite a une map qui les relies a leur pointeur. L'id est très très utile pour savoir si une instance est toujours vivante, car a partir d'un pointeur tu ne peux rien faire a ce niveau.

Depuis que je dev j'ai pas trouvé meilleure structure, et pourtant c'est assez proche de celle utilisé par GM. Le seul défaut c'est que tu peux pas accéder proprement a n'importe quelle instance d'objet dans son type d'origine sans avoir a faire un cast pas très propre.
Mais ça à la limite on en a rarement besoin, et perso j'ajoute un nouveau vector static a ma classe en question si c'est vraiment nécessaire.

Le visitor pattern c'est has been, vive la génération de vtables en TMP :D

Oui ben le visitor pattern c'est facile a implémenter x)
Ton truc je connais même pas de nom

Edit: Ah ok TMP c'est template meta programming >.<

Ouaip, mais comme ça j'peux avoir du dispatching virtuel sur DEUX paramètres