Les Algorithmes de Quoridor.fr

  La modélisation du Plateau de Jeu

  Le parcours du graphe en largeur

//*****************************************************************************************
//       Parcours ou descente en largeur dans le graphe (matrice adjacente)	             //
//*****************************************************************************************		
// initialisation
	game.graphe.init = function (graphe) {
		var visited = [] ;
		for(var i = 0; i < graphe.length ; i++){
			visited[i] = 0; //initialise la liste des noeuds visités à 0 (i est le noeud)
			}
		return visited ;
		} ;

// méthode de descente en largeur
	game.graphe.descenteEnLargeur = function(graphe, start, visited,ligneDestination){
		var valide = false ;
	// creation d'une file vide
		var file = [];
	// intialisation de la file avec le premier sommet
		file.push(start);
		visited[start] = 1;
		var t ;
		var arc ;
		var lignedescente ;
		while (file.length != 0) {
			t = file.splice(0,1) ;    // sort le premier élément de la file
			for(var i =0 ; i < graphe[t].length ; i++) {
				arc = graphe[t][i] ;
				if (visited[i] == 0 && arc == 1) {
					visited[i] = 1;
					file.push(i) ;

    // Partie spécifique au jeu pour vérifier si une ligne est atteinte
					lignedescente = Math.floor(i/10) ;
				if (lignedescente == ligneDestination) {
					valide = true ;		
						}
    // Fin de la partie spécifique à ce jeu
					}
				}
			}
			return valide ;  // return visited ;  //de façon + générale
		} ;
    

  L'Heuristique de l'IA de Quoridor

			// ********************************************************************************************************	
// algorithme de Floyd Warshall pour trouver les plus cours chemin dans le graphe à partir d'un sommet
//
//**********************************************************************************************************

	game.graphe.FloydWarshall =function(grapheJ){
		var jeuG = grapheJ ;
		var INFINI = 1000 ;
		//var len = jeuG.length ;
		var len = 100;
		var valeur ;
		var chemins = [];
		var dist = new Array(100);
		for (var i = 0 ; i<=99 ; i++) {
				dist[i] = new Array();
			}
		var pred = new Array(100);
		for (var i = 0 ; i<=99 ; i++) {
				pred[i] = new Array();
			}
// boucles d'initialisation de l'algorithme
		for (var i=0 ; i < len ; i++) {
			for (j=0 ; j < len ; j++) {
				pred[i][j] = j ;
				dist[i][j]  = INFINI ;
				if((jeuG[i][j]) == 1){
					valeur = jeuG[i][j];
					dist[i][j] = valeur;
					}
		
				}
			}
// boucles de détermination des plus courts chemins de l'ensemble du graph (distances et chemins)

	for (var k = 0; k < len; k++){
			for (var i = 0; i < len; i++) {
				for (var j = 0; j < len; j++) {	
				if (dist[i][j] > (dist[i][k] + dist[k][j])) {
					dist[i][j]= (dist[i][k] + dist[k][j]) ;
					pred[i][j] = pred[i][k] ;
						}
					}
				}
			}
			chemins[0] = dist ;
			chemins[1] = pred ;
			return chemins ; 
		}		;

//**************************************************************************************//
// Recherche des chemins les plus courts à partir des sommets initiaux et finaux        //
//**************************************************************************************//
	game.graphe.courtChemin = function (start, end, pred){
			var chemin = [];
			chemin.push(start) ;
			suivant = pred[start][end] ;
			chemin.push(suivant) ;
		while(suivant!=end){
			suivant = pred[suivant][end];
			chemin.push(suivant) ;
			}
		return chemin ;
			}