スタック実現の小さな迷宮ゲーム

8409 ワード

昨日スタック構造を勉強した後、徹夜でスタックを利用して深い遍歴を実現する迷路の小さなプログラムを書いた.
簡単な説明:
main関数にN*Nの2次元char配列を定義し、すべて#で埋め、buildを呼び出して地図を生成し、output出力地図を呼び出します.
ポイントbuildでは、buildで開始点(0,1)を定義し、スタック構造を定義し、valiableをループして利用可能な方向とステップ数を生成し、schessを呼び出して生成した方向とステップ数を地図に描く.
ポイントを生成できない場合はループを終了し、終了ポイントもオンにすればよい.ここのポイントはvaliable関数で、詳しくは言わないで、コードを見てみましょう.
     # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
     >>      # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
     # #   # #   #   #   # # # # # # #         #         #         # 
     # #     #       #                   # #   # #   # # #   # #   # 
     # # #       #   # #   #   # # # #           #   # #     #     # 
     # # # # # # #     #   #   #         #   #   #         # #   # # 
     # #           #       #   #   #   #     #   # #   #   # #     # 
     # #   #   #       #       #   #   # # # #     # # #     # #   # 
     # #   #   # # #   # # #   #   #           #           # #     # 
     # #   #               #   #     # # # #   #   # # #   #     # # 
     # #   #   # # # #   #       #   # #   #   #             #   # # 
     # #   # # #         #   # # #         #   #   # # # # # #   # # 
     # #         # # #             # # #   #                     # # 
     # #   # #           # #   #       #   #   # #   #   # # #   # # 
     # #     #   # # #     #     # #       # #   #   #   #         # 
     # # #   #   #   # #   # #     #   # #       #         # # # # # 
     # #               #   # # #   #     #   #   # # # #           # 
     # #   # # #   #   #           # #       #           # # # #   # 
     # # # #   #   #   # # # # #       # #       # # #             # 
     # # #     #   #         #     #   # # # #   #   # # # # #   # # 
     # # #   # #   # # # #       # #         #   #           #     # 
     # #     # #       # #   #   #   # # #   #   #   # # #   # #   # 
     # #   #       #     #   #   #   #   #   #   #                 # 
     # #       #   # #       #   #   #       #   #   # # # # # #   # 
     # #   #         #   #   #   #       # # #   # # #             # 
     # #   #   # # # #             # #                   #   #   # # 
     # #   #             # #   #     # #   #   # # # #       #     # 
     # # # #   # # # # #   #   # #   # #   # #           #   # #   # 
     # # #     #           #   #                 # # # # #   # #   # 
     # # #   #     # # #   #       # # # # # # #                   # 
     # # #       # #           #   #               # # # # # # #     >>>
     # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
#include 
#include 
#include 
#include 

#define N 0x20
#define X '#'

typedef struct {
	int x, y;
} point;

enum direction {
	UP,
	RIGHT,
	DOWN,
	LEFT,
	UNVALID
};

typedef struct {
	point *bottom;
	point *top;
	unsigned int length;
} stack;

int initstack(stack *p, unsigned int n)
{
	p->bottom = p->top = (point*)malloc(sizeof(point) * n);
	p->length = n;
	return 0;
}

int cleanstack(stack *p)
{
	free(p->bottom);
	p->bottom = p->top = NULL;
	p->length = 0;
	return 0;
}

int push(stack *p, point n)
{
	*++p->top = n;
	return 0;
}

point pop(stack *p)
{
	return *p->top--;
}

int output(char p[N][N])
{
	int i, j;
	printf("
"); for (i = 0; i < N; i++) { if (i == 1) { printf(">>> "); } else { printf(" "); } for (j = 0; j < N; j++) { printf("%c ", p[j][i]); } if (i == N - 2) { printf(" >>>
"); } else { printf("
"); } } printf("
"); return 0; } enum direction direct(point p) { return UP + rand() % 4; } int steplength() { return rand() % 2 + 1; } enum direction valiable(point *p, int *length, char chess[N][N], stack *x) { enum direction d; int l; int k = 0; int fs = 0; while (1) { int f = 0; int i, r; k += 1; d = direct(*p); l = steplength(); if (fs) { l = 1; } switch (d) { case UP: if (p->y - l > 1 && p->x != 0) { for (i = 1, r = 0; i <= l; i++) { r = r + chess[p->x][p->y - i] + chess[p->x - 1][p->y - i] + chess[p->x + 1][p->y - i]; } if (r / (l * 3) == X) { f = 1; } } break; case RIGHT: if (p->x + l < N - 1) { for (i = 1, r = 0; i <= l; i++) { r = r + chess[p->x + i][p->y] + chess[p->x + i][p->y - 1] + chess[p->x + i][p->y + 1]; } if (r / (l * 3) == X) { f = 1; } } break; case DOWN: if (p->y + l < N - 1 && p->x != 0) { for (i = 1, r = 0; i <= l; i++) { r = r + chess[p->x][p->y + i] + chess[p->x - 1][p->y + i] + chess[p->x + 1][p->y + i]; } if (r / (l * 3) == X) { f = 1; } } break; case LEFT: if (p->x - l > 1) { for (i = 1, r = 0; i <= l; i++) { r = r + chess[p->x - i][p->y] + chess[p->x - i][p->y - 1] + chess[p->x - i][p->y + 1]; } if (r / (l * 3) == X) { f = 1; } } break; default: break; } if (f) { break; } if (k > 10) { k = 0; /*if ((p->x > 1 && p->y > 1 && p->x < N - 2 && p->y < N - 2) && (chess[p->x + 1][p->y] + chess[p->x + 1][p->y - 1] + chess[p->x + 1][p->y + 1] + chess[p->x + 2][p->y] + chess[p->x + 2][p->y - 1] + chess[p->x + 2][p->y + 1] == X * 6 || chess[p->x - 1][p->y] + chess[p->x - 1][p->y - 1] + chess[p->x - 1][p->y + 1] + chess[p->x - 2][p->y] + chess[p->x - 2][p->y - 1] + chess[p->x - 2][p->y + 1] == X * 6 || chess[p->x][p->y + 1] + chess[p->x - 1][p->y + 1] + chess[p->x + 1][p->y + 1] + chess[p->x][p->y + 2] + chess[p->x + 1][p->y + 2] + chess[p->x - 1][p->y + 2] == X * 6 || chess[p->x][p->y - 1] + chess[p->x + 1][p->y - 1] + chess[p->x - 1][p->y - 1] + chess[p->x][p->y - 2] + chess[p->x + 1][p->y - 2] + chess[p->x - 1][p->y - 2] == X * 6)) { continue; fs = 1; } else */if (p->x == 0 && p->y == 1) { *length = 0; return UNVALID; } else { *p = pop(x); } } } *length = l; return d; } point schess(char chess[N][N], enum direction d, int length, point p, stack *x) { int i; switch (d) { case UP: for (i = 0; i < length; i++) { point tp = {p.x, p.y - i}; chess[p.x][p.y - i] = ' '; push(x, tp); //if (p.x == N - 2 && p.y == N - 2) //{ // return p; //} } p.y -= length; break; case RIGHT: for (i = 0; i < length; i++) { point tp = {p.x + i, p.y}; chess[p.x + i][p.y] = ' '; push(x, tp); //if (p.x == N - 2 && p.y == N - 2) //{ // return p; //} } p.x += length; break; case DOWN: for (i = 0; i < length; i++) { point tp = {p.x, p.y + i}; chess[p.x][p.y + i] = ' '; push(x, tp); //if (p.x == N - 2 && p.y == N - 2) //{ // return p; //} } p.y += length; break; case LEFT: for (i = 0; i < length; i++) { point tp = {p.x - i, p.y}; chess[p.x - i][p.y] = ' '; push(x, tp); //if (p.x == N - 2 && p.y == N - 2) //{ // return p; //} } p.x -= length; break; default: break; } return p; } int build(char chess[N][N]) { point p = {0, 1}; stack x; initstack(&x, sizeof(point) * N * N); while (1) { int l; enum direction d = valiable(&p, &l, chess, &x); //output(chess); //printf("%d, %d
", p.x, p.y); if (d == UNVALID) { chess[N - 2][N - 2] = ' '; chess[N - 1][N - 2] = ' '; p.x = N - 1; p.y = N - 2; break; } p = schess(chess, d, l, p, &x); //if (p.x == N - 2 && p.y == N - 2) //{ // chess[p.x][p.y] = ' '; // chess[p.x + 1][p.y] = ' '; // break; //} } cleanstack(&x); return 0; } int main(int argc, char *argv[]) { srand(time(NULL)); char chess[N][N]; memset(chess, X, N * N); chess[0][1] = ' '; build(chess); output(chess); return 0; }