summaryrefslogtreecommitdiff
path: root/dbox.c
diff options
context:
space:
mode:
Diffstat (limited to 'dbox.c')
-rw-r--r--dbox.c162
1 files changed, 90 insertions, 72 deletions
diff --git a/dbox.c b/dbox.c
index aadacb7..aff6b69 100644
--- a/dbox.c
+++ b/dbox.c
@@ -68,12 +68,18 @@ typedef enum {SPACE_GL=' ',
#define DIR_RIGHT 2
#define DIR_DOWN 3
-static int g_move_dir[4] = {-1, -1, 1, 1};
+typedef struct
+{
+ int x;
+ int y;
+} pos_t;
+
+static const pos_t g_move_dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
typedef struct state_t
{
- int player;
- int *box;
+ pos_t player;
+ pos_t *box;
int path;
int dir;
int pushed;
@@ -93,19 +99,19 @@ typedef struct
int height;
int no_targets;
int no_boxes;
- int *target;
+ pos_t *target;
glyph_t *map;
state_t *state;
} level_t;
#define AT(l,x,y) ((l)->map[(l)->width*(y)+(x)])
-#define ATP(l,p) ((l)->map[p])
/* State caches
*/
typedef struct cache_t
{
const state_t *state;
+ map_t *map;
struct cache_t *next;
} cache_t;
@@ -182,11 +188,11 @@ static void *Copy(const void *p_source, size_t p_size)
}
-static const int *FindPos(const int *p_poslist, int p_no, int p_p)
+static const pos_t *FindPos(const pos_t *p_poslist, int p_no, int p_x, int p_y)
{
while(p_no--)
{
- if (*p_poslist == p_p)
+ if (p_poslist->x == p_x && p_poslist->y == p_y)
{
return p_poslist;
}
@@ -198,11 +204,11 @@ static const int *FindPos(const int *p_poslist, int p_no, int p_p)
}
-static int *FindPosForUpdate(int *p_poslist, int p_no, int p_p)
+static pos_t *FindPosForUpdate(pos_t *p_poslist, int p_no, int p_x, int p_y)
{
while(p_no--)
{
- if (*p_poslist == p_p)
+ if (p_poslist->x == p_x && p_poslist->y == p_y)
{
return p_poslist;
}
@@ -221,7 +227,9 @@ static const char *GetLine(FILE *p_fp)
static char s[1024];
size_t l;
- if (!fgets(s, sizeof s, p_fp))
+ fgets(s, sizeof s, p_fp);
+
+ if (feof(p_fp))
{
return NULL;
}
@@ -356,7 +364,8 @@ static level_t *Load(const char *p_path)
case BOX_TARGET_GL:
case TARGET_GL:
AT(new,x,y) = SPACE_GL;
- new->target[tno] = x + y * new->width;
+ new->target[tno].x = x;
+ new->target[tno].y = y;
tno++;
/* NOTE: Runs into following case for BOX_TARGET_GL
@@ -368,7 +377,8 @@ static level_t *Load(const char *p_path)
case BOX_GL:
AT(new,x,y) = SPACE_GL;
- new->state->box[bno] = x + y * new->width;
+ new->state->box[bno].x = x;
+ new->state->box[bno].y = y;
bno++;
break;
@@ -382,7 +392,8 @@ static level_t *Load(const char *p_path)
}
AT(new,x,y) = SPACE_GL;
- new->state->player = x + y * new->width;
+ new->state->player.x = x;
+ new->state->player.y = y;
break;
default:
@@ -429,28 +440,24 @@ static void Display(const level_t *p_level, const state_t *p_state)
static char GetGlyph(const level_t *p_level, const state_t *p_state,
int p_x, int p_y)
{
- int p;
-
- p = p_x + p_y * p_level->width;
-
if (AT(p_level, p_x, p_y) == WALL_GL)
{
return WALL_GL;
}
- else if (FindPos(&p_state->player, 1, p))
+ else if (FindPos(&p_state->player, 1, p_x, p_y))
{
return PLAYER_GL;
}
- else if (FindPos(p_state->box, p_level->no_boxes, p) &&
- FindPos(p_level->target, p_level->no_targets, p))
+ else if (FindPos(p_state->box, p_level->no_boxes, p_x, p_y) &&
+ FindPos(p_level->target, p_level->no_targets, p_x, p_y))
{
return BOX_TARGET_GL;
}
- else if (FindPos(p_state->box, p_level->no_boxes, p))
+ else if (FindPos(p_state->box, p_level->no_boxes, p_x, p_y))
{
return BOX_GL;
}
- else if (FindPos(p_level->target, p_level->no_targets, p))
+ else if (FindPos(p_level->target, p_level->no_targets, p_x, p_y))
{
return TARGET_GL;
}
@@ -483,6 +490,7 @@ static void ClearStates(void)
cache_t *p;
p = g_cache[f]->next;
+ free(g_cache[f]->map);
free(g_cache[f]);
g_cache[f] = p;
}
@@ -502,13 +510,11 @@ static map_t *CreateMap(const level_t *p_level, const state_t *p_state)
m[f] = 0;
}
- m[p_state->player / p_level->width] =
- 0x01llu << ((p_state->player % p_level->width) * 2);
+ m[p_state->player.y] = 0x01llu << (p_state->player.x * 2);
for(f = 0; f < p_level->no_boxes; f++)
{
- m[p_state->box[f] / p_level->width] |=
- 0x10llu << ((p_state->box[f] % p_level->width) * 2);
+ m[p_state->box[f].y] |= 0x10llu << (p_state->box[f].x * 2);
}
return m;
@@ -536,7 +542,7 @@ static map_t CreateHash(const level_t *p_level, const state_t *p_state)
m = CreateMap(p_level, p_state);
- hash = p_state->player;
+ hash = p_state->player.x * p_state->player.y;
for(f = 0; f < p_level->height; f++)
{
@@ -579,31 +585,32 @@ static void DumpCacheDistribution(void)
static int AddNewState(const level_t *p_level, const state_t *p_state)
{
cache_t *p;
+ map_t *map;
map_t hash;
hash = p_state->hash % CACHE_SIZE;
p = g_cache[hash];
+ map = CreateMap(p_level, p_state);
while(p)
{
- if (p_state->player == p->state->player)
+ if (p_state->player.x == p->state->player.x &&
+ p_state->player.y == p->state->player.y)
{
int f;
map_t check;
- check = FALSE;
+ check = 0;
- for(f = 0; f < p_level->no_boxes && !check; f++)
+ for(f = 0; f < p_level->height; f++)
{
- if (!FindPos(p->state->box, p_level->no_boxes, p_state->box[f]))
- {
- check = TRUE;
- }
+ check |= (map[f] ^ p->map[f]);
}
- if (!check)
+ if (check == 0)
{
+ free(map);
return FALSE;
}
}
@@ -614,6 +621,7 @@ static int AddNewState(const level_t *p_level, const state_t *p_state)
p = Grab(sizeof *p);
p->state = p_state;
+ p->map = map;
p->next = g_cache[hash];
g_cache[hash] = p;
@@ -647,11 +655,13 @@ static int CheckImpossible(const level_t *p_level, const state_t *p_state)
for(f = 0; f < p_level->no_boxes; f++)
{
- int p;
+ int x;
+ int y;
- p = p_state->box[f];
+ x = p_state->box[f].x;
+ y = p_state->box[f].y;
- if (!FindPos(p_level->target, p_level->no_targets, p))
+ if (!FindPos(p_level->target, p_level->no_targets, x, y))
{
int d;
int any_move;
@@ -663,17 +673,21 @@ static int CheckImpossible(const level_t *p_level, const state_t *p_state)
for(d = 0; d < 4 && !any_move; d++)
{
- int np;
+ int nx;
+ int ny;
- np = p + g_move_dir[d];
+ nx = x + g_move_dir[d].x;
+ ny = y + g_move_dir[d].y;
- if (ATP(p_level, np) != WALL_GL)
+ if (AT(p_level, nx, ny) != WALL_GL)
{
- int op;
+ int ox;
+ int oy;
- op = p + g_move_dir[(d+2)%4];
+ ox = x + g_move_dir[(d+2)%4].x;
+ oy = y + g_move_dir[(d+2)%4].y;
- if (ATP(p_level, op) != WALL_GL)
+ if (AT(p_level, ox, oy) != WALL_GL)
{
any_move=TRUE;
}
@@ -682,19 +696,17 @@ static int CheckImpossible(const level_t *p_level, const state_t *p_state)
if (!any_move)
{
- NoMoveReason("Couldn't push block at %d, %d",
- p%p_level->width, p/p_level->width);
+ NoMoveReason("Couldn't push block at %d,%d", x, y);
return TRUE;
}
/* Four blocks together is impossible
*/
- if (FindPos(p_state->box, p_level->no_boxes, p+1) &&
- FindPos(p_state->box, p_level->no_boxes, p+p_level->width) &&
- FindPos(p_state->box, p_level->no_boxes, p+p_level->width+1))
+ if (FindPos(p_state->box, p_level->no_boxes, x+1, y) &&
+ FindPos(p_state->box, p_level->no_boxes, x, y+1) &&
+ FindPos(p_state->box, p_level->no_boxes, x+1, y+1))
{
- NoMoveReason("Group of 4 boxes at %d, %d",
- p%p_level->width, p/p_level->width);
+ NoMoveReason("Group of 4 boxes at %d,%d", x, y);
return TRUE;
}
}
@@ -709,40 +721,44 @@ static state_t *CreateState(int p_dir, int p_must_push,
int p_check_possible)
{
state_t *new;
- const int *p;
- int np;
+ const pos_t *p;
+ int x,y;
int push;
- int px;
+ int dx,dy;
- push = FALSE;
+ dx = g_move_dir[p_dir].x;
+ dy = g_move_dir[p_dir].y;
- px = g_move_dir[p_dir];
+ push = FALSE;
- np = p_state->player + px;
+ x = p_state->player.x + dx;
+ y = p_state->player.y + dy;
/* Check for walls
*/
- if (ATP(p_level, np) == WALL_GL)
+ if (AT(p_level, x, y) == WALL_GL)
{
return NULL;
}
/* Check for boxes
*/
- if ((p = FindPos(p_state->box, p_level->no_boxes, np)))
+ if ((p = FindPos(p_state->box, p_level->no_boxes, x, y)))
{
- int bp;
+ int bx;
+ int by;
/* Can the box be pushed?
*/
- bp = *p+px;
+ bx = p->x+dx;
+ by = p->y+dy;
- if (ATP(p_level, bp) == WALL_GL)
+ if (AT(p_level, bx, by) == WALL_GL)
{
return NULL;
}
- if (FindPos(p_state->box, p_level->no_boxes, bp))
+ if (FindPos(p_state->box, p_level->no_boxes, bx, by))
{
return NULL;
}
@@ -756,17 +772,19 @@ static state_t *CreateState(int p_dir, int p_must_push,
}
new = Grab(sizeof *new);
- new->box = Copy(p_state->box, sizeof(int) * p_level->no_boxes);
+ new->box = Copy(p_state->box, sizeof(pos_t) * p_level->no_boxes);
- new->player = np;
+ new->player.x = x;
+ new->player.y = y;
if (push)
{
- int *pd;
+ pos_t *pd;
- pd = FindPosForUpdate(new->box, p_level->no_boxes, np);
+ pd = FindPosForUpdate(new->box, p_level->no_boxes, x, y);
- *pd += px;
+ pd->x += dx;
+ pd->y += dy;
/* (Very) basic checks to see if the move has made the level impossible
*/
@@ -887,7 +905,10 @@ static void SubSolve(const level_t *p_level, state_t *p_state, int p_depth,
for(f = 0; f < p_level->no_targets && ok; f++)
{
- if (!FindPos(s->box, p_level->no_boxes, p_level->target[f]))
+ if (!FindPos(s->box,
+ p_level->no_boxes,
+ p_level->target[f].x,
+ p_level->target[f].y))
{
ok = FALSE;
}
@@ -1400,9 +1421,6 @@ int main(int argc, char *argv[])
}
else
{
- g_move_dir[DIR_UP] = -level->width;
- g_move_dir[DIR_DOWN] = level->width;
-
if (interact)
{
Interactive(level, play, check);