From 241cf0478e2335744586efa5c5a283c78b9b7cdc Mon Sep 17 00:00:00 2001 From: Ian C Date: Mon, 8 May 2017 14:08:52 +0000 Subject: Updated to store positions as a single int. Didn't produce the hoped for speed up. --- dbox.c | 141 ++++++++++++++++++++++++++++++----------------------------------- 1 file changed, 64 insertions(+), 77 deletions(-) diff --git a/dbox.c b/dbox.c index aff6b69..b47fcf1 100644 --- a/dbox.c +++ b/dbox.c @@ -68,18 +68,12 @@ typedef enum {SPACE_GL=' ', #define DIR_RIGHT 2 #define DIR_DOWN 3 -typedef struct -{ - int x; - int y; -} pos_t; - -static const pos_t g_move_dir[4]={{-1,0},{0,-1},{1,0},{0,1}}; +static int g_move_dir[4] = {-1, -1, 1, 1}; typedef struct state_t { - pos_t player; - pos_t *box; + int player; + int *box; int path; int dir; int pushed; @@ -99,12 +93,13 @@ typedef struct int height; int no_targets; int no_boxes; - pos_t *target; + int *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 */ @@ -188,11 +183,11 @@ static void *Copy(const void *p_source, size_t p_size) } -static const pos_t *FindPos(const pos_t *p_poslist, int p_no, int p_x, int p_y) +static const int *FindPos(const int *p_poslist, int p_no, int p_p) { while(p_no--) { - if (p_poslist->x == p_x && p_poslist->y == p_y) + if (*p_poslist == p_p) { return p_poslist; } @@ -204,11 +199,11 @@ static const pos_t *FindPos(const pos_t *p_poslist, int p_no, int p_x, int p_y) } -static pos_t *FindPosForUpdate(pos_t *p_poslist, int p_no, int p_x, int p_y) +static int *FindPosForUpdate(int *p_poslist, int p_no, int p_p) { while(p_no--) { - if (p_poslist->x == p_x && p_poslist->y == p_y) + if (*p_poslist == p_p) { return p_poslist; } @@ -364,8 +359,7 @@ 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 = x; - new->target[tno].y = y; + new->target[tno] = x + y * new->width; tno++; /* NOTE: Runs into following case for BOX_TARGET_GL @@ -377,8 +371,7 @@ static level_t *Load(const char *p_path) case BOX_GL: AT(new,x,y) = SPACE_GL; - new->state->box[bno].x = x; - new->state->box[bno].y = y; + new->state->box[bno] = x + y * new->width; bno++; break; @@ -392,8 +385,7 @@ static level_t *Load(const char *p_path) } AT(new,x,y) = SPACE_GL; - new->state->player.x = x; - new->state->player.y = y; + new->state->player = x + y * new->width; break; default: @@ -440,24 +432,28 @@ 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_x, p_y)) + else if (FindPos(&p_state->player, 1, p)) { return PLAYER_GL; } - 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)) + else if (FindPos(p_state->box, p_level->no_boxes, p) && + FindPos(p_level->target, p_level->no_targets, p)) { return BOX_TARGET_GL; } - else if (FindPos(p_state->box, p_level->no_boxes, p_x, p_y)) + else if (FindPos(p_state->box, p_level->no_boxes, p)) { return BOX_GL; } - else if (FindPos(p_level->target, p_level->no_targets, p_x, p_y)) + else if (FindPos(p_level->target, p_level->no_targets, p)) { return TARGET_GL; } @@ -510,11 +506,13 @@ static map_t *CreateMap(const level_t *p_level, const state_t *p_state) m[f] = 0; } - m[p_state->player.y] = 0x01llu << (p_state->player.x * 2); + m[p_state->player / p_level->width] = + 0x01llu << ((p_state->player % p_level->width) * 2); for(f = 0; f < p_level->no_boxes; f++) { - m[p_state->box[f].y] |= 0x10llu << (p_state->box[f].x * 2); + m[p_state->box[f] / p_level->width] |= + 0x10llu << ((p_state->box[f] % p_level->width) * 2); } return m; @@ -542,7 +540,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.x * p_state->player.y; + hash = p_state->player; for(f = 0; f < p_level->height; f++) { @@ -595,8 +593,7 @@ static int AddNewState(const level_t *p_level, const state_t *p_state) while(p) { - if (p_state->player.x == p->state->player.x && - p_state->player.y == p->state->player.y) + if (p_state->player == p->state->player) { int f; map_t check; @@ -655,13 +652,11 @@ static int CheckImpossible(const level_t *p_level, const state_t *p_state) for(f = 0; f < p_level->no_boxes; f++) { - int x; - int y; + int p; - x = p_state->box[f].x; - y = p_state->box[f].y; + p = p_state->box[f]; - if (!FindPos(p_level->target, p_level->no_targets, x, y)) + if (!FindPos(p_level->target, p_level->no_targets, p)) { int d; int any_move; @@ -673,21 +668,17 @@ static int CheckImpossible(const level_t *p_level, const state_t *p_state) for(d = 0; d < 4 && !any_move; d++) { - int nx; - int ny; + int np; - nx = x + g_move_dir[d].x; - ny = y + g_move_dir[d].y; + np = p + g_move_dir[d]; - if (AT(p_level, nx, ny) != WALL_GL) + if (ATP(p_level, np) != WALL_GL) { - int ox; - int oy; + int op; - ox = x + g_move_dir[(d+2)%4].x; - oy = y + g_move_dir[(d+2)%4].y; + op = p + g_move_dir[(d+2)%4]; - if (AT(p_level, ox, oy) != WALL_GL) + if (ATP(p_level, op) != WALL_GL) { any_move=TRUE; } @@ -696,17 +687,19 @@ static int CheckImpossible(const level_t *p_level, const state_t *p_state) if (!any_move) { - NoMoveReason("Couldn't push block at %d,%d", x, y); + NoMoveReason("Couldn't push block at %d, %d", + p%p_level->width, p/p_level->width); return TRUE; } /* Four blocks together is impossible */ - 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)) + 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)) { - NoMoveReason("Group of 4 boxes at %d,%d", x, y); + NoMoveReason("Group of 4 boxes at %d, %d", + p%p_level->width, p/p_level->width); return TRUE; } } @@ -721,44 +714,40 @@ static state_t *CreateState(int p_dir, int p_must_push, int p_check_possible) { state_t *new; - const pos_t *p; - int x,y; + const int *p; + int np; int push; - int dx,dy; - - dx = g_move_dir[p_dir].x; - dy = g_move_dir[p_dir].y; + int px; push = FALSE; - x = p_state->player.x + dx; - y = p_state->player.y + dy; + px = g_move_dir[p_dir]; + + np = p_state->player + px; /* Check for walls */ - if (AT(p_level, x, y) == WALL_GL) + if (ATP(p_level, np) == WALL_GL) { return NULL; } /* Check for boxes */ - if ((p = FindPos(p_state->box, p_level->no_boxes, x, y))) + if ((p = FindPos(p_state->box, p_level->no_boxes, np))) { - int bx; - int by; + int bp; /* Can the box be pushed? */ - bx = p->x+dx; - by = p->y+dy; + bp = *p+px; - if (AT(p_level, bx, by) == WALL_GL) + if (ATP(p_level, bp) == WALL_GL) { return NULL; } - if (FindPos(p_state->box, p_level->no_boxes, bx, by)) + if (FindPos(p_state->box, p_level->no_boxes, bp)) { return NULL; } @@ -772,19 +761,17 @@ static state_t *CreateState(int p_dir, int p_must_push, } new = Grab(sizeof *new); - new->box = Copy(p_state->box, sizeof(pos_t) * p_level->no_boxes); + new->box = Copy(p_state->box, sizeof(int) * p_level->no_boxes); - new->player.x = x; - new->player.y = y; + new->player = np; if (push) { - pos_t *pd; + int *pd; - pd = FindPosForUpdate(new->box, p_level->no_boxes, x, y); + pd = FindPosForUpdate(new->box, p_level->no_boxes, np); - pd->x += dx; - pd->y += dy; + *pd += px; /* (Very) basic checks to see if the move has made the level impossible */ @@ -905,10 +892,7 @@ 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].x, - p_level->target[f].y)) + if (!FindPos(s->box, p_level->no_boxes, p_level->target[f])) { ok = FALSE; } @@ -1421,6 +1405,9 @@ 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); -- cgit v1.2.3