actual_map is initialized at first, so almost never a SIGSEGV can happen.
Even though it should be initialized at init_so, and protecting against SIGSEGV
there.
#include <assert.h>
#include <string.h>
#include <stdio.h> /**********************************PROVA */
#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;
/* Prototipes */
static Bool are_there_fixed_boxes(struct Map *m,
struct BoxMove movements[MAX_MOVES], int *num_movements);
static void force_move_box(struct Map *m, const struct BoxMove move);
static Bool search_did_found(struct Map maps[], int depth,
struct BoxMove movements[],
int num_movements, float percent, float total_percent);
static void fill_deps(struct Map *m);
#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
static void force_move_box(struct Map *m, const 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 Bool search_did_found(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]);
/* Let's see if we finished */
if (m->NumPlatforms == m->NumBoxesInPlatform)
{
PrintMove(movements[i]);
actual_map = &maps[depth+1];
show_percent_and_map();
return TRUE;
}
if (is_new_map(maps, depth+1))
{
actual_map = &maps[depth+1];
#ifdef DEBUG /* to be out */
show_percent_and_map();
#endif
fill_deps(m);
if (are_there_fixed_boxes(m,
new_movements, &num_new_movements))
{
/* That means that the map is illegal */
/* Maybe we could update the percent here... */
return FALSE;
}
/* the assert should be IN the function before,
before OVERfilling 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;
}
else
{
if (depth+1 < MAX_STEPS)
{
if(search_did_found(maps, depth+1, new_movements,
num_new_movements, next_percent,
total_percent + next_percent*i) == TRUE)
{
PrintMove(movements[i]);
actual_map = &maps[depth+1];
show_percent_and_map();
return TRUE;
}
}
}
}
return FALSE;
}
/* It only fills the m->man_moves structure */
static void paint_mancanmove(struct Map *m)
{
struct Position pos[MAX_MOVES];
struct Position new_pos[MAX_MOVES];
int NumMoves, NewMoves;
int j, i;
struct Position next_pos;
char *next_cell;
/* 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] = WALL;
}
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++;
}
}
}
}
}
/* Returns TRUE if there are fixed boxes that should be moved, FALSE otherwise*/
/* For 'm' it modifies only m->boxes[][] */
static Bool are_there_fixed_boxes(struct Map *m,
struct BoxMove movements[MAX_MOVES], int *num_movements)
{
int i,j;
enum e_direction d;
/* Box dependencies. The first depends on seconds. */
struct
{
Bool box[MAX_BOXES][MAX_BOXES];
int ndeps[MAX_BOXES];
} dep;
/* Free boxes' arrays */
struct
{
Bool box_is_free[MAX_BOXES]; /* This is only used in 'free' */
int box[MAX_BOXES];
int n;
} free, /* List of all boxes free-to-move */
new_free, /* List of boxes for the next loop (code) */
tfree; /* List of boxes of the loop (code) */
struct Position tpos;
Bool is_not_set_free;
/* Initialize to 0 the dependency structures */
memset((void *) &dep, 0, sizeof(dep));
for(i=0; i<m->NumBoxes; i++)
{
new_free.box[i] = FALSE;
}
/* Let's fill the structure */
for(i=0; i<m->NumBoxes; i++)
{
/* See if the box is blocked. That could be
done in fill_deps */
if (m->box_deps[i].dep_dir[0] == BLOCKED &&
m->box_deps[i].dep_dir[1] == BLOCKED &&
m->box_deps[i].dep_dir[2] == BLOCKED &&
m->box_deps[i].dep_dir[3] == BLOCKED )
{
if (m->Cells[m->Box[i].y][m->Box[i].x] !=
PLATFORM)
return TRUE;
/* This is not used actually
else
m->boxes[m->Box[i].y][m->Box[i].x] =
WALL;
*/
}
/* Let's take note of the dependencies */
is_not_set_free = TRUE;
for(d=0; d<4; d++)
{
if(m->box_deps[i].dep_dir[d] > 0)
{
dep.box[i][m->box_deps[i].dep_dir[d]] =
TRUE;
dep.ndeps[i]++;
} else
if(m->box_deps[i].dep_dir[d] == FREE)
{
if (is_not_set_free)
{
new_free.box[new_free.n++] = i;
is_not_set_free = FALSE;
}
}
}
}
/* Let's analyze if the free boxes can really be moved, and
set them as dependant, if they're dependant.
If some can be really moved, we should know _where to_. */
/* Paint MANCANMOVE at each cell the man can reach */
paint_mancanmove(m);
/* For each free movable box, let's see if the man can reach them
fine. If we can, add it to the possible movements. */
*num_movements=0;
for(i=0; i<new_free.n; i++)
{
/* For each direction, try if the box can be moved */
for(d=0; d<4; d++)
{
if(m->box_deps[i].dep_dir[d] == FREE)
{
add_position3(tpos, m->Box[i], move_vectors[OPPOSITE_DIR(d)])
if (m->man_moves[tpos.y][tpos.x] == MANCANMOVE)
{
movements[*num_movements].box = i;
movements[*num_movements].dir =
move_vectors[d];
(*num_movements)++;
}
/* ELSE - we should catch those cases,
where free boxes cannot be moved. Will they
ever be movable?
THIS HAS TO BE IMPROVED */
}
}
}
/* ---------------- The next possible movements have been calculated --
We can still find that this map is illegal. We need to find
further more if there are boxes unmovable (due to dependencies) */
/* Let's take out all dependencies from 'free' boxes */
/* Prepare the 'free' list */
for(i=0; i<m->NumBoxes;i++)
free.box_is_free[i] = FALSE;
free.n = new_free.n;
for(i=0; i<new_free.n; i++)
{
free.box[i] = new_free.box[i];
free.box_is_free[i] = TRUE;
}
/* KACXO-loop */
while (new_free.n > 0)
{
/* Copy new_free into free */
tfree.n = new_free.n;
for(i=0; i<new_free.n; i++)
tfree.box[i] = new_free.box[i];
new_free.n = 0;
for(i=0; i<tfree.n; i++)
{
for(j=0; j<m->NumBoxes; j++)
{
/* The box j no more depends on
the box tfree[i] */
if(dep.box[j][tfree.box[i]])
{
dep.box[j][tfree.box[i]] = FALSE;
dep.ndeps[j]--;
assert(dep.ndeps[j] >= 0);
if (dep.ndeps[j] == 0 &&
!free.box_is_free[i])
{
new_free.box[new_free.n++]=j;
free.box[free.n++]=j;
}
}
}
}
}
/* Now are left only boxes which depend on others-non-free */
for(i=0; i<m->NumBoxes; i++)
{
for(j=0; j<m->NumBoxes; j++)
{
/* We only do one-level search !!! */
/* If the box only depends on another,
which also only depends on this... */
if (dep.box[i][j] && dep.ndeps[i] == 1
&& dep.box[j][i] && dep.ndeps[j] == 1)
{
if (m->Cells[m->Box[i].y][m->Box[i].x]!=
PLATFORM)
{
return TRUE;
}
/* We don't set any wall here, they're not
important */
}
}
}
return FALSE;
}
static void init_cell_boxes(struct Map *m)
{
int i,j;
/* 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++)
m->cells_boxes[j][i] = -1;
for(i=0; i<m->NumBoxes; i++)
{
m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
}
}
/* It fills only m->box_deps */
static void fill_deps(struct Map *m)
{
int i;
enum e_direction dir;
struct Position n; /* Position next to the box */
/* TO BE OPTIMIZED - get into force_move_box */
init_cell_boxes(m);
for(i=0; i<m->NumBoxes; i++)
{
/* Initialize the move freedom */
for(dir=0;dir<4; dir++)
{
m->box_deps[i].dep_dir[dir] = FREE;
}
/* Limit the freedom */
for(dir=0;dir<4; dir++)
{
add_position3(n,m->Box[i],move_vectors[dir]);
if(m->Cells[n.y][n.x] == WALL)
{
/* IMPROVEMENT: The fixed-box detection
could be done here */
m->box_deps[i].dep_dir[dir] = BLOCKED;
m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)] =
BLOCKED;
continue;
}
/* if there is Wall limit, we don't want to set box
dependency */
if(m->box_deps[i].dep_dir[dir] == WALL)
continue;
/* Put the box dependency in the list */
if(m->cells_boxes[n.y][n.x] >= 0)
{
m->box_deps[i].dep_dir[dir] =
m->cells_boxes[n.y][n.x];
/* If the other site is not limited by another
box, we set it up too. */
/* *** MAYBE IT'S BETTER NOT TO SET IT */
if(m->box_deps[i].dep_dir[dir] == FREE)
{
m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)] =
m->cells_boxes[n.y][n.x];
}
continue;
}
if(m->Cells[n.y][n.x] == CORNER)
m->box_deps[i].dep_dir[dir] = BLOCKED;
}
}
}
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);
fill_deps(&maps[0]);
/* Initializing actual_map here AT LEAST gives protection against
SIGSEGV */
actual_map = &maps[0];
assert(!are_there_fixed_boxes(&maps[0], new_movements,
&num_new_movements));
search_did_found(maps, 0, new_movements, num_new_movements, 100, 0);
return 0;
}