--- a/algorithm.c Fri Feb 16 23:53:32 2007 +0100
+++ b/algorithm.c Sat Feb 17 15:14:30 2007 +0100
@@ -1,5 +1,6 @@
#include <assert.h>
#include <string.h>
+#include <stdlib.h>
#include "general.h"
/* Variables related to the showing of information by os */
@@ -425,97 +426,151 @@
}
-
-static int search_depth(struct Map maps[], int depth,
- struct BoxMove movements[],
- int num_movements, float percent, float total_percent)
+static void update_depth_counters(const int depth)
{
- 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++)
+struct Map *all_maps;
+struct BoxMove *all_movements; /* DEPTH movements of MAX_MOVES */
+int *all_mov_tries; /* The actual step in movements for every depth */
+int *all_mov_max; /* Maximum of movements per all_movement element */
+float *percent;
+float *percent_part;
+int depth;
+
+int search_loop(const struct Map *origin)
+{
+ int found; /* bool */
+
+ all_maps = malloc(sizeof(*all_maps) * (MAX_STEPS+1));
+ all_movements = malloc(sizeof(*all_movements)*MAX_MOVES*(MAX_STEPS+1));
+ all_mov_tries = malloc(sizeof(*all_mov_tries)*(MAX_STEPS+1));
+ all_mov_max = malloc(sizeof(*all_mov_max)*(MAX_STEPS+1));
+ percent = malloc(sizeof(*percent)*(MAX_STEPS+1));
+ percent_part = malloc(sizeof(*percent)*(MAX_STEPS+1));
+
+
+ if (load_state())
+ {
+ --depth;
+ if (all_mov_tries[depth] != 0)
+ all_mov_tries[depth] = 0;
+ } else
{
- CopyMap(m, &maps[depth]);
- force_move_box(m, movements[i]);
- if (m->NumPlatforms == m->NumBoxesInPlatform)
+ depth = 0;
+ CopyMap(&all_maps[0], origin);
+ all_mov_max[0] = get_box_movements(&all_maps[0], &all_movements[0]);
+ assert(all_mov_max[0] < MAX_MOVES);
+ assert(all_mov_max[0] > 0);
+ percent[0] = 0.;
+ percent_part[0] = 100.;
+ all_mov_tries[0] = 0;
+ }
+
+
+ found = 0;
+ do
+ {
+ struct BoxMove *new_movements = &all_movements[(depth+1)*MAX_MOVES];
+ struct BoxMove *movements = &all_movements[depth*MAX_MOVES];
+ int num_movements = all_mov_max[depth];
+ int *num_new_movements = &all_mov_max[depth+1];
+ int *step = &all_mov_tries[depth];
+ struct Map *new_map = &all_maps[depth+1];
+
+ update_depth_counters(depth);
+
+ percent_part[depth+1] = percent_part[depth] / num_movements;
+
+ CopyMap(new_map, &all_maps[depth]);
+
+ /* DEBUG */
+#if DEBUG
+ ShowMap(new_map);
+ show_tries(depth);
+ printf("Nummovs[%i]: %i\n", depth, num_movements);
+ printf("Step[%i]: %i\n", depth, *step);
+#endif
+
+ /* Now four things can happen:
+ * - look for depth + 1
+ * - keep looking for movements in depth
+ * - go one depth back.
+ * - solve the puzle */
+
+ /* Go one depth back */
+ if (*step >= num_movements)
{
- PrintMove(movements[i]);
- actual_map = &maps[depth+1];
- show_percent_and_map();
- return 0;
+ --depth;
+ continue;
}
- if (is_new_map(maps, depth+1))
+ force_move_box(new_map, movements[(*step)]);
+
+ ++(*step);
+
+ /* Solve the puzzle */
+ if (new_map->NumPlatforms == new_map->NumBoxesInPlatform)
{
- num_new_movements = get_box_movements(m, new_movements);
- assert(num_new_movements < MAX_MOVES);
+ PrintMoves(all_movements, all_mov_tries, depth+1);
+ actual_map = &all_maps[depth+1];
+ show_percent_and_map();
+ save_state();
+ found = 1;
+ }
+
+ if (is_new_map(all_maps, depth+1))
+ {
+ *num_new_movements =
+ get_box_movements(new_map, new_movements);
+ assert(*num_new_movements < MAX_MOVES);
}
else
- num_new_movements = 0;
+ *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_and_map();
-#endif
-
- }
- else
+ percent[depth] = percent[depth] + percent_part[depth+1];
+ percent_to_show = percent[depth];
+
+ /* Keep looking for movements in depth */
+ if (*num_new_movements == 0)
{
- 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]);
- actual_map = &maps[depth+1];
- show_percent_and_map();
- return 0;
- }
- }
+ depth_to_show = depth;
+ actual_map = &all_maps[depth];
+ continue;
}
- }
- return 1;
+
+ /* Look for depth + 1*/
+ if (depth+1 < MAX_STEPS)
+ {
+ percent[depth+1] = percent[depth];
+ all_mov_tries[depth+1] = 0;
+ ++depth;
+ }
+ } while(!found && depth >= 0);
+ free(all_maps);
+ free(all_movements);
+ free(all_mov_tries);
+ free(all_mov_max);
+
+ return found;
}
int solve_map(const struct Map *origin)
{
- struct Map *maps;
struct BoxMove new_movements[MAX_MOVES];
int num_new_movements;
int ret;
- maps = malloc(sizeof(*maps) * (MAX_STEPS+1));
-
- 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();
- ret = search_depth(maps, 0, new_movements,
- num_new_movements, 100. / num_new_movements,
- 0);
- free(maps);
+ ret = search_loop(origin);
+
return ret;
}