# HG changeset patch # User viric@llimona # Date 1146958310 -7200 # Node ID a2c334a71a6b1fae43c23f8427d628f4cd15cd92 # Parent dcfe4d2d4387e3047e734c07c835b15b26a893bd A minimum working (hope so!) version of the algorithm is working, although it says levels/02 is unsolvable. Now the solution is printed map by map. diff -r dcfe4d2d4387 -r a2c334a71a6b algorithm.c --- 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 #include +#include /**********************************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; jSizeY; j++) for (i=0; iSizeX; i++) @@ -335,8 +301,7 @@ /* Let's put the boxes */ for (i = 0; iNumBoxes; 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; iNumBoxes; 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; iNumBoxes; 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; ibox_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; iNumBoxes;i++) + free.box_is_free[i] = FALSE; + free.n = new_free.n; + for(i=0; iNumBoxesInPlatform++; + 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; iNumBoxes; 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; iNumBoxes; i++) + { + for(j=0; jNumBoxes; 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; jSizeY; j++) + for (i=0; iSizeX; i++) + m->cells_boxes[j][i] = -1; + + for(i=0; iNumBoxes; 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; iNumBoxes; 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; } diff -r dcfe4d2d4387 -r a2c334a71a6b general.h --- a/general.h Sun May 07 01:30:29 2006 +0200 +++ b/general.h Sun May 07 01:31:50 2006 +0200 @@ -8,7 +8,7 @@ #define CORNER '-' #define MANCANMOVE '+' -/* #define DEBUG */ +/*#define DEBUG */ enum { @@ -21,11 +21,12 @@ }; -enum logic +enum eBool { - TRUE=1, + TRUE=!0, FALSE=0 }; +typedef enum eBool Bool; struct Position { @@ -33,34 +34,55 @@ int y; }; +#define add_position2(a, b) {a.x += b.x; a.y += b.y;} +#define add_position3(dest, a, b) {(dest).x = (a).x + (b).x; \ + (dest).y = (a).y + (b).y;} + +enum box_freedom +{ + FREE=-1, + BLOCKED=-2 +}; + +struct tbox_free +{ + /* -1, without dependency in that direction. */ + /* -2, without dependency in that direction. */ + enum box_freedom dep_dir[4]; +}; + struct Map { - char Cells[MAX_Y][MAX_X]; - char cells_boxes[MAX_Y][MAX_X]; - char man_moves[MAX_Y][MAX_X]; + char Cells[MAX_Y][MAX_X]; /* Stores WALLs and PLATFORMs */ + char cells_boxes[MAX_Y][MAX_X]; /* Stores the box number in that cell */ + /* -1 is NO BOX there */ + char man_moves[MAX_Y][MAX_X]; /* Stores boxes, walls, MANCANMOVEs */ +/* int boxes[MAX_Y][MAX_X]; */ int SizeX, SizeY; struct Position Man; - int NumPlatforms; - int NumBoxesInPlatform; - struct Position Box[MAX_BOXES]; + int NumPlatforms; /* This and the next determine when the game */ + int NumBoxesInPlatform; /* finished */ int NumBoxes; + struct Position Box[MAX_BOXES]; /* The box positions */ + struct tbox_free box_deps[MAX_BOXES]; /* The dependencies for each + box*/ }; - enum e_direction { - DIR_LEFT, + DIR_DOWN, DIR_RIGHT, - DIR_DOWN, - DIR_UP + DIR_UP, + DIR_LEFT }; static const struct Position move_vectors[4] = { {0, 1}, + {1, 0}, {0, -1}, - {1, 0}, {-1, 0}}; +#define OPPOSITE_DIR(a) ((a+2)%4) struct BoxMove { @@ -80,6 +102,7 @@ void ShowMap (const struct Map *M); void init_os(); void PrintMove(struct BoxMove b); +void show_percent_and_map(); /* Functions related to map solution * algorithm.c */ diff -r dcfe4d2d4387 -r a2c334a71a6b os.c --- a/os.c Sun May 07 01:30:29 2006 +0200 +++ b/os.c Sun May 07 01:31:50 2006 +0200 @@ -123,18 +123,18 @@ } #endif - printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y); - printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms, + fprintf(stderr,"Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y); + fprintf(stderr,"Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms, Temp.NumBoxesInPlatform); } void PrintMove(const struct BoxMove b) { - printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y); + fprintf(stderr,"Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y); } -static void show_percent_callback(const int parameter) +void show_percent_and_map() { fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show, min_depth_period, max_depth_period); @@ -142,9 +142,12 @@ fflush(stderr); min_depth_period = MAX_STEPS; max_depth_period = 0; -#ifndef DEBUG +} + +static void show_percent_callback(const int parameter) +{ + show_percent_and_map(); alarm(ALARM_SECONDS); -#endif } static void program_alarm() @@ -164,5 +167,8 @@ void init_os() { +#ifndef DEBUG program_alarm(); +#endif } +