[Algo]Cases voisines

[atra27]

Ok alors je tente avec ce raisonnement.

En attendant voila ton exemple:

$map[0]=array(0,1,0);

$map[1]=array(1,2,1);

$map[2]=array(1,2,1);

$map[3]=array(0,1,0);

Cela correspond a la seconde image que j'ai donné dans mon premier post.

[niahoo]

$map[] = array(

    0 => 0,

    1 => 1,

    2 => 0

);

$map[] = array(

    0 => 1,

    1 => 2,

    2 => 1

);

$map[] = array(

    0 => 1,

    1 => 2,

    2 => 1

);

$map[] = array(

    0 => 0,

    1 => 1,

    2 => 0

);

edit: oui je sais ça sert à rien mon post

[nicodd]

J'ai codé rapidement une solution pour expliciter un peu mon algorithme :

Ca fait quelques mois que je n'ai plus fait de php, donc il se peut que j'aille un peu perdu la main et que ce ne soit pas très optimisé mais cela fonctionne :

<?php

function detectGroups($map, $x, $y, $visited=null)

{

	if($map[$x][$y]==0)

		return false;

	$color=$map[$x][$y];

	if($visited===null)

	{

		$visited=$map;

		foreach($visited as $line)

			foreach($line as $cell)

				$cell=false;

	}

	$visited[$x][$y]=true;

	return status($map, $x-1, $y, $color, $visited)

		  && status($map, $x+1, $y, $color, $visited)

		  && status($map, $x, $y-1, $color, $visited)

		  && status($map, $x, $y+1, $color, $visited);

}

function status($map, $x, $y, $color,$visited)

{

	if($x<0 || $x>=count($map) || $y<0 || $y>=count($map[0]))

		return true;

	if($map[$x][$y]==0)

		return false;

	if($map[$x][$y]==$color)

		if(!$visited[$x][$y])

			return detectGroups($map, $x, $y, $visited);

		else

			return true;

	if($map[$x][$y]!=$color)

		return true;

}

$map[0]=array(0,1,0);

$map[1]=array(1,2,1);

$map[2]=array(1,2,1);

$map[3]=array(0,1,0);



for($i=0; $i<count($map); $i++)

	for($j=0; $j<count($map[0]); $j++)

		echo "(".$i.",".$j.") : ".detectGroups($map,$i,$j).'<br/>';

?>

Pour le moment la fonction renvoie true lorsque les cases appartenant à un groupe.
Il est assez facile de modifier ça pour que cela puisse renvoyer les coordonnées de tous les groupes présents dans la carte.
N'hésite pas si tu as des questions pour comprendre ou améliorer mon code, et n'hésite pas à tester sur des maps un peu plus compliquées (h)

[Argorate]

Au vu de tes exemples, j’en déduits que tu ne géres pas le cas des boules en diagonales ?

Sinon au niveau de l’algo, je ne vois pas trop le problème. Il suffit de faire une fonction récursive. La fonction regarde que les coordonnées autour de celle passé en paramètre comportent que des boules « ennemis ».
Ensuite pour le cas « chian », il te suffit d’enregistrer toutes les boule « ami » adjacente que tu rencontres, en stockant les coordonnées de celle-ci dans un tableau $en_attente_de_traitement (par exemple), puis une fois l’algo de la boule en cours terminer, soir il n’y a rien dans $en_attente_de_traitement et tu peux directement en tirer les conclusions dont tu as besoin, soit tu relances la même fonction avec les coordonnées (et autre paramètres de la fonction dont tu aurait éventuellement besoin) de la première boule de la liste $en_attente_de_traitement (bien entendu tu vérifieras de ne pas remettre en attente des boules déjà traité historie de na pas bouclé a l’infinie. De plus tu enregistres dans un autre tableau, genre $resultat, les coordonnées des boules déjà traité et donc potentiellement celle qui t’intéresse, que tu gardes a chaque itération de la fonction, tout comme $en_attente_de_traitement.)
En fin d’algo, tu te retrouves avec $resultat qui est un tableau de x éléments qui sont la ou les solutions que tu souhaites (et $en_attente_de_traitement vide).

C’est marrant, ton projet ma tout de suite fait pensé a un petit jeu que j’ai créé il y a 2 ans, durant un cours d’éco. (que j’ai ensuite codé vite fait sur machine), le but était de mettre le plus de cases de même couleur bout à bout sur une grille de x*x cases avec les couleurs à mettre dans les cases qui été randomisé a chaque tour, pour faire plus de points que son adversaires… bref, je gérais le cas des diagonales pour ce petit jeu là, mais en l’occurrence cela ne change rien à l’algorithme, a part que tu doit t’embêté a ne pas vérifier les diagonales ^^

[atra27]

C'est pas vraiment un projet a par entiére, disons que j'ai entendu parler de ce probléme dans je sais plus quel cours et jme suis demandé comment faire
Et forcément quand on sait pas comment faire, bah y a JeuPhp :p
J'ai pondu un truc, je pense tenir le bon bout. je posterai quand j'aurai le temps de la finir (journée chargée ^^)

[atra27]

Bon... j'arrive tjr pas a régler ce pu**** de probléme

Jsuis incapable d'obtenir un résultat cohérent...
Méme le script de nicodd fonctionne sur la map d'exemple, mais si on prend une map avec plusieurs groupes imbriqués, on encore des groupes a plus de deux pierres on se retrouve avec des résultats incohérents.
J'ai passé l'aprem a essayer de m'en sortir mais la au bout de la 3éme fois que je ré-essaye depuis zéro je reviens chercher de l'aide...

[Sloop]

Donne ton code et ton exemple "complexe".

[niahoo]

Voilà une implémentation possible.
Bien que PHP ne soit pas forcément optimisé pour fonctionner avec de la récursion...

mais ça marche.

Un dernier truc,

quand tu écris $map[0]=array(0,1,0,1,1,1,1,0);
ici le premier 0 symbolise les Y et non pas les X, qui sont représentés par l'odre dans l'array à droite du signe '='.
$map[Y][X] <- le Y sont bien les lignes, lex X les colonnes.

<?php

/* implémentation du test d'encerclement 

Cette implémentation considère qu'un groupe enfermé contre

un bord est enfermé,  et considère  donc que le bord de la

map « joue » pour la couleur adverse

*/







$map=array();

$map[]=array(0,1,0,1,1,1,1,0);

$map[]=array(1,2,1,2,2,1,2,1);

$map[]=array(1,2,1,1,2,1,2,1);

$map[]=array(0,1,1,2,2,1,2,1);

$map[]=array(0,2,2,1,1,1,2,1);

$map[]=array(0,0,0,0,0,1,2,1);

define('white', 1);

define('black', 2);

define('void',  0);

define('circled', 0);





function main_loop($map, $color) {



  $visited = array();

  $groups  = array();

  list($mapx, $mapy) = get_map_size($map);

  for($x = 0; $x < $mapx; $x++) {

    for($y = 0; $y < $mapy; $y++) {

      if(!is_visited($visited,array($x, $y)) && $map[$y][$x] == $color) {

	$node_expand = expand_node($map, $x, $y, $color, $visited, array(),0);

	list($is_circled, $stack, $visited) = $node_expand;

	if($is_circled == circled) {

	  array_push($groups, $stack);

	}

      }

    }

  }

  return $groups;

}



function get_map_size($map) {

  return array(count($map[0]), count($map));

}



/** la fonction expand_node n'est appellée par autre chose qu'elle même qu'avec les coordonnées

    d'une cellule de la couleur choisie **/

function expand_node($map, $x, $y, $color, $visited, $stack, $circle_iter) {

  $visited[$x][$y] = true; 

  $stack[] = array($x, $y);

  $calls = array('top','left','right','bottom');

  foreach($calls as $fun) {

    $side_cell = call_user_func($fun, $x, $y);

    if(cell_exists($map,$side_cell) && !is_visited($visited, $side_cell)) {

      if(cell_color($map, $side_cell) == $color) {

	$node_expand = expand_node($map, $side_cell[0], $side_cell[1], $color, $visited, $stack, $circle_iter);

	list($is_circled, $stack, $visited) = $node_expand;

	$circle_iter += $is_circled;

      }

      elseif(cell_color($map, $side_cell) == void) {

	$circle_iter++;

      }

    }

    /* // Partie à décommenter pour que le bord de la map ne  participe pas à l'encerclement des cases

    elseif(!cell_exists($map, $side_cell)) {

      	$circle_iter++;

    }

    //*/

  }

  return array($circle_iter, $stack, $visited);

}



function cell_color($map, $cell) {

  return $map[$cell[1]][$cell[0]];

}



function top($x, $y) { return array($x, $y-1); }

function left($x, $y) { return array($x-1, $y); }

function right($x, $y) { return array($x+1, $y); }

function bottom($x, $y) { return array($x, $y+1); }



function is_visited($visited, $cell) {

  return isset($visited[$cell[0]][$cell[1]]);

}



function cell_exists($map, $cell) {

  return isset($map[$cell[1]][$cell[0]]);

}



function display_results($groups) {

  echo "Voici les groupes encerclés:\n";

  foreach($groups as $group) {

    echo 'groupe: ';

    foreach($group as $cell)

      echo '('.implode(',', $cell).')';

    echo "\n";

  }

}

display_results(main_loop($map, black));

edit:
une petite optimisation,
remplacer
$calls = array('top','left','right','bottom');
par
$calls = array('right','bottom','top','left');

Puisque on commence en haut à gauche de la map, les groupes seront peut-être plus souvent étendus vers la droite et vers le bas.

[niahoo]

Bon l'algo que je t'ai posté au dessus permet de récupérer les groupes. Si tu veux un algo qui teste juste 1 case, il te suffit de faire remonter une Exception dès qu'une case vide est trouvée.

dans main_loop

try {
... node_expand....
return 'groupe';
}
catch(void_found $e) {
return 'pas entouré';
}

[atra27]

sa tourne parfaitement, plus qu'a comprendrecomment sa marche :p

Thx a lot