--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/algorithm.c Sat May 06 00:34:04 2006 +0200
@@ -0,0 +1,537 @@
+#include <assert.h>
+#include <string.h>
+#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;
+
+#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
+
+/*
+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)
+{
+ struct Position opposite1, opposite2;
+
+ /* The wall corners must exist */
+ opposite1.x = -mov.y;
+ opposite1.y = -mov.x;
+ opposite2.x = mov.y;
+ opposite2.y = mov.x;
+
+#ifdef DEBUG
+ ShowMap(m);
+#endif
+
+ /* Test the first corner */
+ if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]
+ == WALL)
+ {
+ /* 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;
+ }
+ }
+
+ /* Test the second corner */
+ if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]
+ == WALL)
+ {
+ /* 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;
+ }
+ }
+
+ 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;
+
+ /* 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;
+ }
+ 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[])
+{
+ struct Position pos[MAX_MOVES];
+ struct Position new_pos[MAX_MOVES];
+ int NumMoves, NewMoves;
+ 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++)
+ {
+ 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] = BOX;
+ m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
+ }
+
+ 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++;
+ }
+ else if (*next_cell == BOX)
+ {
+
+ /* Check if the box is movable */
+
+ 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++;
+ }
+ }
+
+ }
+
+ }
+ }
+ }
+
+ return num_box_movements;
+}
+
+static void force_move_box(struct Map *m, 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 int is_new_map(struct Map maps[], int depth)
+{
+ struct Map *m;
+ int i;
+
+ m = &maps[depth];
+
+ for(i=0; i<max_depth; i++)
+ {
+ /* No l'hem de comparar amb ell mateix */
+ if (i == depth)
+ continue;
+
+ if (m->NumBoxesInPlatform != maps[i].NumBoxesInPlatform)
+ continue;
+ else
+ {
+ if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes))
+ continue;
+ }
+ return FALSE;
+ }
+ return TRUE;
+}
+
+
+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++)
+ {
+ CopyMap(m, &maps[depth]);
+ force_move_box(m, movements[i]);
+ if (m->NumPlatforms == m->NumBoxesInPlatform)
+ {
+ PrintMove(movements[i]);
+ return 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)
+ {
+ 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)
+ {
+ if(search_depth(maps, depth+1, new_movements,
+ num_new_movements, next_percent,
+ total_percent + next_percent*i) == 0)
+ {
+ PrintMove(movements[i]);
+ return 0;
+ }
+ }
+ }
+ }
+ return 1;
+}
+
+
+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);
+
+ num_new_movements = get_box_movements(&maps[0], new_movements);
+ assert(num_new_movements < MAX_MOVES);
+ assert(num_new_movements > 0);
+
+ init_os();
+
+ return search_depth(maps, 0, new_movements,
+ num_new_movements, 100. / num_new_movements,
+ 0);
+
+}