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;
}