algorithm.c
changeset 28 cd27cb410375
parent 26 95fccfcbd04c
--- 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())
 	{
-		CopyMap(m, &maps[depth]);
-		force_move_box(m, movements[i]);
-		if (m->NumPlatforms == m->NumBoxesInPlatform)
+		--depth;
+		if (all_mov_tries[depth] != 0)
+			all_mov_tries[depth] = 0;
+	} else
+	{
+		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[depth] = percent[depth] + percent_part[depth+1];
+		percent_to_show = percent[depth];
+
+		/* Keep looking for movements in depth */
+		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
-	
+			actual_map = &all_maps[depth];
+			continue;
 		}
-		else
+
+		/* Look for depth + 1*/
+		if (depth+1 < MAX_STEPS)
 		{
-			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;
-				}
-			}
+			percent[depth+1] = percent[depth];
+			all_mov_tries[depth+1] = 0;
+			++depth;
 		}
-	}
-	return 1;
+	} 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;
 }