Bonjour,

je reviens après avoir essayé de concevoir un programme basé sur l'algorithme a*.

Après l'avoir développé j'ai observé des ralentissements, mais des ralentissements tout à fait justifiés (je connais l'origine du problème).

Pour chaque tour dans l'algorithme a*, je fais plusieurs boucles.

L'idée est en fait lorsque je cherche des noeuds adjacents, je fais une boucle for pour vérifier les noeuds adjacents horizontal (donc 3 possibilités), pour chaque noeud vertical (3 possibilités, donc 3*3), pour chaque noeud adjacent je vérifie les obstacles qui sont autour horizontal et vertical pour ne pas que l'entité qui suit le chemin rentre en collision avec des objets du décor (ça revient à du 3*3, soit 3*3*3*3), et sachant que j'ai créé un système de Tilemap, ou chaque tuile de taille 30*30, peut avoir plusieurs zone de hitbox (des zones de hitbox de taille 15*15, donc de 0 à 4 maximum).

Sauf que bon, quand on s'éloigne un peu de l'objectif, le programme commence à devenir lent et j'ai vérifié le nombre d'itérations qui monte jusqu'à 15000 par frame, ce qui fait... beaucoup . Il doit y avoir des moyens d'optimisations. Donc je partage un peu de mon code :

void adjacent_nodes(sf::Vector2f current_node_position, Node current_node, Character *entity, sf::Vector2f goal_position, TileMap* ia_map, NodeList &open_list, NodeList &closed_list, int* calc_number)
{
    //Cherche 8 noeuds adjacents du noeud actuel


    for(int i  =  current_node_position.x-DIST_IA  ;  i  <=  current_node_position.x + DIST_IA ;  i += DIST_IA)
    {
        if(i  <  0   ||   i  >  ia_map->getSize().x*TILE_SZ)
            continue;

        if(abs(current_node_position.x-i)>30)
            continue;

        for(int j = current_node_position.y-DIST_IA  ;  j  <=  current_node_position.y+DIST_IA  ;  j += DIST_IA)
        {

            if(j  <  0   ||   j  >  ia_map->getSize().y*TILE_SZ)
                continue;

            float straight_cost(0);


            if(abs(current_node_position.y-j)>30)
                continue;


            if(i  ==  current_node_position.x  &&  j  ==  current_node_position.y)
                continue;





            // Vérifie si il y a collision

            bool collision_map=false;








	    sf::Rect<float> temp_contact_entity(i-entity->getHitbox().width/2,j-entity->getHitbox().height/2,entity->getHitbox().width, entity->getHitbox().height);


            for(int m(i-TILE_SZ ); m<=i+TILE_SZ ; m+=TILE_SZ )
            {
                if(m<0 || m>ia_map->getSize().x*TILE_SZ )
                    continue;



                for(int n(j-TILE_SZ ); n<=j+TILE_SZ ; n+=TILE_SZ )
                {
                    *calc_number=*calc_number+1;

                    if(n<0 || n>ia_map->getSize().y*TILE_SZ )
                        continue;

                    for(int k(0); k < ia_map->getTile(sf::Vector2f(m/TILE_SZ, n/TILE_SZ)).getElementTile().rect_hitbox.size() && !collision_map; k++)
                    {
                        sf::Rect<float> temp_rect(((m/TILE_SZ)*TILE_SZ)+ia_map->getTile(sf::Vector2f(m/TILE_SZ, n/TILE_SZ)).getElementTile().rect_hitbox[k].left,
                                                  ((n/TILE_SZ)*TILE_SZ)+ia_map->getTile(sf::Vector2f(m/TILE_SZ, n/TILE_SZ)).getElementTile().rect_hitbox[k].top,
                                                  ia_map->getTile(sf::Vector2f(m/TILE_SZ, n/TILE_SZ)).getElementTile().rect_hitbox[k].width,
                                                  ia_map->getTile(sf::Vector2f(m/TILE_SZ, n/TILE_SZ)).getElementTile().rect_hitbox[k].height);


                        sf::Rect<float> temp_contact_entity_2 (i-entity->getHitbox().width*2/2,j-entity->getHitbox().height*2/2,entity->getHitbox().width*2, entity->getHitbox().height*2);

                        if(contact_rectangles(temp_contact_entity, temp_rect))
                            collision_map=true;
                        else if(contact_rectangles(temp_contact_entity_2, temp_rect))
                            straight_cost=DIST_IA;

                    }

                }
            }




            if( collision_map )
                continue;




            // Vérifie si le noeud est dans les listes



            Node temp_node{current_node.m_cost_g+distance_vector(current_node_position, sf::Vector2f(i,j))+straight_cost, distance_vector(sf::Vector2f(i,j), goal_position), current_node_position};

            if(open_list.find(sf::Vector2f(i,j))!=open_list.end() && open_list[sf::Vector2f(i,j)].m_cost_f()<temp_node.m_cost_f())
                continue;


            if(closed_list.find(sf::Vector2f(i,j))!=closed_list.end() && closed_list[sf::Vector2f(i,j)].m_cost_f()<temp_node.m_cost_f())
                continue;
            else
            {
                open_list[sf::Vector2f(i,j)]=temp_node;
            }
        }
    }


}

C'est juste la fonction qui vérifie les noeuds adjacents, mais le problème vient de là j'ai vérifié.

La question c'est est ce que SFML peut supporter autant d'itérations, ou bien le programme se doit d'être absolument optimisé ?

Bon je n'ai pas trouvé de solution, je me demande si générer un chemin en plusieurs frames est une bonne idée.

C'est à dire que je mets une durée limite pour le calcul de chemin, une fois dépassé, si le programme a réussi a trouvé un chemin approprié, tant mieux, sinon j'enregistre l'état et je continue à la frame qui suit et ainsi de suite, ça éviterai de faire ramer le programme.

J'aimerai bien avoir des avis histoire d'éviter de faire de la merde

Disons que ton code requiert quand même une certaine dose de courage pour être lu.
Je suis pas un expert du A* (jamais implémenté mais j'ai fais pas mal de graph)
Alors si on regarde le A*, https://commons.wikimedia.org/wiki/File:Astar_progress_animation.gif?uselang=fr , tu me dis qu'à 15.000 itérations de ça, tu lag.
C'est pas déconnant, je vois des find, je sais pas si ça peut être amélioré, tu es peut-être pas obligé de matter 100% des cases mais sauter une case sur deux (réduire le nombre de case analysée par l'algorithme), tu peux aussi lancer le programme en release si c'est pas déjà fait pour voir si le mode debug réduit trop l'exécution.

Après...je viens de voir un truc, tu me dis 15.000 itération par frame ? Je suis à peu près sûr que l'A* a aucun intérêt à être exécuté à chaque frame. Tu dis à un objet d'aller d'un point A à un point B, l'A* trouve le chemin en une fois et ensuite l'entité a juste à suivre le chemin(plus besoin de relancer A*)

Le 30 juillet 2017 à 00:29:43 whiteapplex a écrit :
Disons que ton code requiert quand même une certaine dose de courage pour être lu.

C'est clair, il est dégueulasse, et faut prendre le temps, mais c'était juste pour illustrer ce que j'ai dit, le code n'a en soi aucun soucis(mis à part au niveau de l'optimisation très certainement), mais j'ai cherché à prendre en compte un maximum de facteur.

Je suis pas un expert du A* (jamais implémenté mais j'ai fais pas mal de graph)
Alors si on regarde le A*, https://commons.wikimedia.org/wiki/File:Astar_progress_animation.gif?uselang=fr , tu me dis qu'à 15.000 itérations de ça, tu lag.
C'est pas déconnant, je vois des find, je sais pas si ça peut être amélioré, tu es peut-être pas obligé de matter 100% des cases mais sauter une case sur deux (réduire le nombre de case analysée par l'algorithme), tu peux aussi lancer le programme en release si c'est pas déjà fait pour voir si le mode debug réduit trop l'exécution.

Je me posais aussi la question comment fonctionnait la recherche pour le find. Je suis pas un expert à 100% en C++, j'essaye de faire mes pattes sur un petit projet et les seuls moyens que je sais pour chercher une valeur dans une std::map c'est soit utiliser un iterateur, soit find (même si je pense que les deux se rapprochent dans le fond), après peut être que y a autre chose

Après...je viens de voir un truc, tu me dis 15.000 itération par frame ? Je suis à peu près sûr que l'A* a aucun intérêt à être exécuté à chaque frame. Tu dis à un objet d'aller d'un point A à un point B, l'A* trouve le chemin en une fois et ensuite l'entité a juste à suivre le chemin(plus besoin de relancer A*)

Oui disons que le dynamisme est de mise L'IA a pour objectif de suivre un personnage, dans notre cas c'est le joueur, et le joueur est très souvent en mouvement. Donc le pathfinding doit être rafraîchi le plus souvent. Mais comme tu me l'as dit, il n'est pas nécessaire de le faire pour chaque frame.

Donc je pense étaler la recherche de chemin sur plusieurs frames et je regarde ce que ça donne.

Et merci beaucoup pour ta réponse whiteapplex

Le 30 juillet 2017 à 00:51:21 vicomteprimary a écrit :

Le 30 juillet 2017 à 00:29:43 whiteapplex a écrit :
Disons que ton code requiert quand même une certaine dose de courage pour être lu.

C'est clair, il est dégueulasse, et faut prendre le temps, mais c'était juste pour illustrer ce que j'ai dit, le code n'a en soi aucun soucis(mis à part au niveau de l'optimisation très certainement), mais j'ai cherché à prendre en compte un maximum de facteur.

Je suis pas un expert du A* (jamais implémenté mais j'ai fais pas mal de graph)
Alors si on regarde le A*, https://commons.wikimedia.org/wiki/File:Astar_progress_animation.gif?uselang=fr , tu me dis qu'à 15.000 itérations de ça, tu lag.
C'est pas déconnant, je vois des find, je sais pas si ça peut être amélioré, tu es peut-être pas obligé de matter 100% des cases mais sauter une case sur deux (réduire le nombre de case analysée par l'algorithme), tu peux aussi lancer le programme en release si c'est pas déjà fait pour voir si le mode debug réduit trop l'exécution.

Je me posais aussi la question comment fonctionnait la recherche pour le find. Je suis pas un expert à 100% en C++, j'essaye de faire mes pattes sur un petit projet et les seuls moyens que je sais pour chercher une valeur dans une std::map c'est soit utiliser un iterateur, soit find (même si je pense que les deux se rapprochent dans le fond), après peut être que y a autre chose

Après...je viens de voir un truc, tu me dis 15.000 itération par frame ? Je suis à peu près sûr que l'A* a aucun intérêt à être exécuté à chaque frame. Tu dis à un objet d'aller d'un point A à un point B, l'A* trouve le chemin en une fois et ensuite l'entité a juste à suivre le chemin(plus besoin de relancer A*)

Oui disons que le dynamisme est de mise L'IA a pour objectif de suivre un personnage, dans notre cas c'est le joueur, et le joueur est très souvent en mouvement. Donc le pathfinding doit être rafraîchi le plus souvent. Mais comme tu me l'as dit, il n'est pas nécessaire de le faire pour chaque frame.

Donc je pense étaler la recherche de chemin sur plusieurs frames et je regarde ce que ça donne.

Et merci beaucoup pour ta réponse whiteapplex

Clairement oui il faut étaler. Tu peux faire un truc du genre "on exécute A* toutes les 3secondes où si le joueur a bougé de 5 cases depuis la dernière exécution".
Si c'est un std::map ça devrait aller je pense, ils utilisent des arbres rouges & noirs en théorie optimisés pour la recherche ( http://www.cplusplus.com/reference/map/map/find/ la complexité est logarithmique et pas linéaire donc ça va (toujours en théorie, vu que je suis pas un expert du code c'est peut-être possible d'avoir du temps constant) ).

De facon general, je ne mettrais pas un calcul lourd comme ca dans le meme thread d'execution que le rafraichissement de l'image.