Ligne de vue

**totofe** · 11/02/2010, 19h25

Bonjour,

Je suis en train de réaliser un jeu de plateau et j'essaye de trouver un algo ou chaque combattant possède une ligne de vue pour savoir s'il peut ou pas tirer.

Voici les différents cas :

Donc, pour qu'il puisse cibler, il faut que, dans chaque cas, les cases rouges soient libres. Avec ces différents cas, je ne vois pas trop l'algo à adopter. Quand la ligne droite est diagonale, c'est simple mais dans les autres cas, ça semble plus compliqué.

Merci.

**Obsidian** · 12/02/2010, 02h56

Il te faut vérifier que chaque case « rouge » est bien vide et pour cela, il faut que tu sois capable de déterminer quelles sont ces cases rouges. Ce problème revient exactement à tracer une ligne sur un écran composé de pixels.

La manière la plus simple d'y parvenir est de considérer que ta droite a une hauteur (différence entre les positions du pixel le plus haut et du plus bas) et une largeur (même chose mais pour le pixel le plus à gauche et le plus à droite). Tu fais ensuite le rapport du plus petit côté sur le plus grand, et tu obtiens une valeur, constante pour une ligne donnée.

Tu fais ensuite une boucle qui parcourt pixel par pixel la plus grande des deux dimensions et, à chaque tour, tu ajoutes cette valeur à la position sur l'autre axe.

Si tu veux faire quelque chose d'un tout petit plus évolué, vois du coté de l'algorithme de Bresenham.

**Mac LAK** · 13/02/2010, 22h41

Envoyé par Obsidian

Si tu veux faire quelque chose d'un tout petit plus évolué, vois du coté de l'algorithme de Bresenham.

Pareil, je dirais Bresenham, mais en faisant attention aussi aux cases adjacentes : par exemple, sur les trois (voire quatre...) derniers exemples de l'OP, Bresenham ne mettrait pas en rouge toutes les cases...

En effet, si l'on se met (par rotation) dans le cas d'un tracé de droite dont l'angle est compris entre 0 et 45°, l'algorithme ne connait que deux cas pour le prochain pixel :

Le pixel est immédiatement à droite (X <- X+1, Y <- Y).
Le pixel est en haut à droite (X <- X+1, Y <- Y+1).

Or, les trois (ou quatre) derniers exemples imposeraient d'avoir un "X" non-incrémenté entre deux étapes, et ça, ce n'est pas possible dans la variante classique de l'algo.

Donc, soit les trois schémas d'exemples sont inutilement complexes (utiliser un peu plus les passages en diagonale comme sur les exemples 2 et 3), soit l'algo final devra être un Bresenham assez fortement adapté.

**totofe** · 14/02/2010, 00h52

OUai je pense que je vais devoir adapter un peu alors... Merci pour m'avoir orienté vers cette algo qui s'en approche. Et j'aimerais indiqué aux joueurs quels cases (et oui c'est pas des pixels ^^') il pourra cibler ou pas. est-ce réalisable? le temps de recherche ne sera t-il pas trop important?

**Mac LAK** · 14/02/2010, 16h04

Bresenham est un algorithme monstrueusement rapide, ne t'inquiètes pas. Il ne fait appel qu'à des opérations entières qui sont, en plus, très simples.

Si as un plateau de, disons, 100 x 100 cases, tu n'as qu'à le considérer comme un "écran" de 100x100 pixels et appliquer l'algo dessus. Ce qui correspond, au final, à tracer / marquer les cases de ton plateau de jeu. L'algo n'a besoin que d'une entité (écran ou matrice) capable d'être adressée via deux coordonnées (X,Y) pour pouvoir fonctionner.

Par rapport aux cases "visables", il faudra affiner un peu, j'explique :

Une unité a, en général, une limite de portée.
Il te faudra tracer un "cercle" autour de l'unité pour pouvoir limiter la recherche. Comme par hasard, figures-toi qu'un certain Bresenham a AUSSI fait un algo, très rapide, de tracé de cercle...
Pour chaque pixel à l'intérieur du cercle, il te faudra tenter de tracer une ligne de visée pour savoir si c'est libre.
Le principe est de parcourir chaque "pixel" du disque en mode "raster". Si le pixel est éligible pour une visée, tu n'as plus qu'à le stocker dans une liste.
A la fin des calculs, tu obtiendras une liste (éventuellement vide !) de cases pouvant être visées.
Plus qu'à montrer ça à l'écran de façon visuelle pour le joueur.

Les deux algos de Bresenham étant franchement très très rapides, ça m'étonnerait que tu mettes plus d'une milliseconde pour déterminer toutes les cases à portée de tir de l'unité visée... Rien d'incompatible avec un jeu fluide, donc.

**totofe** · 14/02/2010, 21h42

ok.
J'essaye déjà de réaliser l'algo de bresenham dans mon cas qui est légèrement différent. Je code en java et je suis parvenu a réalisé cette fonction.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public ArrayList<Point> listCases(Point p1, Point p2)
{
int x,y,dx,dy,incrmX,incrmY,dp,NE,SE;
 
		 dx = p2.getX()-p1.getX();
		 dy = p2.getY()-p1.getY();
 
		 if (dx>0)
		 incrmX = 1;
		 else {
		 incrmX = -1;
		 dx *= -1;
		 }
 
		 if (dy>0)
		 incrmY = 1;
		 else {
		 incrmY = -1;
		 dy *= -1;
		 }
 
 
		 if (dx>=dy) {
		 dp=2*dy-dx;
		 SE=2*dy;
		 NE=2*(dy-dx);
 
		 y=p1.getY();
		 for(x=p1.getX();x!=p2.getX();x+=incrmX) {
 
			  System.out.println(new Point(x,y));
			  tuiles.add(new Point(x,y));
 
		 if (dp<=0) 
		 dp += SE;
		 else {
		 dp += NE;
		 y+=incrmY;
		 }
		 }
		 }
		 else if (dx<dy) {
		 dp=2*dx-dy;
		 SE=2*dx;
		 NE=2*(dx-dy);
 
		 x=p1.getX();
		 for(y=p1.getY();y!=p2.getY();y+=incrmY) {
			  System.out.println(new Point(x,y));
			  tuiles.add(new Point(x,y));
 
		 if (dp<=0) 
		 dp += SE;
		 else {
		 dp += NE;
		 x+=incrmX;
		 }
		 }
		 } 
	  return tuiles;
	}

Donc effectivement certaine case ne s'affiche pas. Notamment dans les 2 derniers cas de mon exemple.
Et je ne trouve pas les modifications a effectué.
avec l'algo de breseham les cases ou le "segment" de la ligne de vue passe légèrement dessus ils n'apparaissent pas, hors dans mon cas ils doivent également apparaître!

**Mac LAK** · 14/02/2010, 22h58

Envoyé par totofe

Donc effectivement certaine case ne s'affiche pas. Notamment dans les 2 derniers cas, et je ne trouve pas les modifications a effectué.

Le problème, c'est que tes deux derniers cas ne sont pas très logiques par rapport aux autres : tu pourrais faire un parcours en diagonale, or tu as choisi de faire un "coude"... Est-ce vraiment ce que tu veux faire ?

Sinon, la solution peut passer par un oversampling... En gros, cela consiste à considérer qu'un "pixel" pour ton tracé de ligne est plus petit qu'une case. Quand tu vas "tracer" la ligne, tu vas donc mordre sur plus d'une case à chaque étape, ce qui te permettra peut-être d'avoir ces fameuses cases supplémentaires.

A vue de nez, je dirais que tu devrais décomposer tes cases de jeu en quatre (2 x 2 "pixels" par case), effectuer le tracé, et considérer qu'une case est dans la ligne de vue si au moins une de ses quatre sous-cases est dans le tracé.

**totofe** · 15/02/2010, 10h43

Si c'est logique je pense. La diffèrence avec breseham c'est qu'il faut faire apparaitre toutes les cases même celle par le quel le segment coupe que très peu la case. n'existe t-il pas un algo pour un segment donnée on trouve tous les pixels par les quels il passe?

**Mac LAK** · 15/02/2010, 11h19

Envoyé par totofe

n'existe t-il pas un algo pour un segment donnée on trouve tous les pixels par les quels il passe?

Celui que je t'ai donné dans le post précédent : l'over-sampling.

**Jimmy_** · 15/02/2010, 16h43

Je ferai plutôt avec du vectoriel, pour la ligne de vue et les obstacles. Trouver si deux vecteurs se coupent, c'est des maths de base.
Ne pas oublier que c'est un jeu et le résultat sera bien de plus 'réel' qu'une application strict de Bresenham. Cela évitera que dans certains cas, les soldats tirent en courbe, ou coupe un obstacle.

Bon courage,

**Mac LAK** · 15/02/2010, 17h06

Comment veux-tu faire du vectoriel sur un plateau de jeu fondamentalement discret ???

**Jimmy_** · 15/02/2010, 17h21

Ayant un peu joué à des wargames dans ma jeunesse, je me souviens bien avoir mesuré les distances et les lignes de vue avec un fil. De même que les décors n'occupaient pas toute la case. Le fil passait dans une case, mais le décors ne touchait pas le fil.... cruel dilème pour simuler ce fait ...

Mais chaque case correspond à un terrain à une echelle réduite. En fonction du nombre de case et de l'echelle il est très facile d'en déduire des coordonnées, en mètre par exemple. Le résultat sera plus fidèle à mon avis. Mais cela dépend aussi du degré de simulation que l'on veux atteindre.

**Mac LAK** · 15/02/2010, 17h37

J'ai aussi joué à des wargames, on utilisait également des fils ou des gabarits de tir... Mais tu tentes de calquer une méthode "humaine", avec en plus un autre joueur et/ou un arbitre qui tranchera sur la légalité (ou pas !) d'un mouvement, avec quelque chose qui sera calculé et décidé par un algorithme, et de façon automatique...

Je reste persuadé que l'over-sampling + Bresenham reste la solution la plus pratique : rapide à implémenter et à exécuter, et fiable.

**totofe** · 16/02/2010, 09h37

J'ai commencé un algo ressemblant a breseham qui me semble pas mal. Le souci étant que j'effectue des divisions et sur ses divisions je j'essaye de savoir s'il est égal à 0. comme se sont des variables binaires le nombre n'est pas précis à 100% à la place de 0 je vais avoir 1E-16 par exemple. sinon l'algo fonctionne bien.

**Mac LAK** · 16/02/2010, 10h19

Quel besoin de divisions ?? Si tu fais un over-sampling, cela reste un algo de Bresenham tout à fait classique...

Regarde sur l'exemple ci-dessous :

Je suis passé à un over-sampling 3x3, histoire d'avoir le centre exact. En effet, l'over-sampling en 2x2 pose quelques soucis parce que l'on ne peut pas obtenir le centre exact de la case, et cela ne permet pas d'arriver exactement à tes exemples.

Comme tu peux le voir, la ligne noire (tracée par Bresenham) partant de la case bleue du haut vers celle du bas "mords" sur plusieurs cases, que j'ai colorié en rouge. Et on arrive très exactement à ton dernier exemple initial...

**totofe** · 16/02/2010, 11h37

HA oui effectivement pas mal ^^. Et je pense que ton algo devrait être plus rapide que le miens ou je suis obligé de passer par une classe BigDecimal qui est "lourde". Je vais essayer ton algo.
Mais j'aimerais savoir si cette algo est fiable et qu'il oublierait pas des cases de temps en temps?
Car je me demande si par exemple je suis sur la case (0,0) et je cible la (10,9). ce n'est pas tout à fait la diagonal donc la case (1,0) devrait être allumé et l'algo de bresehem trace une casi diagonal et je pense pas qu'il passera par (0,1) mais directement par (1, 1) enfin je me trompe peut-être.

**totofe** · 16/02/2010, 22h58

J'ai reussi à réaliser un algo sans passer par des divisions à la place je multiplier ailleurs ^^. Ainsi mon algo concerve un temps d'execution record.:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public ArrayList<Point> tracerSegment(Point p1, Point p2)
	{
		ArrayList<Point> tuiles=new ArrayList<Point>();
int dx, dy, x, y, incrmX, incrmY;
		int ratio;
		int result=0;
		int step;
		 dx = p2.getX()-p1.getX();
		 dy = p2.getY()-p1.getY();
		 if (dx>0)
			 incrmX = 1;
		 else {
			 incrmX = -1;
			 dx *= -1;
		 }
 
		 if (dy>0)
			 incrmY = 1;
		 else {
			 incrmY = -1;
			 dy *= -1;
		 }
 
		 if(dx>=dy)
		 {
			 y=p1.getY();
			 ratio=dy;
			 step=dx;
			 result=step;
			 result-=ratio;
			 if(result==0)
			 {
				 y+=incrmY;
				 result+=step*2;
			 }
			 for(x=p1.getX()+incrmX;x!=p2.getX();x += incrmX)
			 {
				 result-=ratio*2;
				 while(result<0)
				 {
					 tuiles.add(new Point(x,y));	
					 result+=step*2;
					 y+=incrmY;					 
				 }
					 tuiles.add(new Point(x,y));
					 if(result==0)
					 {
						 y+=incrmY;
						 result+=step*2;
					 }
 
			 }
		 }
		else
		 {
			 x=p1.getX();
			 ratio=dx;
			 step=dy;
			 result=step;
			 result-=ratio;
			 for(y=p1.getY()+incrmY;y!=p2.getY();y += incrmY)
			 {
				 result-=ratio*2;
				 while(result<0)
				 {
					 tuiles.add(new Point(x,y));	
					 result+=step*2;
					 x+=incrmX;					 
				 }
					 tuiles.add(new Point(x,y));
					 if(result==0)
					 {
						 x+=incrmX;
						 result+=step*2;
					 }
 
			 }
		 }
 
 
 
		 return tuiles;
	}

**totofe** · 17/02/2010, 21h36

En y repensant je ne trouve pas qu'utiliser l'algo de berehsam est judicieux car "la porté" de mes personnages est en nombre de case donc il passera forcément par tout les points. et pas besoin de calculer quel pixel allumer. par exemple si mon personnage à un porté de 5cases. il faudra allumer toutes les cases qui sont à 5 cases où moins.

Je vais aussi implanter une porté min.
il doit exister un algo simple qui allume tous les pixel a jusqu'à un certain nombres de cases.
me souviens de l'algo de de la goute d'eau je crois... je vais approfondir mes recherches.

**Mac LAK** · 17/02/2010, 21h47

Le tracé de ligne de Bresenham est "nécessaire" (enfin, pratique) pour voir si la case est dans une ligne dégagée... Il n'est d'aucun intérêt pour trouver les cases maximales accessibles, sauf pour les passer une à une et vérifier qu'elles sont bien utilisables.

Par contre, faut définir ta "portée" correctement : si cela inclut le parcours en diagonale, alors c'est un bête carré autour de la position initiale. Sinon, c'est un losange, et nul besoin d'algo à ce niveau : une double boucle suffit amplement.

Ligne de vue

Algorithmes et structures de données

Discussions similaires

Partager

Partager