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).