algorithm.c
author viric@llimona
Sun, 07 May 2006 15:28:39 +0200
changeset 16 fe078fb2e8b4
parent 13 c2b272938a1f
child 17 7c1e68c17c0e
permissions -rw-r--r--
Now I think the code works. There were some indexing mistakse,
return instead of continue, etc.
viric@6
     1
#include <assert.h>
viric@6
     2
#include <string.h>
viric@12
     3
#include <stdio.h> /**********************************PROVA */
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@12
    15
/* Prototipes */
viric@12
    16
static Bool are_there_fixed_boxes(struct Map *m,
viric@12
    17
	struct BoxMove movements[MAX_MOVES], int *num_movements);
viric@12
    18
static void force_move_box(struct Map *m, const struct BoxMove move);
viric@12
    19
static Bool search_did_found(struct Map maps[], int depth,
viric@12
    20
	struct BoxMove movements[],
viric@12
    21
	int num_movements, float percent, float total_percent);
viric@12
    22
static void fill_deps(struct Map *m);
viric@12
    23
viric@6
    24
#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/
viric@6
    25
 Situation:
viric@6
    26
    
viric@6
    27
  ->@$ #
viric@6
    28
      $
viric@6
    29
*/
viric@6
    30
int box_will_be_blocked(const struct Map * m, const struct Position mov,
viric@6
    31
	const struct Position box_pos)
viric@6
    32
{
viric@6
    33
	struct Position next_pos2, tmp, tmp2[2];
viric@6
    34
	int i;
viric@6
    35
viric@6
    36
	next_pos2.x = box_pos.x + mov.x;
viric@6
    37
	next_pos2.y = box_pos.y + mov.y;
viric@6
    38
viric@6
    39
	tmp.x = next_pos2.x + mov.x;
viric@6
    40
	tmp.y = next_pos2.y + mov.y;
viric@6
    41
	tmp2[0].x = next_pos2.x + mov.y;
viric@6
    42
	tmp2[0].y = next_pos2.y + mov.x;
viric@6
    43
	tmp2[1].x = next_pos2.x - mov.y;
viric@6
    44
	tmp2[1].y = next_pos2.y - mov.x;
viric@6
    45
	for (i=0; i < 2; i++)
viric@6
    46
	{
viric@6
    47
		if (m->man_moves[tmp.y][tmp.x] == WALL &&
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
		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
viric@6
    53
			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)
viric@6
    54
		{
viric@6
    55
			return TRUE;
viric@6
    56
		}
viric@6
    57
		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
viric@6
    58
			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
viric@6
    59
		{
viric@6
    60
			return TRUE;
viric@6
    61
		}
viric@6
    62
	}
viric@6
    63
viric@6
    64
	return FALSE;
viric@6
    65
}
viric@6
    66
viric@6
    67
int is_corner_area(const struct Map * m, const struct Position p,
viric@6
    68
	const struct Position box, const struct Position new_box)
viric@6
    69
{
viric@6
    70
	int NumMoves, NewMoves;
viric@6
    71
	struct Position pos[MAX_MOVES];
viric@6
    72
	struct Position new_pos[MAX_MOVES];
viric@6
    73
	char corners[MAX_Y][MAX_X];
viric@6
    74
	int i,j;
viric@6
    75
	struct Position next_pos;
viric@6
    76
	char *next_cell;
viric@6
    77
viric@6
    78
viric@6
    79
	/* Blank the garden */
viric@6
    80
	for (j = 0; j<m->SizeY; j++)
viric@6
    81
		for (i=0; i<m->SizeX; i++)
viric@6
    82
			corners[j][i] = m->Cells[j][i];
viric@6
    83
viric@6
    84
	/* Let's put the boxes */
viric@6
    85
	for (i = 0; i<m->NumBoxes; i++)
viric@6
    86
		corners[m->Box[i].y][m->Box[i].x] = BOX;
viric@6
    87
viric@6
    88
	/* Let's put our box - it can be simply added */
viric@6
    89
	corners[new_box.y][new_box.x] = BOX;
viric@6
    90
	/* Let's remove the original box. */
viric@6
    91
	corners[box.y][box.x] = BLANK;
viric@6
    92
viric@6
    93
	NewMoves = 1;
viric@6
    94
	new_pos[0] = p;
viric@6
    95
	while (NewMoves > 0)
viric@6
    96
	{
viric@6
    97
		/* The before named "New Moves" become the moves we have
viric@6
    98
		   to analyze */
viric@6
    99
		NumMoves = NewMoves;
viric@6
   100
		for (i=0; i<NewMoves; i++)
viric@6
   101
		{
viric@6
   102
			pos[i] = new_pos[i];
viric@6
   103
		}
viric@6
   104
viric@6
   105
		/* Search new positions for each position */
viric@6
   106
		NewMoves = 0;
viric@6
   107
		for (i=0; i<NumMoves; i++)
viric@6
   108
		{
viric@6
   109
			/* For each direction */
viric@6
   110
			for (j=0; j<4; j++)
viric@6
   111
			{
viric@6
   112
				next_pos.x = pos[i].x + move_vectors[j].x;
viric@6
   113
				next_pos.y = pos[i].y + move_vectors[j].y;
viric@6
   114
				next_cell = &corners[next_pos.y][next_pos.x];
viric@6
   115
				if(*next_cell == BLANK ||
viric@6
   116
					*next_cell == PLATFORM)
viric@6
   117
				{
viric@6
   118
					return FALSE;
viric@6
   119
				}
viric@6
   120
				else if(*next_cell == CORNER)
viric@6
   121
				{
viric@6
   122
					new_pos[NewMoves] = next_pos;
viric@6
   123
					*next_cell = MANCANMOVE;
viric@6
   124
					NewMoves++;
viric@6
   125
				}
viric@6
   126
			}
viric@6
   127
		}
viric@6
   128
	}
viric@6
   129
viric@6
   130
	return TRUE;
viric@6
   131
}
viric@6
   132
viric@6
   133
int does_box_close_corners(const struct Map * m, const struct Position mov,
viric@6
   134
	const struct Position box_pos)
viric@6
   135
{
viric@6
   136
	struct Position p, p2;
viric@6
   137
viric@6
   138
	p.x = box_pos.x + mov.x;
viric@6
   139
	p.y = box_pos.y + mov.y;
viric@6
   140
	
viric@6
   141
	/* Let's plan the checks */
viric@6
   142
	/* The point will be marked with a MANCANMOVE */
viric@6
   143
	p2.x = p.x + mov.x;
viric@6
   144
	p2.y = p.y + mov.y;
viric@6
   145
	if (m->Cells[p2.y][p2.x] == CORNER)
viric@6
   146
	{
viric@6
   147
		if (is_corner_area(m, p2, box_pos, p))
viric@6
   148
			return TRUE;
viric@6
   149
	}
viric@6
   150
viric@6
   151
	p2.x = p.x + mov.y;
viric@6
   152
	p2.y = p.y + mov.x;
viric@6
   153
	if (m->Cells[p2.y][p2.x] == CORNER)
viric@6
   154
	{
viric@6
   155
		if (is_corner_area(m, p2, box_pos, p))
viric@6
   156
			return TRUE;
viric@6
   157
	}
viric@6
   158
viric@6
   159
	p2.x = p.x - mov.y;
viric@6
   160
	p2.y = p.y - mov.x;
viric@6
   161
	if (m->Cells[p2.y][p2.x] == CORNER)
viric@6
   162
	{
viric@6
   163
		if (is_corner_area(m, p2, box_pos, p))
viric@6
   164
			return TRUE;
viric@6
   165
	}
viric@6
   166
	return FALSE;
viric@6
   167
}
viric@6
   168
#endif
viric@6
   169
viric@12
   170
viric@12
   171
static void force_move_box(struct Map *m, const struct BoxMove move)
viric@6
   172
{
viric@12
   173
	struct Position newpos;
viric@6
   174
viric@6
   175
viric@12
   176
	/* Add coords */
viric@12
   177
	newpos.x = m->Box[move.box].x + move.dir.x;
viric@12
   178
	newpos.y = m->Box[move.box].y + move.dir.y;
viric@12
   179
viric@12
   180
	/* Be certain the move can be done */
viric@12
   181
	assert(m->Cells[newpos.y][newpos.x] != BOX);
viric@12
   182
	assert(m->Cells[newpos.y][newpos.x] != WALL);
viric@12
   183
viric@12
   184
	/* Control if we moved the box to a platform */
viric@12
   185
	if(m->Cells[newpos.y][newpos.x] == PLATFORM)
viric@12
   186
	{
viric@12
   187
		m->NumBoxesInPlatform++;
viric@12
   188
	}
viric@12
   189
viric@12
   190
	/* Control if we moved the box from a platform */
viric@12
   191
	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
viric@12
   192
	{
viric@12
   193
		m->NumBoxesInPlatform--;
viric@12
   194
	}
viric@12
   195
	m->Man = m->Box[move.box];
viric@12
   196
viric@12
   197
	m->Box[move.box] = newpos;
viric@12
   198
}
viric@12
   199
viric@12
   200
viric@12
   201
viric@12
   202
static Bool search_did_found(struct Map maps[], int depth,
viric@12
   203
	struct BoxMove movements[],
viric@12
   204
	int num_movements, float percent, float total_percent)
viric@12
   205
{
viric@12
   206
	struct BoxMove new_movements[MAX_MOVES];
viric@12
   207
	int num_new_movements;
viric@12
   208
	struct Map *m; 
viric@12
   209
	int i;
viric@12
   210
	float next_percent;
viric@12
   211
viric@12
   212
	next_percent = percent / num_movements;
viric@12
   213
viric@12
   214
	m = &maps[depth+1];
viric@12
   215
	if (depth > max_depth)
viric@12
   216
		max_depth = depth;
viric@12
   217
	if (depth > max_depth_period)
viric@12
   218
		max_depth_period = depth;
viric@12
   219
	if (depth < min_depth_period)
viric@12
   220
		min_depth_period = depth;
viric@12
   221
viric@12
   222
	for (i=0; i < num_movements; i++)
viric@12
   223
	{
viric@12
   224
		CopyMap(m, &maps[depth]);
viric@12
   225
		force_move_box(m, movements[i]);
viric@12
   226
		/* Let's see if we finished */
viric@12
   227
		if (m->NumPlatforms == m->NumBoxesInPlatform)
viric@12
   228
		{
viric@12
   229
			PrintMove(movements[i]);
viric@12
   230
			actual_map = &maps[depth+1];
viric@12
   231
			show_percent_and_map();
viric@12
   232
			return TRUE;
viric@12
   233
		}
viric@12
   234
viric@12
   235
		if (is_new_map(maps, depth+1))
viric@12
   236
		{
viric@12
   237
			fill_deps(m);
viric@12
   238
			if (are_there_fixed_boxes(m,
viric@12
   239
				new_movements, &num_new_movements))
viric@12
   240
			{
viric@12
   241
				/* That means that the map is illegal */
viric@12
   242
				/* Maybe we could update the percent here... */
viric@16
   243
				continue;
viric@12
   244
			}
viric@16
   245
			actual_map = &maps[depth+1];
viric@16
   246
#ifdef DEBUG		/* to be out */
viric@16
   247
			show_percent_and_map();
viric@16
   248
#endif
viric@12
   249
			/* the assert should be IN the function before,
viric@12
   250
			   before OVERfilling new_movements */
viric@12
   251
			assert(num_new_movements < MAX_MOVES);
viric@6
   252
		}
viric@6
   253
		else
viric@12
   254
			num_new_movements = 0;
viric@12
   255
viric@12
   256
		if (num_new_movements == 0)
viric@6
   257
		{
viric@12
   258
			percent_to_show = total_percent + next_percent*i;
viric@12
   259
			depth_to_show = depth;
viric@6
   260
		}
viric@6
   261
		else
viric@6
   262
		{
viric@12
   263
			if (depth+1 < MAX_STEPS)
viric@12
   264
			{
viric@12
   265
				if(search_did_found(maps, depth+1, new_movements,
viric@12
   266
					num_new_movements, next_percent,
viric@12
   267
					total_percent + next_percent*i) == TRUE)
viric@12
   268
				{
viric@12
   269
					PrintMove(movements[i]);
viric@12
   270
					actual_map = &maps[depth+1];
viric@12
   271
					show_percent_and_map();
viric@12
   272
					return TRUE;
viric@12
   273
				}
viric@12
   274
			}
viric@6
   275
		}
viric@6
   276
	}
viric@6
   277
	return FALSE;
viric@6
   278
}
viric@6
   279
viric@6
   280
viric@12
   281
/* It only fills the m->man_moves structure */
viric@12
   282
static void paint_mancanmove(struct Map *m)
viric@6
   283
{
viric@6
   284
	struct Position pos[MAX_MOVES];
viric@6
   285
	struct Position new_pos[MAX_MOVES];
viric@6
   286
	int NumMoves, NewMoves;
viric@6
   287
	int j, i;
viric@6
   288
	struct Position next_pos;
viric@6
   289
	char *next_cell;
viric@12
   290
viric@6
   291
	/* Let's  the map with only walls in man_moves - other, blanks */
viric@6
   292
	for (j = 0; j<m->SizeY; j++)
viric@6
   293
		for (i=0; i<m->SizeX; i++)
viric@6
   294
		{
viric@6
   295
			if (m->Cells[j][i] == WALL)
viric@6
   296
				m->man_moves[j][i] = WALL;
viric@6
   297
			else
viric@6
   298
				m->man_moves[j][i] = BLANK;
viric@6
   299
		}
viric@6
   300
viric@6
   301
	/* Let's put the boxes */
viric@6
   302
	for (i = 0; i<m->NumBoxes; i++)
viric@6
   303
	{
viric@12
   304
		m->man_moves[m->Box[i].y][m->Box[i].x] = WALL;
viric@6
   305
	}
viric@6
   306
viric@6
   307
	NewMoves = 1;
viric@6
   308
	new_pos[0].x = m->Man.x;
viric@6
   309
	new_pos[0].y = m->Man.y;
viric@6
   310
	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;
viric@6
   311
	while (NewMoves > 0)
viric@6
   312
	{
viric@6
   313
		/* The before named "New Moves" become the moves we have
viric@6
   314
		   to analyze */
viric@6
   315
		NumMoves = NewMoves;
viric@6
   316
		for (i=0; i<NewMoves; i++)
viric@6
   317
		{
viric@6
   318
			pos[i] = new_pos[i];
viric@6
   319
		}
viric@6
   320
viric@6
   321
		/* Search new positions for each position */
viric@6
   322
		NewMoves = 0;
viric@6
   323
		for (i=0; i<NumMoves; i++)
viric@6
   324
		{
viric@6
   325
			/* For each direction */
viric@6
   326
			for (j=0; j<4; j++)
viric@6
   327
			{
viric@6
   328
				next_pos.x = pos[i].x + move_vectors[j].x;
viric@6
   329
				next_pos.y = pos[i].y + move_vectors[j].y;
viric@6
   330
				next_cell = &m->man_moves[next_pos.y][next_pos.x];
viric@6
   331
				if(*next_cell == BLANK)
viric@6
   332
				{
viric@6
   333
					new_pos[NewMoves] = next_pos;
viric@6
   334
					*next_cell = MANCANMOVE;
viric@6
   335
					NewMoves++;
viric@6
   336
				}
viric@12
   337
			}
viric@12
   338
		}
viric@12
   339
	}
viric@12
   340
}
viric@12
   341
viric@12
   342
/* Returns TRUE if there are fixed boxes that should be moved, FALSE otherwise*/
viric@12
   343
/* For 'm' it modifies only m->boxes[][] */
viric@12
   344
static Bool are_there_fixed_boxes(struct Map *m,
viric@12
   345
	struct BoxMove movements[MAX_MOVES], int *num_movements)
viric@12
   346
{
viric@12
   347
	int i,j;
viric@12
   348
	enum e_direction d;
viric@12
   349
viric@12
   350
	/* Box dependencies. The first depends on seconds. */
viric@12
   351
	struct
viric@12
   352
	{
viric@12
   353
		Bool box[MAX_BOXES][MAX_BOXES];
viric@12
   354
		int ndeps[MAX_BOXES];
viric@12
   355
	} dep;
viric@12
   356
viric@12
   357
	/* Free boxes' arrays */
viric@12
   358
	struct
viric@12
   359
	{
viric@12
   360
		Bool box_is_free[MAX_BOXES]; /* This is only used in 'free' */
viric@12
   361
		int box[MAX_BOXES];
viric@12
   362
		int n;
viric@12
   363
	} free,			/* List of all boxes free-to-move */
viric@12
   364
		new_free,	/* List of boxes for the next loop (code) */
viric@12
   365
		tfree;	/* List of boxes of the loop (code) */
viric@12
   366
viric@12
   367
	struct Position tpos;
viric@12
   368
viric@12
   369
	Bool is_not_set_free;
viric@12
   370
viric@12
   371
	/* Initialize to 0 the dependency structures */
viric@12
   372
	memset((void *) &dep, 0, sizeof(dep));
viric@16
   373
	new_free.n=0;
viric@12
   374
	for(i=0; i<m->NumBoxes; i++)
viric@12
   375
	{
viric@12
   376
		new_free.box[i] = FALSE;
viric@12
   377
	}
viric@12
   378
viric@12
   379
	/* Let's fill the structure */
viric@12
   380
	for(i=0; i<m->NumBoxes; i++)
viric@12
   381
	{
viric@12
   382
		/* See if the box is blocked. That could be
viric@12
   383
		   done in fill_deps */
viric@12
   384
		if (m->box_deps[i].dep_dir[0] == BLOCKED &&
viric@12
   385
			m->box_deps[i].dep_dir[1] == BLOCKED &&
viric@12
   386
			m->box_deps[i].dep_dir[2] == BLOCKED &&
viric@12
   387
			m->box_deps[i].dep_dir[3] == BLOCKED )
viric@12
   388
		{
viric@12
   389
			if (m->Cells[m->Box[i].y][m->Box[i].x] !=
viric@12
   390
				PLATFORM)
viric@12
   391
				return TRUE;
viric@12
   392
			/* This is not used actually 
viric@12
   393
			else
viric@12
   394
				m->boxes[m->Box[i].y][m->Box[i].x] =
viric@12
   395
					WALL;
viric@12
   396
			*/
viric@12
   397
		}
viric@12
   398
		/* Let's take note of the dependencies */
viric@12
   399
		is_not_set_free = TRUE;
viric@12
   400
		for(d=0; d<4; d++)
viric@12
   401
		{
viric@12
   402
			if(m->box_deps[i].dep_dir[d] > 0)
viric@12
   403
			{
viric@16
   404
				if (!dep.box[i][m->box_deps[i].dep_dir[d]])
viric@16
   405
				{
viric@16
   406
					dep.box[i][m->box_deps[i].dep_dir[d]] =
viric@16
   407
						TRUE;
viric@16
   408
					dep.ndeps[i]++;
viric@16
   409
				}
viric@12
   410
			} else
viric@12
   411
			if(m->box_deps[i].dep_dir[d] == FREE)
viric@12
   412
			{
viric@12
   413
				if (is_not_set_free)
viric@6
   414
				{
viric@12
   415
					new_free.box[new_free.n++] = i;
viric@12
   416
					is_not_set_free = FALSE;
viric@6
   417
				}
viric@6
   418
			}
viric@6
   419
		}
viric@6
   420
	}
viric@6
   421
viric@12
   422
	/* Let's analyze if the free boxes can really be moved, and
viric@12
   423
	   set them as dependant, if they're dependant.
viric@12
   424
	   If some can be really moved, we should know _where to_. */
viric@6
   425
viric@12
   426
	/* Paint MANCANMOVE at each cell the man can reach */
viric@12
   427
	paint_mancanmove(m);
viric@12
   428
	
viric@12
   429
	/* For each free movable box, let's see if the man can reach them
viric@12
   430
	   fine. If we can, add it to the possible movements. */
viric@12
   431
	*num_movements=0;
viric@12
   432
	for(i=0; i<new_free.n; i++)
viric@6
   433
	{
viric@12
   434
		/* For each direction, try if the box can be moved */
viric@12
   435
		for(d=0; d<4; d++)
viric@12
   436
		{
viric@16
   437
			if(m->box_deps[new_free.box[i]].dep_dir[d] == FREE)
viric@12
   438
			{
viric@16
   439
				add_position3(tpos, m->Box[new_free.box[i]], move_vectors[OPPOSITE_DIR(d)])
viric@12
   440
				if (m->man_moves[tpos.y][tpos.x] == MANCANMOVE)
viric@12
   441
				{
viric@16
   442
					movements[*num_movements].box =
viric@16
   443
						new_free.box[i];
viric@12
   444
					movements[*num_movements].dir =
viric@12
   445
						move_vectors[d];
viric@12
   446
					(*num_movements)++;
viric@12
   447
				}
viric@12
   448
				/* ELSE - we should catch those cases,
viric@12
   449
				where free boxes cannot be moved. Will they
viric@12
   450
				ever be movable? 
viric@12
   451
				THIS HAS TO BE IMPROVED */
viric@12
   452
			}
viric@12
   453
		}
viric@6
   454
	}
viric@6
   455
viric@12
   456
viric@12
   457
	/* ---------------- The next possible movements have been calculated --
viric@12
   458
	We can still find that this map is illegal. We need to find
viric@12
   459
	further more if there are boxes unmovable (due to dependencies) */
viric@12
   460
viric@12
   461
	/* Let's take out all dependencies from 'free' boxes */
viric@12
   462
	/* Prepare the 'free' list */
viric@12
   463
	for(i=0; i<m->NumBoxes;i++)
viric@12
   464
		free.box_is_free[i] = FALSE;
viric@12
   465
	free.n = new_free.n;
viric@12
   466
	for(i=0; i<new_free.n; i++)
viric@6
   467
	{
viric@12
   468
		free.box[i] = new_free.box[i];
viric@12
   469
		free.box_is_free[i] = TRUE;
viric@6
   470
	}
viric@6
   471
viric@12
   472
	/* KACXO-loop  */
viric@12
   473
	while (new_free.n > 0)
viric@12
   474
	{
viric@12
   475
		/* Copy new_free into free */
viric@12
   476
		tfree.n = new_free.n;
viric@12
   477
		for(i=0; i<new_free.n; i++)
viric@12
   478
			tfree.box[i] = new_free.box[i];
viric@12
   479
		new_free.n = 0;
viric@6
   480
viric@12
   481
		for(i=0; i<tfree.n; i++)
viric@6
   482
		{
viric@12
   483
			for(j=0; j<m->NumBoxes; j++)
viric@6
   484
			{
viric@12
   485
				/* The box j no more depends on
viric@12
   486
				   the box tfree[i] */
viric@12
   487
				if(dep.box[j][tfree.box[i]])
viric@6
   488
				{
viric@12
   489
					dep.box[j][tfree.box[i]] = FALSE;
viric@12
   490
					dep.ndeps[j]--;
viric@12
   491
					assert(dep.ndeps[j] >= 0);
viric@12
   492
					if (dep.ndeps[j] == 0 &&
viric@16
   493
						!free.box_is_free[tfree.box[i]])
viric@12
   494
					{
viric@12
   495
						new_free.box[new_free.n++]=j;
viric@12
   496
						free.box[free.n++]=j;
viric@12
   497
					}
viric@6
   498
				}
viric@6
   499
			}
viric@6
   500
		}
viric@6
   501
	}
viric@12
   502
viric@12
   503
	/* Now are left only boxes which depend on others-non-free */
viric@12
   504
	for(i=0; i<m->NumBoxes; i++)
viric@12
   505
	{
viric@12
   506
		for(j=0; j<m->NumBoxes; j++)
viric@12
   507
		{
viric@12
   508
			/* We only do one-level search !!! */
viric@12
   509
			/* If the box only depends on another,
viric@12
   510
			   which also only depends on this... */
viric@12
   511
			if (dep.box[i][j] && dep.ndeps[i] == 1
viric@12
   512
				&& dep.box[j][i] && dep.ndeps[j] == 1)
viric@12
   513
			{
viric@12
   514
				if (m->Cells[m->Box[i].y][m->Box[i].x]!=
viric@12
   515
					PLATFORM)
viric@12
   516
				{
viric@12
   517
					return TRUE;
viric@12
   518
				}
viric@12
   519
				/* We don't set any wall here, they're not
viric@12
   520
				   important */
viric@12
   521
			}
viric@12
   522
		}
viric@12
   523
	}
viric@12
   524
viric@12
   525
	return FALSE;
viric@12
   526
}
viric@12
   527
viric@12
   528
static void init_cell_boxes(struct Map *m)
viric@12
   529
{
viric@12
   530
	int i,j;
viric@12
   531
viric@12
   532
	/* Let's  the map with only walls in man_moves - other, blanks */
viric@12
   533
	for (j = 0; j<m->SizeY; j++)
viric@12
   534
		for (i=0; i<m->SizeX; i++)
viric@12
   535
			m->cells_boxes[j][i] = -1;
viric@12
   536
viric@12
   537
	for(i=0; i<m->NumBoxes; i++)
viric@12
   538
	{
viric@12
   539
		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
viric@12
   540
	}
viric@12
   541
}
viric@12
   542
viric@12
   543
/* It fills only m->box_deps */
viric@12
   544
static void fill_deps(struct Map *m)
viric@12
   545
{
viric@12
   546
	int i;
viric@12
   547
	enum e_direction dir;
viric@12
   548
	struct Position n; /* Position next to the box */
viric@12
   549
viric@12
   550
	/* TO BE OPTIMIZED - get into force_move_box */
viric@12
   551
	init_cell_boxes(m);
viric@12
   552
viric@12
   553
	for(i=0; i<m->NumBoxes; i++)
viric@12
   554
	{
viric@12
   555
		/* Initialize the move freedom */
viric@12
   556
		for(dir=0;dir<4; dir++)
viric@12
   557
		{
viric@12
   558
			m->box_deps[i].dep_dir[dir] = FREE;
viric@12
   559
		}
viric@12
   560
viric@12
   561
		/* Limit the freedom */
viric@12
   562
		for(dir=0;dir<4; dir++)
viric@12
   563
		{
viric@12
   564
			add_position3(n,m->Box[i],move_vectors[dir]);
viric@12
   565
			if(m->Cells[n.y][n.x] == WALL)
viric@12
   566
			{
viric@12
   567
				/* IMPROVEMENT: The fixed-box detection
viric@12
   568
				could be done here */
viric@12
   569
				m->box_deps[i].dep_dir[dir] = BLOCKED;
viric@12
   570
				m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)] =
viric@12
   571
					BLOCKED;
viric@12
   572
				continue;
viric@12
   573
			}
viric@12
   574
viric@12
   575
			/* if there is Wall limit, we don't want to set box
viric@12
   576
			   dependency */
viric@12
   577
			if(m->box_deps[i].dep_dir[dir] == WALL)
viric@12
   578
				continue;
viric@12
   579
viric@12
   580
			/* Put the box dependency in the list */
viric@12
   581
			if(m->cells_boxes[n.y][n.x] >= 0)
viric@12
   582
			{
viric@12
   583
				m->box_deps[i].dep_dir[dir] =
viric@12
   584
					m->cells_boxes[n.y][n.x];
viric@12
   585
				/* If the other site is not limited by another
viric@12
   586
				   box, we set it up too. */
viric@12
   587
viric@12
   588
				/* *** MAYBE IT'S BETTER NOT TO SET IT */
viric@16
   589
				if(m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)]
viric@16
   590
					== FREE)
viric@12
   591
				{
viric@12
   592
				m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)] =
viric@12
   593
					m->cells_boxes[n.y][n.x];
viric@12
   594
				}
viric@12
   595
				continue;
viric@12
   596
			}
viric@12
   597
			if(m->Cells[n.y][n.x] == CORNER)
viric@12
   598
				m->box_deps[i].dep_dir[dir] = BLOCKED;
viric@12
   599
				
viric@12
   600
		}
viric@12
   601
	}
viric@6
   602
}
viric@6
   603
viric@6
   604
viric@6
   605
int solve_map(const struct Map origin)
viric@6
   606
{
viric@6
   607
	struct Map maps[MAX_STEPS+1];
viric@6
   608
	struct BoxMove new_movements[MAX_MOVES];
viric@6
   609
	int num_new_movements;
viric@6
   610
viric@6
   611
	CopyMap(&maps[0], &origin);
viric@6
   612
viric@12
   613
	fill_deps(&maps[0]);
viric@13
   614
	/* Initializing actual_map here AT LEAST gives protection against
viric@13
   615
	SIGSEGV */
viric@12
   616
	assert(!are_there_fixed_boxes(&maps[0], new_movements,
viric@12
   617
		&num_new_movements));
viric@12
   618
	search_did_found(maps, 0, new_movements, num_new_movements, 100, 0);
viric@6
   619
viric@12
   620
	return 0;
viric@6
   621
}