#include <assert.h>

#include <string.h>

#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;

#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

/*

Catch the situation where a box is moved next to a corner, where the box

next to it will not be able to be moved.

*/

static int is_dead1(const struct Map * m, const struct Position mov,

	const struct Position new_pos)

{

	struct Position opposite1, opposite2;

	/* The wall corners must exist */

	opposite1.x = -mov.y;

	opposite1.y = -mov.x;

	opposite2.x = mov.y;

	opposite2.y = mov.x;

#ifdef DEBUG

	ShowMap(m);

#endif

	/* Test the first corner */

	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]

		== WALL)

	{

		/* Test wall at opposites 1*/

		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

		/* Test wall at opposites 2 */

		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

	}

	/* Test the second corner */

	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]

		== WALL)

	{

		/* Test wall at opposites 1*/

		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

		/* Test wall at opposites 2 */

		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

	}

	return FALSE;

}

/*

Catch the situation where a corner gets surrounded by boxes.

*/

static int is_dead2(const struct Map * m, const struct Position mov,

	const struct Position new_pos)

{

	struct Position next, opposite1, opposite2;

	next.x = new_pos.x+mov.x;

	next.y = new_pos.y+mov.y;

	/* The corner must exist */

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

		return FALSE;

	/* The wall corners must exist */

	opposite1.x = next.x -mov.y;

	opposite1.y = next.y -mov.x;

	opposite2.x = next.x + mov.y;

	opposite2.y = next.y + mov.x;

	if (m->man_moves[opposite1.y][opposite1.x] == BOX)

	{

		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL

		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)

		   return TRUE;

	}

	if (m->man_moves[opposite2.y][opposite2.x] == BOX)

	{

		if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL

		   && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)

		   return TRUE;

	}

	return FALSE;

}

static int is_box_movable(const struct Map * m, const struct Position mov,

	const struct Position box_pos)

{

	struct Position next_pos2;

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

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

	if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&

		m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||

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

	{

		return FALSE;

	}

	else if (is_dead1(m, mov, next_pos2) == TRUE)

	{

		return FALSE;

	}

	else if (is_dead2(m, mov, next_pos2) == TRUE)

	{

		return FALSE;

	}

	return TRUE;

}

/* It modifies m->man_moves */

static int get_box_movements(struct Map * m,

	struct BoxMove movements[])

{

	struct Position pos[MAX_MOVES];

	struct Position new_pos[MAX_MOVES];

	int NumMoves, NewMoves;

	int j, i;

	struct Position next_pos;

	char *next_cell;

	int num_box_movements = 0;

	/* 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] = BOX;

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

	}

	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++;

				}

				else if (*next_cell == BOX)

				{

					/* Check if the box is movable */

					if (is_box_movable(m, move_vectors[j],

						next_pos ))

					{

						{

					movements[num_box_movements].box =

					m->cells_boxes[next_pos.y][next_pos.x];

					movements[num_box_movements].dir =

					move_vectors[j];

					num_box_movements++;

						}

					}

				}

			}

		}

	}

	return num_box_movements;

}

static void force_move_box(struct Map *m, 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 int is_new_map(struct Map maps[], int depth)

{

	struct Map *m;

	int i;

	m = &maps[depth];

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

	{

		/* No l'hem de comparar amb ell mateix */

		if (i == depth)

			continue;

		if (m->NumBoxesInPlatform != maps[i].NumBoxesInPlatform)

			continue;

		else

		{

			if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes))

				continue;

		}

		return FALSE;

	}

	return TRUE;

}

static int search_depth(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]);

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

		{

			PrintMove(movements[i]);

			return 0;

		}

		if (is_new_map(maps, depth+1))

		{

			num_new_movements = get_box_movements(m, 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;

			actual_map = &maps[depth];

#ifdef DEBUG		/* to be out */

			show_percent_callback(0);

#endif

		}

		else

		{

			if (depth+1 < MAX_STEPS)

			{

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

					num_new_movements, next_percent,

					total_percent + next_percent*i) == 0)

				{

					PrintMove(movements[i]);

					return 0;

				}

			}

		}

	}

	return 1;

}

int solve_map(const struct Map origin)

{

	struct Map maps[MAX_STEPS+1];

	struct BoxMove new_movements[MAX_MOVES];

	int num_new_movements;

	CopyMap(&maps[0], &origin);

	num_new_movements = get_box_movements(&maps[0], new_movements);

	assert(num_new_movements < MAX_MOVES);