summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan C <ianc@noddybox.co.uk>2009-02-05 23:19:07 +0000
committerIan C <ianc@noddybox.co.uk>2009-02-05 23:19:07 +0000
commit8bb30d97767e56bc5304c82013bce4daa99f3e12 (patch)
tree0ce708223ed5bd6ffdc031ac864492becb16ea0d
parentcc307a968ef1036d6cd96ce38c64cc195950ea46 (diff)
Reformatted code
-rw-r--r--dbox.c401
-rw-r--r--makefile5
2 files changed, 271 insertions, 135 deletions
diff --git a/dbox.c b/dbox.c
index a0cb31c..ac00bc3 100644
--- a/dbox.c
+++ b/dbox.c
@@ -1,8 +1,7 @@
/*
-
dbox - Sokoban level solver
- Copyright (C) 2001 Ian Cowburn (ianc@noddybox.demon.co.uk)
+ 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
@@ -30,9 +29,9 @@ static const char cvs_id[]="$Id$";
#include <time.h>
#if (USECURSES == ncurses)
-# include <ncurses.h>
+#include <ncurses.h>
#else
-# include <curses.h>
+#include <curses.h>
#endif
#ifndef TRUE
@@ -79,46 +78,47 @@ typedef enum {QUIET,CSV,VERBOSE} LogMode;
#define DIR_DOWN 3
typedef struct
- {
- PosInt x;
- PosInt y;
- } Pos;
+{
+ PosInt x;
+ PosInt y;
+} Pos;
static const Pos move_dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
typedef struct State
- {
- 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 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;
typedef struct
- {
- char *name;
- int width,height;
- int no;
- Pos *target;
- MapChar *map;
- State *state;
- } Level;
+{
+ char *name;
+ int width;
+ int height;
+ int no;
+ Pos *target;
+ MapChar *map;
+ State *state;
+} Level;
#define STATE_HASH 0x10000
typedef struct StateMap
- {
- State *s;
- struct StateMap *next;
- } StateMap;
+{
+ State *s;
+ struct StateMap *next;
+} StateMap;
static StateMap *state_map[STATE_HASH]={NULL};
static int state_map_no=0;
@@ -154,52 +154,56 @@ int main(int argc, char *argv[])
name=argv[0];
if (argc<2)
- {
+ {
fprintf(stderr,"%s: usage %s [-i|-p] file [file2 ...]\n",name,name);
return EXIT_FAILURE;
- }
+ }
if (strcmp(argv[1],"-i")==0)
- {
+ {
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;
- }
+ }
else
+ {
base=1;
+ }
if (argc<=base)
- {
+ {
fprintf(stderr,"%s: usage %s [-c|-i|-p] file [file2 ...]\n",name,name);
return EXIT_FAILURE;
- }
+ }
for(f=base;f<argc;f++)
- {
+ {
Route route;
Level *level;
if (!(level=Load(argv[f])))
- {
+ {
fprintf(stderr,"%s: %s could not be read\n",name,argv[f]);
- }
+ }
else
- {
+ {
if (interact)
+ {
Interactive(level,play);
+ }
else
- {
+ {
printf("Solving %s\n\n",level->name);
Display(level,level->state);
@@ -207,11 +211,11 @@ int main(int argc, char *argv[])
Solve(level,route,999,mode);
printf("\nRoute = '%s'\n",route);
- }
+ }
FreeLevel(level);
- }
}
+ }
return EXIT_SUCCESS;
}
@@ -230,10 +234,10 @@ static void *Grab(size_t l)
p=malloc(l+sizeof(size_t));
if (!p)
- {
+ {
fprintf(stderr,"%s: malloc(%d) failed\n",name,l);
exit(EXIT_FAILURE);
- }
+ }
*p=l;
@@ -242,15 +246,17 @@ static void *Grab(size_t l)
grab_mb=grab_tot/MEGABYTE;
if (grab_last_mb!=grab_mb)
- {
+ {
grab_last_mb=grab_mb;
- if (grab_mb==MAXMB)
- {
+#if MAXMB != -1
+ if (grab_mb>=MAXMB)
+ {
fprintf(stderr,"Quitting: Allocated %d Mb\n",grab_mb);
exit(EXIT_FAILURE);
- }
}
+#endif
+ }
return p+1;
}
@@ -281,8 +287,12 @@ static Pos *FindPos(Pos *p, int no, int x, int y)
int f;
for (f=0;f<no;f++)
+ {
if (p[f].x==x && p[f].y==y)
+ {
return p+f;
+ }
+ }
return NULL;
}
@@ -293,14 +303,21 @@ static Pos *FindPos(Pos *p, int no, int x, int y)
static char *GetLine(FILE *fp)
{
static char s[1024];
+ size_t l;
fgets(s,sizeof s,fp);
if (feof(fp))
+ {
return NULL;
+ }
+
+ l = strlen(s);
- if (s[strlen(s)-1]=='\n')
- s[strlen(s)-1]=0;
+ if (l && s[l-1]=='\n')
+ {
+ s[l-1]=0;
+ }
return s;
}
@@ -315,7 +332,9 @@ static Level *Load(const char *path)
int pno;
if (!(fp=fopen(path,"r")))
+ {
return NULL;
+ }
new=Grab(sizeof *new);
@@ -331,17 +350,17 @@ static Level *Load(const char *path)
new->height=1;
while((line=GetLine(fp)))
- {
+ {
new->height++;
if (strlen(line)!=new->width)
- {
+ {
fprintf(stderr,"%s: '%s' (line %d) too short "
"(should be %d wide)\n",
name,line,new->height,new->width);
exit(EXIT_FAILURE);
- }
}
+ }
/* Rewind file and skip first two lines
*/
@@ -364,19 +383,20 @@ static Level *Load(const char *path)
pno=0;
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);
- }
+ }
for(x=0;x<new->width;x++)
+ {
switch(line[x])
- {
+ {
case WALL_GL:
AT(new,x,y)=WALL;
break;
@@ -388,12 +408,12 @@ static Level *Load(const char *path)
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;
@@ -403,16 +423,18 @@ static Level *Load(const char *path)
/* NOTE: Runs into following case
*/
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;
@@ -422,28 +444,29 @@ static Level *Load(const char *path)
case PLAYER_GL:
if (pno++==1)
- {
+ {
fprintf(stderr,"%s: too many "
"players in %s\n",name,path);
exit(EXIT_FAILURE);
- }
+ }
AT(new,x,y)=SPACE;
new->state->player.x=x;
new->state->player.y=y;
break;
- }
+ }
}
+ }
fclose(fp);
if (pno==0)
- {
+ {
fprintf(stderr,"%s: no player definied in %s\n",name,path);
exit(EXIT_FAILURE);
- }
+ }
return new;
}
@@ -459,31 +482,44 @@ static void Display(Level *level, State *state)
int x,y;
for(y=0;y<level->height;y++)
- {
+ {
for(x=0;x<level->width;x++)
+ {
putchar(GetGlyph(level,state,x,y));
+ }
putchar('\n');
- }
+ }
}
static char GetGlyph(Level *level, State *state, int x, int y)
{
if (AT(level,x,y)==WALL)
+ {
return WALL_GL;
+ }
else if (FindPos(&state->player,1,x,y))
+ {
return PLAYER_GL;
+ }
else if (FindPos(state->box,level->no,x,y) &&
FindPos(level->target,level->no,x,y))
+ {
return BOX_TARGET_GL;
+ }
else if (FindPos(state->box,level->no,x,y))
+ {
return BOX_GL;
+ }
else if (FindPos(level->target,level->no,x,y))
+ {
return TARGET_GL;
+ }
else
+ {
return SPACE_GL;
-
+ }
}
@@ -503,13 +539,15 @@ static void ClearStates(void)
state_map_no=0;
for(f=0;f<STATE_HASH;f++)
+ {
while(state_map[f])
- {
+ {
StateMap *p;
p=state_map[f]->next;
Release(state_map[f]);
state_map[f]=p;
- }
+ }
+ }
}
@@ -523,24 +561,30 @@ static Bool AddNewState(Level *l, State *s)
p=state_map[hash];
while(p)
- {
+ {
if (s->player.x==p->s->player.x && s->player.y==p->s->player.y)
- {
+ {
int f;
int ok;
ok=FALSE;
for(f=0;f<l->no && !ok;f++)
+ {
if (s->box[f].x!=p->s->box[f].x || s->box[f].y!=p->s->box[f].y)
+ {
ok=TRUE;
+ }
+ }
if (!ok)
+ {
return FALSE;
}
+ }
p=p->next;
- }
+ }
p=Grab(sizeof *p);
@@ -568,7 +612,9 @@ static const char *NoMoveReason(char *fmt,...)
va_start(va,fmt);
if (fmt)
+ {
vsprintf(r,fmt,va);
+ }
va_end(va);
@@ -581,14 +627,14 @@ static Bool CheckImpossible(Level *l, State *s)
int f;
for(f=0;f<l->no;f++)
- {
+ {
int x,y;
x=s->box[f].x;
y=s->box[f].y;
if (!FindPos(l->target,l->no,x,y))
- {
+ {
int d;
int any_move;
@@ -598,40 +644,42 @@ static Bool CheckImpossible(Level *l, State *s)
any_move=FALSE;
for(d=0;d<4 && !any_move;d++)
- {
+ {
int nx,ny;
nx=x+move_dir[d].x;
ny=y+move_dir[d].y;
if (AT(l,nx,ny)!=WALL)
- {
+ {
int ox,oy;
ox=x+move_dir[(d+2)%4].x;
oy=y+move_dir[(d+2)%4].y;
if (AT(l,ox,oy)!=WALL)
+ {
any_move=TRUE;
}
}
+ }
if (!any_move)
- {
+ {
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))
- {
+ {
NoMoveReason("Group of 4 boxes at %d,%d",x,y);
return TRUE;
- }
}
}
+ }
return FALSE;
}
@@ -658,12 +706,14 @@ static State *CreateState(Byte dir, Bool must_push,
/* Check for walls
*/
if (AT(l,x,y)==WALL)
+ {
return NULL;
+ }
/* Check for boxes
*/
if ((p=FindPos(s->box,l->no,x,y)))
- {
+ {
int bx,by;
/* Can the box be pushed?
@@ -672,16 +722,22 @@ static State *CreateState(Byte dir, Bool must_push,
by=p->y+dy;
if (AT(l,bx,by)==WALL)
+ {
return NULL;
+ }
if (FindPos(s->box,l->no,bx,by))
+ {
return NULL;
+ }
push=TRUE;
- }
+ }
if (!push && must_push)
+ {
return NULL;
+ }
new=Grab(sizeof *new);
new->box=Grab(sizeof(Pos)*l->no);
@@ -691,7 +747,7 @@ static State *CreateState(Byte dir, Bool must_push,
new->player.y=y;
if (push)
- {
+ {
p=FindPos(new->box,l->no,x,y);
p->x+=dx;
@@ -700,11 +756,11 @@ static State *CreateState(Byte dir, Bool must_push,
/* (Very) basic checks to see if the move has made the level impossible
*/
if (check_possible && CheckImpossible(l,new))
- {
+ {
FreeState(new);
return NULL;
- }
}
+ }
new->left=NULL;
@@ -724,16 +780,18 @@ static State *CreateState(Byte dir, Bool must_push,
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;
if (!AddNewState(l,new))
- {
+ {
NoMoveReason("State matches previous");
FreeState(new);
return NULL;
- }
+ }
return new;
}
@@ -742,18 +800,18 @@ static State *CreateState(Byte dir, Bool must_push,
static void SetChain(State **first, State **curr, State *new)
{
if (new)
- {
+ {
if (!*first)
- {
+ {
*first=new;
*curr=*first;
- }
+ }
else
- {
+ {
(*curr)->next=new;
(*curr)=new;
- }
}
+ }
}
@@ -769,13 +827,17 @@ static void SubSolve(Level *level, State *state,int depth,
int f;
if (depth>=max_depth)
+ {
return;
+ }
if (depth==1)
+ {
last=time(NULL);
+ }
switch(log)
- {
+ {
case QUIET:
break;
case VERBOSE:
@@ -787,7 +849,7 @@ static void SubSolve(Level *level, State *state,int depth,
printf("%d,%ld,%d,%d\n",
depth,time(NULL)-last,GrabSize(),GetStateNum());
break;
- }
+ }
last=time(NULL);
@@ -798,64 +860,86 @@ static void SubSolve(Level *level, State *state,int depth,
curr=NULL;
while(s)
- {
+ {
/* Check to see whether the level is solved
*/
ok=TRUE;
for(f=0;(f<level->no) && ok;f++)
+ {
if (!FindPos(s->box,level->no,
level->target[f].x,level->target[f].y))
+ {
ok=FALSE;
+ }
+ }
if (ok)
- {
+ {
s->path=TRUE;
s=s->parent;
while(s)
- {
+ {
s->path=TRUE;
s=s->parent;
- }
- return;
}
+ return;
+ }
/* Check moves
*/
if (s->dir==DIR_RIGHT)
+ {
s->left=new=CreateState(DIR_LEFT,!s->pushed,level,s,TRUE);
+ }
else
+ {
s->left=new=CreateState(DIR_LEFT,FALSE,level,s,TRUE);
+ }
SetChain(&first,&curr,new);
if (s->dir==DIR_LEFT)
+ {
s->right=new=CreateState(DIR_RIGHT,!s->pushed,level,s,TRUE);
+ }
else
+ {
s->right=new=CreateState(DIR_RIGHT,FALSE,level,s,TRUE);
+ }
SetChain(&first,&curr,new);
if (s->dir==DIR_DOWN)
+ {
s->up=new=CreateState(DIR_UP,!s->pushed,level,s,TRUE);
+ }
else
+ {
s->up=new=CreateState(DIR_UP,FALSE,level,s,TRUE);
+ }
SetChain(&first,&curr,new);
if (s->dir==DIR_UP)
+ {
s->down=new=CreateState(DIR_DOWN,!s->pushed,level,s,TRUE);
+ }
else
+ {
s->down=new=CreateState(DIR_DOWN,FALSE,level,s,TRUE);
+ }
SetChain(&first,&curr,new);
s=s->next;
- }
+ }
if (first)
+ {
SubSolve(level,first,++depth,max_depth,log);
+ }
}
@@ -871,30 +955,32 @@ static void Solve(Level *level, Route route, int max_depth, LogMode log)
s=level->state;
while(s)
- {
+ {
if (s->left && s->left->path)
- {
+ {
strcat(route,"L");
s=s->left;
- }
+ }
else if (s->right && s->right->path)
- {
+ {
strcat(route,"R");
s=s->right;
- }
+ }
else if (s->up && s->up->path)
- {
+ {
strcat(route,"U");
s=s->up;
- }
+ }
else if (s->down && s->down->path)
- {
+ {
strcat(route,"D");
s=s->down;
- }
+ }
else
+ {
s=NULL;
}
+ }
}
@@ -906,65 +992,86 @@ static void CursesDisplay(Level *l, State *s, int play)
char allow[80];
for(x=0;x<l->width;x++)
- {
+ {
char num[20];
sprintf(num,"%d",x);
f=0;
+
while(num[f])
+ {
mvaddch(3+f,3+x,num[f++]);
+ }
for(y=0;y<l->height;y++)
- {
+ {
if (x==0)
+ {
mvprintw(6+y,0,"%d",y);
+ }
mvaddch(6+y,3+x,GetGlyph(l,s,x,y));
- }
}
+ }
strcpy(allow,"Moves: ");
if (s->left)
+ {
strcat(allow,"left ");
+ }
if (s->right)
+ {
strcat(allow,"right ");
+ }
if (s->up)
+ {
strcat(allow,"up ");
+ }
if (s->down)
+ {
strcat(allow,"down ");
+ }
if (s->parent)
+ {
strcat(allow,"back");
+ }
while(strlen(allow)<70)
+ {
strcat(allow," ");
+ }
mvaddstr(l->height+11,0,allow);
if (!play)
- {
+ {
if (s->path)
+ {
mvaddstr(l->height+10,0,"On solved path: YES");
+ }
else
+ {
mvaddstr(l->height+10,0,"On solved path: NO ");
}
+ }
else
- {
+ {
int depth=0;
while(s)
- {
+ {
depth++;
s=s->parent;
- }
+ }
mvprintw(l->height+10,0,"Depth: %d ",depth);
- }
+ }
mvprintw(LINES-3,0,"Last reason: %-40.40s",NoMoveReason(NULL));
@@ -979,7 +1086,9 @@ static void Interactive(Level *l, int play)
State *s;
if (!play)
+ {
Solve(l,route,999,VERBOSE);
+ }
initscr();
cbreak();
@@ -998,10 +1107,12 @@ static void Interactive(Level *l, int play)
"Q to quit, Backspace/B to step back");
if (!play)
+ {
mvprintw(l->height+9,0,"Route:%s",route);
+ }
while(!quit)
- {
+ {
int key;
CursesDisplay(l,s,play);
@@ -1009,59 +1120,85 @@ static void Interactive(Level *l, int play)
key=getch();
if (key=='p' || key=='P')
- {
+ {
if (s->left && s->left->path)
+ {
key=KEY_LEFT;
+ }
if (s->right && s->right->path)
+ {
key=KEY_RIGHT;
+ }
if (s->up && s->up->path)
+ {
key=KEY_UP;
+ }
if (s->down && s->down->path)
+ {
key=KEY_DOWN;
}
+ }
switch(key)
- {
+ {
case KEY_BACKSPACE:
case 'b':
case 'B':
if (s->parent)
+ {
s=s->parent;
+ }
break;
case KEY_LEFT:
if (play && !s->left)
+ {
s->left=CreateState(DIR_LEFT,FALSE,l,s,TRUE);
+ }
if (s->left)
+ {
s=s->left;
+ }
break;
case KEY_RIGHT:
if (play && !s->right)
+ {
s->right=CreateState(DIR_RIGHT,FALSE,l,s,TRUE);
+ }
if (s->right)
+ {
s=s->right;
+ }
break;
case KEY_DOWN:
if (play && !s->down)
+ {
s->down=CreateState(DIR_DOWN,FALSE,l,s,TRUE);
+ }
if (s->down)
+ {
s=s->down;
+ }
break;
case KEY_UP:
if (play && !s->up)
+ {
s->up=CreateState(DIR_UP,FALSE,l,s,TRUE);
+ }
if (s->up)
+ {
s=s->up;
+ }
break;
case 'q':
@@ -1071,8 +1208,8 @@ static void Interactive(Level *l, int play)
default:
break;
- }
}
+ }
endwin();
}
diff --git a/makefile b/makefile
index 9cc2e62..08bb357 100644
--- a/makefile
+++ b/makefile
@@ -1,8 +1,7 @@
#
-#
# dbox - Sokoban solver
#
-# Copyright (C) 2001 Ian Cowburn (ianc@noddybox.demon.co.uk)
+# 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
@@ -45,7 +44,7 @@ $(TARGET): $(OBJECTS)
-include depend.mak
clean:
- -rm $(TARGET) $(TARGET).exe core *.stackdump *.o depend.mak
+ -rm -f $(TARGET) $(TARGET).exe core *.stackdump *.o depend.mak
depend: $(DEPEND)
@echo Dependencies updated....