Reformatted code

1 files changed, 269 insertions, 132 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();
 }