[Algorithme javaScript] Check de pions sur un plateau

[Furukoo]

Bonjour

Je porte le jeu Ziboologic en HTML5 avec Raphaël JS.

Le but du jeu est de remplir un plateau de 5x5 cases avec des pions de couleur sans
jamais aligner 2 fois la même couleur :
- horizontalement
- verticalement
- sur les 2 diagonales qui passent au centre du plateau

Ma première idée est de vérifier de façon brute tous les cas possibles :

Code :

function horizCheck(index){
  switch(index){
    case 0 :
    case 5 :
    case 10:
    case 15:
    case 20:    
      if(gbd[index].data('c')===gbd[index+1].data('c')){gameLoss=true;};
      if(gbd[index].data('c')===gbd[index+2].data('c')){gameLoss=true;};
      if(gbd[index].data('c')===gbd[index+3].data('c')){gameLoss=true;};
      if(gbd[index].data('c')===gbd[index+4].data('c')){gameLoss=true;};
      break;
    case 1 :
    case 6 :
    case 11:
    case 16:
    case 21:
      if(gbd[index].data('c')===gbd[index-1].data('c')){gameLoss=true;};
      if(gbd[index].data('c')===gbd[index+1].data('c')){gameLoss=true;};
      if(gbd[index].data('c')===gbd[index+2].data('c')){gameLoss=true;};
      if(gbd[index].data('c')===gbd[index+3].data('c')){gameLoss=true;};
      break;
  };
};
// etc ... //

une autre idée ?

http://jsfiddle.net/G7fAQ/97/

[Ter Rowan]

Pas comme ça en tout cas

A mon sens :

La case que tu testes (on dira x y) est sur une ligne (xi = 0 a 4, yi = y) et une colonne (yi =0 a 4, xi=x)
De fait il te suffit de faire une boucle sur toutes les cases de ta ligne et sur toutes les cases de ta colonne
Avec juste une nuance, tu ne testes pas la case qui est en x y évidemment

Meme principe pour la diagonale une boucle suffit

[Xenos]

Salut,

fait plutôt une fonction qui teste si toutes les couleurs d'une ligne N sont les mêmes, une fonction pour la colonne C, et une pour la diagonale D. Après, boucle 5 fois la 1ere fonction, 5 fois la deuxième, et 2 fois la dernière, ce sera plus soft qu'un énorme switch.
Pour tester si une ligne est d'une couleur, prend le premier pion de la ligne, et compare-le à chacun des autres pions de la ligne (boucle for). Idem pour la colonne et la diagonale.

Après, je pense qu'il y a des solutions en voyant le problème comme une matrice de 5x5, mais traduire la condition des couleurs, je ne sais pas trop comment faire (attribuer un nombre à chaque couleur, ok, mais quelles conditions poser sur ces nombres et sur la matrice pour vérifier les alignements?)

[Furukoo]

Salut,

fait plutôt une fonction qui teste si toutes les couleurs d'une ligne N sont les mêmes, une fonction pour la colonne C, et une pour la diagonale D. Après, boucle 5 fois la 1ere fonction, 5 fois la deuxième, et 2 fois la dernière, ce sera plus soft qu'un énorme switch.
Pour tester si une ligne est d'une couleur, prend le premier pion de la ligne, et compare-le à chacun des autres pions de la ligne (boucle for). Idem pour la colonne et la diagonale.

Après, je pense qu'il y a des solutions en voyant le problème comme une matrice de 5x5, mais traduire la condition des couleurs, je ne sais pas trop comment faire (attribuer un nombre à chaque couleur, ok, mais quelles conditions poser sur ces nombres et sur la matrice pour vérifier les alignements?)

Oui c'est ce que j'appelle tester tous les cas :

Code :

function rowCheck(index){
  switch(index){
    case 0 :
    case 5 :
    case 10:
    case 15:
    case 20:    
      if(gbd[index].data('c')===gbd[index+1].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+2].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+3].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+4].data('c')){gameLoss=true;break;};
      break;
    case 1 :
    case 6 :
    case 11:
    case 16:
    case 21:
      if(gbd[index].data('c')===gbd[index-1].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+1].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+2].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+3].data('c')){gameLoss=true;break;};
      break;
    case 2 :
    case 7 :
    case 12:
    case 17:
    case 22:
      if(gbd[index].data('c')===gbd[index-2].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-1].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+1].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+2].data('c')){gameLoss=true;break;};
      break;
    case 3 :
    case 8 :
    case 13:
    case 18:
    case 23:
      if(gbd[index].data('c')===gbd[index-3].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-2].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-1].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+1].data('c')){gameLoss=true;break;};
      break;
    case 4 :
    case 9 :
    case 14:
    case 19:
    case 24:
      if(gbd[index].data('c')===gbd[index-4].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-3].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-2].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-1].data('c')){gameLoss=true;break;};
      break;      
  };
};

function colCheck(index){
  switch(index){
    case 0 :
    case 1 :
    case 2:
    case 3:
    case 4:    
      if(gbd[index].data('c')===gbd[index+5].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+10].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+15].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+20].data('c')){gameLoss=true;break;};
      break;
    case 5 :
    case 6 :
    case 7:
    case 8:
    case 9:    
      if(gbd[index].data('c')===gbd[index-5].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+5].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+10].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+15].data('c')){gameLoss=true;break;};
      break;
    case 10 :
    case 11 :
    case 12:
    case 13:
    case 14:    
      if(gbd[index].data('c')===gbd[index-10].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-5].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+5].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+10].data('c')){gameLoss=true;break;};
      break;
    case 15 :
    case 16 :
    case 17:
    case 18:
    case 19:    
      if(gbd[index].data('c')===gbd[index-15].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-10].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-5].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index+5].data('c')){gameLoss=true;break;};
      break;
    case 20 :
    case 21 :
    case 22:
    case 23:
    case 24:    
      if(gbd[index].data('c')===gbd[index-20].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-15].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-10].data('c')){gameLoss=true;break;};
      if(gbd[index].data('c')===gbd[index-5].data('c')){gameLoss=true;break;};
      break;    
  };
  
};

function diaCheck(index){
  switch(index){
    case 0 :
      if(gbd[0].data('c')===gbd[6].data('c')){gameLoss=true;break;};
      if(gbd[0].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[0].data('c')===gbd[18].data('c')){gameLoss=true;break;};
      if(gbd[0].data('c')===gbd[24].data('c')){gameLoss=true;break;};
      break;
    case 6 :
      if(gbd[6].data('c')===gbd[0].data('c')){gameLoss=true;break;};
      if(gbd[6].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[6].data('c')===gbd[18].data('c')){gameLoss=true;break;};
      if(gbd[6].data('c')===gbd[24].data('c')){gameLoss=true;break;};
      break;
    case 12 :
      if(gbd[12].data('c')===gbd[0].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[6].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[18].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[24].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[4].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[8].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[16].data('c')){gameLoss=true;break;};
      if(gbd[12].data('c')===gbd[20].data('c')){gameLoss=true;break;};
      break;
    case 18 :
      if(gbd[18].data('c')===gbd[0].data('c')){gameLoss=true;break;};
      if(gbd[18].data('c')===gbd[6].data('c')){gameLoss=true;break;};
      if(gbd[18].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[18].data('c')===gbd[24].data('c')){gameLoss=true;break;};
      break;
    case 24 :
      if(gbd[24].data('c')===gbd[0].data('c')){gameLoss=true;break;};
      if(gbd[24].data('c')===gbd[6].data('c')){gameLoss=true;break;};
      if(gbd[24].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[24].data('c')===gbd[18].data('c')){gameLoss=true;break;};
      break;
    case 4 :
      if(gbd[4].data('c')===gbd[8].data('c')){gameLoss=true;break;};
      if(gbd[4].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[4].data('c')===gbd[16].data('c')){gameLoss=true;break;};
      if(gbd[4].data('c')===gbd[20].data('c')){gameLoss=true;break;};
      break;
    case 8 :
      if(gbd[8].data('c')===gbd[4].data('c')){gameLoss=true;break;};
      if(gbd[8].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[8].data('c')===gbd[16].data('c')){gameLoss=true;break;};
      if(gbd[8].data('c')===gbd[20].data('c')){gameLoss=true;break;};
      break;
    case 16 :
      if(gbd[16].data('c')===gbd[4].data('c')){gameLoss=true;break;};
      if(gbd[16].data('c')===gbd[8].data('c')){gameLoss=true;break;};
      if(gbd[16].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[16].data('c')===gbd[20].data('c')){gameLoss=true;break;};
      break;
    case 20 :
      if(gbd[20].data('c')===gbd[4].data('c')){gameLoss=true;break;};
      if(gbd[20].data('c')===gbd[8].data('c')){gameLoss=true;break;};
      if(gbd[20].data('c')===gbd[12].data('c')){gameLoss=true;break;};
      if(gbd[20].data('c')===gbd[16].data('c')){gameLoss=true;break;};
      break;  
  };
};

je cherche un autre algo que celui là

[Xenos]

Heu, non, car je te parle de 3 fonctions, une qui teste une ligne donnée, l'autre qui teste une colonne donnée, la dernière qui teste une diagonale donnée.
Dans chacune de ces fonctions, il n'y a donc qu'une seule boucle for, qui teste toutes les cases de la ligne/colonne/diagonale:

Code :

/**
* @param int l Numéro de ligne
* @param int n Taille du plateau, considéré comme carré n*n
* @return bool true si la ligne est d'une seule couleur
*/
function testeLigne(l, n)
{
var color = plateau[l][0]; //Récupérer la couleur en L,0
for (var i=1;i<n;i++)
if (plateau[l][i] != color)
return false; // J'ai trouvé une couleur différente: je quitte

return true; // Sinon, je renvoie true, car toute la ligne est d'une couleur
}
...

Pour tester toutes les lignes, tu appelles la fonction dans une boucle:

Code :

for (var x=0;x<nb_lignes;x++)
if (testeLigne(x))
return vousAvezPerduCarVousAvezColoreUneLigne();

Il ne s'agit donc pas de faire un énorme "switch", mais d'utiliser des boucles et des fonctions, c'est ce pour quoi est prévu l'informatique: éviter de taper tous les cas possibles un à un.

Oui, en pratique, cela reviendra à tester tous les cas, mais avec un code qui est suffisamment léger pour être lisible et pour être entretenu (car ton switch, si tu passe à un plateau 6x6, tu vas en ch*er!)

Si tu as l'index entier N et que tu cherches les coordonnées ligne-colonne (l,c), c'est assez simple:
(l,c) = (floor(N/p), c%p)
avec p la taille du plateau; valable pour des index non-négatifs; les coordonnées sont entre (0,0) inclus et (p-1,p-1) inclus.