Discussion :

[lange59]

Bonjour,

J'ai un soucis pour un algorithme de recherche si une zone est entouré. Je m'explique

Je développe un petit jeu en 2D , un RAMPART pour ceux qui connaissent mais je bloque sur une partie.

La carte du jeu est en 2D, rectangulaire. Sur cette carte se trouve plusieurs forteresses. Le joueur peut construire des murs et il doit entourer ces forteresses.

Mais je n'arrive pas a trouver de solutions pour détecter si une forteresse est entouré. Touts mes essais sont vains. J'aurais vraiment besoin d'un coup de main, c est la seule chose qui me manque pour pouvoir fini le jeu.

Je pense qu'il doit y avoir une astuce avec la théorie des graphes mais on va dire que je ne comprend pas grand chose à cette théorie.

Cordialement Mathieu

[prgasp77]

Bonjour,
j'imagine que ta map est un quadrillage, sans quoi les choses vont énormément se compliquer.

Si c'est le cas, j'ai une solution naïve et certainement perfectible à proposer. Soit une forteresse, nous cherchons à savoir si elle est protégée.

Réponse : elle l'est si et seulement si chacune des cases voisines le sont. Application : algo récursif de recherche en largeur.

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
Fonction est_sûr(forteresse : case) :
Variables
   cases-traitées: collection de cases
   cases-en-cours: file d'attente (collection de type FIFO)
   c, voisin: case
Début
   insérer forteresse dans cases-en-cours
   Tant Que cases-en-cours est non vide Faire
      c <- pop(cases-en-cours)
      insérer c dans cases-traitées
      Pour Chaque voisin de voisins(c) Faire
        Si voisin n'est pas dans cases-traitées Faire
           Si est_mur(voisin) Faire
              insérer voisin dans cases-traitées
           Sinon Si est_forteresse(voisin)
              retourner faux
           Sinon
              insérer voisin dans cases-en-cours
        Fin Si
     Fin Pour Chaque
   Fin Tant Que
   retourner vrai
Fin Fonction

[Acrim]

Au risque de fournir une réponse redondante avec celle de prgasp77 : il s'agit d'un problème de connexité. En supposant que chaque case de ton plateau correspond à un nœud et qu'un arc existe entre deux nœuds si et seulement les cases correspondantes sont cote-à-cote et qu'elles ne sont pas séparées par un mur.

Le but est alors de trouver les composantes connexe du graphe en mettant des étiquette sur chacun des nœuds. http://www.developpez.net/forums/d10...ntes-connexes/.

Chaque zone délimitée par un mur aura alors une étiquette différente.

[lange59]

Merci à vous.

Je vais regarder pour ta solution prgasp77 même si je comprend pas du tout comment ça marche. Comment je peux trouver si ma forteresse est entouré par des murs vu qu on traite le cas ou on rencontre un mur de la meme facon que si on rencontre "rien" ?

Par contre comment je pourrais récupérer les cases qui sont entourés en même temps que la forteresse sans devoir tester toutes les cases du plateau ( j ai besoin de les avoir pour leur donner une couleur différentes ).

Acrim, c est donc bien à l aide de la théorie des graphes qu'on peux résoudre ce problème.
Peux-tu me détailler la procédure , ca m intéresse grandement ? ( le lien donné est en Java, que je ne connais pas du tout. Je devellope en C++ )

Edit: Avec des infos supplémentaires pourrait peut être vous aider:

La carte est un tableau en 2 dimensions (x,y) de taille variables. Une case peux être soit une forteresse, un mur, de la terre ou de la mer.
En faites ma question était mal formulés, je ne dois pas uniquement vérifier si une forteresse est entouré, je dois connaitre les "zones" de la carte qui sont entouré par des murs ( voir la terre en noire dans le lien avec l exemple )

Lien vers une exemple du jeu:Exemple/

Cordialement Mathieu

[cs_ntd]

EDIT: je crois que c'est le meme algo que prgasp77 a peu de choses pres... sauf qu'on débute pas pareil il me semble... Mais je me perd dans ton algo prgasp77

J'ai une idée, on va appeler ca l'algorithme de la tache d'huile

Le principe c'est de partir des cases qui représente le chateau. Tu les ajoutes dans une liste. Ensuite, tu va dans toues les directions possibles.

Cad, si le chateau ne fait qu'une cellule, tu a donc 4 directions possibles, pareil pour chaque cellule, a moins que la cellule voisine soit :
- Une murraille
- une cellule déja visitée
- un bord du monde
- un autre chateau
- la mer
- etc... n'importe quel obstacle

Et si la cellule suivante est valide, on l'ajoute a la liste des cellules visitée, et on test ses voisines.

A la fin, tu a donc une plage qui contient toutes les cellules que l'ont peut visiter en partant du chateau.

Apres c'est simple : si ont peux visiter toutes les cases libres, c'est que le chateau n'est pas dans une muraille.
Exceptions pour les cellules adjacentes a certains obstacles (exemple mer, ou bords) : si on peu aller dans ces cellules, alors c'est que le chateau n'est pas protégé.

On peux faire ca recursivement, c'est joli, mais ca va etre gourmand en memoire si jamais tu a beaucoup de cellules :

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
 
cellules_vues : Liste[NB_CELL_VISITABLES]
 
cellules_vues += {cellules chateau}
 
VISITER(cell_courante : cellule)
BEGIN
IF NON isVisitable(cell_courante) THEN
    RETURN
ELSE
    cellules_vues += cell_courante
    Visite(cell_haut)
    Visite(cell_bas)
    Visite(cell_gauche)
    Visite(cell_droite)
ENDIF
END

et la fonction isVisitable doit vérifier si la cellule est un mur, un bord... Cette fonction pourrait aussi provoquer l'arret de l'algorithme des le moindre probleme, si par exemple on est dans une cellule adjacente a un bord (forcemment pas protégé)...

Ensuite, tu compare le nombre d'elements de cellules_vues avec le nombre de cellules visitable (a priori NB_CELL_VISITABLES = DIMENSIONS - NB_OBSTACLES). Et si tu les a toutes, c'est que tu n'est pas encerclé. Sinon, c'est bon.

Et en plus, ca te donne la liste des cellules a griser


Je pense que ca marche, ou que ce n'est pas loin de marcher

[Graffito]

Compte tenu des données, est-ce que le calcul de l'appartenance d'un point à un polygone conviendrait ?

Le sujet à été traité souvent dans ce forum.

Une méthode simple (classique) consiste à déterminer les intersections d'une demi droite orientée vers le nord (ou un autre point cardinal) avec les cotés du polygone : si le nombre est pair, le point est à l'extérieur.

Pour résoudre facilement le petit effet de bord lorsqu'un sommet se retrouve sur la demi-droite, on le décale d'epsilon vers la gauche.

Pour traiter les intersections, 3 cas :
1) les 2 extrémités sont au-dessous du point traité : pas d' intersection,
2) les 2 extrémités sont au-dessus du point traité : 1 intersection si l'abcisse du point traité se trouve entre celles des extrémités.
3) autre cas, 1 intersection possible si l'abcisse du point traité se trouve entre celles des extrémités, pas d'intersection sinon. Pour savoir si le point est au-dessus ou au-dessous du segment: il faut comparer Py à
E1y+(E2y-E1y)/(E2x-E1x)

[prgasp77]

Bonus : si la forteresse est convenablement délimitée, alors cases-traitées contient à la fin de la fonction la liste des cases du chateau (forteresse + terrain + murs).

[Acrim]

Compte tenu des données, est-ce que le calcul de l'appartenance d'un point à un polygone conviendrait ?

Il me semble que le problème est justement de savoir si les murs forment un polygone ou non (si le mur n'entoure pas entièrement la forteresse par exemple).

Merci à vous.
Acrim, c est donc bien à l aide de la théorie des graphes qu'on peux résoudre ce problème.
Peux-tu me détailler la procédure , ca m intéresse grandement ? ( le lien donné est en Java, que je ne connais pas du tout. Je devellope en C++ )

J'ai l'impression qu'au final tout le monde te propose à peu près la même solution avec des mots différents. Mais pour répondre à ta question : pour découvrir l'ensemble des nœuds (cases) accessibles depuis un nœud (case) de départ tu dois parcourir ton graphe en mettant une étiquette sur chacun des nœuds rencontrés. Tu changes d'étiquette à chaque fois que ton algo s’arrête (toutes les cases atteignables ont été atteintes) et que tu le relances à partir d'une case non encore visitée.

A la fin, les différentes étiquettes correspondront aux différentes zones.

[lange59]

Bonjour,

Ok merci. j ai enfin compris. Je vais faire la méthode avec les étiquettes , c est elle qui me permettra de gérer le plus facilement/rapidement dans mon cas ( par que si j utilise l algo précédant je dois tester 4800 cases * x forteresses donc pas top ).
Tandis qu'avec les étiquettes pas de problèmes. Je dois juste scanner une seule fois la map par frame. ( et bien sur différenciés l'etiquette de toutes les cases pas entouré ( donc collé au bord ) des autres mais c est pas trop dur ça.

En gros, je fait l algo de cs_ntd mais pas en prenant comme point de départ une forteresse mais une case de Terre quelconque c est bien ça ?

[Acrim]

Tu peux effectivement partir de n'importe qu'elle case puisque toutes les cases atteignables de la zone seront visitées. Il manque quelque chose dans l'algorithme proposé par cs_ntd : vérifier qu'une case n'a pas déjà été visité avant de la visiter à nouveau (pour éviter de tourner en rond par exemple).

[cs_ntd]

Tu peux effectivement partir de n'importe qu'elle case puisque toutes les cases atteignables de la zone seront visitées. Il manque quelque chose dans l'algorithme proposé par cs_ntd : vérifier qu'une case n'a pas déjà été visité avant de la visiter à nouveau (pour éviter de tourner en rond par exemple).

Cad, si le chateau ne fait qu'une cellule, tu a donc 4 directions possibles, pareil pour chaque cellule, a moins que la cellule voisine soit :
- Une murraille
- une cellule déja visitée
- un bord du monde
- un autre chateau
- la mer
- etc... n'importe quel obstacle

J'y avais pensé

[Acrim]

Autant pour moi.

[lange59]

Ok.

Bon donc l algo je le comprend maintenant. En faites c est pas si tordu que ça ( enfin sauf le coté récursif ^^ ).

Mais je bloque sur l'implémentation en C++. Je travaille dessus. Si je bloque trop je post pour un coup de main.

Merci beaucoup pour la solution.

Cordialement Mathieu

[pseudocode]

Ok.

Bon donc l algo je le comprend maintenant. En faites c est pas si tordu que ça ( enfin sauf le coté récursif ^^ ).

Pour des raisons de perfs/robustesse, il faudrait éviter l'implémentation récursive et plutôt utiliser une pile des cellules à visiter. Ou alors utiliser d'autres techniques d'étiquetage (union-find par exemple).

[lange59]

Ok. Pseudocode.

Je viens justement de commencer a regarder un sujet que tu avais poster a un moment sur l implentation de l'union-find en Java et en C.
Ca a l air de parfaitement collé a ce que je dois faire et ca marche d après mes essais
Cependant j ai quelques soucis à le faire fonctionner :p.


En gros je lui balance en argument 1 tableau[LONGEUR][LARGEUR] c est bien ça ? avec a l ,intérieur des indices types genre 1 quand la case est de la Terre, 2 quand c est de la Mer et 3 quand c est un Mur ?

Et ensuite comment je dois faire pour convertir ça en zone ? La je sèche.

PS: voila le lien du sujet: http://www.developpez.net/forums/d48...es-union-find/

[pseudocode]

En gros je lui balance en argument 1 tableau[LONGEUR][LARGEUR] c est bien ça ? avec a l ,intérieur des indices types genre 1 quand la case est de la Terre, 2 quand c est de la Mer et 3 quand c est un Mur ?

oui, c'est ca.

Et ensuite comment je dois faire pour convertir ça en zone ? La je sèche.

Et bien on appelle la méthode compute() qui renvoie le tableau des labels. Ce tableau à la meme taille que celui de départ, et dans chaque case on a le numero du label.

######....       0000001111
#....#....       0222201111
#..###....       0220001111
#..#...~~~  -->  0220111333
####..~~~~       0000113333
.....~~~~~       1111133333
.....~~~~~       1111133333

Cela dit, pour ton problème particulier, l'exploration des voisins avec une pile est sans doute plus pertinent.

[lange59]

Ok donc j'étais dans le vrai.

La méthode serait peut etre la meilleure mais j arrive pas a l implementer sans foiré. Et vu que le temps passe et que je n'ai pas que ça a finir ( je dois encore gérer plein de truc dans le jeu , des choses globalement simple mais bon faut le temps de les coder ^^ )

Le blem la méthode compute() je connais pas :p. Je code en C++ , Java je connais pas. Donc j'ai le résultat mais j arrive pas a le retravailler pour l utiliser :p.

PS: J utilise donc la version C

[pseudocode]

La méthode serait peut etre la meilleure mais j arrive pas a l implementer sans foiré. Et vu que le temps passe et que je n'ai pas que ça a finir ( je dois encore gérer plein de truc dans le jeu , des choses globalement simple mais bon faut le temps de les coder ^^ )

cs_ntd et prgasp77 ont donné la structure de l'algo. Tu peux aussi porter le code PHP de l'exemple que tu as posté.

[lange59]

Bonjour,

Bon je donne des nouvelles :p.
Je n'y arrive pas. J ai beau essayé a chaque fois mon algo me donne des résultats foireux. Je sais plus quoi faire.

Est ce que quelqu'un peux me ré expliquer le tout ? Ou bien avec un exemple en C++ ?

Cordialement lange

[prgasp77]

Maintenant que tu as un algorithme valable, c'est plutôt l'implémentation qui pose problème. Deux solutions : soit tu marques cette discussion et tu demandes de l'aide dans le forum approprié (celui de ton langage), soit tu demande de l'aide ici en espérant qu'il y ait suffisamment de monde qui connaisse ce langage (j'ai toujours pas compris si tu faisais ça en C, C++ ou PHP).

Mais sache que sans extrait de code et sans description d'erreur ou de bug, on ne pourra pas deviner pourquoi tu n'y arrives pas.

Et on ne le fera pas pour toi, on t'as déjà bien mâché le travail. Non mais ho !