pacman

packman

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define CELL_BLOCK  0x00
#define CELL_WAY    0x01
#define CELL_WAY1   0x01
#define CELL_WAY2   0x02
#define CELL_WAY3   0x03
#define CELL_WAY4   0x04

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

#define BUF_SIZE     256

typedef struct
{
	unsigned char x;
	unsigned char y;
}packman_t;

typedef struct
{
	unsigned char x;
	unsigned char y;
	unsigned char type;
	unsigned char dir;
}enemy_t;

typedef struct
{
	unsigned short t;
    packman_t p;
	enemy_t *e;
	unsigned char *dot;
	unsigned short dotnum;
	char *path;
}state_t;

typedef struct
{
	int timeup;
	int width;
	int height;
	unsigned char *cell;
	unsigned char enemynum;
	int bestscore;
}map_t;

typedef struct
{
	unsigned char dir;
	state_t *state;
	struct node_t *parent;
//	struct node_t *next;
//	struct node_t *child;
}node_t;

#define CELL_INDEX(MAP, X, Y) (5 * ((Y) * MAP->width + X))
#define CELL(MAP, X, Y) (MAP->cell[(5 * ((Y) * MAP->width + X))])
//#define CELL_DOWN(MAP, X, Y)  (MAP->cell[(Y + 1) * MAP->width + X])
//#define CELL_LEFT(MAP, X, Y)  (MAP->cell[(Y) * MAP->width + X - 1])
//#define CELL_UP(MAP, X, Y)    (MAP->cell[(Y - 1) * MAP->width + X])
//#define CELL_RIGHT(MAP, X, Y) (MAP->cell[(Y) * MAP->width + X + 1])

#define CELL_DOWN(MAP, X, Y)  (MAP->cell[5 * ((Y + 1) * MAP->width + X)])
#define CELL_LEFT(MAP, X, Y)  (MAP->cell[5 * ((Y) * MAP->width + (X - 1))])
#define CELL_UP(MAP, X, Y)    (MAP->cell[5 * ((Y - 1) * MAP->width + X)])
#define CELL_RIGHT(MAP, X, Y) (MAP->cell[5 * ((Y) * MAP->width + (X + 1))])

#define ENEMY_DOWN(ENEMY)  ENEMY->y++; ENEMY->dir = DIR_DOWN;
#define ENEMY_LEFT(ENEMY)  ENEMY->x--; ENEMY->dir = DIR_LEFT;
#define ENEMY_UP(ENEMY)    ENEMY->y--; ENEMY->dir = DIR_UP;
#define ENEMY_RIGHT(ENEMY) ENEMY->x++; ENEMY->dir = DIR_RIGHT;

#define DOT_INDEX(STATE, MAP, X, Y) ((Y) * MAP->width + X)
#define DOT(STATE, MAP, X, Y) (STATE->dot[(Y) * MAP->width + X])
#define DOT_DOWN(STATE, MAP, X, Y) (STATE->dot[(Y + 1) * MAP->width + X])
#define DOT_LEFT(STATE, MAP, X, Y) (STATE->dot[(Y) * MAP->width + X - 1])
#define DOT_UP(STATE, MAP, X, Y) (STATE->dot[(Y - 1) * MAP->width + X])
#define DOT_RIGHT(STATE, MAP, X, Y) (STATE->dot[(Y) * MAP->width + X + 1])

state_t *state_new()
{
	state_t *state;
	state = malloc(sizeof(state_t));
	state->t = 0;
	state->dot = NULL;
	state->dotnum = 0;
	state->e = NULL;
	return state;
}

int enemy_add(state_t *state, map_t *map, enemy_t e)
{
	map->enemynum++;
	if(state->e){
		state->e = (enemy_t *)realloc(state->e,
									  sizeof(enemy_t) * map->enemynum);
	}else{
		state->e = (enemy_t *)malloc(sizeof(enemy_t) * map->enemynum);
	}
	state->e[map->enemynum - 1] = e;
}

map_t *map_new(const char *file, state_t *state)
{
	FILE *fp;
	int x, y;
	char buf[BUF_SIZE];
	size_t len;
	map_t *map;
	enemy_t e;
	int c;

	fp = fopen(file, "r");
	if(!fp){
		fprintf(stderr, "error: cannot open file: %s\n", file);
		return NULL;
	}

	map = malloc(sizeof(map_t));
	fscanf(fp, "%d\n", &map->timeup);
	fscanf(fp, "%d %d\n", &map->width, &map->height);

	printf("T: %d\n", map->timeup);
	printf("map size: %d, %d\n", map->width, map->height);
	map->cell = malloc(map->width * map->height * 5);
	state->dot = malloc(map->width * map->height);
	state->e = NULL;
	map->enemynum = 0;

	y = 0;
	while(fgets(buf, BUF_SIZE - 1, fp)){
		len = strlen(buf);
		if(buf[len - 1] == '\n'){
			buf[--len] = '\0';
		}
		if(len != map->width){
			fprintf(stderr, "error: invalid input\n");
			return NULL;
		}
		for(x=0; x<map->width; x++){
			DOT(state, map, x, y) = 0;
			CELL(map, x, y) = 1;
			switch(buf[x]){
			case '@':
				state->p.x = x;
				state->p.y = y;
				break;
			case 'V':
			case 'H':
			case 'L':
			case 'R':
			case 'J':
				e.type = buf[x];
				e.x = x;
				e.y = y;
				e.dir = DIR_NONE;
				enemy_add(state, map, e);
				break;
			case '#':
				CELL(map, x, y) = CELL_BLOCK;
				break;
			case '.':
				DOT(state, map, x, y) = 1;
				state->dotnum++;
			case ' ':
				break;
			default:
				printf("error: illigal char: %c\n", buf[x]);
			}
		}
		y++;
	}
	fclose(fp);

	printf("enemynum: %d\n", map->enemynum);
	for(y=1; y<map->height - 1; y++){
		for(x=1; x<map->width - 1; x++){
			if(!CELL(map, x, y)){
				continue;
			}
			c = 0;
			if(CELL_DOWN(map, x, y)) c++;
			if(CELL_LEFT(map, x, y)) c++;
			if(CELL_UP(map, x, y)) c++;
			if(CELL_RIGHT(map, x, y)) c++;
			CELL(map, x, y) = c;
		}
	}

	for(y=1; y<map->height - 1; y++){
		for(x=1; x<map->width - 1; x++){
			if(!CELL(map, x, y)){
				continue;
			}
			c = CELL_INDEX(map, x, y);
			map->cell[c + DIR_DOWN] = CELL_DOWN(map, x, y);
			map->cell[c + DIR_LEFT] = CELL_LEFT(map, x, y);
			map->cell[c + DIR_UP] = CELL_UP(map, x, y);
			map->cell[c + DIR_RIGHT] = CELL_RIGHT(map, x, y);
		}
	}
	map->bestscore = state->dotnum;
	return map;
}

unsigned long stat_node = 0;

node_t *node_new(node_t *parent, state_t *state, map_t *map)
{
	node_t *node;
	node = malloc(sizeof(node_t));
	node->parent = (struct node_t *)parent;
	node->state = state_new();
	memcpy(node->state, state, sizeof(state_t));
	node->state->dot = malloc(map->width * map->height);
	memcpy(node->state->dot, state->dot, map->width * map->height);
	node->state->e = (enemy_t *)malloc(sizeof(enemy_t) * map->enemynum);
	memcpy(node->state->e, state->e, sizeof(enemy_t) * map->enemynum);
	stat_node++;
	if(stat_node % 100000000 == 0){
		printf("stat_node: %ld\n", stat_node);
	}
	return node;
}

void *state_free(state_t *state)
{
	if(state->dot){
		free(state->dot);
	}
	if(state->e){
		free(state->e);
	}
	free(state);
}

void *map_free(map_t *map)
{
	if(map->cell){
		free(map->cell);
	}
	free(map);
}

void *node_free(node_t *node)
{
	if(node->state){
		state_free(node->state);
	}
	free(node);
}

void state_print(state_t *state, map_t *map)
{
	int x, y;
	int c;
	int i;
	printf("t: %d\n", state->t);
	printf("dot: %d\n", state->dotnum);

	for(y=0; y<map->height; y++){
		for(x=0; x<map->width; x++){
			if(x == state->p.x && y == state->p.y){
				c = '@';
			}else if(!CELL(map, x, y)){
				c = '#';
			}else if(DOT(state, map, x, y)){
				c = '.';
			}else{
				c = ' ';
			}
			for(i=0; i<map->enemynum; i++){
				if(x == state->e[i].x && y == state->e[i].y){
					c = state->e[i].type;
				}
			}
			putchar(c);
		}
		putchar('\n');
	}
}

void map_print(map_t *map)
{
	int x, y;
	int c;
	for(y=0; y<map->height; y++){
		for(x=0; x<map->width; x++){
			if(CELL(map, x, y) == CELL_BLOCK){
				c = '#';
			}else if(CELL(map, x, y) == CELL_WAY1){
				c = '1';
			}else if(CELL(map, x, y) == CELL_WAY2){
				c = '2';
			}else if(CELL(map, x, y) == CELL_WAY3){
				c = '3';
			}else{
				c = '?';
			}
			putchar(c);
		}
		putchar('\n');
	}
}

void state_step_0(state_t *state, map_t *map, enemy_t *enemy)
{
	if(CELL_DOWN(map, enemy->x, enemy->y)){
		ENEMY_DOWN(enemy);
	}else if(CELL_LEFT(map, enemy->x, enemy->y)){
		ENEMY_LEFT(enemy);
	}else if(CELL_UP(map, enemy->x, enemy->y)){
		ENEMY_UP(enemy);
	}else if(CELL_RIGHT(map, enemy->x, enemy->y)){
		ENEMY_RIGHT(enemy);
	}
}

void state_step_v(state_t *state, map_t *map, enemy_t *enemy)
{
	int dx, dy;
	dx = state->p.x - enemy->x;
	dy = state->p.y - enemy->y;

	if(dy > 0 && CELL_DOWN(map, enemy->x, enemy->y)){
		ENEMY_DOWN(enemy);
	}else if(dy < 0 && CELL_UP(map, enemy->x, enemy->y)){
		ENEMY_UP(enemy);
	}else if(dx > 0 && CELL_RIGHT(map, enemy->x, enemy->y)){
		ENEMY_RIGHT(enemy);
	}else if(dx < 0 && CELL_LEFT(map, enemy->x, enemy->y)){
		ENEMY_LEFT(enemy);
	}else{
		state_step_0(state, map, enemy);
	}
}

void state_step_h(state_t *state, map_t *map, enemy_t *enemy)
{
	int dx, dy;
	dx = state->p.x - enemy->x;
	dy = state->p.y - enemy->y;

	if(dx > 0 && CELL_RIGHT(map, enemy->x, enemy->y)){
		ENEMY_RIGHT(enemy);
	}else if(dx < 0 && CELL_LEFT(map, enemy->x, enemy->y)){
		ENEMY_LEFT(enemy);
	}else if(dy > 0 && CELL_DOWN(map, enemy->x, enemy->y)){
		ENEMY_DOWN(enemy);
	}else if(dy < 0 && CELL_UP(map, enemy->x, enemy->y)){
		ENEMY_UP(enemy);
	}else{
		state_step_0(state, map, enemy);
	}
}

void state_step_l(state_t *state, map_t *map, enemy_t *enemy)
{
	switch(enemy->dir){
	case DIR_DOWN:
		if(CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}else if(CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}else if(CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}
		break;
	case DIR_LEFT:
		if(CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}else if(CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}else if(CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}
		break;
	case DIR_UP:
		if(CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}else if(CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}else if(CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}
		break;
	case DIR_RIGHT:
		if(CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}else if(CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}else if(CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}
		break;
	}
}

void state_step_r(state_t *state, map_t *map, enemy_t *enemy)
{
	switch(enemy->dir){
	case DIR_DOWN:
		if(CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}else if(CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}else if(CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}
		break;
	case DIR_LEFT:
		if(CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}else if(CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}else if(CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}
		break;
	case DIR_UP:
		if(CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}else if(CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}else if(CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}
		break;
	case DIR_RIGHT:
		if(CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}else if(CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}else if(CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}
		break;
	}
}

void state_step_e(state_t *state, map_t *map, enemy_t *enemy)
{
	//printf("enemy: %c(%d, %d)\n", enemy->type, enemy->x, enemy->y);
	int index = CELL_INDEX(map, enemy->x, enemy->y);
	if(map->cell[index] == CELL_WAY1){
		switch(enemy->dir){
		case DIR_DOWN:
			ENEMY_UP(enemy);
			break;
		case DIR_LEFT:
			ENEMY_RIGHT(enemy);
			break;
		case DIR_UP:
			ENEMY_DOWN(enemy);
			break;
		case DIR_RIGHT:
			ENEMY_LEFT(enemy);
			break;
		}
	}else if(map->cell[index] == CELL_WAY2){
		if(enemy->dir != DIR_UP &&
		   map->cell[index + DIR_DOWN]){
//		   CELL_DOWN(map, enemy->x, enemy->y)){
			ENEMY_DOWN(enemy);
		}else if(enemy->dir != DIR_RIGHT &&
				 map->cell[index + DIR_LEFT]){
//				 CELL_LEFT(map, enemy->x, enemy->y)){
			ENEMY_LEFT(enemy);
		}else if(enemy->dir != DIR_DOWN &&
				 map->cell[index + DIR_UP]){
//				 CELL_UP(map, enemy->x, enemy->y)){
			ENEMY_UP(enemy);
		}else if(enemy->dir != DIR_LEFT &&
				 map->cell[index + DIR_RIGHT]){
//				 CELL_RIGHT(map, enemy->x, enemy->y)){
			ENEMY_RIGHT(enemy);
		}
	}else{
		switch(enemy->type){
		case 'V':
			state_step_v(state, map, enemy);
			break;
		case 'H':
			state_step_h(state, map, enemy);
			break;
		case 'L':
			state_step_l(state, map, enemy);
			break;
		case 'R':
			state_step_r(state, map, enemy);
			break;
		case 'J':
			state_step_l(state, map, enemy);
			enemy->type = 'j';
			break;
		case 'j':
			state_step_r(state, map, enemy);
			enemy->type = 'J';
			break;
		}
	}
}

void state_step_p(state_t *state, char dir){
	switch(dir){
	case DIR_LEFT:
		state->p.x--;
		break;
	case DIR_DOWN:
		state->p.y++;
		break;
	case DIR_UP:
		state->p.y--;
		break;
	case DIR_RIGHT:
		state->p.x++;
		break;
	}
}

int state_step(state_t *state, map_t *map, char dir)
{
	int i;
	int dotindex;
	if(state->t == 0){
		for(i=0; i<map->enemynum; i++){
			state_step_0(state, map, &state->e[i]);
		}
	}else{
		for(i=0; i<map->enemynum; i++){
			state_step_e(state, map, &state->e[i]);
		}
	}

	for(i=0; i<map->enemynum; i++){
		if(state->p.x == state->e[i].x &&
		   state->p.y == state->e[i].y){
			if(dir + state->e[i].dir == 5){
				//printf("GAME OVER!(swap)\n");
				return 3;
			}
		}
	}
	state_step_p(state, dir);
	for(i=0; i<map->enemynum; i++){
		if(state->p.x == state->e[i].x &&
		   state->p.y == state->e[i].y){
			//printf("GAME OVER!(hit)\n");
			return 3;
		}
	}
/*
	dotindex = DOT_INDEX(state, map, state->p.x, state->p.y);
	if(state->dot[dotindex]){
	    state->dot[dotindex] = 0;
		state->dotnum--;
	}
*/
	if(DOT(state, map, state->p.x, state->p.y)){
		DOT(state, map, state->p.x, state->p.y) = 0;
		state->dotnum--;
	}
	state->t++;
	if(!state->dotnum){
		//printf("CLEAR!\n");
		return 1;
	}else if(map->timeup - state->t < state->dotnum){
		//printf("GAME OVER!(timeup)\n");
		return 2;
	}
	return 0;
}

int state_step_str(state_t *state, map_t *map, char *str)
{
	size_t len;
	char dir;
	int ret;
	while(*str){
		switch(*str){
		case 'h':
			if(!CELL_LEFT(map, state->p.x, state->p.y)){
				printf("don't move\n");
				return -1;
			}
			dir = DIR_LEFT;
			break;
		case 'j':
			if(!CELL_DOWN(map, state->p.x, state->p.y)){
				printf("don't move\n");
				return -1;
			}
			dir = DIR_DOWN;
			break;
		case 'k':
			if(!CELL_UP(map, state->p.x, state->p.y)){
				printf("don't move\n");
				return -1;
			}
			dir = DIR_UP;
			break;
		case 'l':
			if(!CELL_RIGHT(map, state->p.x, state->p.y)){
				printf("don't move\n");
				return -1;
			}
			dir = DIR_RIGHT;
			break;
		case '.':
			dir = DIR_NONE;
			break;
		default:
			printf("invalid input string\n");
			return -1;
		}
		ret = state_step(state, map, dir);
		state_print(state, map);
		if(ret > 0){
			break;
		}
		str++;
	}
	return ret;
}

void node_print_path(node_t *node)
{
	char buf[1024];
	int len=0;
	node_t *n = node;
	int i;
	int depth = 0;
	char c;
	while(n = (node_t *)n->parent){
		depth++;
	}
	buf[depth--] = '\0';
	for(n = node; n; n = (node_t*)n->parent){
		switch(n->dir){
		case DIR_DOWN:
			c = 'j';
			break;
		case DIR_LEFT:
			c = 'h';
			break;
		case DIR_UP:
			c = 'k';
			break;
		case DIR_RIGHT:
			c = 'l';
			break;
		case DIR_NONE:
			c = '.';
			break;
		}
		buf[depth--] = c;
	}
	printf("%s\n", buf);
}

void search(node_t *node, map_t *map);

void search_dir(node_t *node, map_t *map, unsigned char dir)
{
	int ret;
	node_t *new_node;
	int score;
	new_node = node_new(node, node->state, map);
	ret = state_step(new_node->state, map, dir);
	new_node->dir = dir;
	if(ret == 1){
		printf("CLEAR(%d): ", new_node->state->t);
		node_print_path(new_node);
		map->timeup = new_node->state->t - 1;
	}if(!ret){
		score = new_node->state->dotnum;
		if(score < map->bestscore){
			printf("GOOD(%d): ", score);
			node_print_path(new_node);
			map->bestscore = score;
		}
		search(new_node, map);
	}else{
		// gameover
/*
		printf("GAMEOVER(%d): ", new_node->state->dotnum);
		node_print_path(new_node);
*/
	}
	node_free(new_node);
}

void search_rand(node_t *node, map_t *map)
{
	state_t *state = node->state;
	int r = rand();
	unsigned char dot[5];
	//printf("rand: %d\n", r);
	//node_print_path(node);
	dot[DIR_DOWN] = DOT_DOWN(state, map, state->p.x, state->p.y);
	dot[DIR_LEFT] = DOT_LEFT(state, map, state->p.x, state->p.y);
	dot[DIR_UP] = DOT_UP(state, map, state->p.x, state->p.y);
	dot[DIR_RIGHT] = DOT_RIGHT(state, map, state->p.x, state->p.y);

	switch(r%24){
	case 0:
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		break;
	case 1:
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		break;
	case 2:
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		break;
	case 3:
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		break;
	case 4:
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		break;
	case 5:
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		break;
	case 6:
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		break;
	case 7:
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		break;
	case 8:
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		break;
	case 9:
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		break;
	case 10:
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		break;
	case 11:
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		break;
	case 12:
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		break;
	case 13:
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		break;
	case 14:
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		break;
	case 15:
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		break;
	case 16:
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		break;
	case 17:
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		break;

	case 18:
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		break;
	case 19:
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		break;
	case 20:
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		break;
	case 21:
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		break;
	case 22:
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		break;
	case 23:
		if(dot[DIR_RIGHT])search_dir(node, map, DIR_RIGHT);
		if(dot[DIR_UP])   search_dir(node, map, DIR_UP);
		if(dot[DIR_LEFT]) search_dir(node, map, DIR_LEFT);
		if(dot[DIR_DOWN]) search_dir(node, map, DIR_DOWN);
		break;
	}

	if(!dot[DIR_DOWN] && CELL_DOWN(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_DOWN);
	}
	if(!dot[DIR_LEFT] && CELL_LEFT(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_LEFT);
	}
	if(!dot[DIR_UP] && CELL_UP(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_UP);
	}
	if(!dot[DIR_RIGHT] && CELL_RIGHT(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_RIGHT);
	}
	//search_dir(node, map, DIR_NONE);
}

void search(node_t *node, map_t *map)
{
	state_t *state = node->state;
	unsigned char dot[5];

	//node_print_path(node);
	dot[DIR_DOWN] = DOT_DOWN(state, map, state->p.x, state->p.y);
	if(dot[DIR_DOWN]){
		search_dir(node, map, DIR_DOWN);
	}
	dot[DIR_LEFT] = DOT_LEFT(state, map, state->p.x, state->p.y);
	if(dot[DIR_LEFT]){
		search_dir(node, map, DIR_LEFT);
	}
	dot[DIR_UP] = DOT_UP(state, map, state->p.x, state->p.y);
	if(dot[DIR_UP]){
		search_dir(node, map, DIR_UP);
	}
	dot[DIR_RIGHT] = DOT_RIGHT(state, map, state->p.x, state->p.y);
	if(dot[DIR_RIGHT]){
		search_dir(node, map, DIR_RIGHT);
	}

	if(!dot[DIR_DOWN] && CELL_DOWN(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_DOWN);
	}
	if(!dot[DIR_LEFT] && CELL_LEFT(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_LEFT);
	}
	if(!dot[DIR_UP] && CELL_UP(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_UP);
	}
	if(!dot[DIR_RIGHT] && CELL_RIGHT(map, state->p.x, state->p.y)){
		search_dir(node, map, DIR_RIGHT);
	}
	//search_dir(node, map, DIR_NONE);
}

int main(int argc, char *argv[])
{
	map_t *map;
	state_t *state;
	char buf[BUF_SIZE];
	size_t len;
	char path[1024] = "";
	int ret;
	int opt;
	int opt_play = 0;
	char *opt_skip = NULL;
	node_t *root;

    if(argc < 2){
        fprintf(stderr, "usage: %s [-p] mapfile\n", argv[0]);
        return EXIT_FAILURE;
    }

	while((opt = getopt(argc, argv, "ps:")) != -1){
		switch(opt){
		case 'p':
			opt_play = 1;
			break;
		case 's':
			opt_skip = optarg;
			break;
		}
	}

	state = state_new();
	map = map_new(argv[argc - 1], state);

	printf("state size: %d\n", sizeof(state_t));
	printf("node size: %d\n", sizeof(node_t));
	map_print(map);
	state_print(state, map);

	if(opt_skip){
		ret = state_step_str(state, map, opt_skip);
		if(ret){
			printf("skip ret: %d\n", ret);
			return EXIT_FAILURE;
		}
	}

	if(opt_play){
		do{
			printf("input: ");
			fgets(buf, BUF_SIZE - 1, stdin);
			len = strlen(buf);
			if(buf[len - 1] == '\n'){
				buf[--len] = '\0';
			}
			ret = state_step_str(state, map, buf);
			strncat(path, buf, BUF_SIZE);
			printf("path:  %s\n", path);
			printf("ret:  %d\n", ret);
			if(ret > 0){
				break;
			}
		}while(1);

	}else{
		srand(0);
		root = node_new(NULL, state, map);
		search(root, map);
		node_free(root);
	}

	map_free(map);
	state_free(state);

    return EXIT_SUCCESS;
}