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