summaryrefslogtreecommitdiff
path: root/dbox.c
diff options
context:
space:
mode:
Diffstat (limited to 'dbox.c')
-rw-r--r--dbox.c1016
1 files changed, 569 insertions, 447 deletions
diff --git a/dbox.c b/dbox.c
index ac00bc3..428f518 100644
--- a/dbox.c
+++ b/dbox.c
@@ -20,13 +20,16 @@
-------------------------------------------------------------------------
*/
-static const char cvs_id[]="$Id$";
+static const char ident[]="$Id$";
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <time.h>
+#include <limits.h>
+#include <ctype.h>
+#include <signal.h>
#if (USECURSES == ncurses)
#include <ncurses.h>
@@ -34,6 +37,8 @@ static const char cvs_id[]="$Id$";
#include <curses.h>
#endif
+/* Global macros
+*/
#ifndef TRUE
#define TRUE 1
#endif
@@ -42,34 +47,21 @@ static const char cvs_id[]="$Id$";
#define FALSE 0
#endif
-static const int DEBUG=TRUE;
-static char *name;
-
-/* Stop the program once this much memory is allocated.
- Set to -1 to disable the check
-*/
-#define MAXMB -1
+#define MAX_ROUTE 8192
-#define MEGABYTE (1024*1024)
/* ---------------------------------------- TYPES
*/
-typedef signed char PosInt;
-typedef unsigned char Byte;
-typedef Byte Bool;
-
-typedef char Route[1024];
+typedef unsigned long long map_t;
+typedef unsigned long hash_t;
+typedef char route_t[MAX_ROUTE+1];
typedef enum {SPACE_GL=' ',
WALL_GL='#',
PLAYER_GL='@',
BOX_GL='B',
TARGET_GL='.',
- BOX_TARGET_GL='X'} Glyph;
-
-typedef enum {SPACE, WALL} MapChar;
-
-typedef enum {QUIET,CSV,VERBOSE} LogMode;
+ BOX_TARGET_GL='X'} glyph_t;
#define DIR_NONE -1
#define DIR_LEFT 0
@@ -79,138 +71,174 @@ typedef enum {QUIET,CSV,VERBOSE} LogMode;
typedef struct
{
- PosInt x;
- PosInt y;
-} Pos;
+ int x;
+ int y;
+} pos_t;
-static const Pos move_dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
+static const pos_t g_move_dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
-typedef struct State
+typedef struct state_t
{
- Pos player;
- Pos *box;
- Bool path;
- Byte dir;
- Bool pushed;
- int hash;
- struct State *left;
- struct State *right;
- struct State *up;
- struct State *down;
- struct State *parent;
- struct State *next;
-} State;
+ pos_t player;
+ pos_t *box;
+ int path;
+ int dir;
+ int pushed;
+ hash_t hash;
+ struct state_t *left;
+ struct state_t *right;
+ struct state_t *up;
+ struct state_t *down;
+ struct state_t *parent;
+ struct state_t *next;
+} state_t;
typedef struct
{
char *name;
int width;
int height;
- int no;
- Pos *target;
- MapChar *map;
- State *state;
-} Level;
+ int no_targets;
+ int no_boxes;
+ pos_t *target;
+ glyph_t *map;
+ state_t *state;
+} level_t;
-#define STATE_HASH 0x10000
+#define AT(l,x,y) ((l)->map[(l)->width*(y)+(x)])
-typedef struct StateMap
+/* State caches
+*/
+typedef struct cache_t
{
- State *s;
- struct StateMap *next;
-} StateMap;
+ const state_t *state;
+ map_t *map;
+ struct cache_t *next;
+} cache_t;
-static StateMap *state_map[STATE_HASH]={NULL};
-static int state_map_no=0;
+#define CACHE_SIZE 65071
-#define AT(l,x,y) ((l)->map[(l)->width*(y)+(x)])
+static unsigned long long g_cached_states;
+static cache_t *g_cache[CACHE_SIZE];
+
+/* Global constants and calculated constants
+*/
+static const char *g_name;
+static const int g_MAX_WIDTH = sizeof(map_t) * CHAR_BIT / 2;
+
+/* Signals
+*/
+static sig_atomic_t g_signal;
/* ---------------------------------------- PROTOS
*/
-static void *Grab(size_t l);
+static void *Grab(size_t p_size);
+static void *Copy(const void *p_source, size_t p_size);
+
+static void Interactive(const level_t *p_level, int p_play);
+
+static level_t *Load(const char *p_path);
+
+static void FreeLevel(level_t *p_level);
-static void Interactive(Level *l, int play);
+static void Display(const level_t *p_level, const state_t *p_state);
-static Level *Load(const char *path);
-static void FreeLevel(Level *l);
-static void Display(Level *level, State *state);
-static char GetGlyph(Level *level, State *state, int x, int y);
-static State *CreateState(Byte dir, Bool must_push, Level *l, State *s,
- Bool check_possible);
-static void Solve(Level *level, Route route, int max_depth, LogMode log);
+static char GetGlyph(const level_t *p_level, const state_t *p_state,
+ int p_x, int p_y);
+
+static state_t *CreateState(int p_dir, int p_must_push,
+ const level_t *p_level, const state_t *p_state,
+ int p_check_possible);
+
+static void Solve(const level_t *p_level, route_t p_route,
+ int p_max_depth, int p_verbose);
+
+
+/* ---------------------------------------- SIGNAL HANDLERS
+*/
+static void SigHandler(int i)
+{
+ g_signal = 1;
+ signal(SIGUSR1, SigHandler);
+}
/* ---------------------------------------- MAIN
*/
int main(int argc, char *argv[])
{
- int interact=FALSE;
- int play=FALSE;
+ int interact = FALSE;
+ int play = FALSE;
int base;
int f;
- LogMode mode=VERBOSE;
+ int verbose = TRUE;
- name=argv[0];
+ g_name = argv[0];
if (argc<2)
{
- fprintf(stderr,"%s: usage %s [-i|-p] file [file2 ...]\n",name,name);
+ fprintf(stderr,"%s: usage %s [-i|-p] file [file2 ...]\n",
+ g_name, g_name);
return EXIT_FAILURE;
}
if (strcmp(argv[1],"-i")==0)
{
- interact=TRUE;
- base=2;
+ interact = TRUE;
+ base = 2;
}
else if (strcmp(argv[1],"-p")==0)
{
- interact=TRUE;
- play=TRUE;
- base=2;
- }
- else if (strcmp(argv[1],"-c")==0)
- {
- interact=FALSE;
- mode=CSV;
- base=2;
+ interact = TRUE;
+ play = TRUE;
+ base = 2;
}
else
{
- base=1;
+ base = 1;
}
- if (argc<=base)
+ if (argc <= base)
{
- fprintf(stderr,"%s: usage %s [-c|-i|-p] file [file2 ...]\n",name,name);
+ fprintf(stderr,"%s: usage %s [-i|-p] file [file2 ...]\n",
+ g_name, g_name);
return EXIT_FAILURE;
}
- for(f=base;f<argc;f++)
+ signal(SIGUSR1, SigHandler);
+
+ for(f = base; f < argc; f++)
{
- Route route;
- Level *level;
+ route_t route;
+ level_t *level;
if (!(level=Load(argv[f])))
{
- fprintf(stderr,"%s: %s could not be read\n",name,argv[f]);
+ fprintf(stderr,"%s: %s could not be read\n", g_name, argv[f]);
}
else
{
if (interact)
{
- Interactive(level,play);
+ Interactive(level, play);
}
else
{
- printf("Solving %s\n\n",level->name);
+ printf("Solving %s\n\n", level->name);
- Display(level,level->state);
+ Display(level, level->state);
- Solve(level,route,999,mode);
+ Solve(level, route, MAX_ROUTE, verbose);
- printf("\nRoute = '%s'\n",route);
+ if (route[0])
+ {
+ printf("\nRoute = '%s'\n",route);
+ }
+ else
+ {
+ printf("\nNo solution found!\n");
+ }
}
FreeLevel(level);
@@ -223,75 +251,55 @@ int main(int argc, char *argv[])
/* ---------------------------------------- UTIL
*/
-static size_t grab_tot=0;
-static int grab_last_mb=0;
-static int grab_mb=0;
-
-static void *Grab(size_t l)
+static void *Grab(size_t p_size)
{
- size_t *p;
+ void *new;
- p=malloc(l+sizeof(size_t));
+ new = malloc(p_size);
- if (!p)
+ if (!new)
{
- fprintf(stderr,"%s: malloc(%d) failed\n",name,l);
+ fprintf(stderr,"%s: malloc(%lu) failed\n",
+ g_name, (unsigned long)p_size);
exit(EXIT_FAILURE);
}
- *p=l;
-
- grab_tot+=l;
-
- grab_mb=grab_tot/MEGABYTE;
-
- if (grab_last_mb!=grab_mb)
- {
- grab_last_mb=grab_mb;
-
-#if MAXMB != -1
- if (grab_mb>=MAXMB)
- {
- fprintf(stderr,"Quitting: Allocated %d Mb\n",grab_mb);
- exit(EXIT_FAILURE);
- }
-#endif
- }
-
- return p+1;
+ return new;
}
-static void Release(void *p)
+static void *Copy(const void *p_source, size_t p_size)
{
- size_t *pp;
-
- pp=p;
-
- pp--;
-
- grab_tot-=*pp;
-
- free(pp);
+ return memcpy(Grab(p_size), p_source, p_size);
}
-static int GrabSize(void)
+static const pos_t *FindPos(const pos_t *p_poslist, int p_no, int p_x, int p_y)
{
- return grab_mb;
+ while(p_no--)
+ {
+ if (p_poslist->x == p_x && p_poslist->y == p_y)
+ {
+ return p_poslist;
+ }
+
+ p_poslist++;
+ }
+
+ return NULL;
}
-static Pos *FindPos(Pos *p, int no, int x, int y)
+static pos_t *FindPosForUpdate(pos_t *p_poslist, int p_no, int p_x, int p_y)
{
- int f;
-
- for (f=0;f<no;f++)
+ while(p_no--)
{
- if (p[f].x==x && p[f].y==y)
+ if (p_poslist->x == p_x && p_poslist->y == p_y)
{
- return p+f;
+ return p_poslist;
}
+
+ p_poslist++;
}
return NULL;
@@ -300,54 +308,84 @@ static Pos *FindPos(Pos *p, int no, int x, int y)
/* ---------------------------------------- LEVEL LOADING
*/
-static char *GetLine(FILE *fp)
+static const char *GetLine(FILE *p_fp)
{
static char s[1024];
size_t l;
- fgets(s,sizeof s,fp);
+ fgets(s, sizeof s, p_fp);
- if (feof(fp))
+ if (feof(p_fp))
{
return NULL;
}
l = strlen(s);
- if (l && s[l-1]=='\n')
+ while (l > 0 && s[l-1] == '\n')
{
- s[l-1]=0;
+ s[--l]=0;
}
return s;
}
-static Level *Load(const char *path)
+
+static int CountChars(const char *p_line, glyph_t p_glyph)
+{
+ int count = 0;
+
+ while (*p_line)
+ {
+ if (*p_line++ == p_glyph)
+ {
+ count++;
+ }
+ }
+
+ return count;
+}
+
+static level_t *Load(const char *p_path)
{
FILE *fp;
- char *line;
- Level *new;
+ const char *line;
+ level_t *new;
int x,y;
int tno,bno;
int pno;
- if (!(fp=fopen(path,"r")))
+ if (!(fp = fopen(p_path, "r")))
{
return NULL;
}
- new=Grab(sizeof *new);
-
- line=GetLine(fp);
- new->name=Grab(strlen(line)+1);
- strcpy(new->name,line);
+ /* Get name
+ */
+ new = Grab(sizeof *new);
- new->no=atoi(GetLine(fp));
+ line = GetLine(fp);
+ new->name = Grab(strlen(line) + 1);
+ strcpy(new->name, line);
- /* Calc sizes
+ /* Calc sizes and counts
*/
- new->width=strlen(GetLine(fp));
- new->height=1;
+ new->width = strlen(GetLine(fp));
+ new->height = 1;
+
+ new->no_boxes = CountChars(line, BOX_GL) +
+ CountChars(line, BOX_TARGET_GL);
+
+ new->no_targets = CountChars(line, TARGET_GL) +
+ CountChars(line, BOX_TARGET_GL);
+
+ if (new->width > g_MAX_WIDTH)
+ {
+ fprintf(stderr,"%s: Your platform supports levels "
+ "up to %d cells wide; level has %d\n",
+ g_name, g_MAX_WIDTH, new->width);
+ exit(EXIT_FAILURE);
+ }
while((line=GetLine(fp)))
{
@@ -355,105 +393,97 @@ static Level *Load(const char *path)
if (strlen(line)!=new->width)
{
- fprintf(stderr,"%s: '%s' (line %d) too short "
- "(should be %d wide)\n",
- name,line,new->height,new->width);
+ fprintf(stderr,"%s: '%s' (line %d) wrong length;"
+ " should be %d cells wide\n",
+ g_name, line, new->height, new->width);
exit(EXIT_FAILURE);
}
+
+ new->no_boxes += CountChars(line, BOX_GL) +
+ CountChars(line, BOX_TARGET_GL);
+
+ new->no_targets += CountChars(line, TARGET_GL) +
+ CountChars(line, BOX_TARGET_GL);
+
}
- /* Rewind file and skip first two lines
+ /* Rewind file and skip name
*/
rewind(fp);
GetLine(fp);
- GetLine(fp);
- new->target=Grab(sizeof(Pos)*new->no);
- new->map=Grab(sizeof(MapChar)*(new->width*new->height));
+ new->target = Grab(sizeof *new->target * new->no_targets);
+
+ new->map = Grab(sizeof *new->map * new->width * new->height);
+
+ new->state = Grab(sizeof *new->state);
- new->state=Grab(sizeof(State));
- new->state->parent=NULL;
- new->state->next=NULL;
- new->state->box=Grab(sizeof(Pos)*new->no);
- new->state->left=new->state->right=new->state->up=new->state->down=NULL;
- new->state->dir=DIR_NONE;
+ new->state->parent = NULL;
+ new->state->next = NULL;
+ new->state->box = Grab(sizeof *new->state->box * new->no_boxes);
+ new->state->left = NULL;
+ new->state->right = NULL;
+ new->state->up = NULL;
+ new->state->down = NULL;
+ new->state->dir = DIR_NONE;
tno=0;
bno=0;
pno=0;
- for(y=0;y<new->height;y++)
+ for(y = 0; y < new->height; y++)
{
- line=GetLine(fp);
-
- if (strlen(line)<new->width)
- {
- fprintf(stderr,"%s: line '%s' too short "
- "(should be %d wide)\n",name,line,new->width);
- exit(EXIT_FAILURE);
- }
+ line = GetLine(fp);
- for(x=0;x<new->width;x++)
+ for(x = 0; x < new->width; x++)
{
switch(line[x])
{
case WALL_GL:
- AT(new,x,y)=WALL;
+ AT(new,x,y) = WALL_GL;
break;
case SPACE_GL:
- AT(new,x,y)=SPACE;
+ AT(new,x,y) = SPACE_GL;
break;
case BOX_TARGET_GL:
case TARGET_GL:
- if (tno==new->no)
- {
- fprintf(stderr,"%s: too many "
- "targets in %s\n",name,path);
-
- exit(EXIT_FAILURE);
- }
-
- AT(new,x,y)=SPACE;
- new->target[tno].x=x;
- new->target[tno].y=y;
+ AT(new,x,y) = SPACE_GL;
+ new->target[tno].x = x;
+ new->target[tno].y = y;
tno++;
- /* NOTE: Runs into following case
+ /* NOTE: Runs into following case for BOX_TARGET_GL
*/
- if (line[x]==TARGET_GL)
+ if (line[x] == TARGET_GL)
{
break;
}
case BOX_GL:
- if (bno==new->no)
- {
- fprintf(stderr,"%s: too many "
- "boxes in %s\n",name,path);
-
- exit(EXIT_FAILURE);
- }
-
- AT(new,x,y)=SPACE;
- new->state->box[bno].x=x;
- new->state->box[bno].y=y;
+ AT(new,x,y) = SPACE_GL;
+ new->state->box[bno].x = x;
+ new->state->box[bno].y = y;
bno++;
break;
case PLAYER_GL:
- if (pno++==1)
+ if (pno++ == 1)
{
fprintf(stderr,"%s: too many "
- "players in %s\n",name,path);
+ "players in %s\n", g_name, p_path);
exit(EXIT_FAILURE);
}
- AT(new,x,y)=SPACE;
- new->state->player.x=x;
- new->state->player.y=y;
+ AT(new,x,y) = SPACE_GL;
+ new->state->player.x = x;
+ new->state->player.y = y;
+ break;
+
+ default:
+ AT(new,x,y) = SPACE_GL;
break;
}
}
@@ -461,10 +491,9 @@ static Level *Load(const char *path)
fclose(fp);
- if (pno==0)
+ if (pno == 0)
{
- fprintf(stderr,"%s: no player definied in %s\n",name,path);
-
+ fprintf(stderr,"%s: no player definied in %s\n", g_name, p_path);
exit(EXIT_FAILURE);
}
@@ -472,20 +501,21 @@ static Level *Load(const char *path)
}
-static void FreeLevel(Level *l)
+static void FreeLevel(level_t *p_level)
{
}
-static void Display(Level *level, State *state)
+static void Display(const level_t *p_level, const state_t *p_state)
{
- int x,y;
+ int x;
+ int y;
- for(y=0;y<level->height;y++)
+ for(y = 0; y < p_level->height; y++)
{
- for(x=0;x<level->width;x++)
+ for(x = 0; x < p_level->width; x++)
{
- putchar(GetGlyph(level,state,x,y));
+ putchar(GetGlyph(p_level, p_state, x, y));
}
putchar('\n');
@@ -493,26 +523,27 @@ static void Display(Level *level, State *state)
}
-static char GetGlyph(Level *level, State *state, int x, int y)
+static char GetGlyph(const level_t *p_level, const state_t *p_state,
+ int p_x, int p_y)
{
- if (AT(level,x,y)==WALL)
+ if (AT(p_level, p_x, p_y) == WALL_GL)
{
return WALL_GL;
}
- else if (FindPos(&state->player,1,x,y))
+ else if (FindPos(&p_state->player, 1, p_x, p_y))
{
return PLAYER_GL;
}
- else if (FindPos(state->box,level->no,x,y) &&
- FindPos(level->target,level->no,x,y))
+ 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(state->box,level->no,x,y))
+ else if (FindPos(p_state->box, p_level->no_boxes, p_x, p_y))
{
return BOX_GL;
}
- else if (FindPos(level->target,level->no,x,y))
+ else if (FindPos(p_level->target, p_level->no_targets, p_x, p_y))
{
return TARGET_GL;
}
@@ -525,10 +556,10 @@ static char GetGlyph(Level *level, State *state, int x, int y)
/* ---------------------------------------- SOLVER
*/
-static void FreeState(State *s)
+static void FreeState(state_t *p_state)
{
- Release(s->box);
- Release(s);
+ free(p_state->box);
+ free(p_state);
}
@@ -536,74 +567,151 @@ static void ClearStates(void)
{
int f;
- state_map_no=0;
+ g_cached_states = 0;
- for(f=0;f<STATE_HASH;f++)
+ for(f = 0; f < CACHE_SIZE; f++)
{
- while(state_map[f])
+ while(g_cache[f])
{
- StateMap *p;
- p=state_map[f]->next;
- Release(state_map[f]);
- state_map[f]=p;
+ cache_t *p;
+
+ p = g_cache[f]->next;
+ free(g_cache[f]->map);
+ free(g_cache[f]);
+ g_cache[f] = p;
}
}
}
-static Bool AddNewState(Level *l, State *s)
+static map_t *CreateMap(const level_t *p_level, const state_t *p_state)
+{
+ map_t *m;
+ int f;
+
+ m = Grab(sizeof *m * p_level->height);
+
+ for(f = 0; f < p_level->height; f++)
+ {
+ m[f] = 0;
+ }
+
+ 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].y] |= 0x10llu << (p_state->box[f].x * 2);
+ }
+
+ return m;
+}
+
+
+static hash_t ROL(hash_t p_val, int p_bits)
{
- StateMap *p;
- int hash;
+ while(p_bits--)
+ {
+ p_val = (p_val >> 31) | (p_val << 1);
+ }
+
+ return p_val;
+}
- hash=s->hash%STATE_HASH;
- p=state_map[hash];
+/* This is almost certainly rubbish
+*/
+static hash_t CreateHash(const level_t *p_level, const state_t *p_state)
+{
+ hash_t hash;
+ int f;
+
+ hash = ROL(p_state->player.x, p_state->player.y);
+
+ for(f = 0; f < p_level->no_boxes; f++)
+ {
+ hash ^= ROL(p_state->box[f].x, p_state->box[f].y);
+ }
+
+ return hash;
+}
+
+
+static void DumpCacheDistribution(void)
+{
+ int f;
+
+ printf("**** START CACHE DISTRIBUTION DUMP (%d ENTRIES)\n", CACHE_SIZE);
+
+ for(f = 0; f < CACHE_SIZE; f++)
+ {
+ cache_t *cache;
+ int count;
+
+ count = 0;
+ cache = g_cache[f];
+
+ while(cache)
+ {
+ count++;
+ cache=cache->next;
+ }
+
+ printf("%d\n", count);
+ }
+
+ printf("**** END CACHE DISTRIBUTION DUMP)\n");
+}
+
+
+static int AddNewState(const level_t *p_level, const state_t *p_state)
+{
+ cache_t *p;
+ map_t *map;
+ hash_t hash;
+
+ hash = p_state->hash % CACHE_SIZE;
+
+ p = g_cache[hash];
+ map = CreateMap(p_level, p_state);
while(p)
{
- if (s->player.x==p->s->player.x && s->player.y==p->s->player.y)
+ if (p_state->player.x == p->state->player.x &&
+ p_state->player.y == p->state->player.y)
{
int f;
- int ok;
+ map_t check;
- ok=FALSE;
+ check = 0;
- for(f=0;f<l->no && !ok;f++)
+ for(f = 0; f < p_level->height; f++)
{
- if (s->box[f].x!=p->s->box[f].x || s->box[f].y!=p->s->box[f].y)
- {
- ok=TRUE;
- }
+ check |= (map[f] ^ p->map[f]);
}
- if (!ok)
+ if (check == 0)
{
- return FALSE;
+ free(map);
+ return FALSE;
}
}
p=p->next;
}
- p=Grab(sizeof *p);
+ p = Grab(sizeof *p);
- p->s=s;
- p->next=state_map[hash];
- state_map[hash]=p;
+ p->state = p_state;
+ p->map = map;
+ p->next = g_cache[hash];
+ g_cache[hash] = p;
- state_map_no++;
+ g_cached_states++;
return TRUE;
}
-static int GetStateNum(void)
-{
- return state_map_no;
-}
-
-
static const char *NoMoveReason(char *fmt,...)
{
static char r[512];
@@ -622,18 +730,19 @@ static const char *NoMoveReason(char *fmt,...)
}
-static Bool CheckImpossible(Level *l, State *s)
+static int CheckImpossible(const level_t *p_level, const state_t *p_state)
{
int f;
- for(f=0;f<l->no;f++)
+ for(f = 0; f < p_level->no_boxes; f++)
{
- int x,y;
+ int x;
+ int y;
- x=s->box[f].x;
- y=s->box[f].y;
+ x = p_state->box[f].x;
+ y = p_state->box[f].y;
- if (!FindPos(l->target,l->no,x,y))
+ if (!FindPos(p_level->target, p_level->no_targets, x, y))
{
int d;
int any_move;
@@ -643,21 +752,23 @@ static Bool CheckImpossible(Level *l, State *s)
*/
any_move=FALSE;
- for(d=0;d<4 && !any_move;d++)
+ for(d = 0; d < 4 && !any_move; d++)
{
- int nx,ny;
+ int nx;
+ int ny;
- nx=x+move_dir[d].x;
- ny=y+move_dir[d].y;
+ nx = x + g_move_dir[d].x;
+ ny = y + g_move_dir[d].y;
- if (AT(l,nx,ny)!=WALL)
+ if (AT(p_level, nx, ny) != WALL_GL)
{
- int ox,oy;
+ int ox;
+ int oy;
- ox=x+move_dir[(d+2)%4].x;
- oy=y+move_dir[(d+2)%4].y;
+ ox = x + g_move_dir[(d+2)%4].x;
+ oy = y + g_move_dir[(d+2)%4].y;
- if (AT(l,ox,oy)!=WALL)
+ if (AT(p_level, ox, oy) != WALL_GL)
{
any_move=TRUE;
}
@@ -666,16 +777,17 @@ static Bool CheckImpossible(Level *l, State *s)
if (!any_move)
{
- NoMoveReason("Couldn't push block at %d,%d",x,y);
+ NoMoveReason("Couldn't push block at %d,%d", x, y);
return TRUE;
}
/* Four blocks together is impossible
*/
- if (FindPos(s->box,l->no,x+1,y) && FindPos(s->box,l->no,x,y+1) &&
- FindPos(s->box,l->no,x+1,y+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",x,y);
+ NoMoveReason("Group of 4 boxes at %d,%d", x, y);
return TRUE;
}
}
@@ -685,77 +797,79 @@ static Bool CheckImpossible(Level *l, State *s)
}
-static State *CreateState(Byte dir, Bool must_push,
- Level *l, State *s, Bool check_possible)
+static state_t *CreateState(int p_dir, int p_must_push,
+ const level_t *p_level, const state_t *p_state,
+ int p_check_possible)
{
- State *new;
- Pos *p;
+ state_t *new;
+ const pos_t *p;
int x,y;
int push;
int dx,dy;
- int f;
- dx=move_dir[dir].x;
- dy=move_dir[dir].y;
+ dx = g_move_dir[p_dir].x;
+ dy = g_move_dir[p_dir].y;
- push=FALSE;
+ push = FALSE;
- x=s->player.x+dx;
- y=s->player.y+dy;
+ x = p_state->player.x + dx;
+ y = p_state->player.y + dy;
/* Check for walls
*/
- if (AT(l,x,y)==WALL)
+ if (AT(p_level, x, y) == WALL_GL)
{
return NULL;
}
/* Check for boxes
*/
- if ((p=FindPos(s->box,l->no,x,y)))
+ if ((p = FindPos(p_state->box, p_level->no_boxes, x, y)))
{
- int bx,by;
+ int bx;
+ int by;
/* Can the box be pushed?
*/
- bx=p->x+dx;
- by=p->y+dy;
+ bx = p->x+dx;
+ by = p->y+dy;
- if (AT(l,bx,by)==WALL)
+ if (AT(p_level, bx, by) == WALL_GL)
{
return NULL;
}
- if (FindPos(s->box,l->no,bx,by))
+ if (FindPos(p_state->box, p_level->no_boxes, bx, by))
{
return NULL;
}
- push=TRUE;
+ push = TRUE;
}
- if (!push && must_push)
+ if (!push && p_must_push)
{
return NULL;
}
- new=Grab(sizeof *new);
- new->box=Grab(sizeof(Pos)*l->no);
- memcpy(new->box,s->box,sizeof(Pos)*l->no);
+ new = Grab(sizeof *new);
+ new->box = Copy(p_state->box, sizeof(pos_t) * p_level->no_boxes);
- new->player.x=x;
- new->player.y=y;
+ new->player.x = x;
+ new->player.y = y;
if (push)
{
- p=FindPos(new->box,l->no,x,y);
+ pos_t *pd;
- p->x+=dx;
- p->y+=dy;
+ pd = FindPosForUpdate(new->box, p_level->no_boxes, x, y);
+
+ pd->x += dx;
+ pd->y += dy;
/* (Very) basic checks to see if the move has made the level impossible
*/
- if (check_possible && CheckImpossible(l,new))
+ if (p_check_possible && CheckImpossible(p_level, new))
{
FreeState(new);
return NULL;
@@ -763,30 +877,23 @@ static State *CreateState(Byte dir, Bool must_push,
}
- new->left=NULL;
- new->right=NULL;
- new->up=NULL;
- new->down=NULL;
+ new->left = NULL;
+ new->right = NULL;
+ new->up = NULL;
+ new->down = NULL;
- new->parent=s;
- new->next=NULL;
+ new->parent = (state_t*) p_state;
+ new->next = NULL;
- new->path=FALSE;
- new->pushed=push;
- new->dir=dir;
+ new->path = FALSE;
+ new->pushed = push;
+ new->dir = p_dir;
/* Calculate a hash based on box and player positions
*/
- new->hash=0;
-
- for(f=0;f<l->no;f++)
- {
- new->hash+=new->box[f].x+new->box[f].y*l->height;
- }
-
- new->hash+=(STATE_HASH>>2)+new->box[f].x+new->box[f].y*l->height;
+ new->hash = CreateHash(p_level, new);
- if (!AddNewState(l,new))
+ if (!AddNewState(p_level ,new))
{
NoMoveReason("State matches previous");
FreeState(new);
@@ -797,67 +904,66 @@ static State *CreateState(Byte dir, Bool must_push,
}
-static void SetChain(State **first, State **curr, State *new)
+static void SetChain(state_t **first, state_t **curr, state_t *new)
{
if (new)
{
if (!*first)
{
- *first=new;
- *curr=*first;
+ *first = new;
+ *curr = *first;
}
else
{
- (*curr)->next=new;
- (*curr)=new;
+ (*curr)->next = new;
+ (*curr) = new;
}
}
}
-static void SubSolve(Level *level, State *state,int depth,
- int max_depth, LogMode log)
+static void SubSolve(const level_t *p_level, state_t *p_state, int p_depth,
+ int p_max_depth, int p_log)
{
static time_t last=0;
- State *first;
- State *curr;
- State *new;
- State *s;
+ state_t *first;
+ state_t *curr;
+ state_t *new;
+ state_t *s;
int ok;
int f;
- if (depth>=max_depth)
+ if (p_depth >= p_max_depth)
{
+ fprintf(stderr, "%s: blown maximum solution depeth of %d\n",
+ g_name, p_max_depth);
return;
}
- if (depth==1)
+ if (p_depth == 1)
{
last=time(NULL);
}
- switch(log)
+ if (p_log)
{
- case QUIET:
- break;
- case VERBOSE:
- printf("Searching %d moves deep "
- "(%ld secs, used %dMb - %d unique states)\n",
- depth,time(NULL)-last,GrabSize(),GetStateNum());
- break;
- case CSV:
- printf("%d,%ld,%d,%d\n",
- depth,time(NULL)-last,GrabSize(),GetStateNum());
- break;
+ printf("Searching %d moves deep (%ld secs, %llu unique states)\n",
+ p_depth, time(NULL) - last, g_cached_states);
}
- last=time(NULL);
+ if (g_signal)
+ {
+ DumpCacheDistribution();
+ g_signal = 0;
+ }
+
+ last = time(NULL);
/* Loop across all states at this depth
*/
- s=state;
- first=NULL;
- curr=NULL;
+ s = p_state;
+ first = NULL;
+ curr = NULL;
while(s)
{
@@ -865,116 +971,128 @@ static void SubSolve(Level *level, State *state,int depth,
*/
ok=TRUE;
- for(f=0;(f<level->no) && ok;f++)
+ for(f = 0; f < p_level->no_targets && ok; f++)
{
- if (!FindPos(s->box,level->no,
- level->target[f].x,level->target[f].y))
+ if (!FindPos(s->box,
+ p_level->no_boxes,
+ p_level->target[f].x,
+ p_level->target[f].y))
{
- ok=FALSE;
+ ok = FALSE;
}
}
if (ok)
{
- s->path=TRUE;
- s=s->parent;
+ s->path = TRUE;
+ s = s->parent;
while(s)
{
- s->path=TRUE;
- s=s->parent;
+ s->path = TRUE;
+ s = s->parent;
}
+
return;
}
/* Check moves
*/
- if (s->dir==DIR_RIGHT)
+ if (s->dir == DIR_RIGHT)
{
- s->left=new=CreateState(DIR_LEFT,!s->pushed,level,s,TRUE);
+ s->left = CreateState(DIR_LEFT, !s->pushed, p_level, s, TRUE);
+ new = s->left;
}
else
{
- s->left=new=CreateState(DIR_LEFT,FALSE,level,s,TRUE);
+ s->left = CreateState(DIR_LEFT, FALSE, p_level, s, TRUE);
+ new = s->left;
}
- SetChain(&first,&curr,new);
+ SetChain(&first, &curr, new);
- if (s->dir==DIR_LEFT)
+ if (s->dir == DIR_LEFT)
{
- s->right=new=CreateState(DIR_RIGHT,!s->pushed,level,s,TRUE);
+ s->right = CreateState(DIR_RIGHT, !s->pushed, p_level, s, TRUE);
+ new = s->right;
}
else
{
- s->right=new=CreateState(DIR_RIGHT,FALSE,level,s,TRUE);
+ s->right = CreateState(DIR_RIGHT, FALSE, p_level, s, TRUE);
+ new = s->right;
}
- SetChain(&first,&curr,new);
+ SetChain(&first, &curr, new);
- if (s->dir==DIR_DOWN)
+ if (s->dir == DIR_DOWN)
{
- s->up=new=CreateState(DIR_UP,!s->pushed,level,s,TRUE);
+ s->up = CreateState(DIR_UP, !s->pushed, p_level, s, TRUE);
+ new = s->up;
}
else
{
- s->up=new=CreateState(DIR_UP,FALSE,level,s,TRUE);
+ s->up = CreateState(DIR_UP, FALSE, p_level, s, TRUE);
+ new = s->up;
}
- SetChain(&first,&curr,new);
+ SetChain(&first, &curr, new);
- if (s->dir==DIR_UP)
+ if (s->dir == DIR_UP)
{
- s->down=new=CreateState(DIR_DOWN,!s->pushed,level,s,TRUE);
+ s->down = CreateState(DIR_DOWN, !s->pushed, p_level, s, TRUE);
+ new = s->down;
}
else
{
- s->down=new=CreateState(DIR_DOWN,FALSE,level,s,TRUE);
+ s->down = CreateState(DIR_DOWN, FALSE, p_level, s, TRUE);
+ new = s->down;
}
- SetChain(&first,&curr,new);
+ SetChain(&first, &curr, new);
- s=s->next;
+ s = s->next;
}
if (first)
{
- SubSolve(level,first,++depth,max_depth,log);
+ SubSolve(p_level, first, ++p_depth, p_max_depth, p_log);
}
}
-static void Solve(Level *level, Route route, int max_depth, LogMode log)
+static void Solve(const level_t *p_level, route_t p_route,
+ int p_max_depth, int p_log)
{
- State *s;
+ state_t *s;
- route[0]=0;
+ p_route[0] = 0;
ClearStates();
- SubSolve(level,level->state,1,max_depth,log);
+ SubSolve(p_level, p_level->state, 1, p_max_depth, p_log);
- s=level->state;
+ s = p_level->state;
while(s)
{
if (s->left && s->left->path)
{
- strcat(route,"L");
- s=s->left;
+ strcat(p_route,"L");
+ s = s->left;
}
else if (s->right && s->right->path)
{
- strcat(route,"R");
- s=s->right;
+ strcat(p_route,"R");
+ s = s->right;
}
else if (s->up && s->up->path)
{
- strcat(route,"U");
- s=s->up;
+ strcat(p_route,"U");
+ s = s->up;
}
else if (s->down && s->down->path)
{
- strcat(route,"D");
- s=s->down;
+ strcat(p_route,"D");
+ s = s->down;
}
else
{
@@ -986,159 +1104,163 @@ static void Solve(Level *level, Route route, int max_depth, LogMode log)
/* ---------------------------------------- INTERACTIVE MODE
*/
-static void CursesDisplay(Level *l, State *s, int play)
+static void CursesDisplay(const level_t *p_level,
+ const state_t *p_state,
+ int play)
{
- int x,y,f;
char allow[80];
+ int x;
+ int y;
+ int f;
- for(x=0;x<l->width;x++)
+ for(x = 0; x < p_level->width; x++)
{
char num[20];
- sprintf(num,"%d",x);
+ sprintf(num, "%d", x);
- f=0;
+ f = 0;
while(num[f])
{
- mvaddch(3+f,3+x,num[f++]);
+ mvaddch(3+f, 3+x, num[f++]);
}
- for(y=0;y<l->height;y++)
+ for(y = 0; y < p_level->height; y++)
{
- if (x==0)
+ if (x == 0)
{
- mvprintw(6+y,0,"%d",y);
+ mvprintw(6+y, 0, "%d", y);
}
- mvaddch(6+y,3+x,GetGlyph(l,s,x,y));
+ mvaddch(6+y, 3+x, GetGlyph(p_level, p_state, x, y));
}
}
strcpy(allow,"Moves: ");
- if (s->left)
+ if (p_state->left)
{
- strcat(allow,"left ");
+ strcat(allow, "left ");
}
- if (s->right)
+ if (p_state->right)
{
- strcat(allow,"right ");
+ strcat(allow, "right ");
}
- if (s->up)
+ if (p_state->up)
{
- strcat(allow,"up ");
+ strcat(allow, "up ");
}
- if (s->down)
+ if (p_state->down)
{
- strcat(allow,"down ");
+ strcat(allow, "down ");
}
- if (s->parent)
+ if (p_state->parent)
{
- strcat(allow,"back");
+ strcat(allow, "back");
}
- while(strlen(allow)<70)
+ while(strlen(allow) < 70)
{
- strcat(allow," ");
+ strcat(allow, " ");
}
- mvaddstr(l->height+11,0,allow);
+ mvaddstr(p_level->height + 11, 0, allow);
if (!play)
{
- if (s->path)
+ if (p_state->path)
{
- mvaddstr(l->height+10,0,"On solved path: YES");
+ mvaddstr(p_level->height + 10, 0, "On solved path: YES");
}
else
{
- mvaddstr(l->height+10,0,"On solved path: NO ");
+ mvaddstr(p_level->height + 10, 0, "On solved path: NO ");
}
}
else
{
- int depth=0;
+ int depth = 0;
- while(s)
+ while(p_state)
{
depth++;
- s=s->parent;
+ p_state = p_state->parent;
}
- mvprintw(l->height+10,0,"Depth: %d ",depth);
+ mvprintw(p_level->height + 10, 0, "Depth: %d ", depth);
}
- mvprintw(LINES-3,0,"Last reason: %-40.40s",NoMoveReason(NULL));
+ mvprintw(LINES - 3, 0, "Last reason: %-40.40s", NoMoveReason(NULL));
refresh();
}
-static void Interactive(Level *l, int play)
+static void Interactive(const level_t *p_level, int play)
{
int quit;
- Route route;
- State *s;
+ route_t route;
+ state_t *s;
if (!play)
{
- Solve(l,route,999,VERBOSE);
+ Solve(p_level, route, MAX_ROUTE, TRUE);
}
initscr();
cbreak();
noecho();
nonl();
- intrflush(stdscr,FALSE);
- keypad(stdscr,TRUE);
+ intrflush(stdscr, FALSE);
+ keypad(stdscr, TRUE);
- quit=FALSE;
- s=l->state;
+ quit = FALSE;
+ s = p_level->state;
clear();
- mvaddstr(0,0,l->name);
+ mvaddstr(0, 0, p_level->name);
mvaddstr(LINES-1,0,"Cursors to move, P to follow path, "
"Q to quit, Backspace/B to step back");
if (!play)
{
- mvprintw(l->height+9,0,"Route:%s",route);
+ mvprintw(p_level->height + 9, 0, "Route:%s", route);
}
while(!quit)
{
int key;
- CursesDisplay(l,s,play);
+ CursesDisplay(p_level, s, play);
- key=getch();
+ key = getch();
if (key=='p' || key=='P')
{
if (s->left && s->left->path)
{
- key=KEY_LEFT;
+ key = KEY_LEFT;
}
if (s->right && s->right->path)
{
- key=KEY_RIGHT;
+ key = KEY_RIGHT;
}
if (s->up && s->up->path)
{
- key=KEY_UP;
+ key = KEY_UP;
}
if (s->down && s->down->path)
{
- key=KEY_DOWN;
+ key = KEY_DOWN;
}
}
@@ -1149,14 +1271,14 @@ static void Interactive(Level *l, int play)
case 'B':
if (s->parent)
{
- s=s->parent;
+ s = s->parent;
}
break;
case KEY_LEFT:
if (play && !s->left)
{
- s->left=CreateState(DIR_LEFT,FALSE,l,s,TRUE);
+ s->left = CreateState(DIR_LEFT, FALSE, p_level, s, TRUE);
}
if (s->left)
@@ -1168,42 +1290,42 @@ static void Interactive(Level *l, int play)
case KEY_RIGHT:
if (play && !s->right)
{
- s->right=CreateState(DIR_RIGHT,FALSE,l,s,TRUE);
+ s->right = CreateState(DIR_RIGHT, FALSE, p_level, s, TRUE);
}
if (s->right)
{
- s=s->right;
+ s = s->right;
}
break;
case KEY_DOWN:
if (play && !s->down)
{
- s->down=CreateState(DIR_DOWN,FALSE,l,s,TRUE);
+ s->down = CreateState(DIR_DOWN, FALSE, p_level, s, TRUE);
}
if (s->down)
{
- s=s->down;
+ s = s->down;
}
break;
case KEY_UP:
if (play && !s->up)
{
- s->up=CreateState(DIR_UP,FALSE,l,s,TRUE);
+ s->up = CreateState(DIR_UP, FALSE, p_level, s, TRUE);
}
if (s->up)
{
- s=s->up;
+ s = s->up;
}
break;
case 'q':
case 'Q':
- quit=TRUE;
+ quit = TRUE;
break;
default: