diff options
Diffstat (limited to 'dbox.c')
| -rw-r--r-- | dbox.c | 1081 |
1 files changed, 1081 insertions, 0 deletions
@@ -0,0 +1,1081 @@ +/* + + dbox - Sokoban level solver + + Copyright (C) 2001 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 + + ------------------------------------------------------------------------- + +*/ +static const char cvs_id[]="$Id$"; + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <stdarg.h> +#include <time.h> + +#if (USECURSES == ncurses) +# include <ncurses.h> +#else +# include <curses.h> +#endif + +#ifndef TRUE +#define TRUE 1 +#endif + +#ifndef FALSE +#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 MEGABYTE (1024*1024) + +/* ---------------------------------------- TYPES +*/ +typedef signed char PosInt; +typedef unsigned char Byte; +typedef Byte Bool; + +typedef char Route[1024]; + +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; + +#define DIR_NONE -1 +#define DIR_LEFT 0 +#define DIR_UP 1 +#define DIR_RIGHT 2 +#define DIR_DOWN 3 + +typedef struct + { + 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; + +typedef struct + { + char *name; + int width,height; + int no; + Pos *target; + MapChar *map; + State *state; + } Level; + +#define STATE_HASH 0x10000 + +typedef struct StateMap + { + State *s; + struct StateMap *next; + } StateMap; + +static StateMap *state_map[STATE_HASH]={NULL}; +static int state_map_no=0; + +#define AT(l,x,y) ((l)->map[(l)->width*(y)+(x)]) + + +/* ---------------------------------------- PROTOS +*/ +static void *Grab(size_t l); + +static void Interactive(Level *l, int play); + +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); + + +/* ---------------------------------------- MAIN +*/ +int main(int argc, char *argv[]) +{ + int interact=FALSE; + int play=FALSE; + int base; + int f; + LogMode mode=VERBOSE; + + 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); + + Solve(level,route,999,mode); + + printf("\nRoute = '%s'\n",route); + } + + FreeLevel(level); + } + } + + return EXIT_SUCCESS; +} + + +/* ---------------------------------------- UTIL +*/ +static size_t grab_tot=0; +static int grab_last_mb=0; +static int grab_mb=0; + +static void *Grab(size_t l) +{ + size_t *p; + + p=malloc(l+sizeof(size_t)); + + if (!p) + { + fprintf(stderr,"%s: malloc(%d) failed\n",name,l); + 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 (grab_mb==MAXMB) + { + fprintf(stderr,"Quitting: Allocated %d Mb\n",grab_mb); + exit(EXIT_FAILURE); + } + } + + return p+1; +} + + +static void Release(void *p) +{ + size_t *pp; + + pp=p; + + pp--; + + grab_tot-=*pp; + + free(pp); +} + + +static int GrabSize(void) +{ + return grab_mb; +} + + +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; +} + + +/* ---------------------------------------- LEVEL LOADING +*/ +static char *GetLine(FILE *fp) +{ + static char s[1024]; + + fgets(s,sizeof s,fp); + + if (feof(fp)) + return NULL; + + if (s[strlen(s)-1]=='\n') + s[strlen(s)-1]=0; + + return s; +} + +static Level *Load(const char *path) +{ + FILE *fp; + char *line; + Level *new; + int x,y; + int tno,bno; + int pno; + + if (!(fp=fopen(path,"r"))) + return NULL; + + new=Grab(sizeof *new); + + line=GetLine(fp); + new->name=Grab(strlen(line)+1); + strcpy(new->name,line); + + new->no=atoi(GetLine(fp)); + + /* Calc sizes + */ + new->width=strlen(GetLine(fp)); + 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 + */ + rewind(fp); + GetLine(fp); + GetLine(fp); + + new->target=Grab(sizeof(Pos)*new->no); + new->map=Grab(sizeof(MapChar)*(new->width*new->height)); + + 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; + + tno=0; + bno=0; + 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; + + case SPACE_GL: + AT(new,x,y)=SPACE; + 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; + tno++; + + /* 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; + new->state->box[bno].y=y; + bno++; + break; + + 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; +} + + +static void FreeLevel(Level *l) +{ +} + + +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; + +} + + +/* ---------------------------------------- SOLVER +*/ +static void FreeState(State *s) +{ + Release(s->box); + Release(s); +} + + +static void ClearStates(void) +{ + int f; + + 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; + } +} + + +static Bool AddNewState(Level *l, State *s) +{ + StateMap *p; + int hash; + + hash=s->hash%STATE_HASH; + + 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); + + p->s=s; + p->next=state_map[hash]; + state_map[hash]=p; + + state_map_no++; + + return TRUE; +} + + +static int GetStateNum(void) +{ + return state_map_no; +} + + +static const char *NoMoveReason(char *fmt,...) +{ + static char r[512]; + va_list va; + + va_start(va,fmt); + + if (fmt) + vsprintf(r,fmt,va); + + va_end(va); + + return r; +} + + +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; + + /* Check that the box can be pushed at all for the next go + (Simple wall based check) + */ + 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; +} + + +static State *CreateState(Byte dir, Bool must_push, + Level *l, State *s, Bool check_possible) +{ + State *new; + Pos *p; + int x,y; + int push; + int dx,dy; + int f; + + dx=move_dir[dir].x; + dy=move_dir[dir].y; + + push=FALSE; + + x=s->player.x+dx; + y=s->player.y+dy; + + /* 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? + */ + bx=p->x+dx; + 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); + memcpy(new->box,s->box,sizeof(Pos)*l->no); + + new->player.x=x; + new->player.y=y; + + if (push) + { + p=FindPos(new->box,l->no,x,y); + + p->x+=dx; + p->y+=dy; + + /* (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; + new->right=NULL; + new->up=NULL; + new->down=NULL; + + new->parent=s; + new->next=NULL; + + new->path=FALSE; + new->pushed=push; + new->dir=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; + + if (!AddNewState(l,new)) + { + NoMoveReason("State matches previous"); + FreeState(new); + return NULL; + } + + return new; +} + + +static void SetChain(State **first, State **curr, State *new) +{ + if (new) + { + if (!*first) + { + *first=new; + *curr=*first; + } + else + { + (*curr)->next=new; + (*curr)=new; + } + } +} + + +static void SubSolve(Level *level, State *state,int depth, + int max_depth, LogMode log) +{ + static time_t last=0; + State *first; + State *curr; + State *new; + State *s; + int ok; + int f; + + if (depth>=max_depth) + return; + + if (depth==1) + last=time(NULL); + + switch(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; + } + + last=time(NULL); + + /* Loop across all states at this depth + */ + s=state; + first=NULL; + 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; + } + + /* 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); +} + + +static void Solve(Level *level, Route route, int max_depth, LogMode log) +{ + State *s; + + route[0]=0; + ClearStates(); + + SubSolve(level,level->state,1,max_depth,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; + } +} + + +/* ---------------------------------------- INTERACTIVE MODE +*/ +static void CursesDisplay(Level *l, State *s, int play) +{ + int x,y,f; + 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)); + + refresh(); +} + + +static void Interactive(Level *l, int play) +{ + int quit; + Route route; + State *s; + + if (!play) + Solve(l,route,999,VERBOSE); + + initscr(); + cbreak(); + noecho(); + nonl(); + intrflush(stdscr,FALSE); + keypad(stdscr,TRUE); + + quit=FALSE; + s=l->state; + + clear(); + mvaddstr(0,0,l->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); + + while(!quit) + { + int key; + + CursesDisplay(l,s,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': + case 'Q': + quit=TRUE; + break; + + default: + break; + } + } + + endwin(); +} + + +/* END OF FILE */ |