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 ?

[Kraaneur]

Ah alors c'est en déplacement case par case. Si j'ai 4 de portée, je tirerai au mieux à 4 cases de loin, sachant qu'une diagonal coûte 2 de portée (la 4-connexité si j'ai bien compris). Le truc, c'est que ce n'est pas un déplacement à proprement dit, puisque mon joueur ne bouge pas, il n'a la possibilité que de tirer dans mon exemple.
Ce serait donc pour résumé, un déplacement de 4 cases, mais au lieu de calculé à chaque déplacement de 1 les cases adjacentes atteignable et faire la même chose N fois (N étant la portée) (comme tu me l'avais expliqué dans ton premier commentaire), il faudrai calculer directement les cases atteignable depuis là où l'on est, comme si on pouvait "sauter" à N cases de distance.

[ToTo13]

Mmm... dans la 4-connexité, tu ne peux pas aller directement en diagonale, donc normalement la case en bas à gauche n'est pas atteignable.
Par contre, je confirme donc qu'il manque deux cases en haut, une à droite, une à gauche et une en bas. Mais toutes ces cases sont proches d'un obstacle et c'est sans doute pour cela que tu ne les comptes pas, alors qu'elles sont bien à une distance de 4 de la case de départ.
Bref, tu n'es pas réellement en 4-connexité. Mais dans tout les cas, la case en bas à gauche ne devrait absolument pas être dans la solution.

Une solution serait alors de modifier l'algorithme que j'ai donné en ajoutant de diminuer la distance de 1 si un chemin touche deux fois le même obstacle (impossible de tourner autour, ce qui est ton cas).

[the-morpher]

Bonsoir,

Désolé de reprendre la discussion alors que le dernier message remonte au mois de juin, mais je n'ai pas aussi réussi à trouver se que je voulais, à savoir un algorithme qui permet de voir si les cases sont ciblés ou pas, en prenons en considération les obstacles, et aussi la portée autorisé.

aillons longtemps cherché sur internet je n'ai rien trouvé, c'est pourquoi je viens ici tenter ma chance

[tbc92]

Bonsoir,

Des tas de gens pourront te donner des tas d'algorithmes, mais je pense que la difficulté réside essentiellement dans la compréhension. Ils vont exprimer leur algorithme , avec leurs mots... que tu ne comprendras pas.

Donne nous l'algorithme auquel tu es parvenu avec tes mots à toi, et on pourra te répondre avec des mots que tu comprendras.

[Invité]

hello,

pour trois cases données:
C: le centre
O: l'obstacle
P: une case quelconque potentiellement cachée par l'obstacle.

Le but est d'avoir une fonction <isHidden(center, obstacle, cell)> qui dit si oui ou non la case est cachée par l'obstacle.

pour ca il faut définir quand est-ce qu'on considère que la case est cachée que tu devrais fournir (et pas nous)

Partons de la définition suivante:
pour tous les rayons lumineux qui partent du centre et qui passent sur la case,
si l'un d'entre eux passe par l'obstacle, alors la case est cachée.

Ca veut dire qu'il faut pour <isHidden(center, obstacle, cell)>
1: trouver les rayons extremes de l'obstacle idem les deux corners de l'obstacle "gauche" et "droite" (en mettant des coordonées aux coins de l'obstacle et en comparant les angles)
2: tracer les rayons [centre, gauche) et [centre droite)
3: retourner si l'un de ces rayons intersectent la case

enfin, c'est comme ca que je ferais ma portée...

[yahiko]

J'ai lu rapidement la question, mais il me semble qu'on est typiquement dans l'application d'algorithme A*

[Invité]

je ne pense pas. Peux-tu développer?

[the-morpher]

Bonsoir,

non on ai pas dans l'application A*
se qu'il veux dire et se que j'essai de dire c'est que .. enfin voici une image avec un cas de figure réel de mon problème sous mon jeux :


c'est se que j'ai pu faire avec mon code, mais normalement il y à des cases qui devrai être caché comme ceci :



j'ai comme même réussi a réalisé cela mais avec une distance de 1 case entre le joueur et l'obstacle, mais des que le joueur s'éloigne de plusieurs cases, l'ago ne change pas.
en quelque sorte il y à un jeux qui a réussi cette énigme et que vous le connaissez tous :


plus loin de l'obstacle de quelque tuiles



je ne sais pas si j'arriverai à faire un algo pour l'ensemble ou biens dois-je faire un algo pour chaque distance à savoir si la distance entre le joueur est de 1 case verticalement, je dois choisir algo1, si 2 case donc algo 2 ...
j'ai bon cherché mais j'ai pas trouvé.
en tout cas je sais comme même qu'il faut prendre en considération ses critères :
distance horizontal entre le joueur et l'obstacle (Xdistance)
distance vertical entre le joueur et l'obstacle (Ydistance)
combien de cases reste à afficher horizontalement (XtileLeft)
combien de cases reste à afficher verticalement (YtileLeft)

voici le bout de code qui me permet cela :

Code C# :

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
 
       for (int rows = 1; rows < YtileLeft; rows++)
       {
            for (int cols = 1; cols < XtileLeft; cols++)
            {
                 // liste qui contiens tous avec la porté demandé
                 // l'objet sort_tuile_info contiens la position de la tuile, si elle bloque la vue, si on peux marcher dessus
                 sort_tuile_info sti = allTuilesInfo.Find(f => f.TuilePoint.X == allTuilesInfo[i].TuilePoint.X + ((playerPosition.X < allTuilesInfo[i].TuilePoint.X) ? cols : -cols) && f.TuilePoint.Y == allTuilesInfo[i].TuilePoint.Y + ((playerPosition.Y < allTuilesInfo[i].TuilePoint.Y) ? rows: -rows));
                for (int i = 0; i < not_block_view_tile.Count; i++)
                {
                    // controle pour savoir si on fait face a 1 seul obstacle situé sur la position x=16/y=10 sur ma map, pour bien étudier mon probleme
                    if (not_block_view_tile[i].TuilePoint.X == 16 && not_block_view_tile[i].TuilePoint.Y == 10)
                    {
                        // determination des index
                        // distance entre le joueur et l'obstacle
                        int Xdistance = playerPosition.X - not_block_view_tile[i].TuilePoint.X;
                        int Ydistance = playerPosition.Y - not_block_view_tile[i].TuilePoint.Y;
 
                        int Xindex = (Math.Abs(Xdistance) + 1) / 3;
                        int Yindex = (Math.Abs(Ydistance) + 1) / 3;
 
                        int XtileLeft = pe - Math.Abs(not_block_view_tile[i].TuilePoint.X - playerPosition.X);
                        int YtileLeft = pe - Math.Abs(not_block_view_tile[i].TuilePoint.Y - playerPosition.Y);
 
                        // mise en mode "block_vien" tous les tuiles caché par l'obstacle en cours dans la matrice
                        // parcourir la matrice tant d’éléments se trouvant horizontalement et verticalement
                        for (int rows = 1; rows < YtileLeft; rows++)
                        {
                            for (int cols = 1; cols < XtileLeft; cols++)
                            {
                                // recherche de la tuile concerné
                                sort_tuile_info sti = allTuilesInfo.Find(f => f.TuilePoint.X == allTuilesInfo[i].TuilePoint.X + ((playerPosition.X < allTuilesInfo[i].TuilePoint.X) ? cols : -cols) && f.TuilePoint.Y == allTuilesInfo[i].TuilePoint.Y + ((playerPosition.Y < allTuilesInfo[i].TuilePoint.Y) ? rows: -rows));
                                if (sti != null)
                                {
                                    // cheque si la distance vertical / 3 pour savoir combien de tuiles horizontal on dois parcourir pour autoriser la prochaine tuile
                                    //pour avoir ligne de vus, le chiffre 3 est un nombre que je tolère pour avoir la prochaine vus sur la case
                                    if (Ydistance - 3 > 0)
                                        sti.isBlockingView = false;
                                    else
                                        sti.isBlockingView = true;
                                }
                                else
                                    break;                // sortir de la boucle si l'objet sti est null, si c'est le cas ça veux dire qu'il ne reste aucune tuile a vérifier
                            }
                        }
                        break;            // on arrête notre logique puisque les autres obstacles sur la map ne m’intéresse pas pour le moment
                    }
                }

voila j'ai juste collé ce bout de code comme ça

[tbc92]

Ok !


Effectivement, une bonne partie des gens qui ont lu ce message ont compris que le personnage se déplaçait, et pouvait donc contourner les obstacles.
Et ton besoin c'est une question de tir, ou de vision..
Alors, quelques question?

* S'il n'y a aucun obstacle, les cases qu'on peut atteindre, elles forment un cercle, ou elles forment un losange. ET comme apparemment tu vas répondre losange, ... losange c'est ce que tu VEUX faire, ou c'est ce que tu fais parce que tu ne sais pas faire un cercle ?

* S'il y a un obstacle juste à coté du personnage (la case juste à droite ... et pas la case en diagonale) tu peux nous recenser les case 'masquées' ... ou bien tu fais confiance aux matheux pour faire le choix le plus cohérent.

.... parce qu'en fait, je pense que c'est d'abord une question de maths, puis ensuite une question d'informatique ou d'algo.

[Invité]

.... parce qu'en fait, je pense que c'est d'abord une question de maths, puis ensuite une question d'informatique ou d'algo.

raté.. c'est une question de modélisation.

Ca dépend comment the-morpher décide si tel ou telle case est accessible si jamais il y a un obstacle, ca a rien à voir avec des maths.
Après ya quelque jours déjà, j'ai bien précisé qu'il fallait à the-morpher préciser comment on interprétait la perte d'accessibilité à cause d'un obstacle.
J'ai également proposé une modélisation, mais vraisemblablement on m'a ignoré

ET comme apparemment tu vas répondre losange, ... losange c'est ce que tu VEUX faire, ou c'est ce que tu fais parce que tu ne sais pas faire un cercle ?

je réponds pour the-morpher. Tu peux considérer la distance de manhattan, le but c'est que si on te dit t'as 6PO (portée), tu comptes 6 cases...

[tbc92]

Voici une proposition.

Dans cette proposition :

-La portée sert à définir un Cercle, et non un losange.
Chaque obstacle est un cercle.
Dans cet exemple, j'ai pris 3 tailles de cercles, pour voir l'effet.
A partir du Centre, je trace les tangentes au Cercle ; Cela définit un Triangle.
Les cases dont le centre est dans ce triangle sont hors de portée.

Les cases atteignables sont les cases bleues.




Et ... une fois tout cela dit, en fait, le nombre de positions à analyser est relativement restreint.
Et donc, pour chaque position de l'obstacle, recenser les cases masquées, et mettre tout cela 'en dur' dans le programme, c'est peut-être la solution la plus efficace.

[the-morpher]

Bonsoir,

et merci pour vos réponses, déjà ça laisse croire que des gents essais de m'aider dans ce petit galère qui ma bloqué de coder pendant 3 jours maintenant

pour tbc92

* S'il n'y à aucun obstacle, les cases qu'on peut atteindre, elles forment un cercle, ou elles forment un losange. ET comme apparemment tu vas répondre losange, ... losange c'est ce que tu VEUX faire, ou c'est ce que tu fais parce que tu ne sais pas faire un cercle ?

c'est biens un losange que je veux faire et non un cercle pare que j'utilise des tuiles carrés et aussi j’agis selon la portée d'un sort, donc la y à pas de soucie.

* S'il y a un obstacle juste à coté du personnage (la case juste à droite ... et pas la case en diagonale) tu peux nous recenser les case 'masquées' ... ou bien tu fais confiance aux matheux pour faire le choix le plus cohérent.

eu on faite c'est pas compliqué, faites si comme si vous êtes à la place du joueur et qu'il y à un obstacle, donc il va surement caché une partie du paysage,
donc se que j'essaie de trouver c'est une méthode / code qui me permet de trouver les cases caché, avec bien sur un niveau de tolérance qui nous permet d'avoir une vue sur les cases loin mais qui étés précédaient caché dépendamment de l'angle de vus qui est influencé par la distance horizontale et verticale:



mais si le personnage se décale à gauche ou à droite, cette tolérance dois être sensibilisé dépendamment.

pour galerien69
excuse moi je ne t'es pas ignoré mais j'ai effectivement répondu à ton message en développent mon problème

j'ai bon cherché un truc en math mais j'ai rien trouvé.
mais je commence à avoir des idées sur 2 méthodes:

Premièrement :
imaginer un angle géométrique puis avec une sorte de code savoir si tel et tel case fait partie dans cet angle.



problèmes :
comment mette en place cet angle, faut le dessiner dans un calque invisible ?!
et puis après, j'ai du mal à savoir comment je vais reconnaître les cases dedans,
et après, pour la tolérance, il faut faire en sorte que si une cases est à 60% dans la zone de l'angle, la considérer comme cases autorisé, mais ... pour cela il faut faire une boucle pour contrôler 90 pixel :

Code C# :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int cntPixel = 0;        compteur de nombre de pixel dans la zone de tolérance
for(int ligne = 0; ligne < 30; ligne++)
    for(int colonne = 0; colonne < 30; colonne++
    {
          // just un code tapé comme ca :mrgreen:
          if(map.GetPixel(ligne,colone).Color =="red")
          cntPixel++;
    }
 
if(cntPxeil>=60)
{
     // case accessible par le sort
}

problème : ça va bloquer le thread principale un bon moment le temps de chercher tous les cases dans le champ, se qui va surement bloquer l'application.
pour le mettre dans un thread eu ... il faut bloquer le processus jusqu'à se que le thread me retourne le résultat et ça va aussi être super long, donc non pas pratique

2éme méthodes, ... je l'ai oublié carrément en tapant tout ceci

[the-morpher]

Bonsoir,

et merci pour la pain de répondre ainsi pour le dessine, par contre mon dernier poste à été publié avant que je vois le tien, tu devais être entrain de le rédiger aussi j'imagine.

cela dis on partage aussi le même point de vus à savoir un angle.
pour le faite de dessiner un cercle et non un losange c'est qu'il y à une incohérence dans ton déssine qui ne respecte pas la portée



donc si on considéré que le joueur à une portée de 3, en vers il arrive à avoir une portée jusqu'à 4. et l'inverse est exacte.
on tombera sur un problème encore plus difficile, qui ne nous garantie pas une vrai porté puisque certaines cases sont à moitié dans le cercle et donc peux pas définir leurs appartenance

[Invité]

effectivement boucler sur des pixels c'est un peu naze.

un algorithme est le suivant:
tu traces ton triangle (ca ca devrait pas etre trop dur)
soit ABC ton triangle et A le sommet qui nous interesse (c'est ton joueur)
tu considères cette case comme case contour.
Une case contour c'est juste une case qui est traversé par un côté du triangle. (a 2% ou 60 peut importe).
(1) Tu listes les cases contour de [AB] et [AC]
Ensuite pour la première case contour de AC, tu vas vers le haut, la gauche la droite ou le bas (ca dépend l'orientation de ton triangle, mais c'est pas la mort).
Au bout d'un moment, tu vas trouver la case contour...de l'autre coté du triangle!
toutes les cases entre, elles sont inaccessibles.
(2) Les cases contour sont à traiter au cas par cas

(1) pour les lister les cases contour, tu as la direction (vecteur AB) qui a une composante horizontale et verticale.
pour la case contour courante, tu explore la case dans la même direction horizontale que vecteur AB Et aussi celle dans la direction verticale.
explorer une case ca veut dire, si la case est coupée par vecteur AB, alors c'est une case contour, et tu boucles. Sinon, c'est une case inaccessible 100% ou totalement accessible et donc inintéressante

(2) lorsque tu as une case contour... tu es capable de trouver les points d'intersection de vecteur AB avec la case(normalement un nombre pair, comme le carré c'est quatre côté, ca sera généralement 2), tu es donc capable de calculer l'air délimitée de chaque côté de la droite.
il reste à savoir laquelle contabiliser.
pour ca tu peux tracer la perpendiculaire à AB orientée (un peu comme une force de centrifuge), et récupérer la composante verticale qui te donnera un des points dont tu t'es servi pour calculer l'aire. Et ce point est à l'intérieur de la zone inaccessible


c'est un problème plus intéressant qu'il n'en a l'air!