diff options
| author | Ian C <ianc@noddybox.co.uk> | 2009-02-05 23:19:07 +0000 | 
|---|---|---|
| committer | Ian C <ianc@noddybox.co.uk> | 2009-02-05 23:19:07 +0000 | 
| commit | 8bb30d97767e56bc5304c82013bce4daa99f3e12 (patch) | |
| tree | 0ce708223ed5bd6ffdc031ac864492becb16ea0d | |
| parent | cc307a968ef1036d6cd96ce38c64cc195950ea46 (diff) | |
Reformatted code
| -rw-r--r-- | dbox.c | 401 | ||||
| -rw-r--r-- | makefile | 5 | 
2 files changed, 271 insertions, 135 deletions
| @@ -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();  } @@ -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.... | 
