Updated to store positions as a single int. Didn't produce the hoped for

speed up.

1 files 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);