algorithm.c
author viric@llimona
Sat, 17 Feb 2007 15:14:30 +0100
changeset 28 cd27cb410375
parent 26 95fccfcbd04c
permissions -rw-r--r--
Recursivity changed into a loop. Now the state is loaded on boot, and saved on TERM.
viric@6
     1
#include <assert.h>
viric@6
     2
#include <string.h>
viric@28
     3
#include <stdlib.h>
viric@6
     4
#include "general.h"
viric@6
     5
viric@6
     6
/* Variables related to the showing of information by os */
viric@6
     7
extern float percent_to_show;
viric@6
     8
extern int depth_to_show;
viric@6
     9
viric@6
    10
extern int max_depth;
viric@6
    11
extern int min_depth_period;
viric@6
    12
extern int max_depth_period;
viric@6
    13
extern struct Map * actual_map;
viric@6
    14
viric@6
    15
#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/
viric@6
    16
 Situation:
viric@6
    17
    
viric@6
    18
  ->@$ #
viric@6
    19
      $
viric@6
    20
*/
viric@6
    21
int box_will_be_blocked(const struct Map * m, const struct Position mov,
viric@6
    22
	const struct Position box_pos)
viric@6
    23
{
viric@6
    24
	struct Position next_pos2, tmp, tmp2[2];
viric@6
    25
	int i;
viric@6
    26
viric@6
    27
	next_pos2.x = box_pos.x + mov.x;
viric@6
    28
	next_pos2.y = box_pos.y + mov.y;
viric@6
    29
viric@6
    30
	tmp.x = next_pos2.x + mov.x;
viric@6
    31
	tmp.y = next_pos2.y + mov.y;
viric@6
    32
	tmp2[0].x = next_pos2.x + mov.y;
viric@6
    33
	tmp2[0].y = next_pos2.y + mov.x;
viric@6
    34
	tmp2[1].x = next_pos2.x - mov.y;
viric@6
    35
	tmp2[1].y = next_pos2.y - mov.x;
viric@6
    36
	for (i=0; i < 2; i++)
viric@6
    37
	{
viric@6
    38
		if (m->man_moves[tmp.y][tmp.x] == WALL &&
viric@6
    39
			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
viric@6
    40
		{
viric@6
    41
			return TRUE;
viric@6
    42
		}
viric@6
    43
		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
viric@6
    44
			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)
viric@6
    45
		{
viric@6
    46
			return TRUE;
viric@6
    47
		}
viric@6
    48
		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
viric@6
    49
			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
viric@6
    50
		{
viric@6
    51
			return TRUE;
viric@6
    52
		}
viric@6
    53
	}
viric@6
    54
viric@6
    55
	return FALSE;
viric@6
    56
}
viric@6
    57
viric@6
    58
int is_corner_area(const struct Map * m, const struct Position p,
viric@6
    59
	const struct Position box, const struct Position new_box)
viric@6
    60
{
viric@6
    61
	int NumMoves, NewMoves;
viric@6
    62
	struct Position pos[MAX_MOVES];
viric@6
    63
	struct Position new_pos[MAX_MOVES];
viric@6
    64
	char corners[MAX_Y][MAX_X];
viric@6
    65
	int i,j;
viric@6
    66
	struct Position next_pos;
viric@6
    67
	char *next_cell;
viric@6
    68
viric@6
    69
viric@6
    70
	/* Blank the garden */
viric@6
    71
	for (j = 0; j<m->SizeY; j++)
viric@6
    72
		for (i=0; i<m->SizeX; i++)
viric@6
    73
			corners[j][i] = m->Cells[j][i];
viric@6
    74
viric@6
    75
	/* Let's put the boxes */
viric@6
    76
	for (i = 0; i<m->NumBoxes; i++)
viric@6
    77
		corners[m->Box[i].y][m->Box[i].x] = BOX;
viric@6
    78
viric@6
    79
	/* Let's put our box - it can be simply added */
viric@6
    80
	corners[new_box.y][new_box.x] = BOX;
viric@6
    81
	/* Let's remove the original box. */
viric@6
    82
	corners[box.y][box.x] = BLANK;
viric@6
    83
viric@6
    84
	NewMoves = 1;
viric@6
    85
	new_pos[0] = p;
viric@6
    86
	while (NewMoves > 0)
viric@6
    87
	{
viric@6
    88
		/* The before named "New Moves" become the moves we have
viric@6
    89
		   to analyze */
viric@6
    90
		NumMoves = NewMoves;
viric@6
    91
		for (i=0; i<NewMoves; i++)
viric@6
    92
		{
viric@6
    93
			pos[i] = new_pos[i];
viric@6
    94
		}
viric@6
    95
viric@6
    96
		/* Search new positions for each position */
viric@6
    97
		NewMoves = 0;
viric@6
    98
		for (i=0; i<NumMoves; i++)
viric@6
    99
		{
viric@6
   100
			/* For each direction */
viric@6
   101
			for (j=0; j<4; j++)
viric@6
   102
			{
viric@6
   103
				next_pos.x = pos[i].x + move_vectors[j].x;
viric@6
   104
				next_pos.y = pos[i].y + move_vectors[j].y;
viric@6
   105
				next_cell = &corners[next_pos.y][next_pos.x];
viric@6
   106
				if(*next_cell == BLANK ||
viric@6
   107
					*next_cell == PLATFORM)
viric@6
   108
				{
viric@6
   109
					return FALSE;
viric@6
   110
				}
viric@6
   111
				else if(*next_cell == CORNER)
viric@6
   112
				{
viric@6
   113
					new_pos[NewMoves] = next_pos;
viric@6
   114
					*next_cell = MANCANMOVE;
viric@6
   115
					NewMoves++;
viric@6
   116
				}
viric@6
   117
			}
viric@6
   118
		}
viric@6
   119
	}
viric@6
   120
viric@6
   121
	return TRUE;
viric@6
   122
}
viric@6
   123
viric@6
   124
int does_box_close_corners(const struct Map * m, const struct Position mov,
viric@6
   125
	const struct Position box_pos)
viric@6
   126
{
viric@6
   127
	struct Position p, p2;
viric@6
   128
viric@6
   129
	p.x = box_pos.x + mov.x;
viric@6
   130
	p.y = box_pos.y + mov.y;
viric@6
   131
	
viric@6
   132
	/* Let's plan the checks */
viric@6
   133
	/* The point will be marked with a MANCANMOVE */
viric@6
   134
	p2.x = p.x + mov.x;
viric@6
   135
	p2.y = p.y + mov.y;
viric@6
   136
	if (m->Cells[p2.y][p2.x] == CORNER)
viric@6
   137
	{
viric@6
   138
		if (is_corner_area(m, p2, box_pos, p))
viric@6
   139
			return TRUE;
viric@6
   140
	}
viric@6
   141
viric@6
   142
	p2.x = p.x + mov.y;
viric@6
   143
	p2.y = p.y + mov.x;
viric@6
   144
	if (m->Cells[p2.y][p2.x] == CORNER)
viric@6
   145
	{
viric@6
   146
		if (is_corner_area(m, p2, box_pos, p))
viric@6
   147
			return TRUE;
viric@6
   148
	}
viric@6
   149
viric@6
   150
	p2.x = p.x - mov.y;
viric@6
   151
	p2.y = p.y - mov.x;
viric@6
   152
	if (m->Cells[p2.y][p2.x] == CORNER)
viric@6
   153
	{
viric@6
   154
		if (is_corner_area(m, p2, box_pos, p))
viric@6
   155
			return TRUE;
viric@6
   156
	}
viric@6
   157
	return FALSE;
viric@6
   158
}
viric@6
   159
#endif
viric@6
   160
viric@6
   161
/*
viric@6
   162
Catch the situation where a box is moved next to a corner, where the box
viric@6
   163
next to it will not be able to be moved.
viric@6
   164
*/
viric@6
   165
static int is_dead1(const struct Map * m, const struct Position mov,
viric@6
   166
	const struct Position new_pos)
viric@6
   167
{
viric@6
   168
	struct Position opposite1, opposite2;
viric@6
   169
viric@6
   170
	/* The wall corners must exist */
viric@6
   171
	opposite1.x = -mov.y;
viric@6
   172
	opposite1.y = -mov.x;
viric@6
   173
	opposite2.x = mov.y;
viric@6
   174
	opposite2.y = mov.x;
viric@6
   175
viric@6
   176
#ifdef DEBUG
viric@6
   177
	ShowMap(m);
viric@6
   178
#endif
viric@6
   179
viric@6
   180
	/* Test the first corner */
viric@6
   181
	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]
viric@6
   182
		== WALL)
viric@6
   183
	{
viric@6
   184
		/* Test wall at opposites 1*/
viric@6
   185
		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
viric@6
   186
			== WALL &&
viric@6
   187
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
viric@6
   188
		{
viric@6
   189
				return TRUE;
viric@6
   190
		}
viric@6
   191
		else
viric@6
   192
		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
viric@6
   193
			== BOX &&
viric@6
   194
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
viric@6
   195
		{
viric@6
   196
				return TRUE;
viric@6
   197
		}
viric@6
   198
		/* Test wall at opposites 2 */
viric@6
   199
		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
viric@6
   200
			== WALL &&
viric@6
   201
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
viric@6
   202
		{
viric@6
   203
				return TRUE;
viric@6
   204
		}
viric@6
   205
		else
viric@6
   206
		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
viric@6
   207
			== BOX &&
viric@6
   208
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
viric@6
   209
		{
viric@6
   210
				return TRUE;
viric@6
   211
		}
viric@6
   212
	}
viric@6
   213
viric@6
   214
	/* Test the second corner */
viric@6
   215
	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]
viric@6
   216
		== WALL)
viric@6
   217
	{
viric@6
   218
		/* Test wall at opposites 1*/
viric@6
   219
		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
viric@6
   220
			== WALL &&
viric@6
   221
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
viric@6
   222
		{
viric@6
   223
				return TRUE;
viric@6
   224
		}
viric@6
   225
		else
viric@6
   226
		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
viric@6
   227
			== BOX &&
viric@6
   228
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
viric@6
   229
		{
viric@6
   230
				return TRUE;
viric@6
   231
		}
viric@6
   232
		/* Test wall at opposites 2 */
viric@6
   233
		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
viric@6
   234
			== WALL &&
viric@6
   235
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
viric@6
   236
		{
viric@6
   237
				return TRUE;
viric@6
   238
		}
viric@6
   239
		else
viric@6
   240
		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
viric@6
   241
			== BOX &&
viric@6
   242
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
viric@6
   243
		{
viric@6
   244
				return TRUE;
viric@6
   245
		}
viric@6
   246
	}
viric@6
   247
viric@6
   248
	return FALSE;
viric@6
   249
}
viric@6
   250
viric@6
   251
/*
viric@6
   252
Catch the situation where a corner gets surrounded by boxes.
viric@6
   253
*/
viric@6
   254
static int is_dead2(const struct Map * m, const struct Position mov,
viric@6
   255
	const struct Position new_pos)
viric@6
   256
{
viric@6
   257
	struct Position next, opposite1, opposite2;
viric@6
   258
viric@6
   259
	next.x = new_pos.x+mov.x;
viric@6
   260
	next.y = new_pos.y+mov.y;
viric@6
   261
viric@6
   262
	/* The corner must exist */
viric@6
   263
	if (m->Cells[next.y][next.x] != CORNER)
viric@6
   264
		return FALSE;
viric@6
   265
viric@6
   266
viric@6
   267
	/* The wall corners must exist */
viric@6
   268
	opposite1.x = next.x -mov.y;
viric@6
   269
	opposite1.y = next.y -mov.x;
viric@6
   270
	opposite2.x = next.x + mov.y;
viric@6
   271
	opposite2.y = next.y + mov.x;
viric@6
   272
viric@6
   273
	if (m->man_moves[opposite1.y][opposite1.x] == BOX)
viric@6
   274
	{
viric@6
   275
		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL
viric@6
   276
		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)
viric@6
   277
		   return TRUE;
viric@6
   278
	}
viric@6
   279
viric@6
   280
	if (m->man_moves[opposite2.y][opposite2.x] == BOX)
viric@6
   281
	{
viric@6
   282
		if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL
viric@6
   283
		   && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)
viric@6
   284
		   return TRUE;
viric@6
   285
	}
viric@6
   286
	return FALSE;
viric@6
   287
}
viric@6
   288
viric@6
   289
static int is_box_movable(const struct Map * m, const struct Position mov,
viric@6
   290
	const struct Position box_pos)
viric@6
   291
{
viric@6
   292
	struct Position next_pos2;
viric@6
   293
viric@6
   294
	next_pos2.x = box_pos.x + mov.x;
viric@6
   295
	next_pos2.y = box_pos.y + mov.y;
viric@6
   296
viric@6
   297
	if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&
viric@6
   298
		m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||
viric@6
   299
		m->man_moves[next_pos2.y][next_pos2.x] == BOX)
viric@6
   300
	{
viric@6
   301
		return FALSE;
viric@6
   302
	}
viric@6
   303
	else if (is_dead1(m, mov, next_pos2) == TRUE)
viric@6
   304
	{
viric@6
   305
		return FALSE;
viric@6
   306
	}
viric@6
   307
	else if (is_dead2(m, mov, next_pos2) == TRUE)
viric@6
   308
	{
viric@6
   309
		return FALSE;
viric@6
   310
	}
viric@6
   311
	return TRUE;
viric@6
   312
}
viric@6
   313
viric@6
   314
/* It modifies m->man_moves */
viric@6
   315
static int get_box_movements(struct Map * m,
viric@6
   316
	struct BoxMove movements[])
viric@6
   317
{
viric@6
   318
	struct Position pos[MAX_MOVES];
viric@6
   319
	struct Position new_pos[MAX_MOVES];
viric@6
   320
	int NumMoves, NewMoves;
viric@6
   321
	int j, i;
viric@6
   322
	struct Position next_pos;
viric@6
   323
	char *next_cell;
viric@6
   324
	int num_box_movements = 0;
viric@6
   325
	
viric@6
   326
	/* Let's  the map with only walls in man_moves - other, blanks */
viric@6
   327
	for (j = 0; j<m->SizeY; j++)
viric@6
   328
		for (i=0; i<m->SizeX; i++)
viric@6
   329
		{
viric@6
   330
			if (m->Cells[j][i] == WALL)
viric@6
   331
				m->man_moves[j][i] = WALL;
viric@6
   332
			else
viric@6
   333
				m->man_moves[j][i] = BLANK;
viric@6
   334
		}
viric@6
   335
viric@6
   336
	/* Let's put the boxes */
viric@6
   337
	for (i = 0; i<m->NumBoxes; i++)
viric@6
   338
	{
viric@6
   339
		m->man_moves[m->Box[i].y][m->Box[i].x] = BOX;
viric@6
   340
		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
viric@6
   341
	}
viric@6
   342
viric@6
   343
	NewMoves = 1;
viric@6
   344
	new_pos[0].x = m->Man.x;
viric@6
   345
	new_pos[0].y = m->Man.y;
viric@6
   346
	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;
viric@6
   347
	while (NewMoves > 0)
viric@6
   348
	{
viric@6
   349
		/* The before named "New Moves" become the moves we have
viric@6
   350
		   to analyze */
viric@6
   351
		NumMoves = NewMoves;
viric@6
   352
		for (i=0; i<NewMoves; i++)
viric@6
   353
		{
viric@6
   354
			pos[i] = new_pos[i];
viric@6
   355
		}
viric@6
   356
viric@6
   357
		/* Search new positions for each position */
viric@6
   358
		NewMoves = 0;
viric@6
   359
		for (i=0; i<NumMoves; i++)
viric@6
   360
		{
viric@6
   361
			/* For each direction */
viric@6
   362
			for (j=0; j<4; j++)
viric@6
   363
			{
viric@6
   364
				next_pos.x = pos[i].x + move_vectors[j].x;
viric@6
   365
				next_pos.y = pos[i].y + move_vectors[j].y;
viric@6
   366
				next_cell = &m->man_moves[next_pos.y][next_pos.x];
viric@6
   367
				if(*next_cell == BLANK)
viric@6
   368
				{
viric@6
   369
					new_pos[NewMoves] = next_pos;
viric@6
   370
					*next_cell = MANCANMOVE;
viric@6
   371
					NewMoves++;
viric@6
   372
				}
viric@6
   373
				else if (*next_cell == BOX)
viric@6
   374
				{
viric@6
   375
						
viric@6
   376
					/* Check if the box is movable */
viric@6
   377
viric@6
   378
					if (is_box_movable(m, move_vectors[j],
viric@6
   379
						next_pos ))
viric@6
   380
					{
viric@6
   381
						{
viric@6
   382
					movements[num_box_movements].box =
viric@6
   383
					m->cells_boxes[next_pos.y][next_pos.x];
viric@6
   384
					movements[num_box_movements].dir =
viric@6
   385
					move_vectors[j];
viric@6
   386
					num_box_movements++;
viric@6
   387
						}
viric@6
   388
					}
viric@6
   389
					
viric@6
   390
				}
viric@6
   391
viric@6
   392
			}
viric@6
   393
		}
viric@6
   394
	}
viric@6
   395
viric@6
   396
	return num_box_movements;
viric@6
   397
}
viric@6
   398
viric@10
   399
static void force_move_box(struct Map *m, const struct BoxMove move)
viric@6
   400
{
viric@6
   401
	struct Position newpos;
viric@6
   402
viric@6
   403
viric@6
   404
	/* Add coords */
viric@6
   405
	newpos.x = m->Box[move.box].x + move.dir.x;
viric@6
   406
	newpos.y = m->Box[move.box].y + move.dir.y;
viric@6
   407
viric@6
   408
	/* Be certain the move can be done */
viric@6
   409
	assert(m->Cells[newpos.y][newpos.x] != BOX);
viric@6
   410
	assert(m->Cells[newpos.y][newpos.x] != WALL);
viric@6
   411
viric@6
   412
	/* Control if we moved the box to a platform */
viric@6
   413
	if(m->Cells[newpos.y][newpos.x] == PLATFORM)
viric@6
   414
	{
viric@6
   415
		m->NumBoxesInPlatform++;
viric@6
   416
	}
viric@6
   417
viric@6
   418
	/* Control if we moved the box from a platform */
viric@6
   419
	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
viric@6
   420
	{
viric@6
   421
		m->NumBoxesInPlatform--;
viric@6
   422
	}
viric@6
   423
	m->Man = m->Box[move.box];
viric@6
   424
viric@6
   425
	m->Box[move.box] = newpos;
viric@6
   426
}
viric@6
   427
viric@6
   428
viric@28
   429
static void update_depth_counters(const int depth)
viric@6
   430
{
viric@6
   431
	if (depth > max_depth)
viric@6
   432
		max_depth = depth;
viric@6
   433
	if (depth > max_depth_period)
viric@6
   434
		max_depth_period = depth;
viric@6
   435
	if (depth < min_depth_period)
viric@6
   436
		min_depth_period = depth;
viric@28
   437
}
viric@6
   438
viric@28
   439
struct Map *all_maps;
viric@28
   440
struct BoxMove *all_movements; /* DEPTH movements of MAX_MOVES */
viric@28
   441
int *all_mov_tries; /* The actual step in movements for every depth */
viric@28
   442
int *all_mov_max; /* Maximum of movements per all_movement element */
viric@28
   443
float *percent;
viric@28
   444
float *percent_part;
viric@28
   445
int depth;
viric@28
   446
viric@28
   447
int search_loop(const struct Map *origin)
viric@28
   448
{
viric@28
   449
	int found; /* bool */
viric@28
   450
viric@28
   451
	all_maps = malloc(sizeof(*all_maps) * (MAX_STEPS+1));
viric@28
   452
	all_movements = malloc(sizeof(*all_movements)*MAX_MOVES*(MAX_STEPS+1));
viric@28
   453
	all_mov_tries = malloc(sizeof(*all_mov_tries)*(MAX_STEPS+1));
viric@28
   454
	all_mov_max = malloc(sizeof(*all_mov_max)*(MAX_STEPS+1));
viric@28
   455
	percent = malloc(sizeof(*percent)*(MAX_STEPS+1));
viric@28
   456
	percent_part = malloc(sizeof(*percent)*(MAX_STEPS+1));
viric@28
   457
viric@28
   458
viric@28
   459
	if (load_state())
viric@6
   460
	{
viric@28
   461
		--depth;
viric@28
   462
		if (all_mov_tries[depth] != 0)
viric@28
   463
			all_mov_tries[depth] = 0;
viric@28
   464
	} else
viric@28
   465
	{
viric@28
   466
		depth = 0;
viric@28
   467
		CopyMap(&all_maps[0], origin);
viric@28
   468
		all_mov_max[0] = get_box_movements(&all_maps[0], &all_movements[0]);
viric@28
   469
		assert(all_mov_max[0] < MAX_MOVES);
viric@28
   470
		assert(all_mov_max[0] > 0);
viric@28
   471
		percent[0] = 0.;
viric@28
   472
		percent_part[0] = 100.;
viric@28
   473
		all_mov_tries[0] = 0;
viric@28
   474
	}
viric@28
   475
viric@28
   476
viric@28
   477
	found = 0;
viric@28
   478
	do
viric@28
   479
	{
viric@28
   480
		struct BoxMove *new_movements = &all_movements[(depth+1)*MAX_MOVES];
viric@28
   481
		struct BoxMove *movements = &all_movements[depth*MAX_MOVES];
viric@28
   482
		int num_movements = all_mov_max[depth];
viric@28
   483
		int *num_new_movements = &all_mov_max[depth+1];
viric@28
   484
		int *step = &all_mov_tries[depth];
viric@28
   485
		struct Map *new_map = &all_maps[depth+1];
viric@28
   486
viric@28
   487
		update_depth_counters(depth);
viric@28
   488
viric@28
   489
		percent_part[depth+1] = percent_part[depth] / num_movements;
viric@28
   490
viric@28
   491
		CopyMap(new_map, &all_maps[depth]);
viric@28
   492
viric@28
   493
		/* DEBUG */
viric@28
   494
#if DEBUG
viric@28
   495
		ShowMap(new_map);
viric@28
   496
		show_tries(depth);
viric@28
   497
		printf("Nummovs[%i]: %i\n", depth, num_movements);
viric@28
   498
		printf("Step[%i]: %i\n", depth, *step);
viric@28
   499
#endif
viric@28
   500
viric@28
   501
		/* Now four things can happen:
viric@28
   502
		 * - look for depth + 1
viric@28
   503
		 * - keep looking for movements in depth
viric@28
   504
		 * - go one depth back.
viric@28
   505
		 * - solve the puzle */
viric@28
   506
viric@28
   507
		/* Go one depth back */
viric@28
   508
		if (*step >= num_movements)
viric@6
   509
		{
viric@28
   510
			--depth;
viric@28
   511
			continue;
viric@6
   512
		}
viric@6
   513
viric@28
   514
		force_move_box(new_map, movements[(*step)]);
viric@28
   515
viric@28
   516
		++(*step);
viric@28
   517
viric@28
   518
		/* Solve the puzzle */
viric@28
   519
		if (new_map->NumPlatforms == new_map->NumBoxesInPlatform)
viric@6
   520
		{
viric@28
   521
			PrintMoves(all_movements, all_mov_tries, depth+1);
viric@28
   522
			actual_map = &all_maps[depth+1];
viric@28
   523
			show_percent_and_map();
viric@28
   524
			save_state();
viric@28
   525
			found = 1;
viric@28
   526
		}
viric@28
   527
		
viric@28
   528
		if (is_new_map(all_maps, depth+1))
viric@28
   529
		{
viric@28
   530
			*num_new_movements =
viric@28
   531
				get_box_movements(new_map, new_movements);
viric@28
   532
			assert(*num_new_movements < MAX_MOVES);
viric@6
   533
		}
viric@6
   534
		else
viric@28
   535
			*num_new_movements = 0;
viric@6
   536
viric@28
   537
		percent[depth] = percent[depth] + percent_part[depth+1];
viric@28
   538
		percent_to_show = percent[depth];
viric@28
   539
viric@28
   540
		/* Keep looking for movements in depth */
viric@28
   541
		if (*num_new_movements == 0)
viric@6
   542
		{
viric@6
   543
			depth_to_show = depth;
viric@28
   544
			actual_map = &all_maps[depth];
viric@28
   545
			continue;
viric@6
   546
		}
viric@28
   547
viric@28
   548
		/* Look for depth + 1*/
viric@28
   549
		if (depth+1 < MAX_STEPS)
viric@6
   550
		{
viric@28
   551
			percent[depth+1] = percent[depth];
viric@28
   552
			all_mov_tries[depth+1] = 0;
viric@28
   553
			++depth;
viric@6
   554
		}
viric@28
   555
	} while(!found && depth >= 0);
viric@28
   556
	free(all_maps);
viric@28
   557
	free(all_movements);
viric@28
   558
	free(all_mov_tries);
viric@28
   559
	free(all_mov_max);
viric@28
   560
viric@28
   561
	return found;
viric@6
   562
}
viric@6
   563
viric@6
   564
viric@26
   565
int solve_map(const struct Map *origin)
viric@6
   566
{
viric@6
   567
	struct BoxMove new_movements[MAX_MOVES];
viric@6
   568
	int num_new_movements;
viric@26
   569
	int ret;
viric@6
   570
viric@6
   571
	init_os();
viric@6
   572
viric@28
   573
	ret = search_loop(origin);
viric@28
   574
viric@26
   575
	return ret;
viric@6
   576
}