sokosol: comparison algorithm.c

equal deleted inserted replaced

-:7d212921dad4
+:e73048967870
 				/* Maybe we could update the percent here... */
 				continue;
 			}
 			actual_map = &maps[depth+1];
 #ifdef DEBUG		/* to be out */
+			actual_map = &maps[depth+1];
 			show_percent_and_map();
 #endif
 			/* the assert should be IN the function before,
 			   before OVERfilling new_movements */
 			assert(num_new_movements < MAX_MOVES);
 	} dep;
 	/* Free boxes' arrays */
 	struct
 	{
-		Bool box_is_free[MAX_BOXES]; /* This is only used in 'free' */
+		Bool tag[MAX_BOXES]; /*This is only used in 'free' & 'blocked'*/
 		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) */
+		tfree,	/* List of boxes of the loop (code) */
+		new_blocked,
+		tblocked,
+		blocked;
 	struct Position tpos;
 	Bool is_not_set_free;
 	/* Initialize to 0 the dependency structures */
 	memset((void *) &dep, 0, sizeof(dep));
 	new_free.n=0;
+	blocked.n=0;
+	new_blocked.n=0;
 	for(i=0; i<m->NumBoxes; i++)
 	{
 		new_free.box[i] = FALSE;
+		blocked.tag[i] = FALSE;
+		new_blocked.tag[i] = FALSE;
 	}
 	/* Let's fill the structure */
 	for(i=0; i<m->NumBoxes; i++)
 	{
 			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
+			{
+				blocked.tag[i] = TRUE;
+				blocked.box[blocked.n++] = i;
+				new_blocked.box[new_blocked.n++] = i;
+				/* This is not used actually
 				m->boxes[m->Box[i].y][m->Box[i].x] =
 					WALL;
-			*/
+				*/
+				/* The dependencies are checked. All blocked.*/
+				continue;
+			}
 		}
 		/* Let's take note of the dependencies */
 		is_not_set_free = TRUE;
 		for(d=0; d<4; d++)
 		{
 	/* ---------------- 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) */
+	/* Let's block those boxes dependant on blocked boxes.
+	   If some of those is not in a platform, the function exits TRUE. */
+	/* The new_blocked and blocked structures are filled fine */
+	while (new_blocked.n > 0)
+	{
+		/* Copy new_blocked into tblocked */
+		tblocked.n = new_blocked.n;
+		for(i=0; i<new_blocked.n; i++)
+			tblocked.box[i] = new_blocked.box[i];
+		new_blocked.n = 0;
+		for(i=0; i<tblocked.n; i++)
+		{
+			for(j=0; j<m->NumBoxes; j++)
+			{
+				if(dep.box[j][tblocked.box[i]])
+				{
+				/* The next line depends on the multiple-
+				   dependency improvement, still not done. */
+				   	/* Look for the dep direction */
+					for(d=0;d<4;d++)
+					{
+						if(m->box_deps[j].dep_dir[d]==
+						tblocked.box[i])
+							break;
+					}
+					/* d owns the dependency dir. */
+					/* Look if the other directions are
+					blocked */
+					if(m->box_deps[j].dep_dir[(d+1)%4] !=
+						BLOCKED ||
+					m->box_deps[j].dep_dir[(d+3)%4] !=
+						BLOCKED)
+						continue;
+					/* A dependancy on a blocked box found*/
+					if (!blocked.tag[j])
+					{
+						/* If the box is not already
+						known as blocked...*/
+						if (m->Cells[m->Box[j].y][m->Box[j].x] != PLATFORM)
+						{
+							return TRUE;
+						}
+						else
+						{
+							new_blocked.box[new_blocked.n++]=j;
+							/* The next line is not
+							really used
+							blocked.box[blocked.n++]=j;
+							*/
+							blocked.tag[j]=TRUE;
+						}
+					}
+				}
+			}
+		}
+	}
 	/* 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.tag[i] = FALSE;
 	free.n = new_free.n;
 	for(i=0; i<new_free.n; i++)
 	{
 		free.box[i] = new_free.box[i];
-		free.box_is_free[new_free.box[i]] = TRUE;
+		free.tag[new_free.box[i]] = TRUE;
 	}
 	/* KACXO-loop  */
 	while (new_free.n > 0)
 	{
 			{
 				/* The box j no more depends on
 				   the box tfree[i] */
 				if(dep.box[j][tfree.box[i]])
 				{
+					/* Remove the dependency */
 					dep.box[j][tfree.box[i]] = FALSE;
 					dep.ndeps[j]--;
 					assert(dep.ndeps[j] >= 0);
 					if (dep.ndeps[j] == 0 &&
-						!free.box_is_free[tfree.box[i]])
+						!free.tag[j])
 					{
 						new_free.box[new_free.n++]=j;
 						free.box[free.n++]=j;
+						free.tag[j]=TRUE;
 					}
 				}
 			}
 		}
 	}
 	/* 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++)
 				continue;
 			}
 			/* if there is Wall limit, we don't want to set box
 			   dependency */
-			if(m->box_deps[i].dep_dir[dir] == WALL)
+			if(m->box_deps[i].dep_dir[dir] == BLOCKED)
 				continue;
 			/* Put the box dependency in the list */
 			if(m->cells_boxes[n.y][n.x] >= 0)
 			{

changeset 21	e73048967870
parent 17	7c1e68c17c0e