/*
    dbox - Sokoban level 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

    -------------------------------------------------------------------------

*/
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>
#else
#include <curses.h>
#endif

/* Global macros
*/
#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

#define MAX_ROUTE	8192


/* ---------------------------------------- TYPES
*/
typedef unsigned long long	map_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_t;

#define DIR_NONE	-1
#define DIR_LEFT	0
#define DIR_UP		1
#define DIR_RIGHT	2
#define DIR_DOWN	3

static int g_move_dir[4] = {-1, -1, 1, 1};

typedef struct state_t
{
    int			player;
    int			*box;
    int			path;
    int			dir;
    int			pushed;
    map_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_targets;
    int			no_boxes;
    int			*target;
    glyph_t		*map;
    state_t		*state;
} level_t;

#define AT(l,x,y)	((l)->map[(l)->width*(y)+(x)])
#define ATP(l,p)	((l)->map[p])

/* State caches
*/
typedef struct cache_t
{
    const state_t	*state;
    struct cache_t	*next;
} cache_t;

#define CACHE_SIZE	65071

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 p_size);
static void	*Copy(const void *p_source, size_t p_size);

static void	Interactive(const level_t *p_level, int p_play, int p_check);

static level_t	*Load(const char *p_path);

static void	FreeLevel(level_t *p_level);

static void	Display(const level_t *p_level, const state_t *p_state);

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);
}


/* ---------------------------------------- UTIL
*/
static void *Grab(size_t p_size)
{
    void *new;

    new = malloc(p_size);

    if (!new)
    {
	fprintf(stderr,"%s: malloc(%lu) failed\n",
			g_name, (unsigned long)p_size);
	exit(EXIT_FAILURE);
    }

    return new;
}


static void *Copy(const void *p_source, size_t p_size)
{
    return memcpy(Grab(p_size), p_source, p_size);
}


static const int *FindPos(const int *p_poslist, int p_no, int p_p)
{
    while(p_no--)
    {
	if (*p_poslist == p_p)
	{
	    return p_poslist;
	}

	p_poslist++;
    }

    return NULL;
}


static int *FindPosForUpdate(int *p_poslist, int p_no, int p_p)
{
    while(p_no--)
    {
	if (*p_poslist == p_p)
	{
	    return p_poslist;
	}

	p_poslist++;
    }

    return NULL;
}


/* ---------------------------------------- LEVEL LOADING
*/
static const char *GetLine(FILE *p_fp)
{
    static char s[1024];
    size_t l;

    fgets(s, sizeof s, p_fp);

    if (feof(p_fp))
    {
	return NULL;
    }

    l = strlen(s);

    while (l > 0 && s[l-1] == '\n')
    {
	s[--l]=0;
    }

    return s;
}


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;
    const char *line;
    level_t *new;
    int x,y;
    int tno,bno;
    int pno;

    if (!(fp = fopen(p_path, "r")))
    {
    	return NULL;
    }

    /* Get name
    */
    new = Grab(sizeof *new);

    line = GetLine(fp);
    new->name = Grab(strlen(line) + 1);
    strcpy(new->name, line);

    /* Calc sizes and counts
    */
    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)))
    {
	new->height++;

	if (strlen(line)!=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 name
    */
    rewind(fp);
    GetLine(fp);

    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->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++)
    {
	line = GetLine(fp);

	for(x = 0; x < new->width; x++)
	{
	    switch(line[x])
	    {
		case WALL_GL:
		    AT(new,x,y) = WALL_GL;
		    break;

		case SPACE_GL:
		    AT(new,x,y) = SPACE_GL;
		    break;

		case BOX_TARGET_GL:
		case TARGET_GL:
		    AT(new,x,y) = SPACE_GL;
		    new->target[tno] = x + y * new->width;
		    tno++;

		    /* NOTE: Runs into following case for BOX_TARGET_GL
		    */
		    if (line[x] == TARGET_GL)
		    {
			break;
		    }

		case BOX_GL:
		    AT(new,x,y) = SPACE_GL;
		    new->state->box[bno] = x + y * new->width;
		    bno++;
		    break;

		case PLAYER_GL:
		    if (pno++ == 1)
		    {
			fprintf(stderr,"%s: too many "
					"players in %s\n", g_name, p_path);

			exit(EXIT_FAILURE);
		    }

		    AT(new,x,y) = SPACE_GL;
		    new->state->player = x + y * new->width;
		    break;

		default:
		    AT(new,x,y) = SPACE_GL;
		    break;
	    }
	}
    }

    fclose(fp);

    if (pno == 0)
    {
	fprintf(stderr,"%s: no player definied in %s\n", g_name, p_path);
	exit(EXIT_FAILURE);
    }

    return new;
}


static void FreeLevel(level_t *p_level)
{
}


static void Display(const level_t *p_level, const state_t *p_state)
{
    int x;
    int y;

    for(y = 0; y < p_level->height; y++)
    {
	for(x = 0; x < p_level->width; x++)
	{
	    putchar(GetGlyph(p_level, p_state, x, y));
	}

	putchar('\n');
    }
}


static char GetGlyph(const level_t *p_level, const state_t *p_state,
		     int p_x, int p_y)
{
    int p;

    p = p_x + p_y * p_level->width;

    if (AT(p_level, p_x, p_y) == WALL_GL)
    {
	return WALL_GL;
    }
    else if (FindPos(&p_state->player, 1, p))
    {
	return PLAYER_GL;
    }
    else if (FindPos(p_state->box, p_level->no_boxes, p) &&
		FindPos(p_level->target, p_level->no_targets, p))
    {
	return BOX_TARGET_GL;
    }
    else if (FindPos(p_state->box, p_level->no_boxes, p))
    {
	return BOX_GL;
    }
    else if (FindPos(p_level->target, p_level->no_targets, p))
    {
	return TARGET_GL;
    }
    else
    {
	return SPACE_GL;
    }
}


/* ---------------------------------------- SOLVER
*/
static void FreeState(state_t *p_state)
{
    free(p_state->box);
    free(p_state);
}


static void ClearStates(void)
{
    int f;

    g_cached_states = 0;

    for(f = 0; f < CACHE_SIZE; f++)
    {
	while(g_cache[f])
	{
	    cache_t *p;

	    p = g_cache[f]->next;
	    free(g_cache[f]);
	    g_cache[f] = p;
	}
    }
}


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 / p_level->width] =
    	0x01llu << ((p_state->player % p_level->width) * 2);

    for(f = 0; f < p_level->no_boxes; f++)
    {
	m[p_state->box[f] / p_level->width] |=
	    0x10llu << ((p_state->box[f] % p_level->width) * 2);
    }

    return m;
}


static map_t ROL(map_t p_val, int p_bits)
{
    while(p_bits--)
    {
    	p_val = (p_val >> 63) | (p_val << 1);
    }

    return p_val;
}


/* This is slightly better than the previous hash
*/
static map_t CreateHash(const level_t *p_level, const state_t *p_state)
{
    map_t *m;
    map_t hash;
    int f;

    m = CreateMap(p_level, p_state);

    hash = p_state->player;

    for(f = 0; f < p_level->height; f++)
    {
	hash ^= ROL(m[f], f);
    }

    free(m);

    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 hash;

    hash = p_state->hash % CACHE_SIZE;

    p = g_cache[hash];

    while(p)
    {
	if (p_state->player == p->state->player)
	{
	    int f;
	    map_t check;

	    check = FALSE;

	    for(f = 0; f < p_level->no_boxes && !check; f++)
	    {
	    	if (!FindPos(p->state->box, p_level->no_boxes, p_state->box[f]))
		{
		    check = TRUE;
		}
	    }

	    if (!check)
	    {
		return FALSE;
	    }
	}

	p=p->next;
    }

    p = Grab(sizeof *p);

    p->state = p_state;
    p->next = g_cache[hash];
    g_cache[hash] = p;

    g_cached_states++;

    return TRUE;
}


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 int CheckImpossible(const level_t *p_level, const state_t *p_state)
{
    int f;

    for(f = 0; f < p_level->no_boxes; f++)
    {
	int p;

	p = p_state->box[f];

	if (!FindPos(p_level->target, p_level->no_targets, p))
	{
	    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 np;

		np = p + g_move_dir[d];

		if (ATP(p_level, np) != WALL_GL)
		{
		    int op;

		    op = p + g_move_dir[(d+2)%4];

		    if (ATP(p_level, op) != WALL_GL)
		    {
		    	any_move=TRUE;
		    }
		}
	    }

	    if (!any_move)
	    {
		NoMoveReason("Couldn't push block at %d, %d",
					p%p_level->width, p/p_level->width);
		return TRUE;
	    }

	    /* Four blocks together is impossible
	    */
	    if (FindPos(p_state->box, p_level->no_boxes, p+1) &&
	    	FindPos(p_state->box, p_level->no_boxes, p+p_level->width) &&
	    	FindPos(p_state->box, p_level->no_boxes, p+p_level->width+1))
	    {
		NoMoveReason("Group of 4 boxes at %d, %d",
					p%p_level->width, p/p_level->width);
	    	return TRUE;
	    }
	}
    }

    return FALSE;
}


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_t *new;
    const int *p;
    int np;
    int push;
    int px;

    push = FALSE;

    px = g_move_dir[p_dir];

    np = p_state->player + px;

    /* Check for walls
    */
    if (ATP(p_level, np) == WALL_GL)
    {
    	return NULL;
    }

    /* Check for boxes
    */
    if ((p = FindPos(p_state->box, p_level->no_boxes, np)))
    {
	int bp;

	/* Can the box be pushed?
	*/
	bp = *p+px;

	if (ATP(p_level, bp) == WALL_GL)
	{
	    return NULL;
	}

	if (FindPos(p_state->box, p_level->no_boxes, bp))
	{
	    return NULL;
	}

	push = TRUE;
    }

    if (!push && p_must_push)
    {
    	return NULL;
    }

    new = Grab(sizeof *new);
    new->box = Copy(p_state->box, sizeof(int) * p_level->no_boxes);

    new->player = np;

    if (push)
    {
	int *pd;

	pd = FindPosForUpdate(new->box, p_level->no_boxes, np);

	*pd += px;

	/* (Very) basic checks to see if the move has made the level impossible
	*/
	if (p_check_possible && CheckImpossible(p_level, new))
	{
	    FreeState(new);
	    return NULL;
	}
    }


    new->left = NULL;
    new->right = NULL;
    new->up = NULL;
    new->down = NULL;

    new->parent = (state_t*) p_state;
    new->next = NULL;

    new->path = FALSE;
    new->pushed = push;
    new->dir = p_dir;

    /* Calculate a hash based on box and player positions 
    */
    new->hash = CreateHash(p_level, new);

    if (!AddNewState(p_level ,new))
    {
	NoMoveReason("State matches previous");
	FreeState(new);
	return NULL;
    }

    return new;
}


static void SetChain(state_t **first, state_t **curr, state_t *new)
{
    if (new)
    {
	if (!*first)
	{
	    *first = new;
	    *curr = *first;
	}
	else
	{
	    (*curr)->next = new;
	    (*curr) = new;
	}
    }
}


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_t *first;
    state_t *curr;
    state_t *new;
    state_t *s;
    int ok;
    int f;
    unsigned long long cache_size;
    unsigned long long max_cache;
    int warned;

    if (p_depth >= p_max_depth)
    {
	fprintf(stderr, "%s: blown maximum solution depth of %d\n",
				g_name, p_max_depth);
    	return;
    }

    if (p_depth == 1)
    {
    	last=time(NULL);
    }

    if (p_log)
    {
	printf("Searching %d moves deep (%ld secs, %llu unique states)\n",
			p_depth, time(NULL) - last, g_cached_states);
    }

    if (g_signal)
    {
    	DumpCacheDistribution();
	g_signal = 0;
    }

    last = time(NULL);

    /* Loop across all states at this depth
    */
    s = p_state;
    first = NULL;
    curr = NULL;

    cache_size = g_cached_states;
    max_cache = cache_size * 4;

    if (max_cache < cache_size)
    {
    	max_cache = 0xffffffffffffffffllu;
    }

    warned = FALSE;

    while(s)
    {
	/* Check to see whether the level is solved
	*/
	ok=TRUE;

	for(f = 0; f < p_level->no_targets && ok; f++)
	{
	    if (!FindPos(s->box, p_level->no_boxes, p_level->target[f]))
	    {
		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 = CreateState(DIR_LEFT, !s->pushed, p_level, s, TRUE);
	    new = s->left;
	}
	else
	{
	    s->left = CreateState(DIR_LEFT, FALSE, p_level, s, TRUE);
	    new = s->left;
	}

	SetChain(&first, &curr, new);

	if (s->dir == DIR_LEFT)
	{
	    s->right = CreateState(DIR_RIGHT, !s->pushed, p_level, s, TRUE);
	    new = s->right;
	}
	else
	{
	    s->right = CreateState(DIR_RIGHT, FALSE, p_level, s, TRUE);
	    new = s->right;
	}

	SetChain(&first, &curr, new);

	if (s->dir == DIR_DOWN)
	{
	    s->up = CreateState(DIR_UP, !s->pushed, p_level, s, TRUE);
	    new = s->up;
	}
	else
	{
	    s->up = CreateState(DIR_UP, FALSE, p_level, s, TRUE);
	    new = s->up;
	}

	SetChain(&first, &curr, new);

	if (s->dir == DIR_UP)
	{
	    s->down = CreateState(DIR_DOWN, !s->pushed, p_level, s, TRUE);
	    new = s->down;
	}
	else
	{
	    s->down = CreateState(DIR_DOWN, FALSE, p_level, s, TRUE);
	    new = s->down;
	}

	SetChain(&first, &curr, new);

	s = s->next;

	if (g_cached_states < cache_size)
	{
	    printf("WARNING: number of cached states has wrapped\n");
	    cache_size = g_cached_states;
	}

	if (p_depth > 1 && !warned && g_cached_states > max_cache)
	{
	    printf("WARNING: got over four times the number of "
	    		"cached states at one depth...\n");
	    warned = TRUE;
	}
    }

    if (first)
    {
	SubSolve(p_level, first, ++p_depth, p_max_depth, p_log);
    }
}


static void Solve(const level_t *p_level, route_t p_route,
		  int p_max_depth, int p_log)
{
    state_t *s;

    p_route[0] = 0;
    ClearStates();

    SubSolve(p_level, p_level->state, 1, p_max_depth, p_log);

    s = p_level->state;

    while(s)
    {
	if (s->left && s->left->path)
	{
	    strcat(p_route,"L");
	    s = s->left;
	}
	else if (s->right && s->right->path)
	{
	    strcat(p_route,"R");
	    s = s->right;
	}
	else if (s->up && s->up->path)
	{
	    strcat(p_route,"U");
	    s = s->up;
	}
	else if (s->down && s->down->path)
	{
	    strcat(p_route,"D");
	    s = s->down;
	}
	else
	{
	    s=NULL;
	}
    }
}


/* ---------------------------------------- INTERACTIVE MODE
*/
static int StateDepth(const state_t *p_state)
{
    int depth = 0;

    while(p_state)
    {
	depth++;
	p_state = p_state->parent;
    }

    return depth;
}


static void CursesDisplay(const level_t *p_level,
			  const state_t *p_state,
			  int p_play,
			  const route_t p_route)
{
    char allow[80];
    int x;
    int y;
    int f;

    for(x = 0; x < p_level->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 < p_level->height; y++)
	{
	    if (x == 0)
	    {
	    	mvprintw(6+y, 0, "%d", y);
	    }

	    mvaddch(6+y, 3+x, GetGlyph(p_level, p_state, x, y));
	}
    }

    strcpy(allow,"Moves: ");

    if (p_state->left)
    {
    	strcat(allow, "left ");
    }

    if (p_state->right)
    {
    	strcat(allow, "right ");
    }

    if (p_state->up)
    {
    	strcat(allow, "up ");
    }

    if (p_state->down)
    {
    	strcat(allow, "down ");
    }

    if (p_state->parent)
    {
    	strcat(allow, "back");
    }

    while(strlen(allow) < 70)
    {
    	strcat(allow, "     ");
    }

    mvaddstr(p_level->height + 11, 0, allow);

    if (!p_play)
    {
	if (p_state->path)
	{
	    mvaddstr(p_level->height + 10, 0, "On solved path: YES");
	}
	else
	{
	    mvaddstr(p_level->height + 10, 0, "On solved path: NO ");
	}
    }
    else
    {
	int d;

	d = StateDepth(p_state);

	if (d == MAX_ROUTE)
	{
	    mvprintw(p_level->height + 10, 0, "Depth: MAX");
	}
	else
	{
	    mvprintw(p_level->height + 10, 0, "Depth: %d ", d);
	}

	if (strlen(p_route) > COLS-6)
	{
	    mvprintw(p_level->height + 9, 0, "Route:%*.*s...",
						COLS-10, COLS-10, p_route);
	}
	else
	{
	    mvprintw(p_level->height + 9, 0, "Route:%s ", p_route);
	}
    }

    mvprintw(LINES - 3, 0, "Last reason: %-40.40s", NoMoveReason(NULL));

    refresh();
}


static void Interactive(const level_t *p_level, int p_play, int p_check)
{
    int quit;
    route_t route = {0};
    state_t *s;

    if (!p_play)
    {
	Solve(p_level, route, MAX_ROUTE, TRUE);
    }

    initscr();
    cbreak();
    noecho();
    nonl();
    intrflush(stdscr, FALSE);
    keypad(stdscr, TRUE);

    quit = FALSE;
    s = p_level->state;

    clear();
    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 (!p_play)
    {
    	if (route[0])
	{
	    if (strlen(route) > COLS-6)
	    {
		mvprintw(p_level->height + 9, 0, "Route:%*.*s...",
						    COLS-10, COLS-10, route);
	    }
	    else
	    {
		mvprintw(p_level->height + 9, 0, "Route:%s", route);
	    }
	}
	else
	{
	    mvprintw(p_level->height + 9, 0, "Route: None found -- "
						"level possibly impossible");
	}
    }

    while(!quit)
    {
	int key;

	CursesDisplay(p_level, s, p_play, route);

	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;

		    if (p_play)
		    {
		    	route[StateDepth(s) - 1] = 0;
		    }
		}
	    	break;

	    case KEY_LEFT:
		if (p_play && !s->left && StateDepth(s) < MAX_ROUTE)
		{
		    s->left = CreateState(DIR_LEFT, FALSE, p_level, s, p_check);
		}

		if (s->left)
		{
		    if (p_play)
		    {
		    	route[StateDepth(s) - 1] = 'L';
		    }

		    s=s->left;
		}
	    	break;

	    case KEY_RIGHT:
		if (p_play && !s->right && StateDepth(s) < MAX_ROUTE)
		{
		    s->right = CreateState(DIR_RIGHT, FALSE, p_level,
		    				s, p_check);
		}

		if (s->right)
		{
		    if (p_play)
		    {
		    	route[StateDepth(s) - 1] = 'R';
		    }

		    s = s->right;
		}
	    	break;

	    case KEY_DOWN:
		if (p_play && !s->down && StateDepth(s) < MAX_ROUTE)
		{
		    s->down = CreateState(DIR_DOWN, FALSE, p_level, s, p_check);
		}

		if (s->down)
		{
		    if (p_play)
		    {
		    	route[StateDepth(s) - 1] = 'D';
		    }

		    s = s->down;
		}
	    	break;

	    case KEY_UP:
		if (p_play && !s->up && StateDepth(s) < MAX_ROUTE)
		{
		    s->up = CreateState(DIR_UP, FALSE, p_level, s, p_check);
		}

		if (s->up)
		{
		    if (p_play)
		    {
		    	route[StateDepth(s) - 1] = 'U';
		    }

		    s = s->up;
		}
	    	break;

	    case 'q':
	    case 'Q':
	    	quit = TRUE;
		break;

	    default:
	    	break;
	}
    }

    endwin();

    if (p_play)
    {
	printf("Route = '%s'\n",route);
    }
}


/* ---------------------------------------- MAIN
*/
int main(int argc, char *argv[])
{
    int interact = FALSE;
    int play = FALSE;
    int check = TRUE;
    int base;
    int f;
    int verbose = FALSE;

    g_name = argv[0];

    base = 1;

    while(argv[base] && argv[base][0] == '-')
    {
    	switch(argv[base++][1])
	{
	    case 'i':
		interact = TRUE;
		break;

	    case 'p':
		interact = TRUE;
		play = TRUE;
		break;

	    case 'P':
		interact = TRUE;
		play = TRUE;
		check = FALSE;
		break;

	    case 'v':
		verbose = TRUE;
		break;

	    default:
	    	base = argc;
	    	break;
	}
    }

    if (!argv[base])
    {
	fprintf(stderr,"%s: usage %s [-v|-i|-p|-P] file [file2 ...]\n",
				g_name, g_name);
	return EXIT_FAILURE;
    }

    signal(SIGUSR1, SigHandler);

    for(f = base; f < argc; f++)
    {
	route_t route;
	level_t *level;

	if (!(level=Load(argv[f])))
	{
	    fprintf(stderr,"%s: %s could not be read\n", g_name, argv[f]);
	}
	else
	{
	    g_move_dir[DIR_UP] = -level->width;
	    g_move_dir[DIR_DOWN] = level->width;

	    if (interact)
	    {
	    	Interactive(level, play, check);
	    }
	    else
	    {
		printf("Solving %s\n\n", level->name);

		Display(level, level->state);

		Solve(level, route, MAX_ROUTE, verbose);

		if (route[0])
		{
		    printf("\nRoute = '%s'\n",route);
		}
		else
		{
		    printf("\nNo solution found!\n");
		}
	    }

	    FreeLevel(level);
	}
    }

    return EXIT_SUCCESS;
}


/* END OF FILE */