Irrlicht et le pathfinding

Pages: 1

Accueil forums
» Algorithmique et I.A
» Irrlicht et le pathfinding

06-05-2013 13:33:01

darhkan: Membres; Date d'inscription:; Messages: 4; IP: 82.228.231.185; Courriel

Bonjour a tous,

Je post pour la première et j'espère que vous arriverez a m'aider car je suis a bout, une semaine que je cherche d'ou vient mon erreur, je m'explique:
J'essaie d'implémenter l'algorithme A* pour du pathfinding, mon but étant de faire bouger un robot dans un entrepôt en lui donnant un endroit a atteindre tout en évitant les obstacles.

J'ai tester mon algo sans irrlicht en 2D avec un tableau de 0(obstacle) et 1(terrain praticable) pour la map et tout marche parfaitement, malheureusement quand j'essaie de le faire avec Irrlicht ça ne passe pas.
Le calcul de l'itinéraire se bloque 1 fois sur 2 et selon la destination soit le robot arrive difficilement a son objectif soit il reste tout bêtement bloqué dans les obstacle alors qu'il devrait les détecter et les contourner...

Voici ma fonction calculant l'itinéraire :

Code c++ :


bool AutomaticDeplacement::pathFinding(irr::core::vector3df arrivee)
{
    m_arrivee = arrivee;
    m_depart = m_robot->getPosition();
    m_current = m_robot->getPosition();
    int xValue[8] = {-1,-1,0,+1,+1,+1,0,-1};
    int zValue[8] = {0,+1,+1,+1,0,-1,-1,-1};
    int factor[8] = {10,14,10,14,10,14,10,14};
    float xVector[8]= {100,60,0,-60,-100,-60,0,60};
    float zVector[8]= {0,-60,-100,-60,0,60,100,60};
    irr::core::vector3df a = irr::core::vector3df(1000000,1000000,1000000);
    Node depart(m_current, a, 0, 0, m_arrivee);
    
    listeFermee.push_back(depart);
    searching = true;
    pathFound = false;
    while(searching)
    {
         if(listeFermee.size()==0)
        {
            cout << "Progression = 0%" << endl;
        }
        else
        {
            int ancienPourcentage = 0;
            ancienPourcentage = pourcentage;
            pourcentage = 100-((listeFermee.back().getF() - listeFermee.back().getG())/100);
            if(ancienPourcentage!=pourcentage)
                cout << "Progression = " << pourcentage << "%" << endl;
        }

        Node parent = listeFermee.back();
        if(parent.getPosition().X == m_arrivee.X && parent.getPosition().Z == m_arrivee.Z)
        {
            searching = false;
            pathFound = true;
        }
        else
        {
            for(unsigned int i=0; i<8; i++)
            {
                irr::core::vector3df newPosition = m_robot->getPosition();
                newPosition.X = parent.getPosition().X + xValue[i];
                newPosition.Z = parent.getPosition().Z + zValue[i];
                Node currentNode(newPosition, parent.getPosition(), parent.getG(), factor[i], m_arrivee);
                if(!checkCollision(currentNode.getPosition(),xVector[i], zVector[i]) && !checkListeFermee(currentNode))
                {
                    if(!checkListeOuverte(currentNode, parent))
                        listeOuverte.push_back(currentNode);
                }


            }
            LowestF(parent);
        }
    }
    if(pathFound)
        {
            list<Node>::reverse_iterator it;
            for(it = listeFermee.rbegin(); it!=listeFermee.rend();++it)
            {
                Node currentNode = *it;
                finalPath.push_back(currentNode.getPosition());
            }
        }

    return true;
}

bool AutomaticDeplacement::checkCollision(irr::core::vector3df position, float vectorX, float vectorZ)
{
    ray.start = position;
    ray.end = ray.start + irr::core::vector3df(X,40,Z);
    coll = collisionManager->getSceneNodeAndCollisionPointFromRay(ray,outCollisionPoint,outTriangle);
    if(coll)
    {
        return true;
        cout << "Collision" << endl;
    }
    else
        return false;
}

Si vous avez besoin d'un autre bout de code en particulier dites les moi.

Merci d'avance
Darhkan

Hors ligne

Historique

06-05-2013 16:45:34

Magun: Administrateurs; Date d'inscription:; Messages: 910; IP: 37.220.52.79; Courriel Site web

si ton algo marche en 2D ça peut venir que du raytest donc la c'est un probleme d'irrlicht (je connais le bug sur le svn ... si tu boss dessus)
ce qui me chagrine le plus dans ton code ce sont les testes d’égalité sur des floatants, tu ne peut garantir l'égalité dans certain cas

bon c'était une réponse vite fait j'ai pas beaucoup de temps, le plus simple serait que tu face une démo compilable

Project: ImmortalGalaxy, portfolio, github, Agence DRIAD

Hors ligne

Historique

07-05-2013 08:25:19

darhkan: Membres; Date d'inscription:; Messages: 4; IP: 82.228.231.185; Courriel

Et bien apres des dizaines de test hier j'ai vu que meme quand le test de collision est positif la valeur est ajouté dans ma listeOuverte et peut etre utilisé en tant que position courante.. J'arrive pas a voir comment ça se fait.

Hors ligne

Historique

07-05-2013 10:30:37

Magun: Administrateurs; Date d'inscription:; Messages: 910; IP: 193.54.203.134; Courriel Site web

peut tu poster les fonctions/class/struct LowestF, checkListeOuverte et Node ?

Project: ImmortalGalaxy, portfolio, github, Agence DRIAD

Hors ligne

Historique

07-05-2013 13:03:36

darhkan: Membres; Date d'inscription:; Messages: 4; IP: 82.228.231.185; Courriel

Node.h :

Code c++ :


#ifndef NODE_H
#define NODE_H
#include <irrlicht.h>

class Node
{
    public:
        Node();
        virtual ~Node();
        Node(irr::core::vector3df position, irr::core::vector3df parent, float Gparent, int factor,irr::core::vector3df arrivee);
        float getH() const;
        float getG() const;
        float getF() const;
        void setF();
        void setH(float a);
        void setG(float a);
        void afficher() const;
        irr::core::vector3df getPosition() const;
        void setParent(irr::core::vector3df positionParent);
        irr::core::vector3df getParent();
    protected:
    private:
        float F,G,H;
        irr::core::vector3df m_position;
        irr::core::vector3df m_parent;
        irr::core::vector3df m_arrivee;
};

#endif // NODE_H

Node.cpp :

Code c++ :


#include "Node.h"
#include "AutomaticDeplacement.h"
#include <iostream>

using namespace std;

Node::Node()
{

}

Node::Node(irr::core::vector3df position, irr::core::vector3df parent, float Gparent, int factor, irr::core::vector3df arrivee) : m_position(position), m_parent(parent), m_arrivee(arrivee)
{
    G = Gparent + factor;
    //H = 10 * abs(m_position.X-m_arrivee.X) + abs(m_position.X-m_arrivee.X);
    H = sqrt((m_position.X-m_arrivee.X)*(m_position.X-m_arrivee.X)+(m_position.Z-m_arrivee.Z)*(m_position.Z-m_arrivee.Z));
    //cout << "H = " << H << " position x = " << m_position.X << " position z = " << m_position.Z << " m_arrivee x = " << m_arrivee.X << " m_arrivee.Z = " << m_arrivee.Z << endl;
    F = G+H;
}

Node::~Node()
{
}

void Node::setG(float a)
{
    G = a;
}

float Node::getG() const
{
    return G;
}

void Node::setH(float a)
{
    H = a;
}

float Node::getH() const
{
    return H;
}

float Node::getF() const
{
    return F;
}

void Node::setF()
{
    F = G+H;
}

irr::core::vector3df Node::getPosition() const
{
    return m_position;
}

void Node::setParent(irr::core::vector3df positionParent)
{
    m_parent = positionParent;
}

irr::core::vector3df Node::getParent()
{
    return m_parent;
}

void Node::afficher() const
{
    cout << "Node : " << endl;
    cout << "coordonnee = " << m_position.X << " / " << m_position.Z << endl;
    cout << "coordonnee du parent = " << m_parent.X << " / " << m_parent.Z << endl;
    cout << "F = " << F << " G = " << G << " H = " << H << endl;
}


LowestF : 

void AutomaticDeplacement::LowestF(Node parent)
{
    int plusPetit = 1000000, indice;
    Node test;
    for(unsigned int i=0; i<listeOuverte.size(); i++)
    {
        if(listeOuverte[i].getF() < plusPetit && listeOuverte[i].getParent() == parent.getPosition())
        {
            plusPetit = listeOuverte[i].getF();
            test = listeOuverte[i];
            m_current = listeOuverte[i].getPosition();
            indice = i;
        }
    }
    //listeOuverte[indice].afficher();
    listeOuverte.erase(listeOuverte.begin()+indice);
    cout << "nouveau point : X = " << test.getPosition().X << " Z = " << test.getPosition().Z << endl;
    listeFermee.push_back(test);
}

checkListeOuverte :

Code c++ :


bool AutomaticDeplacement::checkListeOuverte(Node current,Node parent)
{
    for(unsigned int i=0; i<listeOuverte.size(); i++)
    {
        if(listeOuverte[i].getPosition().X == current.getPosition().X && listeOuverte[i].getPosition().Z == current.getPosition().Z)
        {
            if(current.getG() < listeOuverte[i].getG())
            {
                listeOuverte[i].setG(current.getG());
                listeOuverte[i].setH(current.getH());
                listeOuverte[i].setF();
                listeOuverte[i].setParent(current.getParent());
                return true;
            }
        }
    }
    return false;
}

Hors ligne

Historique

11-05-2013 16:00:26

Magun: Administrateurs; Date d'inscription:; Messages: 910; IP: 92.146.114.53; Courriel Site web

je ne t'ai pas oublier, mais je n'ai pas beaucoup de temps à moi désolé

Project: ImmortalGalaxy, portfolio, github, Agence DRIAD

Hors ligne

Historique

27-05-2013 15:01:41

darhkan: Membres; Date d'inscription:; Messages: 4; IP: 82.228.231.185; Courriel

Une idée?

Hors ligne

Historique

27-05-2013 15:52:28

Magun: Administrateurs; Date d'inscription:; Messages: 910; IP: 92.146.237.118; Courriel Site web

aucune désoler

d'après ce que tu dit ça viens de checkListeOuverte
mais d'autre par tu me dit que ton algo marche en 2d

à par la détection des collisions et les float que je t'st déjà parler ; ton algo est identique je suppose ...
donc tu n'a que ça à regarder, je pensse

Project: ImmortalGalaxy, portfolio, github, Agence DRIAD

Hors ligne

Historique