1 #include <assert.h>

     2 #include <string.h>

     3 #include "general.h"

     4 

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

     6 extern float percent_to_show;

     7 extern int depth_to_show;

     8 

     9 extern int max_depth;

    10 extern int min_depth_period;

    11 extern int max_depth_period;

    12 extern struct Map * actual_map;

    13 

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

    15  Situation:

    16     

    17   ->@$ #

    18       $

    19 */

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

    21 	const struct Position box_pos)

    22 {

    23 	struct Position next_pos2, tmp, tmp2[2];

    24 	int i;

    25 

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

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

    28 

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

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

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

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

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

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

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

    36 	{

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

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

    39 		{

    40 			return TRUE;

    41 		}

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

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

    44 		{

    45 			return TRUE;

    46 		}

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

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

    49 		{

    50 			return TRUE;

    51 		}

    52 	}

    53 

    54 	return FALSE;

    55 }

    56 

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

    58 	const struct Position box, const struct Position new_box)

    59 {

    60 	int NumMoves, NewMoves;

    61 	struct Position pos[MAX_MOVES];

    62 	struct Position new_pos[MAX_MOVES];

    63 	char corners[MAX_Y][MAX_X];

    64 	int i,j;

    65 	struct Position next_pos;

    66 	char *next_cell;

    67 

    68 

    69 	/* Blank the garden */

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

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

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

    73 

    74 	/* Let's put the boxes */

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

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

    77 

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

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

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

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

    82 

    83 	NewMoves = 1;

    84 	new_pos[0] = p;

    85 	while (NewMoves > 0)

    86 	{

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

    88 		   to analyze */

    89 		NumMoves = NewMoves;

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

    91 		{

    92 			pos[i] = new_pos[i];

    93 		}

    94 

    95 		/* Search new positions for each position */

    96 		NewMoves = 0;

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

    98 		{

    99 			/* For each direction */

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

   101 			{

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

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

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

   105 				if(*next_cell == BLANK ||

   106 					*next_cell == PLATFORM)

   107 				{

   108 					return FALSE;

   109 				}

   110 				else if(*next_cell == CORNER)

   111 				{

   112 					new_pos[NewMoves] = next_pos;

   113 					*next_cell = MANCANMOVE;

   114 					NewMoves++;

   115 				}

   116 			}

   117 		}

   118 	}

   119 

   120 	return TRUE;

   121 }

   122 

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

   124 	const struct Position box_pos)

   125 {

   126 	struct Position p, p2;

   127 

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

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

   130 	

   131 	/* Let's plan the checks */

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

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

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

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

   136 	{

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

   138 			return TRUE;

   139 	}

   140 

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

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

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

   144 	{

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

   146 			return TRUE;

   147 	}

   148 

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

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

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

   152 	{

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

   154 			return TRUE;

   155 	}

   156 	return FALSE;

   157 }

   158 #endif

   159 

   160 /*

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

   162 next to it will not be able to be moved.

   163 */

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

   165 	const struct Position new_pos)

   166 {

   167 	struct Position opposite1, opposite2;

   168 

   169 	/* The wall corners must exist */

   170 	opposite1.x = -mov.y;

   171 	opposite1.y = -mov.x;

   172 	opposite2.x = mov.y;

   173 	opposite2.y = mov.x;

   174 

   175 #ifdef DEBUG

   176 	ShowMap(m);

   177 #endif

   178 

   179 	/* Test the first corner */

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

   181 		== WALL)

   182 	{

   183 		/* Test wall at opposites 1*/

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

   185 			== WALL &&

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

   187 		{

   188 				return TRUE;

   189 		}

   190 		else

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

   192 			== BOX &&

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

   194 		{

   195 				return TRUE;

   196 		}

   197 		/* Test wall at opposites 2 */

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

   199 			== WALL &&

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

   201 		{

   202 				return TRUE;

   203 		}

   204 		else

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

   206 			== BOX &&

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

   208 		{

   209 				return TRUE;

   210 		}

   211 	}

   212 

   213 	/* Test the second corner */

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

   215 		== WALL)

   216 	{

   217 		/* Test wall at opposites 1*/

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

   219 			== WALL &&

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

   221 		{

   222 				return TRUE;

   223 		}

   224 		else

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

   226 			== BOX &&

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

   228 		{

   229 				return TRUE;

   230 		}

   231 		/* Test wall at opposites 2 */

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

   233 			== WALL &&

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

   235 		{

   236 				return TRUE;

   237 		}

   238 		else

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

   240 			== BOX &&

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

   242 		{

   243 				return TRUE;

   244 		}

   245 	}

   246 

   247 	return FALSE;

   248 }

   249 

   250 /*

   251 Catch the situation where a corner gets surrounded by boxes.

   252 */

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

   254 	const struct Position new_pos)

   255 {

   256 	struct Position next, opposite1, opposite2;

   257 

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

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

   260 

   261 	/* The corner must exist */

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

   263 		return FALSE;

   264 

   265 

   266 	/* The wall corners must exist */

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

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

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

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

   271 

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

   273 	{

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

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

   276 		   return TRUE;

   277 	}

   278 

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

   280 	{

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

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

   283 		   return TRUE;

   284 	}

   285 	return FALSE;

   286 }

   287 

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

   289 	const struct Position box_pos)

   290 {

   291 	struct Position next_pos2;

   292 

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

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

   295 

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

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

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

   299 	{

   300 		return FALSE;

   301 	}

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

   303 	{

   304 		return FALSE;

   305 	}

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

   307 	{

   308 		return FALSE;

   309 	}

   310 	return TRUE;

   311 }

   312 

   313 /* It modifies m->man_moves */

   314 static int get_box_movements(struct Map * m,

   315 	struct BoxMove movements[])

   316 {

   317 	struct Position pos[MAX_MOVES];

   318 	struct Position new_pos[MAX_MOVES];

   319 	int NumMoves, NewMoves;

   320 	int j, i;

   321 	struct Position next_pos;

   322 	char *next_cell;

   323 	int num_box_movements = 0;

   324 	

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

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

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

   328 		{

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

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

   331 			else

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

   333 		}

   334 

   335 	/* Let's put the boxes */

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

   337 	{

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

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

   340 	}

   341 

   342 	NewMoves = 1;

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

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

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

   346 	while (NewMoves > 0)

   347 	{

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

   349 		   to analyze */

   350 		NumMoves = NewMoves;

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

   352 		{

   353 			pos[i] = new_pos[i];

   354 		}

   355 

   356 		/* Search new positions for each position */

   357 		NewMoves = 0;

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

   359 		{

   360 			/* For each direction */

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

   362 			{

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

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

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

   366 				if(*next_cell == BLANK)

   367 				{

   368 					new_pos[NewMoves] = next_pos;

   369 					*next_cell = MANCANMOVE;

   370 					NewMoves++;

   371 				}

   372 				else if (*next_cell == BOX)

   373 				{

   374 						

   375 					/* Check if the box is movable */

   376 

   377 					if (is_box_movable(m, move_vectors[j],

   378 						next_pos ))

   379 					{

   380 						{

   381 					movements[num_box_movements].box =

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

   383 					movements[num_box_movements].dir =

   384 					move_vectors[j];

   385 					num_box_movements++;

   386 						}

   387 					}

   388 					

   389 				}

   390 

   391 			}

   392 		}

   393 	}

   394 

   395 	return num_box_movements;

   396 }

   397 

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

   399 {

   400 	struct Position newpos;

   401 

   402 

   403 	/* Add coords */

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

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

   406 

   407 	/* Be certain the move can be done */

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

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

   410 

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

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

   413 	{

   414 		m->NumBoxesInPlatform++;

   415 	}

   416 

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

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

   419 	{

   420 		m->NumBoxesInPlatform--;

   421 	}

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

   423 

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

   425 }

   426 

   427 static int is_new_map(struct Map maps[], int depth)

   428 {

   429 	struct Map *m;

   430 	int i;

   431 

   432 	m = &maps[depth];

   433 

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

   435 	{

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

   437 		if (i == depth)

   438 			continue;

   439 

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

   441 			continue;

   442 		else

   443 		{

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

   445 				continue;

   446 		}

   447 		return FALSE;

   448 	}

   449 	return TRUE;

   450 }

   451 

   452 

   453 static int search_depth(struct Map maps[], int depth,

   454 	struct BoxMove movements[],

   455 	int num_movements, float percent, float total_percent)

   456 {

   457 	struct BoxMove new_movements[MAX_MOVES];

   458 	int num_new_movements;

   459 	struct Map *m; 

   460 	int i;

   461 	float next_percent;

   462 

   463 	next_percent = percent / num_movements;

   464 

   465 	m = &maps[depth+1];

   466 	if (depth > max_depth)

   467 		max_depth = depth;

   468 	if (depth > max_depth_period)

   469 		max_depth_period = depth;

   470 	if (depth < min_depth_period)

   471 		min_depth_period = depth;

   472 

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

   474 	{

   475 		CopyMap(m, &maps[depth]);

   476 		force_move_box(m, movements[i]);

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

   478 		{

   479 			PrintMove(movements[i]);

   480 			return 0;

   481 		}

   482 

   483 		if (is_new_map(maps, depth+1))

   484 		{

   485 			num_new_movements = get_box_movements(m, new_movements);

   486 			assert(num_new_movements < MAX_MOVES);

   487 		}

   488 		else

   489 			num_new_movements = 0;

   490 

   491 		if (num_new_movements == 0)

   492 		{

   493 			percent_to_show = total_percent + next_percent*i;

   494 			depth_to_show = depth;

   495 			actual_map = &maps[depth];

   496 #ifdef DEBUG		/* to be out */

   497 			show_percent_callback(0);

   498 #endif

   499 	

   500 		}

   501 		else

   502 		{

   503 			if (depth+1 < MAX_STEPS)

   504 			{

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

   506 					num_new_movements, next_percent,

   507 					total_percent + next_percent*i) == 0)

   508 				{

   509 					PrintMove(movements[i]);

   510 					return 0;

   511 				}

   512 			}

   513 		}

   514 	}

   515 	return 1;

   516 }

   517 

   518 

   519 int solve_map(const struct Map origin)

   520 {

   521 	struct Map maps[MAX_STEPS+1];

   522 	struct BoxMove new_movements[MAX_MOVES];

   523 	int num_new_movements;

   524 

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

   526 

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

   528 	assert(num_new_movements < MAX_MOVES);

   529 	assert(num_new_movements > 0);

   530 

   531 	init_os();

   532 

   533 	return search_depth(maps, 0, new_movements,

   534 		num_new_movements, 100. / num_new_movements,

   535 		0);

   536 

   537 }