--- a/algorithm.c Sun May 07 01:30:29 2006 +0200
+++ b/algorithm.c Sun May 07 01:31:50 2006 +0200
@@ -1,5 +1,6 @@
#include <assert.h>
#include <string.h>
+#include <stdio.h> /**********************************PROVA */
#include "general.h"
/* Variables related to the showing of information by os */
@@ -11,6 +12,15 @@
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:
@@ -157,162 +167,119 @@
}
#endif
-/*
-Catch the situation where a box is moved next to a corner, where the box
-next to it will not be able to be moved.
-*/
-static int is_dead1(const struct Map * m, const struct Position mov,
- const struct Position new_pos)
+
+static void force_move_box(struct Map *m, const struct BoxMove move)
{
- struct Position opposite1, opposite2;
+ struct Position newpos;
+
- /* The wall corners must exist */
- opposite1.x = -mov.y;
- opposite1.y = -mov.x;
- opposite2.x = mov.y;
- opposite2.y = mov.x;
+ /* Add coords */
+ newpos.x = m->Box[move.box].x + move.dir.x;
+ newpos.y = m->Box[move.box].y + move.dir.y;
-#ifdef DEBUG
- ShowMap(m);
-#endif
+ /* Be certain the move can be done */
+ assert(m->Cells[newpos.y][newpos.x] != BOX);
+ assert(m->Cells[newpos.y][newpos.x] != WALL);
- /* Test the first corner */
- if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]
- == WALL)
+ /* Control if we moved the box to a platform */
+ if(m->Cells[newpos.y][newpos.x] == PLATFORM)
{
- /* Test wall at opposites 1*/
- if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
- == WALL &&
- m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
- {
- return TRUE;
- }
- else
- if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
- == BOX &&
- m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
- {
- return TRUE;
- }
- /* Test wall at opposites 2 */
- if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
- == WALL &&
- m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
- {
- return TRUE;
- }
- else
- if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
- == BOX &&
- m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
- {
- return TRUE;
- }
+ m->NumBoxesInPlatform++;
}
- /* Test the second corner */
- if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]
- == WALL)
+ /* Control if we moved the box from a platform */
+ if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
{
- /* Test wall at opposites 1*/
- if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
- == WALL &&
- m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
+ 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)
{
- return TRUE;
+ PrintMove(movements[i]);
+ actual_map = &maps[depth+1];
+ show_percent_and_map();
+ return TRUE;
}
- else
- if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
- == BOX &&
- m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
+
+ if (is_new_map(maps, depth+1))
{
- return TRUE;
- }
- /* Test wall at opposites 2 */
- if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
- == WALL &&
- m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
- {
- return TRUE;
+ 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
- if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
- == BOX &&
- m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
- {
- return TRUE;
- }
- }
-
- return FALSE;
-}
-
-/*
-Catch the situation where a corner gets surrounded by boxes.
-*/
-static int is_dead2(const struct Map * m, const struct Position mov,
- const struct Position new_pos)
-{
- struct Position next, opposite1, opposite2;
-
- next.x = new_pos.x+mov.x;
- next.y = new_pos.y+mov.y;
+ num_new_movements = 0;
- /* The corner must exist */
- if (m->Cells[next.y][next.x] != CORNER)
- return FALSE;
-
-
- /* The wall corners must exist */
- opposite1.x = next.x -mov.y;
- opposite1.y = next.y -mov.x;
- opposite2.x = next.x + mov.y;
- opposite2.y = next.y + mov.x;
-
- if (m->man_moves[opposite1.y][opposite1.x] == BOX)
- {
- if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL
- && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)
- return TRUE;
- }
-
- if (m->man_moves[opposite2.y][opposite2.x] == BOX)
- {
- if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL
- && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)
- return TRUE;
+ 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;
}
-static int is_box_movable(const struct Map * m, const struct Position mov,
- const struct Position box_pos)
-{
- struct Position next_pos2;
- next_pos2.x = box_pos.x + mov.x;
- next_pos2.y = box_pos.y + mov.y;
-
- if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&
- m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||
- m->man_moves[next_pos2.y][next_pos2.x] == BOX)
- {
- return FALSE;
- }
- else if (is_dead1(m, mov, next_pos2) == TRUE)
- {
- return FALSE;
- }
- else if (is_dead2(m, mov, next_pos2) == TRUE)
- {
- return FALSE;
- }
- return TRUE;
-}
-
-/* It modifies m->man_moves */
-static int get_box_movements(struct Map * m,
- struct BoxMove movements[])
+/* 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];
@@ -320,8 +287,7 @@
int j, i;
struct Position next_pos;
char *next_cell;
- int num_box_movements = 0;
-
+
/* 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++)
@@ -335,8 +301,7 @@
/* Let's put the boxes */
for (i = 0; i<m->NumBoxes; i++)
{
- m->man_moves[m->Box[i].y][m->Box[i].x] = BOX;
- m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
+ m->man_moves[m->Box[i].y][m->Box[i].x] = WALL;
}
NewMoves = 1;
@@ -369,126 +334,265 @@
*next_cell = MANCANMOVE;
NewMoves++;
}
- else if (*next_cell == BOX)
- {
-
- /* Check if the box is movable */
+ }
+ }
+ }
+}
+
+/* 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;
+ }
- if (is_box_movable(m, move_vectors[j],
- next_pos ))
- {
- {
- movements[num_box_movements].box =
- m->cells_boxes[next_pos.y][next_pos.x];
- movements[num_box_movements].dir =
- move_vectors[j];
- num_box_movements++;
- }
- }
-
+ /* 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 */
}
}
}
- return num_box_movements;
-}
-static void force_move_box(struct Map *m, const struct BoxMove move)
-{
- struct Position newpos;
-
+ /* ---------------- 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) */
- /* 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)
+ /* 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++)
{
- m->NumBoxesInPlatform++;
+ free.box[i] = new_free.box[i];
+ free.box_is_free[i] = TRUE;
}
- /* 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 int search_depth(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++)
+ /* KACXO-loop */
+ while (new_free.n > 0)
{
- CopyMap(m, &maps[depth]);
- force_move_box(m, movements[i]);
- if (m->NumPlatforms == m->NumBoxesInPlatform)
- {
- PrintMove(movements[i]);
- return 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;
- if (is_new_map(maps, depth+1))
- {
- num_new_movements = get_box_movements(m, new_movements);
- assert(num_new_movements < MAX_MOVES);
- }
- else
- num_new_movements = 0;
-
- if (num_new_movements == 0)
+ for(i=0; i<tfree.n; i++)
{
- percent_to_show = total_percent + next_percent*i;
- depth_to_show = depth;
- actual_map = &maps[depth];
-#ifdef DEBUG /* to be out */
- show_percent_callback(0);
-#endif
-
- }
- else
- {
- if (depth+1 < MAX_STEPS)
+ for(j=0; j<m->NumBoxes; j++)
{
- if(search_depth(maps, depth+1, new_movements,
- num_new_movements, next_percent,
- total_percent + next_percent*i) == 0)
+ /* The box j no more depends on
+ the box tfree[i] */
+ if(dep.box[j][tfree.box[i]])
{
- PrintMove(movements[i]);
- return 0;
+ 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;
+ }
}
}
}
}
- return 1;
+
+ /* 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;
+
+ }
+ }
}
@@ -500,14 +604,10 @@
CopyMap(&maps[0], &origin);
- num_new_movements = get_box_movements(&maps[0], new_movements);
- assert(num_new_movements < MAX_MOVES);
- assert(num_new_movements > 0);
-
- init_os();
+ fill_deps(&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 search_depth(maps, 0, new_movements,
- num_new_movements, 100. / num_new_movements,
- 0);
-
+ return 0;
}