Improvement, managing the case a box depends ONLY on a blocked box (it will therefore be considered as blocked)
--- a/TODO Sun May 07 19:31:33 2006 +0200
+++ b/TODO Sun May 07 19:32:41 2006 +0200
@@ -1,6 +1,12 @@
-This algorithm:
-1. Add n-level dependencies control. How? I don't know
-2. Check for boxes depending on movement from never-reachable areas.
+This algorithm - to be done:
+2. Add n-level dependencies control. How? I don't know
+3. Check for boxes depending on movement from never-reachable areas.
+
+This algorithm - done:
+* Add checking for boxes dependant on blocked ones.
+ * It's not true that a box depending on a blocked SHOULD BE blocked. It may
+ also depend on some other to become free. The amount of dependencies must
+ be checked.
Other algorithm - endpoints:
We don't treat box moves as moves to next cell, but to moves until an endpoint.
--- a/algorithm.c Sun May 07 19:31:33 2006 +0200
+++ b/algorithm.c Sun May 07 19:32:41 2006 +0200
@@ -244,6 +244,7 @@
}
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,
@@ -357,12 +358,15 @@
/* 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;
@@ -371,9 +375,13 @@
/* 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 */
@@ -389,11 +397,19 @@
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;
@@ -458,15 +474,74 @@
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 */
@@ -486,20 +561,23 @@
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++)
{
@@ -574,7 +652,7 @@
/* 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 */