Discussion :

[LiquidHuk]

Je suis en train de travailler sur un code de lissage d'A*. Mon but est de vérifier si un nœud et visible par un autre.

Pour cela, je commence par parcourir l'ensemble de mes obstacles statiques, je calcule leur distance par rapport au segment qui va d'un nœud à l'autre. Ainsi, je peux définir s'il est possible de parcourir le segment sans risque de rencontrer un obstacle.
Une fois l'idée mise en place, je pense l'améliorer en rangeant les obstacles dans un arbre.

Après plusieurs tests, je suis bloqué et le résultat n'est pas satisfaisant... Je pense que le problème provient du calcul de l'équation de la droite.

Code :

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool PathFinding::lineOfSight(Vecteur start, Vecteur goal)
{
	int x = start.x;
	int y = start.y;
	int gx =  goal.x;
	int gy =  goal.y;
	int distance;			//Distance entre la droite et l'obstacle
 
	int dx = ABS(gx - x);
	int dy = ABS(gy - y);
 
	float a, b;
 
	if(dx == 0 && dy ==0)
		return true;
 
	if(dy != 0)
	{
		a = dy/dx;
		b = y - a*x;
 
                //On parcourt la liste des obstacles
		std::unordered_set<int>::iterator it(m_staticObstacles.begin());
		for(; it != m_staticObstacles.end(); it++)
		{
                        //On récupère la coordonée du noeud obstacle à partir de son ID
			y = (*it)/m_world.worldSize;
			x = (*it) -y;
                        //On calcule la distance entre le noeud obstacle et la droite
			distance =  ABS(-a*x -y +b ) / pow((int)pow(a,2) +1, 0.5);
			if(distance  < m_world.step)
				return false;
		}
	}
 
	else
	  distance = dx;
 
 
	return true;
}

[-Gesicht-]

Salut,

Je n'ai pas très bien compris, tu veux faire un lancer de rayons?
Si c'est le cas pourquoi ne pas decouper ta scnène en octree par exemple?

sinon pour l'équation de la droite ce n'est pas plutôt a=dy/dx?

[LiquidHuk]

Oui, je compte en effet découper ma scène par la suite.

A la sortie du A* j'ai une série de coordonnées que j'aimerais épurer en ne conservant que les points indispensables. Le résultats devrait me permettre d'obtenir des trajectoires directes au lieu d'une série de petits déplacements fournie par l'A*.

sinon pour l'équation de la droite ce n'est pas plutôt a=dy/dx?

En effet, j'ai oublié de supprimer une partie de mes tests.

Étrangement, je trouve une distance qui vaut 0 ou 7.07 comme seules valeurs inférieurs à m_worldStep (qui vaut 10). Mais surtout, je trouve une de ces deux valeurs à chaque segments (alors que certains segments sont loin de tout obstacle)

EDIT : J'ai corrigé le code dans le premier post et ai rajouté quelques commentaires

[saad.hessane]

Bonjour,

J'ai à peine parcouru ton algorithme, donc pas de commentaire dessus (peut être plus tard).
Sache qu'un algorithme connu dans le domaine de la cartographie est utilisé justement pour simplifier les géométries (linéaires ou surfaciques).
Il s'agit de l'algorithme de Douglas-Peucker.
Je te laisse regarder.

++

[-Gesicht-]

La distance d'un point à une droite ce serait plutôt

Code :

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

1
2
 
distance = abs(a*x + b*y) / sqrt(a*a + b*b);

J'ai une autre question, tu utilises une bijection pour stocker les coordonnées de ton nœud? Je dis ça car je ne comprend pas très bien pour quoi ton nœud n'as pas un x,y comme coordonnées.

[LiquidHuk]

Il s'agit de l'algorithme de Douglas-Peucker.
Je te laisse regarder.

Merci pour le conseil, je vais regarder ça !

La distance d'un point à une droite ce serait plutôt

Code :

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

1
2
 
distance = abs(a*x + b*y) / sqrt(a*a + b*b);

J'avoue que je n'ai plus de souvenir de cette formule de mes cours de maths. J'en ai testé plusieurs trouvées à droite à gauche sans succès. Je vais reposter avec les résultats de cout et un affichage du chemin avec la SFML histoire que vous puissiez y voir plus clair.

J'ai une autre question, tu utilises une bijection pour stocker les coordonnées de ton nœud? Je dis ça car je ne comprend pas très bien pour quoi ton nœud n'as pas un x,y comme coordonnées.

J'utilise dans l'A* un objet nœud qui stocke les coordonnées et un ID (y*m_world.WorldSize + x), en plus des calculs de l'A*. J'utilise l'ID afin d'avoirr le container unordered_set qui me permet de ne gérer que des int dans mon algorithme et grâce à l'ID, je peux retrouver le nœud et ses infos si j'en ai besoin.

[LiquidHuk]

Tout d'abord, voici la portion de code qui utilise lineOfSight() :

Code :

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
27
28
29
30
31
void PathFinding::smoothPath()
{
    Vecteur startPosition(*m_resultPath.begin());			//Noeud de départ pour le segment étudié
    Vecteur lastVisiblePosition(*m_resultPath.begin());		//Le dernier noeud visible depuis startPosition
    std::vector<Vecteur> tempPath;							//Le chemin obtenu est stocké ici
 
    tempPath.push_back(startPosition);
 
	//On parcourt les positions retournées par l'algorithme A*
    std::vector<Vecteur>::iterator it(m_resultPath.begin());
    for(; it != m_resultPath.end(); it++)
    {
		//Si le noeud de départ ne "voit" pas le noeud pointé par it
		if(!lineOfSight(startPosition, *it))
		{
			//On stocke le dernier noeud visible dans tempPath
			tempPath.push_back(lastVisiblePosition);
			//DEBUG
			std::cout << "NEW NODE" << std::endl;
			sf::CircleShape shape( m_world.step / 4);
			shape.setFillColor(sf::Color::Green);
			shape.setPosition(lastVisiblePosition.x, lastVisiblePosition.y);
			m_shapes.push_back(shape);
		}
		//Si le pointé par it est visible par le noeud de départ
		else
			//On actualise la valeur de la variable qui stocke le dernier noeud visible
			lastVisiblePosition = *it;
    }
    m_resultPath = tempPath;
}

En pièce jointe j'ai mis un screenshot du résultat :
- En noir les nœud utilisables
- En blanc les nœud obstacles
- En violet les nœud obstacles dynamiques
- En bleu le résultat de l'A*
- En vert le résultat après lissage

Le lissage ne renvoie donc que le nœud de départ, ce qui est logique puisque dés le premier nœud il pense être trop prés d'un obstacle (distance = 0).

Il s'agit de l'algorithme de Douglas-Peucker.
Je te laisse regarder.

Merci pour le conseil, je vais regarder ça !

J'ai regardé le fonctionnement de l'algorithme, mais je ne vois pas comment je pourrais l'appliquer à un cas avec des obstacles. Ici je cherche à simplifier une liste de points, mais pour cela je dois prendre en compte une liste d'obstacles.

[saad.hessane]

Bonjour,

Une fois l'algorithme A* appliqué, tu te retrouves avec une liste de points de la forme (x,y).
Pour lisser simplifier ta géométrie tu n'as plus besoin de connaitre tes obstacles.
Ta géométrie représente un ensemble de points qui peuvent former une ligne droite. Tu n'as besoin que du point de début et du point de fin de cette ligne droite. Pour cela appliquer l'algorithme de Douglas-Peucker avec une distance point/droite de 0 serait une solution (la formule de calcule de la distance utilisé dans le lien que je t'ai donné est à changer par contre - voir plus bas).

Tu peux aussi faire plus simple en parcourant la collection de point et en éliminant les points qui se retrouvent alignés avec le point précédent et suivant.

La distance d'un point à une droite ce serait plutôt

Code :

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

1
2
 
distance = abs(a*x + b*y) / sqrt(a*a + b*b);

Vu le schéma en quadrillage, la distance utilisée est celle de Manhattan. D'où je suppose la formule qu'il a utilisé (formule à vérifier quand même). [EDIT] Bêtise

[LiquidHuk]

Bonjour,

Une fois l'algorithme A* appliqué, tu te retrouves avec une liste de points de la forme (x,y).
Pour lisser simplifier ta géométrie tu n'as plus besoin de connaitre tes obstacles.

Dans l'exemple en pièce jointe (message précédent), je voudrais obtenir le résultat en pièce jointe (de ce message). Mais si je ne prends pas en compte les obstacles et qu'un obstacle se trouve entre le premier et le deuxième point, je ne pourrais pas le savoir et l'algorithme de Douglas-Peucker m'enverra droit dans le mur, non ?

[saad.hessane]

Je pensais à une simplification plus du genre de l'image ci-jointe.
L'algorithme de Douglas-Peucker est utile si tu veux simplifier suivant une tolérance. Vu que tu veux garder exactement la même géométrie mais supprimer les points inutiles, pense plutôt à la version simplifier dont je te parlais.

[LiquidHuk]

En fait je ne veux pas garder la même géométrie, justement. Je veux obtenir un résultat similaire à un algorithme theta* : me déplacer "d'obstacle en obstacle", parcourir le chemin réel le plus court pour atteindre la position d'arrivée.

[saad.hessane]

Ah d'accord. Donc oui oublie ce que je t'ai dit, j'avais mal compris ton problème .

[EDIT] : je regarde ton code...

[LiquidHuk]

Cet après midi je pense avoir compris une partie du problème qui fait que mon algorithme ne fonctionne pas : j'utilise l'équation de droite pour tester la distance entre la droite et les nœuds obstacles. Je ne teste pas la distance entre le segment et les nœuds obstacles. C'est tout à fait logique que je trouve une distance droite-obstacle valant toujours 0 puisque toutes les droites testées coupent au moins un obstacle !

[LiquidHuk]

Code :

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

1
2
 
distance = abs(a*x + b*y) / sqrt(a*a + b*b);

Comment est-ce possible d'avoir une équation en y = ax + b et une distance point/droite se calculant avec b*y ?

J'ai corrigé plusieurs erreurs, dont

a = dy/dx qui doit s'écrire a = 1.0f *dy/dx afin de ne pas avoir la simplification en int...

J'ai également corrigé l'erreur dont j'ai parlé dans le post précédent (avec le calcul qui se faisait sur toute la droite et non pas sur le segment).

Les équations de droites sont correctes (sauf cas particuliers que je gérerais plus tard), j'ai des problèmes avec la formule de distance visiblement.