library Paturages;

type
	Grid = array of array of integer ;
	Coord = record
		l, c : integer;
	end;

function get_name : string; cdecl;
begin
	get_name := 'Paturages';
end;

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//                                             //    VERIFICATION DE LA GRILLE / CHEMIN OPTIMAL    //
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


procedure dijkstraGrille(grille : matrix ; var grilcoups : matrix ; tresor, enter, taille : coord ; var valide : boolean);
// INGOUFF Christian, 16/01/12
// Inspiré de l'algorithme de Dijkstra (Chemin le plus court optimal)
// Retournera la "grille des distances" (grilcoups) avec les cases libres marquées de leur distance par rapport au départ et la validité ou non de la grille.
// Les cases remplies auront comme nombre leur distance par rapport au départ. La distance enter/tresor avec les murs est ainsi obtenue.
var
	i, j, k, dist : integer; // dist = Distance par rapport au départ
	loc, inf, sup : coord; // inf et sup = valeurs qui augmenteront selon la distance au départ (recherche en "cercle")
	direc : array_coord; // Cases adjacentes à une case donnée
begin
	setLength(grilcoups,taille[1],taille[2]);
	remiseZero(grilcoups,taille,-1);
	grilcoups[enter[1],enter[2]] := 0; // Initialisation : l'algorithme va d'abord chercher cette case
	valide := TRUE; // Pour ne pas casser la boucle dès le début
	dist := 0;
	while valide and (grilcoups[tresor[1],tresor[2]] = -1) do // Boucle jusqu'à trésor trouvé ou impossible de continuer
	begin
		valide := FALSE; // Initialisation de "valide"
		bornes(inf,sup,enter,taille,dist); // Définition des bornes inférieure et supérieure
		for i := inf[1]-1 to sup[1]-1 do
			for j := inf[2]-1 to sup[2]-1 do // On parcourt le tableau d'abord en cercle (avec inf et sup) puis en entier quand dist > taille
				if (grilcoups[i,j] = dist) then // Si la case correspond à ce tour (dist)
				begin
					loc[1] := i;
					loc[2] := j; // On assigne les coordonnées de cette case à "loc"
					arrayDirec(direc,loc); // On obtient les coordonnées des cases adjacentes
					for k := 1 to 4 do // Pour chaque case adjacente
						if (grilcoups[direc[k,1],direc[k,2]] = -1) and (grille[direc[k,1],direc[k,2]] > -42) then // Si la case n'a pas été franchie et n'est pas un mur
						begin
							grilcoups[direc[k,1],direc[k,2]] := dist+1; // La remplir pour le tour suivant (dist+1)
							valide := TRUE; // Indique qu'au moins une case a été remplie pendant ce tour
						end;
				end;
		dist := dist+1; // On continue tant que le trésor n'a pas été marqué de sa distance par rapport au départ,
				// ou jusqu'à ce que toutes les cases accessibles soient marquées.
	end;
end;

function dijkstra(grille : matrix ; tresor, enter, taille : coord): integer;
// INGOUFF Christian, 16/01/12
// Retourne le nombre de coups minimum requis pour atteindre le trésor
// Principalement utilisé dans la définition de la difficulté de jeu.
var
	grilcoups : matrix;
	valide : boolean;
begin
	dijkstraGrille(grille,grilcoups,tresor,enter,taille,valide); // Création de la grille des distances
	if not valide then dijkstra := -1 // Si grille non valide
	else dijkstra := grilcoups[tresor[1],tresor[2]]; // Nombre de coups optimal
end;

function recurMeilleur(prec, loc : coord ; grilcoups : matrix):coord;
// INGOUFF Christian, 20/01/12
// Fonction récursive qui parcourt le chemin le plus court (tracé par Dijkstra) depuis le trésor jusqu'à un départ donné.
// (De la valeur "nombre de coups optimal" à 0 (le point donné))
// Retourne la coordonnée de la case la plus avantageuse.
var
	direc : array_coord;
	sens : integer;
begin
	arrayDirec(direc,loc); // On obtient les coordonnées des cases adjacentes
	sens := 1;
	if grilcoups[loc[1],loc[2]] <> 0 then // Jusqu'à ce qu'on soit au départ
		while sens < 5 do // Pour chaque sens
		begin
			if grilcoups[direc[sens,1],direc[sens,2]] = grilcoups[loc[1],loc[2]]-1 then // Vérifie si la case est sur le chemin (à l'envers)
			begin
				recurMeilleur := recurMeilleur(loc,direc[sens],grilcoups); // On continue le chemin
				sens := 5; // Fin boucle
			end
			else sens := sens+1; // Sinon, un autre sens
		end
	else recurMeilleur := prec; // Quand on est au départ, la coordonnée optimale est la précédente traitée.
end;

function meilleurCoup(grille : matrix ; tresor, depart : coord):integer;
// INGOUFF Christian, 20/01/12
// Fonction qui recherche la direction la plus avantageuse :
// 1 = Haut, 2 = Bas, 3 = Gauche, 4 = Droite
var
	direc : array_coord;
	objectif, taille_large : coord;
	i : integer;
	grilcoups : matrix;
	valide : boolean;
begin
	taille_large[1] := length(grille); // Taille réelle des grilles (jeu = x*x, réel = (x+2)*(x+2))
	taille_large[2] := length(grille[0]);
	meilleurCoup := -1;
	dijkstraGrille(grille,grilcoups,tresor,depart,taille_large,valide); // Création de la grille des distances
	if valide then // Si grille valide
	begin
		arrayDirec(direc,depart); // Cases adjacentes
		objectif := recurMeilleur(depart,tresor,grilcoups); // Le bot voudra aller sur cette case
		i := 1;
		repeat // Il cherche cette case
			if (direc[i,1] = objectif[1]) and (direc[i,2] = objectif[2]) then meilleurCoup := i; // Et en retourne le sens (cf description)
			i := i+1;
		until meilleurCoup > -1;
	end;
end;


//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//                  				   //    INITIALISATION DE LA GRILLE    //
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


procedure remplCase(var grille : matrix ; taille : coord ; type_case : integer ; var coord_case : coord);
// INGOUFF Christian, 11/01/12
// Permet d'attribuer à une case au hasard d'une grille une valeur particulière (le type de case : trésor, entrée, murs) si elle est libre.
// Retourne la grille avec cette case remplie et les coordonnées de la case remplie.
var
  valide : boolean;
begin
	repeat
		coord_case[1] := random(taille[1]-1) + 1;
		coord_case[2] := random(taille[1]-1) + 1;
		valide := grille[coord_case[1],coord_case[2]] = 0; // Vérifie si la case n'est pas occupée par autre chose
		if valide then grille[coord_case[1],coord_case[2]] := type_case
	until valide;
end;

procedure iniGrille(var grille:matrix; taille : coord ; var tresor, enter : coord ; min, max : integer);
// Pré-condition : Reçoit un tableau vide de taille définie (non nulle) et la difficulté du jeu aussi définie (min, max)
// Post-condition : Renvoie la grille remplie et les coordonnées du trésor et de l'entrée.
// INGOUFF Christian, 11/01/12
var
	i, nb_coups, nb_murs : integer;
	tmp : coord;
	valide : boolean;
begin
	remiseZero(grille,taille,0); // Initialise la grille
	nb_murs := trunc(( 15 / 49 ) * ( (taille[1]-2) * (taille[2]-2) )); // Définit le nombre de murs
	remplCase(grille,taille,42,tresor); // Trésor = 42
	remplCase(grille,taille,10,enter); // Porte d'entrée = 10
	if dijkstra(grille,tresor,enter,taille) < 3 then iniGrille(grille,taille,tresor,enter,min,max) // S'ils ne sont pas assez éloignés
	else
	begin
		for i := 1 to nb_murs do // Placement des murs
			repeat
				remplCase(grille,taille,-42,tmp); // Mur = -42
				valide := dijkstra(grille,tresor,enter,taille) > -1;
				if not valide then grille[tmp[1],tmp[2]] := 0; // Si la grille n'est pas valide après placement du mur, recommencer
			until valide;
		nb_coups := dijkstra(grille,tresor,enter,taille); // Nombre de coups optimal
		if (nb_coups < min) or (nb_coups > max) then	// Si la grille ne vérifie pas les conditions de la difficulté de jeu
			iniGrille(grille,taille,tresor,enter,min,max); // Recommencer
	end;
end;

procedure init_grid(var _grid : Grid ; h, w, nb_walls : integer); cdecl;
var
	i, j : integer;
	tresor, enter : coord;
begin
	for i := 0 to taille[1]-1 do
		for j := 0 to taille[2]-1 do
			_grid[i,j] := 0;
	remplCase(grille,taille,42,tresor); // Trésor = 42
	remplCase(grille,taille,10,enter); // Porte d'entrée = 10
	if dijkstra(grille,tresor,enter,taille) < 3 then iniGrille(grille,taille,tresor,enter,min,max) // S'ils ne sont pas assez éloignés
	else
	begin
		for i := 1 to nb_murs do // Placement des murs
			repeat
				remplCase(grille,taille,-42,tmp); // Mur = -42
				valide := dijkstra(grille,tresor,enter,taille) > -1;
				if not valide then grille[tmp[1],tmp[2]] := 0; // Si la grille n'est pas valide après placement du mur, recommencer
			until valide;
		nb_coups := dijkstra(grille,tresor,enter,taille); // Nombre de coups optimal
		if (nb_coups < min) or (nb_coups > max) then	// Si la grille ne vérifie pas les conditions de la difficulté de jeu
			iniGrille(grille,taille,tresor,enter,min,max); // Recommencer
	end;
end;

function play (var _grid : Grid ; h, w : integer ) : Coord ; cdecl;
begin
end;

procedure outcome (var _grid : Grid ; h, w : integer; just_played : Coord; answer : integer ); cdecl;
begin
	if _grid[just_played.l,just_played.c] = -1 Then
	Case answer Of
		0, 1, 2 : _grid[just_played.l,just_played.c] := answer;
	end;
end;

exports
get_name, init_grid, play, outcome ;
end.