#include <assert.h>

#include <string.h>

#include <stdio.h> /**********************************PROVA */

#include "general.h"

/* Variables related to the showing of information by os */

extern float percent_to_show;

extern int depth_to_show;

extern int max_depth;

extern int min_depth_period;

extern int max_depth_period;

extern struct Map * actual_map;

/* Prototipes */

static Bool are_there_fixed_boxes(struct Map *m,

	struct BoxMove movements[MAX_MOVES], int *num_movements);

static void force_move_box(struct Map *m, const struct BoxMove move);

static Bool search_did_found(struct Map maps[], int depth,

	struct BoxMove movements[],

	int num_movements, float percent, float total_percent);

static void fill_deps(struct Map *m);

#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/

 Situation:

  ->@$ #

      $

*/

int box_will_be_blocked(const struct Map * m, const struct Position mov,

	const struct Position box_pos)

{

	struct Position next_pos2, tmp, tmp2[2];

	int i;

	next_pos2.x = box_pos.x + mov.x;

	next_pos2.y = box_pos.y + mov.y;

	tmp.x = next_pos2.x + mov.x;

	tmp.y = next_pos2.y + mov.y;

	tmp2[0].x = next_pos2.x + mov.y;

	tmp2[0].y = next_pos2.y + mov.x;

	tmp2[1].x = next_pos2.x - mov.y;

	tmp2[1].y = next_pos2.y - mov.x;

	for (i=0; i < 2; i++)

	{

		if (m->man_moves[tmp.y][tmp.x] == WALL &&

			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)

		{

			return TRUE;

		}

		else if (m->man_moves[tmp.y][tmp.x] == BOX &&

			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)

		{

			return TRUE;

		}

		else if (m->man_moves[tmp.y][tmp.x] == BOX &&

			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)

		{

			return TRUE;

		}

	}

	return FALSE;

}

int is_corner_area(const struct Map * m, const struct Position p,

	const struct Position box, const struct Position new_box)

{

	int NumMoves, NewMoves;

	struct Position pos[MAX_MOVES];

	struct Position new_pos[MAX_MOVES];

	char corners[MAX_Y][MAX_X];

	int i,j;

	struct Position next_pos;

	char *next_cell;

	/* Blank the garden */

	for (j = 0; j<m->SizeY; j++)

		for (i=0; i<m->SizeX; i++)

			corners[j][i] = m->Cells[j][i];

	/* Let's put the boxes */

	for (i = 0; i<m->NumBoxes; i++)

		corners[m->Box[i].y][m->Box[i].x] = BOX;

	/* Let's put our box - it can be simply added */

	corners[new_box.y][new_box.x] = BOX;

	/* Let's remove the original box. */

	corners[box.y][box.x] = BLANK;

	NewMoves = 1;

	new_pos[0] = p;

	while (NewMoves > 0)

	{

		/* The before named "New Moves" become the moves we have

		   to analyze */

		NumMoves = NewMoves;

		for (i=0; i<NewMoves; i++)

		{

			pos[i] = new_pos[i];

		}

		/* Search new positions for each position */

		NewMoves = 0;

		for (i=0; i<NumMoves; i++)

		{

			/* For each direction */

			for (j=0; j<4; j++)

			{

				next_pos.x = pos[i].x + move_vectors[j].x;

				next_pos.y = pos[i].y + move_vectors[j].y;

				next_cell = &corners[next_pos.y][next_pos.x];

				if(*next_cell == BLANK ||

					*next_cell == PLATFORM)

				{

					return FALSE;

				}

				else if(*next_cell == CORNER)

				{

					new_pos[NewMoves] = next_pos;

					*next_cell = MANCANMOVE;

					NewMoves++;

				}

			}

		}

	}

	return TRUE;

}

int does_box_close_corners(const struct Map * m, const struct Position mov,

	const struct Position box_pos)

{

	struct Position p, p2;

	p.x = box_pos.x + mov.x;

	p.y = box_pos.y + mov.y;

	/* Let's plan the checks */

	/* The point will be marked with a MANCANMOVE */

	p2.x = p.x + mov.x;

	p2.y = p.y + mov.y;

	if (m->Cells[p2.y][p2.x] == CORNER)

	{

		if (is_corner_area(m, p2, box_pos, p))

			return TRUE;

	}

	p2.x = p.x + mov.y;

	p2.y = p.y + mov.x;

	if (m->Cells[p2.y][p2.x] == CORNER)

	{

		if (is_corner_area(m, p2, box_pos, p))

			return TRUE;

	}

	p2.x = p.x - mov.y;

	p2.y = p.y - mov.x;

	if (m->Cells[p2.y][p2.x] == CORNER)

	{

		if (is_corner_area(m, p2, box_pos, p))

			return TRUE;

	}

	return FALSE;

}

#endif

static void force_move_box(struct Map *m, const struct BoxMove move)

{

	struct Position newpos;

	/* Add coords */

	newpos.x = m->Box[move.box].x + move.dir.x;

	newpos.y = m->Box[move.box].y + move.dir.y;

	/* Be certain the move can be done */

	assert(m->Cells[newpos.y][newpos.x] != BOX);

	assert(m->Cells[newpos.y][newpos.x] != WALL);

	/* Control if we moved the box to a platform */

	if(m->Cells[newpos.y][newpos.x] == PLATFORM)

	{

		m->NumBoxesInPlatform++;

	}

	/* Control if we moved the box from a platform */

	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)

	{

		m->NumBoxesInPlatform--;

	}

	m->Man = m->Box[move.box];

	m->Box[move.box] = newpos;

}

static Bool search_did_found(struct Map maps[], int depth,

	struct BoxMove movements[],

	int num_movements, float percent, float total_percent)

{

	struct BoxMove new_movements[MAX_MOVES];

	int num_new_movements;

	struct Map *m; 

	int i;

	float next_percent;

	next_percent = percent / num_movements;

	m = &maps[depth+1];

	if (depth > max_depth)

		max_depth = depth;

	if (depth > max_depth_period)

		max_depth_period = depth;

	if (depth < min_depth_period)

		min_depth_period = depth;

	for (i=0; i < num_movements; i++)

	{

		CopyMap(m, &maps[depth]);

		force_move_box(m, movements[i]);

		/* Let's see if we finished */

		if (m->NumPlatforms == m->NumBoxesInPlatform)

		{

			PrintMove(movements[i]);

			actual_map = &maps[depth+1];

			show_percent_and_map();

			return TRUE;

		}

		if (is_new_map(maps, depth+1))

		{

			actual_map = &maps[depth+1];

#ifdef DEBUG		/* to be out */

			show_percent_and_map();

#endif

			fill_deps(m);

			if (are_there_fixed_boxes(m,

				new_movements, &num_new_movements))

			{

				/* That means that the map is illegal */

				/* Maybe we could update the percent here... */

				return FALSE;

			}

			/* the assert should be IN the function before,

			   before OVERfilling new_movements */

			assert(num_new_movements < MAX_MOVES);

		}

		else

			num_new_movements = 0;

		if (num_new_movements == 0)

		{

			percent_to_show = total_percent + next_percent*i;

			depth_to_show = depth;

		}

		else

		{

			if (depth+1 < MAX_STEPS)

			{

				if(search_did_found(maps, depth+1, new_movements,

					num_new_movements, next_percent,

					total_percent + next_percent*i) == TRUE)

				{

					PrintMove(movements[i]);

					actual_map = &maps[depth+1];

					show_percent_and_map();

					return TRUE;

				}

			}

		}

	}

	return FALSE;

}

/* It only fills the m->man_moves structure */

static void paint_mancanmove(struct Map *m)

{

	struct Position pos[MAX_MOVES];

	struct Position new_pos[MAX_MOVES];

	int NumMoves, NewMoves;

	int j, i;

	struct Position next_pos;

	char *next_cell;

	/* Let's  the map with only walls in man_moves - other, blanks */

	for (j = 0; j<m->SizeY; j++)

		for (i=0; i<m->SizeX; i++)

		{

			if (m->Cells[j][i] == WALL)

				m->man_moves[j][i] = WALL;

			else

				m->man_moves[j][i] = BLANK;

		}

	/* Let's put the boxes */

	for (i = 0; i<m->NumBoxes; i++)

	{

		m->man_moves[m->Box[i].y][m->Box[i].x] = WALL;

	}

	NewMoves = 1;

	new_pos[0].x = m->Man.x;

	new_pos[0].y = m->Man.y;

	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;

	while (NewMoves > 0)

	{

		/* The before named "New Moves" become the moves we have

		   to analyze */

		NumMoves = NewMoves;

		for (i=0; i<NewMoves; i++)

		{

			pos[i] = new_pos[i];

		}

		/* Search new positions for each position */

		NewMoves = 0;

		for (i=0; i<NumMoves; i++)

		{

			/* For each direction */

			for (j=0; j<4; j++)

			{

				next_pos.x = pos[i].x + move_vectors[j].x;

				next_pos.y = pos[i].y + move_vectors[j].y;

				next_cell = &m->man_moves[next_pos.y][next_pos.x];

				if(*next_cell == BLANK)

				{

					new_pos[NewMoves] = next_pos;

					*next_cell = MANCANMOVE;

					NewMoves++;

				}

			}

		}

	}

}

/* Returns TRUE if there are fixed boxes that should be moved, FALSE otherwise*/

/* For 'm' it modifies only m->boxes[][] */

static Bool are_there_fixed_boxes(struct Map *m,

	struct BoxMove movements[MAX_MOVES], int *num_movements)

{

	int i,j;

	enum e_direction d;

	/* Box dependencies. The first depends on seconds. */

	struct

	{

		Bool box[MAX_BOXES][MAX_BOXES];

		int ndeps[MAX_BOXES];

	} dep;

	/* Free boxes' arrays */

	struct

	{

		Bool box_is_free[MAX_BOXES]; /* This is only used in 'free' */

		int box[MAX_BOXES];

		int n;

	} free,			/* List of all boxes free-to-move */

		new_free,	/* List of boxes for the next loop (code) */

		tfree;	/* List of boxes of the loop (code) */

	struct Position tpos;

	Bool is_not_set_free;

	/* Initialize to 0 the dependency structures */

	memset((void *) &dep, 0, sizeof(dep));

	for(i=0; i<m->NumBoxes; i++)

	{

		new_free.box[i] = FALSE;

	}

	/* Let's fill the structure */

	for(i=0; i<m->NumBoxes; i++)

	{

		/* See if the box is blocked. That could be

		   done in fill_deps */

		if (m->box_deps[i].dep_dir[0] == BLOCKED &&

			m->box_deps[i].dep_dir[1] == BLOCKED &&

			m->box_deps[i].dep_dir[2] == BLOCKED &&

			m->box_deps[i].dep_dir[3] == BLOCKED )

		{

			if (m->Cells[m->Box[i].y][m->Box[i].x] !=

				PLATFORM)

				return TRUE;

			/* This is not used actually 

			else

				m->boxes[m->Box[i].y][m->Box[i].x] =

					WALL;

			*/

		}

		/* Let's take note of the dependencies */

		is_not_set_free = TRUE;

		for(d=0; d<4; d++)

		{

			if(m->box_deps[i].dep_dir[d] > 0)

			{

				dep.box[i][m->box_deps[i].dep_dir[d]] =

					TRUE;

				dep.ndeps[i]++;

			} else

			if(m->box_deps[i].dep_dir[d] == FREE)

			{

				if (is_not_set_free)

				{

					new_free.box[new_free.n++] = i;

					is_not_set_free = FALSE;

				}

			}

		}

	}

	/* Let's analyze if the free boxes can really be moved, and

	   set them as dependant, if they're dependant.

	   If some can be really moved, we should know _where to_. */

	/* Paint MANCANMOVE at each cell the man can reach */

	paint_mancanmove(m);

	/* For each free movable box, let's see if the man can reach them

	   fine. If we can, add it to the possible movements. */

	*num_movements=0;

	for(i=0; i<new_free.n; i++)

	{

		/* For each direction, try if the box can be moved */

		for(d=0; d<4; d++)

		{

			if(m->box_deps[i].dep_dir[d] == FREE)

			{

				add_position3(tpos, m->Box[i], move_vectors[OPPOSITE_DIR(d)])

				if (m->man_moves[tpos.y][tpos.x] == MANCANMOVE)

				{

					movements[*num_movements].box = i;

					movements[*num_movements].dir =

						move_vectors[d];

					(*num_movements)++;

				}

				/* ELSE - we should catch those cases,

				where free boxes cannot be moved. Will they

				ever be movable? 

				THIS HAS TO BE IMPROVED */

			}

		}

	}

	/* ---------------- The next possible movements have been calculated --

	We can still find that this map is illegal. We need to find

	further more if there are boxes unmovable (due to dependencies) */

	/* Let's take out all dependencies from 'free' boxes */

	/* Prepare the 'free' list */

	for(i=0; i<m->NumBoxes;i++)

		free.box_is_free[i] = FALSE;

	free.n = new_free.n;

	for(i=0; i<new_free.n; i++)

	{

		free.box[i] = new_free.box[i];

		free.box_is_free[i] = TRUE;

	}

	/* KACXO-loop  */

	while (new_free.n > 0)

	{

		/* Copy new_free into free */

		tfree.n = new_free.n;

		for(i=0; i<new_free.n; i++)

			tfree.box[i] = new_free.box[i];

		new_free.n = 0;

		for(i=0; i<tfree.n; i++)

		{

			for(j=0; j<m->NumBoxes; j++)

			{

				/* The box j no more depends on

				   the box tfree[i] */

				if(dep.box[j][tfree.box[i]])

				{

					dep.box[j][tfree.box[i]] = FALSE;

					dep.ndeps[j]--;

					assert(dep.ndeps[j] >= 0);

					if (dep.ndeps[j] == 0 &&

						!free.box_is_free[i])

					{

						new_free.box[new_free.n++]=j;

						free.box[free.n++]=j;

					}

				}

			}

		}

	}

	/* Now are left only boxes which depend on others-non-free */

	for(i=0; i<m->NumBoxes; i++)

	{

		for(j=0; j<m->NumBoxes; j++)

		{

			/* We only do one-level search !!! */

			/* If the box only depends on another,

			   which also only depends on this... */

			if (dep.box[i][j] && dep.ndeps[i] == 1

				&& dep.box[j][i] && dep.ndeps[j] == 1)