Discussion :

[Med_Prog]

'lut ,
j'ai un bleme algorithmique dans un jeu que je suis en train de realiser, l'algo existe mais comme je sais pas comment il s'appelle, je vais vous decrire la situation :

j'ai un damier avec des cases et un pion sur une des cases.
sur certaine cases ya des murs.
j'aimerais appliquer un traitement à toutes les cases que le pion peut "voir" à partir de sa case , sachant qu'il ne voit pas a travers les murs .

comment trouver les coordonnées de ces cases ?

Ps : si vous avez pas compris je réexplique
ps2 : je prog en java si ca peut changer qque choz ..

[Benny]

Salut

Ton probleme me fais penser à la reconnaissance d'un chemin dans un automate

L'utilisation d'une pile est necesaire pour savoir par ou on est deja passe et on a besoin de traiter ca en recurrance

Complexite en O(n²) je crois .

Je vais chercher dans mes bouquins d'algo et je reviens ce soir

@+

[DrQ]

Pour ce qui est de l'automate j'aurais plutot utilsé un graphe qui se compose au fur et à mesure du chemin parcouru.

Sinon peutx tu nous donner la structure de ton damier. Je suppose que c'est un tableau à deux dimensions d'objets "case".
Cet objet case quel est sa structure ?

[Med_Prog]

ouai en 2d avec des cases.
une case est un JPanel (c du java)
caracterisée par sont abscisse et sont ordonnée sur le plateau de jeu .
et d'autre petits attributs qui sont pas important pour le resultat.

il n'y a aucun repere geometrique, donc pas moyen de dire (comme je pensait faire au debut) que le pion voit une case si il est possible de tracer une ligne du centre de la case ou est le pion vers le centre de la case testée sans couper une case contenant un mur ...

[DrQ]

Tu n'as aucun objet pour définir ton damier ????

[Med_Prog]

si si , un JPanel surchargé ..

[Med_Prog]

pour etre plus claire :
le damier est un panneau qui affiche un tableau de cases
les cases sont des panneaux representé par leur coordonnées sur le damier ..
voili voilou..

[Benny]

Merci Doc d'avoir si joliement recuperer ma bourde

je pensait bien a un graph et a l'agorithme de Ford-Fulkerson

Mais tout a bien avance depuis

@+

[Pazz]

et ça te couterait vraiment cher de faire un repère ?

[mio]

Pourquoi un repere ?

[Pazz]

Pour pouvoir utiliser l'algo de bresenham ou un truc du genre, ça serait super rapide. Après peut être qu'il y a des algos spécialisés encore plus effcaces, je n'en sais rien.

[mio]

Compris. Ca ressemble a rally robot son truc.

[Pazz]

optimiser à fond un tel algorithme doit être intéressant...

[mio]

Oui mais l'initiateur de la conversation ne semble plus la suivre donc on ne sait pas ce qu'il a fait et ce qu'il veut exactement maintenant.

[Rudyweb]

Bonsoir,
je suis confronté à un problème similaire.

Pour le résoudre, j'utilise un algorithme basé sur la formule y = ax + b, afin de calculer les différents points que traverse la ligne et vérifier si un obstacle passe dedans.

Le problème survient lorsque je dois calculer les diagonales. Si 2 murs se touchent par le coin, les cases derrières seront visibles, alors qu'elles devraient être cachées. Mais attention, s'il n'y a pas un mur de chaque côté de la ligne, ces cases ne seront pas cachées.

Je vais essayer de schématiser mon problème, ce sera sans doute plus explicite.

Légende
M = mur
X = "caméra"
C = caché
V = visible
? = les cases qui devraient être cachées mais qui restent visibles

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
 
Damier incorrect (2 murs)
? C C C V V
C ? C C V V
C C ? M V V
C C M V V V
V V V V X V
V V V V V V
 
Damier correct (2 murs)
C C C C V V
C C C C V V
C C C M V V
C C M V V V
V V V V X V
V V V V V V
 
Damier correct (1 seul mur)
V C C C V V
V V C C V V
V V V M V V
V V V V V V
V V V V X V
V V V V V V
 
Damier incorrect (2 murs)
? C C C V V
C ? C C V V
C M V M V V
V V V V V V
V V V V X V
 
Damier correct (2 murs)
C C C C V V
C C C C V V
C M V M V V
V V V V V V
V V V V X V

A par calculer les points des diagonales paraalèles et vérifier qu'ils ne contiennent pas de mur, je ne vois pas comment faire pour résoudre mon problème. Mais cette solution ne serait pas propre et pas optimisée pour un poil.

J'ai tenté de me diriger vers une solution où je n'ai pas à calculer la ligne pour chacune des cases, en me basant sur la position des murs qui sont stockées dans une matrice de booléens. Cela réduirait concidérablement les calculs à effectuer car s'il n'y a qu'un mur, on n'aurait que la moitié du damier (au pire) à analyser au lieu du damier complet. Mais je n'ai pas réussi...

Si quelqu'un peut me mettre sur la voie, voir connait un lien pour résoudre ce type de problème, je suis preneur.

[Matthieu Brucher]

Pourquoi le 2ème damier est incorrect ?

[Rudyweb]

Code :

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

1
2
3
4
5
6
Damier incorrect (2 murs)
? C C C V V
C ? C C V V
C M V M V V
V V V V V V
V V V V X V

Si tu décalles le mur de droite d'un cran vers le nord-ouest (ou celui de gauche vers le sud-est), on se retrouve dans la même situation que dans le premier damier.