Discussion :

[Greg L.]

Bonjour à tous,

Les cours de maths de terminale S et de BTS remontent pas mal, donc j'avoue que je sèche.

Dans le cadre d'un jeu de combat, différentes unités se placent sur une grille. Les unités peuvent se déplacer sur des cases qui ne contiennent pas d'obstacles. Chaque unité dispose de types d'attaque, avec une certaine portée ... mais la condition nécessaire pour pouvoir attaquer une unité, c'est que celle-ci soit visible, donc qu'il n'y ait pas d'obstacle entre deux unités ennemies.

Mon problème est qu'il est (je pense) difficile d'avoir des calculs suffisamment fiables quand on bosse sur des entiers restreints (entre 0 et 50 on va dire).

Quel méthode pourrais-je utiliser pour déterminer s'il n'y a pas un obstacle entre mon unité A et mon unité B sur ma grille ?

[pseudocode]

Un certain Bresenham s'est déjà posé la question dans les années 1960...

(L'histoire ne dit pas si c'etait pour un jeu de combat... )

[Greg L.]

Merci pour le tuyau ! ;-)

[Greg L.]

L'article est super intéressant, mais je m'y perds un peu dans les notations mathématiques. Personne n'aurait un exemple en C (par exemple) pour que je m'y retrouve ?

Merci d'avance.

[pseudocode]

je pense que l'algo de Bresenham doit exister en plusieurs milliers d'exemplaires.

http://www.google.com/codesearch?q=l...Bresenham+line

[phryte]

Salut.
Les données d'entrées sont bien :
Unité 1 (type x,y.....)
Unité 2 (type,x,y....)
Obstacles (dx,dy....) ?

[PRomu@ld]

Quel méthode pourrais-je utiliser pour déterminer s'il n'y a pas un obstacle entre mon unité A et mon unité B sur ma grille ?

Raycasting ? avec un parcours simple d'une grille régulière.

Un exemple :

http://www.flipcode.com/archives/Ray...ivisions.shtml

[khayyam90]

L'algo de Bresenham va te permettre de connaître toutes les cases survolées par une ligne donnée.
Nous avons une ressource (en C) sur ce sujet sur developpez.com :
http://anomaly.developpez.com/tutoriel/sdl/partie2/#L3

[phryte]

Salut.

Quel méthode pourrais-je utiliser

Je pense que Bresenham est la bonne solution comme te l'indiquent plusieurs réponses.
Néanmoins, si tu as Matlab tu peux essayer ceci :
(Basé sur le calcul des distances du centre des cases à la droite liant les deux unités.

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
clear
N=10;%Nombre de lignes et de colonnes
U1=[2 3];U2=[8 6];%Coordonnées des unités
X_obs=[5 5 5 7 7 7 7 5];%Pour le tracé de l'obstacle
Y_obs=[4 5 5 5 5 4 4 4];%Pour le tracé de l'obstacle
pos_obs=[46 47];%Numéros des cases ocupées par l'de l'obstacle
%Matrice obstacle
Mobs=zeros(10,10);
Mobs(N-fix(pos_obs(1)/10),pos_obs(1)-fix(pos_obs(1)/10)*10)=1;
Mobs(N-fix(pos_obs(2)/10),pos_obs(2)-fix(pos_obs(2)/10)*10)=1;
%Equation de la droite entre unités
A=(U2(2)-U1(2))/(U2(1)-U1(1));
B=-1;
C=-A*U1(1)+U1(2);
D=(sqrt(A^2+B^2));
%Calcul distances et affectation des cases coupées
for j=0:N-1
for k=0:N-1
 d=(A*(k+0.5)+B*(j+0.5)+C)/D;
    if abs(d) < 0.5 
     M(N-j,k+1)=1;
     else
      if abs(d) > 0.707
        M(N-j,k+1)=0;
        else
        M(N-j,k+1)=1;
       end
    end
end
end
%Tracé
plot([U1(1) U2(1)],[U1(2) U2(2)])
hold on
h=line(X_obs,Y_obs);
set(h,'Color','r','LineWidth',3)
scatter(U1(1),U1(2),300,[0 0 0])
scatter(U2(1),U2(2),300,[0 0 1])
grid
axis([0 10 0 10])
%Test de présence d'obstacle
 [ligne,colonne] =find(M-2*Mobs==-1)