Visibilité en ligne directe

Bonjour,

JE suis en train de m'amuser à faire un petit jeu.

J'ai une grille 2D contenant une map vue de haut. Pour faire simple, on va dire que 0 = la case est libre, 1 = il y a un mur (on ne peut pas passer par cette case). Dans le vrai jeu il y a plusieurs types de cases franchissables ou non, bénéfiques ou non pour le joueur; mais ici on s'en fiche.

Le joueur se trouve en position (X1;Y1). Un ennemi ou un objet quelconque se trouve en position (X2;Y2). La question que j'ai est la suivante: comment déterminer s'il est visible en ligne directe ? C'est-à-dire, concrètement, savoir si on peut tracer une ligne droite allant de (X1;Y1) à (X2;Y2) sans passer par un mur, peu importe la direction de la ligne ?

Par exemple pour la grille suivante, (0;0) en haut à gauche :

1
2
3

0 0 0 0 0
1 1 1 0 1
0 0 0 1 1

Le joueur se trouvant en (0;0), l'algorithme me répondrait oui pour (4;0), mais non pour (2;2) et (3;1). Pour les cas limites, p.ex. (2;2) est-il visible depuis (4;0), je préfèrerais que la réponse soit non, ou autrement dit qu'on ne voie pas à travers un mur continu en diagonale. Le joueur et les ennemis ne peuvent pas se déplacer en diagonale de toute façon.

Il faudrait que l'algorithme soit assez rapide quand même, je pourrais avoir à tester une bonne vingtaine d'objets par frame, 40ms dans mon cas (tous les objets dans un rayon de 15-20 cases). J'ai bien une idée, mais elle est extrêmement naïve, et je ne suis même pas sûr qu'elle soit en mesure de couvrir tous les cas.

Est-ce que ça aurait été plus simple de répondre à cette question si, au lieu d'une grille, je ne stockais qu'une liste de murs avec leurs extrêmités ? Le problème se réduirait à faire des tests d'intersection de segments dans ce cas. Sachant que, selon les niveaux, j'ai autant de passages labyrinthiques que de grandes salles. Le jeu est en 2D, pas en 3D (du moins pas vraiment), alors j'ai l'impression que ne pas le modéliser sous forme de grille compliquerait pas mal la chose (parce qu'en plus après il y a tous les tests de collision). Bref la modélisation en grille m'arrange bien et j'aimerais bien la garder.

Qu'en pensez-vous ?

Merci pour vos réponses.

La map est grande ? Y a peut-être moyen de pré-calculer ça ? En ne conservant que les cases qu'on peut atteindre. Si tu as une vingtaine d'élément, je suppose que oui elle doit l'être un peu …

Une vingtaine ? C'est pas beaucoup. J'ai bien un algo très rapide si tu utilises des segments. Sans segments, avec si peu d'objets (20 à 30 …), tu dois pouvoir faire ça à partir de la pense du segment. Tu prends le coef directeur et d'un algo de tracé de segment.

Précalculer, je vois mal comment, étant donné que les entités peuvent être en mouvement.

Au niveau de la taille, je n'ai pas encore bien défini mais ça va être grosso modo du 100x100 je pense. Le joueur ne voit pas toute la map en même temps.

J'élimine déjà ce qui est trop loin (plus de 15-20 cases en distance euclidienne sqrt(dx^2+dy^2))

Je vais regarder l'algorithme que tu proposes. Au passage le lien est faux, la bonne page est: https://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_segment_de_Bresenham

Merci.

Ceci pourrait t'aider je pense.

J'ai essayé l'algorithme de tracé de segment proposé par ache sur une map de 100x100 sans le moindre mur (potentiellement le pire cas). Ca a l'air de fonctionner plutôt bien, et en terme de CPU c'est apparament totalement indolore.

Ce qui m'embête c'est les cas limites, comme la diagonale exacte de l'exemple ci-dessus.

Pour régler ce cas, je pensais jouer avec l'accumulateur d'erreur de l'algorithme. L'idée était que, si on entre à plus de 25% dans la case voisine, alors il faut la tester aussi. Mais ça ne marche pas.

L'ennui c'est que, dans le cas de la diagonale exacte, l'erreur reste à 0, et donc elle passe à travers un mur qui est dans la diagonale opposée.

Une idée ?

Merci en tout cas pour cet algorithme; je ne connaissais absolument pas.

Pour ceux que ça intéresse, voici mon code, sans mon histoire de 25% qui ne marche de toute façon pas correctement :

 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
42
43
44
45
46
47
48
49

bool World::hasDirectPath (int x1, int y1, int x2, int y2) {
int e, dx = x2-x1, dy=y2-y1;
int incX=dx>0?1:-1, incY=dy>0?1:-1;
//printf("Test from(%d,%d) to(%d,%d). dx=%d, dy=%d, incX=%d, incY=%d\r\n", x1, y1, x2, y2, dx, dy, incX, incY);
if (dx==0 && dy==0) return true;
else if (dy==0) { // Horizontal line
while(x1!=x2 && !isWall(x1+=incX, y1)) {
//printf("x=%d, y=%d, e=%d\r\n", x1, y1, e);
}
return x1==x2;
}
else if (dx==0) { // Vertical line
while(y1!=y2 && !isWall(x1, y1+=incY)) {
//printf("x=%d, y=%d, e=%d\r\n", x1, y1, e);
}
return y1==y2;
}
else if (abs(dx)>=abs(dy)) { // Line being more horizontal than vertical
dx = abs(dx*2);
dy = abs(dy*2);
e = dx/-2;
//printf("x=%d, y=%d, e=%d\r\n", x1, y1, e);
while(x1!=x2) {
x1+=incX;
e+=dy;
if (e>=0) {
e-=dx;
y1+=incY;
}
if (isWall(x1,y1)) return false;
//printf("x=%d, y=%d, e=%d\r\n", x1, y1, e);
}}
else if (abs(dx)<=abs(dy)) { // Line being more vertical than horizontal
dx = abs(dx*2);
dy = abs(dy*2);
e = dy/-2;
//printf("x=%d, y=%d, e=%d\r\n", x1, y1, e);
while(y1!=y2) {
y1+=incY;
e+=dx;
if (e>=0) {
e-=dy;
x1+=incX;
}
if (isWall(x1,y1)) return false;
//printf("x=%d, y=%d, e=%d\r\n", x1, y1, e);
}}
return true;
}

Bon, finalement je n'ai pas besoin de chipoter sur les cas limites après tout. IL me suffit d'ajouter des murs de telle sorte que la situation ne se produise jamais.

Je garde le lien de Grimur au chaud; il ne m'a pas aidé pour le moment mais il le pourrait bien dans une prochaîne phase de développement. L'article est intéressant et je suis sûr que plein de jeux ont été basiquement conçus de la façon exposée sans même qu'on s'en doute le moins du monde.

Sujet résolu, merci à tous.

que les entités bougent ou pas, ça ne change pas qu'elles ne se déplacent pas lorsque tu fais tes tests de "vision". Donc tu peux calculer la visibilité entre chaque couple de case au chargement de la map (ou avoir ces calculs déjà fait dans un fichier à part) comme ça, tu auras une matrice contenant la visibilité et tu auras juste à faire if(visibilite[case1][case2]) {}

C'est envisageable. Si on considère une portée de 20 case, pour une map de 100 cases :

10000*400 Octets

Si tu stockes le booléen dans un char. Tu divises pas 8 si tu utilises les bits de char.

Bref, c'est envisageable, par forcément nécessaire. Il y a mieux pour ton cas je pense. Dans certain cas, ce serrait une idée tout à fait correcte.

Elle est limité car il est hors de question d'agrandir trop ta map.

Ca ferait donc 4 Mo pour l'exemple. C'est pas si énorme, c'est vrai.

Mais quand je parlais de mouvement, ce n'est pas non plus exclu que les murs bougent. Enfin plus exactement, il y a des portes qui peuvent changer la donne selon qu'elles sont ouvertes ou fermées. Du coup ça reste peu pratique de précalculer d'après moi.

Heureusement, l'algorithme de tracé de segment est assez rapide pour que ça soit sans douleur apparament.