diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | dbox.c | 1016 | ||||
| -rw-r--r-- | level0 | 1 | ||||
| -rw-r--r-- | level1 | 1 | ||||
| -rw-r--r-- | level14 | 1 | ||||
| -rw-r--r-- | level15 | 1 | ||||
| -rw-r--r-- | level4 | 1 | ||||
| -rw-r--r-- | level5 | 1 | ||||
| -rw-r--r-- | level73 | 1 | ||||
| -rw-r--r-- | levelA | 1 | ||||
| -rw-r--r-- | levelB | 1 | ||||
| -rw-r--r-- | levelC | 1 | ||||
| -rw-r--r-- | levelD | 1 | ||||
| -rw-r--r-- | levelE | 1 | ||||
| -rw-r--r-- | levelF | 11 | ||||
| -rw-r--r-- | levelG | 8 | ||||
| -rw-r--r-- | makefile | 56 |
17 files changed, 589 insertions, 516 deletions
@@ -31,7 +31,7 @@ OBJECTS = $(SOURCES:.c=.o) LIBS = -lncurses -FLAGS = -O2 -g -Wall -pedantic -ansi -std=c99 +FLAGS = -O2 -g -Wall -std=c99 DEPEND = depend.mak @@ -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: @@ -1,5 +1,4 @@ Test Level -2 ####### #.B@B.# ####### @@ -1,5 +1,4 @@ Level 1 -4 ### #.# # #### @@ -1,5 +1,4 @@ Level 14 -6 ######## # # # # B..B # @@ -1,5 +1,4 @@ Level 15 -6 ####### ## # # B BB # @@ -1,5 +1,4 @@ Level 4 -5 #### ## # #@B # @@ -1,5 +1,4 @@ Level 5 -3 ##### #@ ### # B # @@ -1,5 +1,4 @@ Level 73 -12 ######## # # # ####### BB...# @@ -1,5 +1,4 @@ Test Level -2 ##### #@B.# # B.# @@ -1,5 +1,4 @@ Test Level -2 ####### #.B@B.# ####### @@ -1,5 +1,4 @@ Test Level -1 ######### ##### # #@B # @@ -1,5 +1,4 @@ Test Level -3 ######### #@ # # # # # @@ -1,5 +1,4 @@ Test Level -2 ########## #@ # # # # @@ -0,0 +1,11 @@ +Test Level +########## +#@ # +# # # +# B # +# # # +# B # +# # +# # # +# .# +########## @@ -0,0 +1,8 @@ +Impossible... +########## +#@ B # +# ###### # +# # .B # # +# ###### # +# .# +########## diff --git a/makefile b/makefile deleted file mode 100644 index 08bb357..0000000 --- a/makefile +++ /dev/null @@ -1,56 +0,0 @@ -# -# dbox - Sokoban solver -# -# Copyright (C) 2001-2009 Ian Cowburn (ianc@noddybox.demon.co.uk) -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; either version 2 of the License, or -# (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License -# along with this program; if not, write to the Free Software -# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -# -# ------------------------------------------------------------------------- -# - - -TARGET = dbox - -SOURCES = dbox.c - -HEADERS = - -OBJECTS = $(SOURCES:.c=.o) - -LIBS = -lncurses - -FLAGS = -O2 -g -Wall -pedantic -ansi - -DEPEND = depend.mak - -$(TARGET): $(OBJECTS) - $(CC) $(FLAGS) -o $(TARGET) $(OBJECTS) $(LIBS) - -%.o: %.c - $(CC) $(CFLAGS) $(CPPFLAGS) $(FLAGS) $(TRACE) -c $< -o $@ - --include depend.mak - -clean: - -rm -f $(TARGET) $(TARGET).exe core *.stackdump *.o depend.mak - -depend: $(DEPEND) - @echo Dependencies updated.... - -$(DEPEND): $(SOURCES) $(HEADERS) - $(CC) -MM $(SOURCES) > $(DEPEND) - - -# END OF FILE |