#include #include #include #include #include #include #define DISPLAY_INTERVAL 1500 //画面に表示する間隔 #define NODE_NUM 100000 //保存する全状態の数 #define MIN(a, b) (((a) > (b)) ? (b) : (a)) #define MAX(a, b) (((a) < (b)) ? (b) : (a)) #define ABS(a) (((a) > 0) ? (a) : (-a)) #define XY_S(a, b) ((b)*(X_NUM) + (a)) //(x, y)をスカラーへ変換 #define S_X(a) ((a) % (X_NUM)) //スカラーからxへ変換 #define S_Y(a) ((int)((a) / (X_NUM))) //スカラーからyへ変換 typedef enum{ WALL = 0, PATH, MAN, LOAD, DEST, D_MAN, D_LOAD, GRASS } field;//フィールド情報のenum #define STAGE 1 #if STAGE == 1 #define X_NUM 7//X広さ #define Y_NUM 7//Y広さ #define LOAD_NUM 1//荷物の個数 field init_world[Y_NUM][X_NUM] = { {WALL, WALL, WALL, WALL, WALL, WALL, WALL}, {WALL, PATH, PATH, PATH, PATH, PATH, WALL}, {WALL, MAN, LOAD, PATH, WALL, WALL, WALL}, {WALL, PATH, WALL, PATH, PATH, DEST, WALL}, {WALL, WALL, PATH, PATH, PATH, PATH, WALL}, {GRASS, WALL, PATH, PATH, PATH, PATH, WALL}, {GRASS, WALL, WALL, WALL, WALL, WALL, WALL} };//初期のフィールドの様子 #elif STAGE == 2 #define X_NUM 7//X広さ #define Y_NUM 7//Y広さ #define LOAD_NUM 2//荷物の個数 field init_world[Y_NUM][X_NUM] = { {WALL, WALL, WALL, WALL, WALL, WALL, WALL}, {WALL, PATH, PATH, PATH, PATH, PATH, WALL}, {WALL, MAN, LOAD, PATH, WALL, WALL, WALL}, {WALL, PATH, WALL, PATH, PATH, DEST, WALL}, {WALL, WALL, PATH, LOAD, PATH, PATH, WALL}, {GRASS, WALL, PATH, PATH, PATH, DEST, WALL}, {GRASS, WALL, WALL, WALL, WALL, WALL, WALL} };//初期のフィールドの様子 #elif STAGE == 3 #define X_NUM 10//X広さ #define Y_NUM 5//Y広さ #define LOAD_NUM 3//荷物の個数 field init_world[Y_NUM][X_NUM] = { {WALL, WALL, WALL, GRASS, GRASS, GRASS, GRASS, GRASS, GRASS, GRASS}, {WALL, DEST, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL}, {WALL, DEST, PATH, PATH, LOAD, PATH, LOAD, PATH, PATH, WALL}, {WALL, DEST, LOAD, PATH, PATH, PATH, PATH, PATH, MAN, WALL}, {WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL} };//初期のフィールドの様子 #elif STAGE == 4 #define X_NUM 9//X広さ #define Y_NUM 8//Y広さ #define LOAD_NUM 6//荷物の個数 field init_world[Y_NUM][X_NUM] = { {GRASS, GRASS, GRASS, WALL, WALL, WALL, WALL, GRASS, GRASS}, {GRASS, GRASS, GRASS, WALL, PATH, PATH, WALL, GRASS, GRASS}, {WALL, WALL, WALL, WALL, PATH, LOAD, WALL, WALL, WALL}, {WALL, PATH, LOAD, DEST, DEST, DEST, LOAD, PATH, WALL}, {WALL, PATH, PATH, DEST, DEST, DEST, PATH, PATH, WALL}, {WALL, PATH, LOAD, PATH, WALL, LOAD, LOAD, PATH, WALL}, {WALL, WALL, WALL, PATH, MAN, PATH, WALL, WALL, WALL}, {GRASS, GRASS, WALL, WALL, WALL, WALL, WALL, GRASS, GRASS} };//初期のフィールドの様子 #elif STAGE == 5 #define X_NUM 8//X広さ #define Y_NUM 8//Y広さ #define LOAD_NUM 4//荷物の個数 field init_world[Y_NUM][X_NUM] = { {WALL, WALL, WALL, WALL, WALL, GRASS, GRASS, GRASS}, {WALL, PATH, PATH, PATH, WALL, GRASS, GRASS, GRASS}, {WALL, LOAD, WALL, PATH, WALL, WALL, WALL, WALL}, {WALL, DEST, PATH, PATH, PATH, PATH, PATH, WALL}, {WALL, PATH, PATH, D_LOAD, PATH, D_LOAD, PATH, WALL}, {WALL, PATH, D_LOAD, PATH, WALL, PATH, WALL, WALL}, {WALL, WALL, WALL, PATH, MAN, PATH, WALL, GRASS}, {GRASS, GRASS, WALL, WALL, WALL, WALL, WALL, GRASS} };//初期のフィールドの様子 #elif STAGE == 6 #define X_NUM 8//X広さ #define Y_NUM 8//Y広さ #define LOAD_NUM 3//荷物の個数 field init_world[Y_NUM][X_NUM] = { {WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL}, {WALL, PATH, PATH, PATH, WALL, PATH, PATH, WALL}, {WALL, PATH, WALL, PATH, WALL, LOAD, DEST, WALL}, {WALL, PATH, PATH, PATH, PATH, LOAD, DEST, WALL}, {WALL, PATH, WALL, PATH, WALL, LOAD, DEST, WALL}, {WALL, PATH, PATH, PATH, WALL, PATH, PATH, WALL}, {WALL, WALL, WALL, WALL, WALL, MAN, PATH, WALL}, {GRASS, GRASS, GRASS, GRASS, WALL, WALL, WALL, WALL} };//初期のフィールドの様子 #endif typedef struct{ long int depth; long int heuristic; long int man; long int load[LOAD_NUM]; long int next[LOAD_NUM * 4]; long int prev; int valid_next_node; } node_t;//人と荷物の位置を記録するノードの構造体 int mode = 0;//0:プレイ 1:広さ優先探索 2:反復深化探索 3:A*探索 long int t = -1; int dt = 1; int wx = 500, wy = 500; /* ウィンドウサイズ */ int p_size;//画面上での１マスの大きさ field world[Y_NUM][X_NUM];//現在のフィールドの様子 int reach[Y_NUM][X_NUM];//移動可能な範囲 long int dest_s[LOAD_NUM]; int dest_id = 0; int h_value[Y_NUM][X_NUM];//最も近い目標地点への（荷物の重なりを許した場合の）移動コスト node_t node[NODE_NUM];//過去に調べた全ノード long int node_num;//全ノード数 long int answer[NODE_NUM / 4];//正解のノード列 long int list[NODE_NUM];//調べるべきノードのリスト long int list_num = 0;//リストの長さ long int current_node = 0;//現在表示中のノード void node_save(long int n);//現在の人・荷物の状態をノードに記録 void next_node_save(long int n1);//現在の人・荷物の状態を、ノードn1からのびる新たなノードとして記録 int is_same_node(long int n1, long int n2);//２つのノードの人・荷物の状態が同じかを判定 void get_world(long int n);//ノードの情報からマップを再構築する void get_reach(long int man);//manで表される位置から移動できる範囲を求める int is_finish(void);//ゲームクリアか否かを判定する void get_h_value(void);//（プログラム開始時のみ）最も近い目標地点への（荷物の重なりを許した場合の）移動コストを計算（ヒューリスティック関数でh?¨いる） long int get_heuristic(long int n);//ノードnのヒューリスティック関数値を求める !world, reachをいじる副作用あり long int pop(int kind); //kind 0:キュー 1:スタック 2:ヒューリスティック関数値で整列済みのリスト void push(long int n, int kind); //kind 0:キュー 1:スタック 2:ヒューリスティック関数値で整列済みのリスト int solve_width(void);//広さ優先探索で倉庫番の問題を解き、解答のノード列を返す。解答がなければ返り値0。 int solve_depth(void);//反復深化探索で倉庫番の問題を解き、解答のノード列を返す。解答がなければ返り値0。 int solve_heuristic(void);//ヒューリスティック探索で倉庫番の問題を解き、解答のノード列を返す。解答がなければ返り値0。 //(man_x,man_y)から(dx,dy)だけ移動し（移動できない場合は何もしない）、移動できた場合1を、できなければ0を返す。 int move(long int man_x, long int man_y, int dx, int dy); void var_init(void);/* 変数の初期化 */ void node_save(long int n){//現在の人・荷物の状態をノードに記録 if(n >= NODE_NUM) printf("#insufficient memory!!\n"); int i, j; int count = 0; for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ switch(world[j][i]){ case MAN: case D_MAN: node[n].man = XY_S(i, j); break; case LOAD: case D_LOAD: node[n].load[count] = XY_S(i, j); count++; break; } } } } void next_node_save(long int n1){//現在の人・荷物の状態を、ノードn1からのびる新たなノードとして記録 node_save(node_num); node[node_num].depth = node[n1].depth + 1; node[node_num].heuristic = get_heuristic(node_num); node[node_num].prev = n1; node[node_num].valid_next_node = 0; node[n1].next[node[n1].valid_next_node] = node_num; node[n1].valid_next_node++; node_num++; if(node_num >= NODE_NUM) printf("#insufficient memory!\n"); } int is_same_node(long int n1, long int n2){//ノードn1, n2の人・荷物の状態が同じかを判定 int i; if(node[n1].man != node[n2].man) return 0; for(i = 0; i < LOAD_NUM; i++){ if(node[n1].load[i] != node[n2].load[i]) return 0; } return 1; } void get_world(long int n){//ノードの情報からマップを再構築する int i, j; for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ switch(init_world[j][i]){ case MAN: case LOAD: world[j][i] = PATH; break; case D_MAN: case D_LOAD: world[j][i] = DEST; break; default: world[j][i] = init_world[j][i]; break; } } } //フィールドの初期化(動くものは除去) //人の配置 switch(world[S_Y(node[n].man)][S_X(node[n].man)]){ case DEST: world[S_Y(node[n].man)][S_X(node[n].man)] = D_MAN; break; default: world[S_Y(node[n].man)][S_X(node[n].man)] = MAN; break; } //荷物の配置 for(i = 0; i < LOAD_NUM; i++){ switch(world[S_Y(node[n].load[i])][S_X(node[n].load[i])]){ case DEST: world[S_Y(node[n].load[i])][S_X(node[n].load[i])] = D_LOAD; break; default: world[S_Y(node[n].load[i])][S_X(node[n].load[i])] = LOAD; break; } } } void get_reach_rec(long int s){//sで表される位置から移動できる範囲（再帰用） int x = S_X(s); int y = S_Y(s); if(reach[y][x] == 1) return; switch(world[y][x]){ case PATH: case MAN: case DEST: case D_MAN: reach[y][x] = 1; if(x > 0) get_reach_rec(XY_S(x - 1, y)); if(x < X_NUM - 1) get_reach_rec(XY_S(x + 1, y)); if(y > 0) get_reach_rec(XY_S(x, y - 1)); if(y < Y_NUM - 1) get_reach_rec(XY_S(x, y + 1)); break; default: return; break; } } void get_reach(long int man){//manで表される位置から移動できる範囲を求める int i, j; for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ reach[j][i] = 0; } } get_reach_rec(man); } int is_finish(void){//ゲームクリアか否かを判定する int i, j; for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ if(world[j][i] == LOAD) return 0; } } return 1; } void get_h_value_rec(long int s, long int value){ int x = S_X(s); int y = S_Y(s); if(value < h_value[y][x]){ switch(init_world[S_Y(s)][S_X(s)]){ case WALL: return; break; default: h_value[y][x] = value; if(x > 0) get_h_value_rec(XY_S(x - 1, y), value + 1); if(x < X_NUM - 1) get_h_value_rec(XY_S(x + 1, y), value + 1); if(y > 0) get_h_value_rec(XY_S(x, y - 1), value + 1); if(y < Y_NUM - 1) get_h_value_rec(XY_S(x, y + 1), value + 1); break; } } } void get_h_value(void){//（プログラム開始時のみ）最も近い目標地点への（荷物の重なりを許した場合の）移動コストを計算（ヒューリスティック関数でh?¨いる） int i, j; dest_id = 0; for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ h_value[j][i] = X_NUM + Y_NUM; if(world[j][i] == DEST || world[j][i] == D_MAN || world[j][i] == D_LOAD){ dest_s[dest_id] = XY_S(i, j); dest_id++; } } } for(i = 0; i < LOAD_NUM; i++) get_h_value_rec(dest_s[i], 0); /* for(j = 0; j < Y_NUM; j++){ for(i = 0; i < X_NUM; i++){ printf("%4d ", h_value[j][i]); } printf("\n"); } */ } long int get_heuristic(long int n){//ノードnのヒューリスティック関数値を求める !world, reachをいじる副作用あり int i, j; long int ans = 0; get_world(n); get_reach(node[n].man); //動かせる可能性のある荷物を消去する for(i = 0; i < LOAD_NUM; i++){ long int x = S_X(node[n].load[i]); long int y = S_Y(node[n].load[i]); get_reach(node[n].man); if(world[y][x] == LOAD || world[y][x] == D_LOAD){ if(y > 0 && y < Y_NUM - 1 && reach[y + 1][x] == 1 && (world[y - 1][x] == PATH || world[y - 1][x] == MAN || world[y - 1][x] == DEST || world[y - 1][x] == D_MAN)){ world[y][x] = PATH; i = -1;} if(y > 0 && y < Y_NUM - 1 && reach[y - 1][x] == 1 && (world[y + 1][x] == PATH || world[y + 1][x] == MAN || world[y + 1][x] == DEST || world[y + 1][x] == D_MAN)){ world[y][x] = PATH; i = -1;} if(x > 0 && x < X_NUM - 1 && reach[y][x + 1] == 1 && (world[y][x - 1] == PATH || world[y][x - 1] == MAN || world[y][x - 1] == DEST || world[y][x - 1] == D_MAN)){ world[y][x] = PATH; i = -1;} if(x > 0 && x < X_NUM - 1 && reach[y][x - 1] == 1 && (world[y][x + 1] == PATH || world[y][x + 1] == MAN || world[y][x + 1] == DEST || world[y][x + 1] == D_MAN)){ world[y][x] = PATH; i = -1;} } } get_reach(node[n].man);//荷物の依存関係を考えてもどうやってもたどりつけない範囲を再計算 for(i = 0; i < LOAD_NUM; i++){ if(world[S_Y(dest_s[i])][S_X(dest_s[i])] != D_LOAD && reach[S_Y(dest_s[i])][S_X(dest_s[i])] == 0){ get_world(n); get_reach(node[n].man); return (X_NUM+Y_NUM)*LOAD_NUM + 1;//到達できない目標地点があればヒューリスティック関数値は無限大((X_NUM+Y_NUM)*LOAD_NUM + 1)になる } long int x = S_X(node[n].load[i]); long int y = S_Y(node[n].load[i]); if(y > 0 && y < Y_NUM - 1 && reach[y + 1][x] == 1 && (world[y - 1][x] == PATH || world[y - 1][x] == MAN || world[y - 1][x] == DEST || world[y - 1][x] == D_MAN)) ans+=h_value[y][x]; else if(y > 0 && y < Y_NUM - 1 && reach[y - 1][x] == 1 && (world[y + 1][x] == PATH || world[y + 1][x] == MAN || world[y + 1][x] == DEST || world[y + 1][x] == D_MAN)) ans+=h_value[y][x]; else if(x > 0 && x < X_NUM - 1 && reach[y][x + 1] == 1 && (world[y][x - 1] == PATH || world[y][x - 1] == MAN || world[y][x - 1] == DEST || world[y][x - 1] == D_MAN)) ans+=h_value[y][x]; else if(x > 0 && x < X_NUM - 1 && reach[y][x - 1] == 1 && (world[y][x + 1] == PATH || world[y][x + 1] == MAN || world[y][x + 1] == DEST || world[y][x + 1] == D_MAN)) ans+=h_value[y][x]; else if(init_world[y][x] != DEST && init_world[y][x] != D_LOAD && init_world[y][x] != D_MAN){ get_world(n); get_reach(node[n].man); return (X_NUM+Y_NUM)*LOAD_NUM + 1;//運べない未完了荷物があればヒューリスティック関数値は無限大((X_NUM+Y_NUM)*LOAD_NUM + 1)になる } } get_world(n); get_reach(node[n].man); return ans; } long int pop(int kind){ //kind 0:キュー 1:スタック 2:ヒューリスティック関数値で整列済みのリスト int i; long int ans = list[0]; if(list_num <= 0) return -1; switch(kind){ case 0: for(i = 1; i < list_num; i++){ list[i - 1] = list[i]; } list_num--; return ans; break; case 1: case 2: list_num--; //printf("node %ld popped.\nlist: ", list[list_num]); //for(i = 0; i < list_num; i++) printf("%ld ", list[i]); //printf("\n"); return list[list_num]; break; } } void push(long int n, int kind){ //kind 0:キュー 1:スタック 2:ヒューリスティック関数値で整列済みのリスト if(kind == 2){ int i = list_num - 1; while(i >= 0 && (node[n].heuristic + node[n].depth) > (node[list[i]].heuristic + node[list[i]].depth)){ list[i + 1] = list[i]; i--; } list[i + 1] = n; } else list[list_num] = n; list_num++; int j; //printf("node %ld added.\nlist: ", n); //for(j = 0; j < list_num; j++) printf("%ld ", list[j]); //printf("\n"); } //(man_x,man_y)から(dx,dy)だけ移動し（移動できない場合は何もしない）、移動できた場合1を、できなければ0を返す。 int move(long int man_x, long int man_y, int dx, int dy){ if(man_x + dx < 0 || man_x + dx >= X_NUM || man_y + dy < 0 || man_y + dy >= Y_NUM) return 0; switch(world[man_y + dy][man_x + dx]){ case WALL: return 0; break; case PATH: world[man_y + dy][man_x + dx] = MAN; break; case DEST: world[man_y + dy][man_x + dx] = D_MAN; break; case LOAD: if(man_x + dx * 2 < 0 || man_x + dx * 2 >= X_NUM || man_y + dy * 2 < 0 || man_y + dy * 2 >= Y_NUM) return 0; switch(world[man_y + dy * 2][man_x + dx * 2]){ case WALL: case LOAD: case D_LOAD: return 0; break; case PATH: world[man_y + dy * 2][man_x + dx * 2] = LOAD; world[man_y + dy][man_x + dx] = MAN; break; case DEST: world[man_y + dy * 2][man_x + dx * 2] = D_LOAD; world[man_y + dy][man_x + dx] = MAN; break; } break; case D_LOAD: if(man_x + dx * 2 < 0 || man_x + dx * 2 >= X_NUM || man_y + dy * 2 < 0 || man_y + dy * 2 >= Y_NUM) return 0; switch(world[man_y + dy * 2][man_x + dx * 2]){ case WALL: case LOAD: case D_LOAD: return 0; break; case PATH: world[man_y + dy * 2][man_x + dx * 2] = LOAD; world[man_y + dy][man_x + dx] = D_MAN; break; case DEST: world[man_y + dy * 2][man_x + dx * 2] = D_LOAD; world[man_y + dy][man_x + dx] = D_MAN; break; } break; } if(world[man_y][man_x] == MAN) world[man_y][man_x] = PATH; else if(world[man_y][man_x] == D_MAN) world[man_y][man_x] = DEST; return 1; } void var_init(void){/* 変数の初期化 */ int i, j; srand((unsigned)time(NULL)); p_size = MIN(wx/X_NUM, wy/Y_NUM); for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ world[j][i] = init_world[j][i]; reach[j][i] = 0; } } get_h_value(); node_num = 1; node_save(0); get_world(0); node[0].depth = 1; node[0].heuristic = get_heuristic(0); node[0].prev = 0; node[0].valid_next_node = 0; current_node = 0; t = -1; list_num = 0; } int solve_width_sub(long int now_node, long int mx, long int my){//幅優先探索 クリア時とそうでないときの処理 int i; node_save(node_num); for(i = 0; i < node_num; i++){//同一状態のノードの登録を防ぐ if(is_same_node(i, node_num)){ get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; return 0; } } next_node_save(now_node); if(is_finish()){//クリアしていた場合、解答に至るノード列を生成する now_node = node_num - 1; printf("Solved in %ld step(s).\n", node[now_node].depth - 1); answer[node[now_node].depth] = -1; for(i = node[now_node].depth - 1; i >= 0; i--){ answer[i] = now_node; printf("%ld ", now_node); now_node = node[now_node].prev; } printf("\n"); return 1; } push(node_num - 1, 0); get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; return 0; } int solve_width(void){//広さ優先探索で倉庫番の問題を解き、解答のノード列を返す。解答がなければ返り値0。 int i,j; long int now_node;//現在注目しているノード push(0, 0); while(list_num > 0){ now_node = pop(0);//リストの先頭から１つノードを取り出し、探索を始める get_world(now_node); get_reach(node[now_node].man);//荷物に触れずに移動できる範囲を求める /* ひとまず、人は退場する */ long int mx = S_X(node[now_node].man); long int my = S_Y(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; //各荷物について、上下左右に移動できるかを調べ、移動可能ならば移動した結果のフィールドを記録し、リストに追加する for(i = 0; i < LOAD_NUM; i++){ long int lx = S_X(node[now_node].load[i]); long int ly = S_Y(node[now_node].load[i]); if(ly < Y_NUM - 1 && reach[ly + 1][lx] == 1 && move(lx, ly + 1, 0, -1)) if(solve_width_sub(now_node, mx, my)) return 1;//荷物を上に動かせる if(ly > 0 && reach[ly - 1][lx] == 1 && move(lx, ly - 1, 0, 1)) if(solve_width_sub(now_node, mx, my)) return 1;//荷物を下に動かせる if(lx < X_NUM - 1 && reach[ly][lx + 1] == 1 && move(lx + 1, ly, -1, 0)) if(solve_width_sub(now_node, mx, my)) return 1;//荷物を左に動かせる if(lx > 0 && reach[ly][lx - 1] == 1 && move(lx - 1, ly, 1, 0)) if(solve_width_sub(now_node, mx, my)) return 1;//荷物を右に動かせる } //printf("node %ld finished.\nlist: ", now_node); //for(j = 0; j < list_num; j++) printf("%ld ", list[j]); //printf("\n"); } printf("No solution. list_num: %ld\n", list_num); for(j = 0; j < list_num; j++) printf("%ld ", list[j]); printf("\n"); return 0; } int solve_depth_sub(long int now_node, long int mx, long int my, int depth){//反復深化探索 クリア時とそうでないときの処理 返り値 0:通常 -1:深さ制限で終了 1:クリア int i; node_save(node_num); for(i = 0; i < node_num; i++){//同一状態のノードの登録を防ぐ if(is_same_node(i, node_num) && node[i].depth <= node[now_node].depth + 1){ get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; return 0; } } next_node_save(now_node); if(is_finish()){//クリアしていた場合、解答に至るノード列を生成する now_node = node_num - 1; printf("Solved in %ld step(s).\n", node[now_node].depth - 1); answer[node[now_node].depth] = -1; for(i = node[now_node].depth - 1; i >= 0; i--){ answer[i] = now_node; printf("%ld ", now_node); now_node = node[now_node].prev; } printf("\n"); return 1; } get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; if(node[node_num - 1].depth > depth) return -1; push(node_num - 1, 1); return 0; } int solve_depth_1(int depth){//反復深化探索 深さdepthで探索する。返り値 0:解なし -1:深さ制限で解なし 1:クリア int i,j; long int now_node;//現在注目しているノード int depth_limit = 0; //深さ制限に一回でもかかったら-1 int tmp; push(0, 1); while(list_num > 0){ now_node = pop(1);//リストの先頭から１つノードを取り出し、探索を始める get_world(now_node); get_reach(node[now_node].man);//荷物に触れずに移動できる範囲を求める /* ひとまず、人は退場する */ long int mx = S_X(node[now_node].man); long int my = S_Y(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; //各荷物について、上下左右に移動できるかを調べ、移動可能ならば移動した結果のフィールドを記録し、リストに追加する for(i = 0; i < LOAD_NUM; i++){ long int lx = S_X(node[now_node].load[i]); long int ly = S_Y(node[now_node].load[i]); if(lx > 0 && reach[ly][lx - 1] == 1 && move(lx - 1, ly, 1, 0)) if((tmp = solve_depth_sub(now_node, mx, my, depth)) == 1) return 1;//荷物を右に動かせる if(tmp == -1) depth_limit = -1; if(lx < X_NUM - 1 && reach[ly][lx + 1] == 1 && move(lx + 1, ly, -1, 0)) if((tmp = solve_depth_sub(now_node, mx, my, depth)) == 1) return 1;//荷物を左に動かせる if(tmp == -1) depth_limit = -1; if(ly > 0 && reach[ly - 1][lx] == 1 && move(lx, ly - 1, 0, 1)) if((tmp = solve_depth_sub(now_node, mx, my, depth)) == 1) return 1;//荷物を下に動かせる if(tmp == -1) depth_limit = -1; if(ly < Y_NUM - 1 && reach[ly + 1][lx] == 1 && move(lx, ly + 1, 0, -1)) if((tmp = solve_depth_sub(now_node, mx, my, depth)) == 1) return 1;//荷物を上に動かせる if(tmp == -1) depth_limit = -1; } //printf("node %ld finished.\nlist: ", now_node); //for(j = 0; j < list_num; j++) printf("%ld ", list[j]); //printf("\nlist_num:%ld\n", list_num); } if(depth_limit == 0)printf("No solution.\n"); else printf("No solution in %ld step(s).\n", depth); return depth_limit; } int solve_depth(void){//反復深化探索で倉庫番の問題を解き、解答のノード列を返す。解答がなければ返り値0。 int result; int depth = get_heuristic(0); while((result = solve_depth_1(depth)) == -1){ depth++; var_init(); } return result; } int solve_heuristic_sub(long int now_node, long int mx, long int my){//ヒューリスティック探索 クリア時とそうでないときの処理 int i; node_save(node_num); if(get_heuristic(node_num) > (X_NUM+Y_NUM)*LOAD_NUM){//クリアの見込みがないノードの登録を防ぐ get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; return 0; } for(i = 0; i < node_num; i++){//同一状態のノードの登録を防ぐ if(is_same_node(i, node_num)){ get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; return 0; } } next_node_save(now_node); if(is_finish()){//クリアしていた場合、解答に至るノード列を生成する now_node = node_num - 1; printf("Solved in %ld step(s).\n", node[now_node].depth - 1); answer[node[now_node].depth] = -1; for(i = node[now_node].depth - 1; i >= 0; i--){ answer[i] = now_node; printf("%ld ", now_node); now_node = node[now_node].prev; } printf("\n"); return 1; } push(node_num - 1, 2); get_world(now_node); get_reach(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; return 0; } int solve_heuristic(void){//ヒューリスティック探索で倉庫番の問題を解き、解答のノード列を返す。解答がなければ返り値0。 int i,j; long int now_node;//現在注目しているノード push(0, 2); while(list_num > 0){ now_node = pop(2);//リストの先頭から１つノードを取り出し、探索を始める get_world(now_node); get_reach(node[now_node].man);//荷物に触れずに移動できる範囲を求める /* ひとまず、人は退場する */ long int mx = S_X(node[now_node].man); long int my = S_Y(node[now_node].man); if(world[my][mx] == MAN) world[my][mx] = PATH; else if(world[my][mx] == D_MAN) world[my][mx] = DEST; //各荷物について、上下左右に移動できるかを調べ、移動可能ならば移動した結果のフィールドを記録し、リストに追加する for(i = 0; i < LOAD_NUM; i++){ long int lx = S_X(node[now_node].load[i]); long int ly = S_Y(node[now_node].load[i]); if(ly < Y_NUM - 1 && reach[ly + 1][lx] == 1 && move(lx, ly + 1, 0, -1)) if(solve_heuristic_sub(now_node, mx, my)) return 1;//荷物を上に動かせる if(ly > 0 && reach[ly - 1][lx] == 1 && move(lx, ly - 1, 0, 1)) if(solve_heuristic_sub(now_node, mx, my)) return 1;//荷物を下に動かせる if(lx < X_NUM - 1 && reach[ly][lx + 1] == 1 && move(lx + 1, ly, -1, 0)) if(solve_heuristic_sub(now_node, mx, my)) return 1;//荷物を左に動かせる if(lx > 0 && reach[ly][lx - 1] == 1 && move(lx - 1, ly, 1, 0)) if(solve_heuristic_sub(now_node, mx, my)) return 1;//荷物を右に動かせる } //printf("node %ld finished.\nlist: ", now_node); //for(j = 0; j < list_num; j++) printf("%ld ", list[j]); //printf("\n"); } printf("No solution. list_num: %ld\n", list_num); for(j = 0; j < list_num; j++) printf("%ld ", list[j]); printf("\n"); return 0; } void idle(){ if(mode == 0) t = -1; else t+=dt; if(t % DISPLAY_INTERVAL == 0){ if(answer[t / DISPLAY_INTERVAL] == -1) { t = -1; return; } current_node = answer[t / DISPLAY_INTERVAL]; get_world(current_node); get_reach(node[current_node].man); } glutPostRedisplay(); } /* 絵の描画関数 */ void display(){ int i, j; glClear(GL_COLOR_BUFFER_BIT); /* ウィンドウをクリアする */ glPointSize(10); /* 点の大きさ (単位はピクセル) */ glColor3f(1, 1, 1); /* 色の設定. 光の3原色(赤, 緑, 青) */ glClearColor(0.0, 0.0, 0.0, 1.0);/* 背景色の設定 */ for(i = 0; i < X_NUM; i++){ for(j = 0; j < Y_NUM; j++){ switch(world[j][i]){ case WALL: glColor3d(0, 0, 0); glBegin(GL_QUADS); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); break; case GRASS: glColor3d(1, 1, 1); glBegin(GL_QUADS); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); break; case PATH: glColor3d(0.5, 0.5, 0.5); glBegin(GL_QUADS); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); break; case MAN: glColor3d(0.5, 0.5, 0.5); glBegin(GL_QUADS); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); glPointSize(p_size / 3); glColor3d(1.0, 0.0, 0.0); glBegin(GL_POINTS); glVertex2d(p_size * i + p_size / 2, p_size * j + p_size / 2); glEnd(); break; case LOAD: glBegin(GL_QUADS); glColor3d(0.7, 0.7, 0.0); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); glColor3d(0.0, 0.0, 0.0); glBegin(GL_LINE_LOOP); glVertex2d(p_size * i + p_size / 5, p_size * j + p_size / 5); glVertex2d(p_size * (i + 1) - p_size / 5, p_size * j + p_size / 5); glVertex2d(p_size * (i + 1) - p_size / 5, p_size * (j + 1) - p_size / 5); glVertex2d(p_size * i + p_size / 5, p_size * (j + 1) - p_size / 5); glEnd(); break; case DEST: glColor3d(0.5, 0.5, 0.5); glBegin(GL_QUADS); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); glPointSize(p_size / 6); glColor3d(0.0, 0.0, 1.0); glColor3d(0, 0, 1.0); glBegin(GL_TRIANGLES); glVertex2d(p_size * (i + 0.5), p_size * j + p_size / 2.5); glVertex2d(p_size * (i + 1) - p_size / 2.5, p_size * (j + 1) - p_size / 2.5); glVertex2d(p_size * i + p_size / 2.5, p_size * (j + 1) - p_size / 2.5); glEnd(); break; case D_MAN: glColor3d(0.5, 0.5, 0.5); glBegin(GL_QUADS); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); glPointSize(p_size / 3); glBegin(GL_POINTS); glColor3d(0.5, 0.0, 0.0); glVertex2d(p_size * i + p_size / 2, p_size * j + p_size / 2); glEnd(); glColor3d(0, 0, 1.0); glBegin(GL_TRIANGLES); glVertex2d(p_size * (i + 0.5), p_size * j + p_size / 2.5); glVertex2d(p_size * (i + 1) - p_size / 2.5, p_size * (j + 1) - p_size / 2.5); glVertex2d(p_size * i + p_size / 2.5, p_size * (j + 1) - p_size / 2.5); glEnd(); break; case D_LOAD: glBegin(GL_QUADS); glColor3d(0.3, 0.3, 0.0); glVertex2d(p_size * i, p_size * j); glVertex2d(p_size * (i + 1), p_size * j); glVertex2d(p_size * (i + 1), p_size * (j + 1)); glVertex2d(p_size * i, p_size * (j + 1)); glEnd(); glColor3d(0.0, 0.0, 0.0); glBegin(GL_LINE_LOOP); glVertex2d(p_size * i + p_size / 5, p_size * j + p_size / 5); glVertex2d(p_size * (i + 1) - p_size / 5, p_size * j + p_size / 5); glVertex2d(p_size * (i + 1) - p_size / 5, p_size * (j + 1) - p_size / 5); glVertex2d(p_size * i + p_size / 5, p_size * (j + 1) - p_size / 5); glEnd(); glColor3d(0, 0, 1.0); glBegin(GL_TRIANGLES); glVertex2d(p_size * (i + 0.5), p_size * j + p_size / 2.5); glVertex2d(p_size * (i + 1) - p_size / 2.5, p_size * (j + 1) - p_size / 2.5); glVertex2d(p_size * i + p_size / 2.5, p_size * (j + 1) - p_size / 2.5); glEnd(); break; } if(reach[j][i]){ glPointSize(p_size / 6); glBegin(GL_POINTS); glColor3d(1.0, 1.0, 1.0); glVertex2d(p_size * i + p_size / 6, p_size * j + p_size / 6); glEnd(); } } } glutSwapBuffers(); } void keyboard(unsigned char key, int x, int y){ /* キーボードの処理 */ clock_t start; switch(key){ case '\033': /* Escキーで終了 */ exit(0); break; case 'p': case 'P': //プレイ var_init(); mode = 0; break; case 'w': case 'W': //広さ優先探索 var_init(); start = clock(); if(solve_width()) mode = 1; printf("time: %d[ms]\n", clock() - start); break; case 'd': case 'D': //深さ優先探索 var_init(); start = clock(); if(solve_depth()) mode = 2; printf("time: %d[ms]\n", clock() - start); break; case 'h': case 'H': //ヒューリスティック探索 var_init(); start = clock(); if(solve_heuristic()) mode = 3; printf("time: %d[ms]\n", clock() - start); break; case 'a': case 'A': //元に戻す if(current_node > 0){ current_node = node[current_node].prev; get_world(current_node); get_reach(node[current_node].man); } break; case 't': case 'T': dt = (dt + 1) % 2; break; } } void arrow(int key, int x, int y){ /* 矢印キーの処理 */ if(mode > 0) return; switch(key){ case GLUT_KEY_UP: if(move(S_X(node[current_node].man), S_Y(node[current_node].man), 0, -1)){ next_node_save(current_node); current_node = node_num - 1; } break; case GLUT_KEY_DOWN: if(move(S_X(node[current_node].man), S_Y(node[current_node].man), 0, 1)){ next_node_save(current_node); current_node = node_num - 1; } break; case GLUT_KEY_LEFT: if(move(S_X(node[current_node].man), S_Y(node[current_node].man), -1, 0)){ next_node_save(current_node); current_node = node_num - 1; } break; case GLUT_KEY_RIGHT: if(move(S_X(node[current_node].man), S_Y(node[current_node].man), 1, 0)){ next_node_save(current_node); current_node = node_num - 1; } break; } } /* ウィンドウのサイズが変わった時に呼ばれる関数 */ void reshape(int w, int h){ /*引数はサイズの幅と高さ */ glViewport(0, 0, w, h); /* スクリーンの大きさを決める */ glLoadIdentity(); /*座標変換行列の初期化 */ glOrtho(0, w, h, 0, -1, 1); /* スクリーンと座標系の対応を指定する */ wx = w; wy = h; p_size = MIN(wx/X_NUM, wy/Y_NUM); } /* この関数が最初に実行される */ int main(int argc, char** argv){ var_init(); /* 変数の初期化 */ glutInit(&argc, argv); /* glut を初期化 */ glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); /* 使用するバッファの設定 */ glutInitWindowSize(500, 500); /* ウィンドウの大きさ */ glutCreateWindow("souko"); /* ウィンドウのタイトル */ glutReshapeFunc(reshape); /* 画面更新用の関数を登録 */ glutDisplayFunc(display); /* ウインドウのサイズ変更時の関数を登録 */ glutKeyboardFunc(keyboard);/* キーボード用関数を登録*/ glutSpecialFunc(arrow);/* 矢印キーの処理用関数を登録 */ glutIdleFunc(idle); /* イベントが無いときの処理関数を登録 */ glutMainLoop(); /* メインループを開始 */ return 0; }