Discussion :

[bombseb]

Bonjour,

Pour un jeu en 2D que je suis en train de développer, j'ai implémenté l'algorithme A* pour le déplacement des ennemis.
L'algo à l'air de pas trop mal marcher, sauf que le calcul du chemin est très lent : Pour déplacer un personnage de 200 pixels, le calcul dure environ 15 secondes.
Je me suis inspiré de ce tuto : http://khayyam.developpez.com/articles/algo/astar/

Ce qui ralenti mon calcul c'est le test de collision (fonction ajouter_cases_adjacentes du tuto) à la ligne :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
if (*((Uint8 *)s->pixels + j * s->pitch + i * s->format->BytesPerPixel) == NOIR)
                /* obstace, terrain non franchissable, on oublie */
                continue;

Sauf que j'utilise un quadtree pour optimiser les tests de collisions justement, mais bon ma fonction de test de collision marche bien je l'ai testé.
Le problème vient du fait que mes ennemis se déplacent au pixel près, pas par case (tiles), du coup cette fonction est appelée plusieurs fois par pixel analysés.

Ma classe QuadTreeNode :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class QuadTreeNode
{
public:
     [...]
 
    sf::IntRect getBounds() const;
 
    bool isCollision (Collisionnable *c, sf::Vector2i p); // Renvoie true si le point passé en paramètre est en collision avec un autre objet que celui passé en paramètre
 
private:
    QuadTreeNode *m_ParentNode;
    sf::IntRect m_Bounds;
    QuadTreeNode *m_ChildNodes[4];                  // Dans l'ordre : NE SE SW NW
    std::vector<Collisionnable*> m_Objets;
 
};

L'implémentation de ma méthode isCollision du quadtree :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool QuadTreeNode::isCollision(Collisionnable *c, sf::Vector2i p)
{
    for (unsigned int i = 0; i < m_Objets.size(); i++)
    {
        if (m_Objets[i] != c)
        {
            sf::IntRect b = m_Objets[i]->getBounds ();
 
            if (b.contains(p)) return true; // si je commente cette ligne le calcul est quasiment instantané
        }
    }
 
    for (unsigned int i = 0; i < 4; i++)
    {
        if (m_ChildNodes[i] != 0)
        {
            sf::IntRect b = m_ChildNodes[i]->getBounds ();
            if (b.contains(p))
            {
                if (m_ChildNodes[i]->isCollision(c, p)) return true; // si je commente cette ligne le calcul est quasiment instantané également
            }
        }
    }
 
    return false;
}

Et voici comment j'appelle cette fonction dans ajouter_cases_adjacentes() :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
            if (m_Map->getQuadTree()->isCollision(this, sf::Vector2i (i,j)))
            {
                // obstacle, terrain non franchissable, on oublie
                continue;
            }

Pour déplacer un personnage de la coordonnée 865,466 à la coordonnée 600,449 (il y a des obstacles entre le point de départ et le point d'arrivée) cette fonction est appelée 2096504 fois par la fonction ajouter_cases_adjacentes().

Merci d'avance pour votre aide...

[bombseb]

Après différents tests, j'arrive à la conclusion que ce qui ralentis l'algo c'est lorsqu'il détecte une collision, ca l'oblige à rallonger le chemin...

[LittleWhite]

Bonjour,

Je pense que votre fonction de collision est appelée bien trop souvent pour le déplacement que vous avez décrit.

Votre fonction isCollision est fausse dans la classe QuadTreeNode.
Le principe du quadtree est qu'il est récursif. Le test fait est le suivant :

- Si l'objet pour lequel on teste la collision n'est pas dans ce rectangle (le rectangle du quad), alors on retourne (false pour indiquer qu'li y n'y a pas la collision là)
- Si ne suis pas dans un noeud final, alors je parcours les 4 sous noeuds (récursion)
- Si je suis dans un noeud final, alors je test les N objets présent dans ce noeud, pour savoir si je suis bien en collision avec l'un d'eux. On retourne le résultat à la fonction parente (qui fera remonter le résultat).

Il me semble que vous n'avez pas du tout fait cela et du coup, vous n'utilisez pas efficacement votre quad tree

[bombseb]

Salut Littlewhite (tu peux me tutoyer hein )

Merci de m'avoir répondu

Ma fonction isCollision marche très bien :

Dans mon node racine je test d'abord la collision avec chaque objet contenu par celui ci, s'il y a collision avec l'un d'entre eux je retourne true (collision).
Sinon, j'appelle la fonction isCollision de mes quatres noeuds enfants (récursion), qui font de même. Si l'un d'entre eux me retourne true, alors le noeud parent retourne true.
S'il aucune collision n'a étée détectée par mes noeuds enfant alors je retourne false (pas de collision)

En fait j'ai bien analysé le problème... Il faut que je revoit la façon dont mes personnages se déplacent. j'ai modifié mon algo A* pour que les personnages se déplacent tile par tile et là c'est quasiment instantané...

[LittleWhite]

Ma fonction isCollision marche très bien :

Oui, elle fonctionne, mais pas de façon optimale, d'après moi.

Dans mon node racine je test d'abord la collision avec chaque objet contenu par celui ci, s'il y a collision avec l'un d'entre eux je retourne true (collision).
Sinon, j'appelle la fonction isCollision de mes quatres noeuds enfants (récursion), qui font de même. Si l'un d'entre eux me retourne true, alors le noeud parent retourne true.
S'il aucune collision n'a étée détectée par mes noeuds enfant alors je retourne false (pas de collision)

En théorie, vous n'avez pas besoin de tester les objets du noeud courant, car ces mêmes objets seront dans un noeuds enfant. Mais cela dépend énormément de comment vous construisez/gérer le quad tree.
De plus, en théorie, vous n'avez aucune obligation d'appeler à chaque fois, les quatres noeuds enfant (seul un, devrait être appelé).

[bombseb]

En théorie, vous n'avez pas besoin de tester les objets du nœud courant, car ces mêmes objets seront dans un nœud enfant. Mais cela dépend énormément de comment vous construisez/gérer le quad tree.

En fait, mes objets se trouvent toujours dans les derniers enfants (au niveau hiérarchique le plus bas), donc dans un parent il ne devrais même pas rentrer dans la 1ere boucle (puisque m_Objet.size() == 0). Mais sur le fond je suis bien d'accord.

De plus, en théorie, vous n'avez aucune obligation d'appeler à chaque fois, les quatre nœuds enfant (seul un, devrait être appelé).

Oui je teste d'abord les limites du nœud enfant et j'appelle sa fonction isCollision seulement si l'objet envoyé en paramètre est contenu dans ses limites :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
sf::IntRect b = m_ChildNodes[i]->getBounds ();
if (b.contains(p))
{
     if (m_ChildNodes[i]->isCollision(c, p)) return true; // si je commente cette ligne le calcul est quasiment instantané également
}

[LittleWhite]

Combien faites vous de subdivision ?
Combien de pixels sont contenu dans les derniers quad et quel est la taille de l'objet testé ?

[bombseb]

Ma map fait 3200 pixels par 3200 pixels (100 tiles par 100 tiles)
Le node racine fait donc la même dimension, les derniers nodes enfants font 100 pixels par 100pixels mais j'ai mis une valeur arbitraire pour l'instant.
L'objet testé, et bien ca dépend, j'ai des objets de toutes les tailles. Mes personnages font 38*36 et par exemple j'ai un mur qui fait 256 pixels par 32.
Mais bon la map et les sprties sont temporaires, je me concentre d'abord sur le moteur du jeu, je chercherais un graphiste plus tard

[LittleWhite]

Essayez de descendre jusqu'à des noeuds de 32x32, ou peut être 64x64.
Après, à part un bogue de remplissage du quadtree, je vois pas cette fois :s

[bombseb]

Oui j'essaierais...

Non mais sinon mon problème de lenteur est simple en fait. J'utilise l'algo A* pour déplacer mes personnage au pixel, c'est ca qui demande trop de calcul.
Et ca demande encore plus de calcul lorsqu'il y a collision car l'algo est obligé de toruver un autre chemin.
Finalement je l'ai modifié pour que mes personnages se déplacent tile par tile, et le calcul est maintenant instantané...