Hello

Je fais un jeu en Java, un tactical RPG, qui demande à ce que je définisse des lignes de vue lors d'un affichage de la portée d'un sort.
En gros, lorsque le joueur clique sur un bouton d'un sort, la zone du sort (l'ensemble des cases ciblables) sont affichées sur la map.
J'aimerai que cet affichage prenne en compte les obstacles se trouvant sur la map. En gros, s'il y a un rocher qui bloque la vue du personnage, ce dernier ne pourra pas lancer son sort sur certaines cases.

Je me suis renseigné et j'ai trouvé un algo qui correspond à mes attentes : https://fr.wikipedia.org/wiki/Algorithme_de_tracé_de_segment_de_Bresenham

J'ai donc repris le pseudo-code de Wikipédia et l'ai mis dans mon jeu en Java, sans succès

J'ai fais en sorte que ma fonction getZoneFinale prenne en argument un tableau 2D de booleens et la position (x, y) du personnage. Ce tableau représente la zone du sort sans prendre en compte la topologie de la map. Case ciblable -> true. Case non ciblable -> false. Ce tableau est nommé zoneIntermediaire.
Un croquis valant mille mots : le cercle rouge représentant le personnage. Le point (0, 0) étant en haut à gauche.

La fonction va créer un second tableau 2D de booleens, de la même taille que zoneIntermediaire. Ce tableau sera initialement rempli de false. Ce tableau est nommé zoneFinale. C'est ce que va retourner la fonction.

Ce que je cherche à avoir : le carré gris étant un obstacle, le personnage n'a plus accès aux 3 cases en haut à gauche.

Voici le code des deux fonctions : http://pastebin.com/2nRrLdtx j'espère avoir assez commenté.
La seconde fonction utilise Bresenham pour renvoyer les points du segment.
L'objet Array est un objet spécifique à LibGdx. Pour ceux qui ne connaissent pas, cet objet fonctionne quasiment comme une ArrayList.

La variable tabTuiles représente un tableau 2D de Tuile. Ca représente les cases de la map.

Pour le moment la zone affichée montre trop peu de cases (pour l'exemple des croquis, le jeu me montre 3 cases ciblables lorsqu'il n'y a pas d'obstacle...).

Je vous remercie d'avance.

C'est exactement ça oui.

La portée initiale du sort est de 2 cases, c'est à dire que le joueur ne peut pas cibler les cases adjacentes au personnage. C'est dû à la configuration du sort.

Deja tu as testé que ton implémentation de Bresenham marche, sans prendre en compte les histoires de zones et d'obstacles ?

Je ne sais pas si ton algorithme est bien judicieux pour calculer les lignes de vue, il pourrait par passer à côté de l'obstacle pour tracer sa ligne.

Après au niveau de la zone d'effet du sort, il ne peut pas taper autour de lui mais certaines cases à 2 de portées ne sont pas ciblables (les diagonales) et d'autres sont ciblables (ligne droite) par le sort.
Je ne sais pas si c'est propre à ce sort là ou à tous les sorts de ton jeu mais c'est pas très logique ^^

Après tu peux développer toi même un vérificateur simple qui interdit de tirer sur les cases derrière l'obstacle, si la zone n'est que de deux cases la vérification est simplifiée.

Après je t'avoue que je ne saurais pas gérer la portée en carré si tu veux faire quelque chose de modulable (genre portée de 65 cases )

Finalement je me suis rendu compte, un peu tard, que LibGdx possédait déjà une implémentation de cet algorithme https://libgdx.badlogicgames.com/nightlies/docs/api/com/badlogic/gdx/math/Bresenham2.html

Du coup bah je l'ai implémenté facilement et il fonctionne !

Maintenant j'ai un autre problème, mineur cette fois. Certaines cases ne devant pas être ciblables le sont. En image ça donne ça :

Une seule case est rendue inaccessible par l'obstacle, alors qu'il devrait y en avoir 3.

Merci pour votre aide d'ailleurs

Le 01 octobre 2015 à 22:24:20 Kwaki-crap a écrit :
Je ne sais pas si ton algorithme est bien judicieux pour calculer les lignes de vue, il pourrait par passer à côté de l'obstacle pour tracer sa ligne.

Le 01 octobre 2015 à 22:46:08 Kwaki-crap a écrit :

Le 01 octobre 2015 à 22:24:20 Kwaki-crap a écrit :
Je ne sais pas si ton algorithme est bien judicieux pour calculer les lignes de vue, il pourrait par passer à côté de l'obstacle pour tracer sa ligne.

Ah donc le problème viendrait de l'algo lui-même ? C'est plutôt problématique
Je vois pas quoi utiliser d'autre.

Ben le problème est que tu as deux "plus courts chemins" qui sont équivalents et dont l'un passe par ton obstacle, l'autre non. Bresenham te renvoie l'un des deux sans préférence, donc ça risque de te donner des résultats pas toujours satisfaisants au cas pas cas comme ça.
Faudrait préciser quel est la critère exact qui t'a poussé à dire que les trois cases du coin devraient ne pas être accessibles, perso ça me parait pas choquant sur le dessin que les deux cases adjacentes au coin puissent être atteintes par le sort.

Des critères possibles :
- Tous les plus courts chemins (au sens de Bresenham) évitent les obstacles
- Au moins un plus court chemin évite les obstacles
- En reliant les centres des cases "à vol d'oiseau" (sans regarder les pixels, pas de Bresenham donc), on évite les obstacles
- etc

Finalement en réfléchissant, ça peut peut être marcher.
J'étais parti sur autre chose

Déroule ton algo à la main et regarde où ça cloche !

Le 01 octobre 2015 à 23:40:32 whiteapplex a écrit :
Tu veux faire ça en fait ?

Tu peux pas juste calculer les points qui appartiennent au triangle vert (qui s'étend super loin virtuellement)

C'est exactement ce que je souhaite oui.
Comment calculer les points du triangle ? Je vois pas comment faire.

En fait dans mon code je fais exactement comme tu dis.

Ma fonction renvoie la liste des cases entre le perso et la case finale, dans cet ordre.
Ensuite je check chaque case de cette liste dans une boucle. Lorsque je rencontre un obstacle, je stop la boucle.

Il y a deux cas que je trouve très étrange.

Premier cas :
Le sort du personnage arrive à accéder à la case (1, 0), celle en haut à gauche, la deuxième.
Au début j'ai pensé que ça venait de mon code, de mes conditions qui était mauvaise, mais il n'en est rien.
La fonction line() de Bresenham2 me retourne la liste des points parcourus. De la position du personnage à la case ciblée ca fait 4 cases : (2, 2) -> personnage, (2, 1), (2, 0), (1, 0) -> tuile ciblée. J'ai mis un point orange sur les tuiles concernées.
La liste de contenant aucun obstacle, la tuile ciblée est valide.

Pourquoi l'algo de Bresenham ne prend pas en compte l'obstacle en (1, 1) ??

Autre situation : (ne prenez pas en compte les booleens, on admet de base que le sort peut toucher n'importe quelle case)
La tuile ciblée est (1, 1). Le perso est en (2, 2). Il y a un obstacle en (1, 2).
Normalement l'obstacle ne gène pas, la tuile ciblée étant accessible via la diagonale. La tuile est pourtant inaccessible en jeu.
Le problème vient encore de l'algo de Bresenham. L'algo me renvoit les points suivants :
(2, 2) -> personnage, (1, 2) -> obstacle, (1, 1) -> tuile ciblée. J'ai mis un point orange sur les tuiles concernées.
Le fait qu'un des points soit un obstacle rend la case ciblée inaccessible !

Pourquoi l'algo passe par cet obstacle ??

Bon, déjà, l'algo de Bresenham n'est pas unique, il y a des variantes.

L'algo "classique" que l'on retrouve le plus souvent fait des lignes qui ressemblent à ça :

D'après tes dessins, le tien a plutôt l'air de faire des lignes comme ça :

Note la différence : dans le premier cas, on autorise à ce que deux cases voisines se touchent "en diagonale", alors que dans le deuxième cas, elles partagent toujours au moins un côté.

Le truc que tu utilises s'appelle apparemment "Bresenham2", essaye de voir s'il n'y a pas une version "Bresenham" classique, c'est probablement plutôt celle-ci que tu as envie d'utiliser. Ça devrait déjà résoudre ton second cas de figure, puisque ça autorisera à lancer le sort en diagonale.

Maintenant, le gros soucis avec ce que tu fais est le suivant :

Pour aller du point rouge au point vert, il y a deux chemins possibles, en violet et en mauve sur le dessin, qui correspondent tous les deux à des lignes droites au sens de l'algorithme de Bresenham. Ce que ça veut dire, c'est que l'algo va te renvoyer l'un de ces deux chemins, et surtout n'importe lequel des deux.
Ton problème, c'est que pour ce que tu fais, ces deux chemins ne sont pas du tout équivalents : le mauve passe par l'obstacle, alors que le violet ne passe par aucun obstacle. Donc la case verte sera autorisée ou interdite, suivant un critère totalement arbitraire et hors de ton contrôle : lequel des deux chemins est renvoyé par l'algo de Bresenham ?

Maintenant, quelle est la solution ?
Ça dépend du comportement exact que tu veux donner à ton truc.
Par exemple, dans un cas comme ça :

est-ce que tu voudrais que le point vert soit atteignable, ou pas ? Ça c'est à toi de le décider, ce n'est qu'en clarifiant quel est exactement le critère que tu veux appliquer pour savoir si une case est ou non bloquée par les obstacles, qu'on pourra ensuite t'aider à savoir comment implémenter ce critère.

Je vais me renseigner sur les variantes de l'algo.

Le 02 octobre 2015 à 16:16:44 AlphaCygni a écrit :
Maintenant, quelle est la solution ?
Ça dépend du comportement exact que tu veux donner à ton truc.
Par exemple, dans un cas comme ça :

est-ce que tu voudrais que le point vert soit atteignable, ou pas ? Ça c'est à toi de le décider, ce n'est qu'en clarifiant quel est exactement le critère que tu veux appliquer pour savoir si une case est ou non bloquée par les obstacles, qu'on pourra ensuite t'aider à savoir comment implémenter ce critère.

Oui, je souhaite que le point vert soit atteignable.

A mon avis, la solution la plus simple pour avoir un truc qui marche et qui fait grosso modo ce que tu veux, c'est de tracer un segment (un "vrai" segment, pas un truc pixellisé à la bresenham), reliant le centre de la case joueur et de la case cible, et regarder s'il croise une case obstacle ou pas. Faut faire un peu de géométrie fatigante mais ça doit pas être trop compliqué.

Une autre solution si tu veux vraiment utiliser bresenham (ça peut être amusant à coder) serait de générer tous les chemins possibles, et vérifier qu'aucun d'entre eux ne croise un obstacle. A vérifier, mais a vue de nez je dirais qu'il devrait suffire de regarder deux chemins "extrêmes", et que si tu es chanceux tu devrais pouvoir les obtenir en faisant tourner ton bresenham une fois de A vers B, et une fois de B vers A. Par contre si ça marche pas faudrait coder un truc custom et là il faut réfléchir un peu à comment ça marche

Finalement j'ai repris un code Java de l'algo sur le net. Code testé et à priori approuvé.

La bonne nouvelle c'est que toutes les cases ciblables le sont.

Par contre parfois certaines cases sont ciblables alors qu'elles ne doivent pas l'être. C'est typiquement mon problème du schéma précédent

Le 02 octobre 2015 à 15:23:42 Chnapy a écrit :

Il y a cette fois une différence notable. L'algo passe directement de la case (2, 1) à la case ciblée (1, 0). Il passe donc par la diagonale.

Le pastebin de la fonction : http://pastebin.com/QM7WZD11