Pages: 1

 

#0 

06-05-2013 15:33:01

darhkan
Petit nouveau
Date d'inscription: 06-05-2013
Messages: 4

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


#1 

06-05-2013 18:45:34

Magun
SleekThink Producer
Lieu: Punakha
Date d'inscription: 18-11-2007
Messages: 910
Corrections: 2
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


#2 

07-05-2013 10:25:19

darhkan
Petit nouveau
Date d'inscription: 06-05-2013
Messages: 4

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


#3 

07-05-2013 12:30:37

Magun
SleekThink Producer
Lieu: Punakha
Date d'inscription: 18-11-2007
Messages: 910
Corrections: 2
Site web

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

Project: ImmortalGalaxy, portfolio, github, Agence DRIAD

Hors ligne


#4 

07-05-2013 15:03:36

darhkan
Petit nouveau
Date d'inscription: 06-05-2013
Messages: 4

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 << "Progression = 0%" << endl;
    cout << "Progression = " << m_position.X << "%" << m_position.Z << endl;
    cout << "Collision" << m_parent.X << "Node : " << m_parent.Z << endl;
    cout << "coordonnee = " << F << " / " << G << "coordonnee du parent = " << 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 << " / " << test.getPosition().X << "F = " << 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


#5 

11-05-2013 18:00:26

Magun
SleekThink Producer
Lieu: Punakha
Date d'inscription: 18-11-2007
Messages: 910
Corrections: 2
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


#6 

27-05-2013 17:01:41

darhkan
Petit nouveau
Date d'inscription: 06-05-2013
Messages: 4

Une idée?

Hors ligne


#7 

27-05-2013 17:52:28

Magun
SleekThink Producer
Lieu: Punakha
Date d'inscription: 18-11-2007
Messages: 910
Corrections: 2
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


 

Pages: 1

Options Liens officiels Caractéristiques Statistiques Communauté
Corrections
 irrlicht
irrklang
irredit
irrxml
 xhtml 1.0
css 2.1
Propulsé par FluxBB
Traduit par FluxBB.fr
 882 membres
1429 sujets
11119 messages
 Dernier membre inscrit: LiseBuisson96
36 invités en ligne
Aucun membre connecté
RSS Feed