Discussion :

[Kraaneur]

Bonjour à tous,

Je code actuellement un jeu de plateau basé sur le système des échecs, à la différence qu’une unité à de la portée de tir, et qu’il y a des obstacles sur le terrain de jeu. J’utilise le C associé au SDL, grâce au très bon cours de Matéo21 soit dit en passant.

Mon but :

Soit une grille 2D, où nous aurions une unité, ici en rouge, et des obstacles, ici en noir.




Donnons à cette unité 4 points de portée. Et donc maintenant en bleu les cases ciblables par cette unité (j’ai essayé de faire tous les cas de figure possible au niveau du gêne occasionné par les obstacles).




Ma question :

Existe-t-il un algorithme capable de trouver ces cases ciblables à partir d’une case et d’une portée donné ? Et si non, auriez-vous des idées de fonction, ou de parcours spécifique de grille pour arriver à ce résultat ?

Personnellement, j’ai tourné le problème dans tous les sens durant des heures, et je n’ai vraiment rien trouvé de concluant, voire même juste une piste à exploiter…

Je ne sais pas si j’ai le droit sur un forum de faire des exemples de ce type sur un forum,mais je me suis inspiré du système de portée de sort dans un combat sur le jeu Dofus (auquel je jouais il y a bien longtemps…) pour ceux qui connaissent, si ça peut vous aidez à comprendre ce que j’essaie de faire.

J’espère avoir été assez clair, si ce n’est pas le cas n’hésitez pas à me poser des questions pour éclaircir tel ou tel point.

Merci d’avance

Kraaneur

[ToTo13]

Bonjour,
dans ton dessin, il manque deux cases en bleu vers le haut :-)
Tu peux utiliser un simple algorithme pour régler ton problème. Cela consiste à explorer à partir de la case rouge, comme si l'on répandait un germe.

- Données - Une case de départ (la rouge), une distance à parcourir N (ici 4) et un type de voisinage à utiliser (dans ton exemple c'est de la 4-connexité).
- 1 - Ajouter la case à analyser à la liste des points à explorer (un point comportant deux coordonnées et une distance par rapport à l'origine)
- 2 - tant qu'il y a des points dans la liste

• - sortir le premier point P de la liste.
• - si P a déjà été exploré, retourner à 2.
• - marquer P comme exploré
• - si la distance de P à la case d'origine est inférieure à N, ajouter les voisins de P à la liste.

[Kraaneur]

Bonjour Toto13, merci de prendre le temps de t'arrêter sur mon problème.

Je pense avoir compris ton algorithme, mais il ne me donnera pas la portée de mon unité, seulement les cases accessibles en ce déplaçant. Par exemple, sur mon dessin, il y a une case bleue en bas à gauche, en diagonale de mon unité. Avec ton algo, cette case n'est pas bleutée. C'est donc aussi pour ça que les deux cases "manquante" dont tu me parles ne sont pas bleues, c'est juste que de là où est mon unité, cette case n'est pas "ciblable", j'entends par là qu'elle ne pourra pas tirer sur une unité adverse ce trouvant sur ces cases là, contrairement à celle en diagonale.

[ToTo13]

...
Pourquoi est ce qu'un coup tu peux te déplacer en 4-connexité et un coup en 8-connexité ?

[Kraaneur]

Non mais non.. Bon alors, je recommence

Mon personnage (case rouge) NE SE DEPLACE PAS. Il a zéro point de mouvement, et ne peux pas aller sur une autre case que celle où il est .
Ceci étant dit, notre ami la case rouge n'a pas fini de jouer, il a encore la possibilité de TIRER sur case autours de lui, a un maximum de 4 cases de portée. La question est donc, comment faire pour calculer les cases atteignable (ici en bleu), de celle qui ne le sont pas. Par atteignable j'entend dans sa ligne de mire !

Excuse moi si je n'ai pas été clair dès le départ.

[ToTo13]

Je pense que c'est ta définition de distance qui n'est pas bonne.
Lorsque tu dis à une distance de N (modulo les obstacles), est ce en distance euclidienne par rapport aux cases ou est ce en déplacement case par case ?