c 자국 (6): 배열 과 재 귀 를 결합 하여 응용 하 는 작은 게임
개술
앞에서 각각 배열 과 재 귀 를 서술 했다. 그들 은 c 언어 프로 그래 밍 과 프로 그래 밍 에서 매우 유용 하고 나타 나 는 빈도 도 비교적 높다. 다음은 두 개의 전형 적 인 작은 게임 (한 노 타, 미로) 으로 배열 과 재 귀 의 구체 적 인 응용 을 설명 한다.
2. 하 노 타 워 (하노이 타 워)
한 노 타: 한 노 타 문 제 는 인도의 오래된 전설 에서 유래 한 익 지 장난감 이다.대 범 천 은 세 계 를 만 들 때 세 개의 금강석 기둥 을 만 들 었 고 한 기둥 에 아래 에서 위로 크기 순 으로 64 개의 황금 원반 을 쌓 았 다.대 범 천 은 브라만 에 게 원반 을 아래 부터 크기 순 으로 다른 기둥 위 에 다시 놓 으 라 고 명령 했다.또 작은 원반 에 서 는 원반 을 확대 할 수 없고, 세 기둥 사이 에 서 는 한 번 에 한 개의 원반 만 이동 할 수 있 도록 규정 하고 있다.
이것 은 비교적 고전적 인 귀속 문제 라 고 할 수 있다.그 실현 방식 을 간단히 설명 하 겠 습 니 다.
1. 한 노 타 를 알고리즘 문제 화 설명 으로 바 꾸 기
만약 에 여기 A, B, C 세 개의 기둥 이 있 고 기둥 A 에 n 개의 큰 것 에서 작은 것 까지 의 원반 이 있다 고 가정 하면 A 기둥 에 있 는 원반 을 모두 C 기둥 으로 옮 겨 야 한다. 그 구체 적 인 규칙 은 다음 과 같다. - 원반 은 항상 위 에서 아래로 큰 순 서 를 유지 해 야 한다. - 한 번 에 하나의 원반 만 이동 할 수 있다. - A 에서 C 로 이동 하 는 과정 에서 기둥 B 가 중간 이동 을 하 는 것 을 기억 할 수 있다.
2. 분석
여기 서 숫자 로 원반 을 표시 합 니 다. 숫자의 크기 는 원반 의 크기 입 니 다. 그러면 한 노 타 는 간단하게 자막 과 숫자 로 표시 할 수 있 습 니 다.
A B C
1 2 … n - 1 n
a. n = 1 일 때
원반 을 A 에서 C, A - > C 로 직접 이동 합 니 다.
b. n = 2 일 때
이동 순서:
원반
이동 정책
1
A ——> B
2
A ——> C
1
B ——> C
c. n = 3 일 때
위의 두 개의 원반 (1, 2) 을 하나의 전 체 를 볼 수 있 습 니 다. 그러면 위 처럼 두 개의 원반 만 처리 할 수 있 습 니 다. 여 기 는 대문자 '1' 로 (1, 2) 두 개의 원반 의 합 체 를 표시 하고 '2' 로 원반 3 을 표시 합 니 다. 그 이동 순 서 는 다음 과 같 습 니 다.
원반
이동 정책
하나.
A ——> B
둘째.
A ——> C
하나.
B ——> C
전체 전개 시 이동 순 서 는 다음 과 같 습 니 다.
원반
이동 정책
1
A ——> C
2
A ——> B
1
C ——> B
3
A ——> C
1
B ——> A
2
B ——> C
1
A ——> C
d. n = N 일 때
위 와 마찬가지 로 앞의 N - 1 개의 원반 을 동의 하 는 원반 으로 볼 수 있 고, N 개의 원반 을 두 번 째 원반 으로 볼 수 있다. 그러면 공급 순 서 는 다음 과 같다.
원반
이동 정책
N-1
A ——> B
N
A ——> C
N-1
B ——> C
이 이동 전략 은 한 노 타가 귀납 한 통용 이동 전략 이다. 즉, 한 노 타 게임 의 귀속 함 수 는 이런 이동 전략 만 실현 하면 된다.
3. 실현
여기 서 말 하 는 작은 게임 은 일반적인 시 크 한 인터페이스 가 있 는 게임 이 아니다. 이 한 노 타 작은 게임 은 간단 한 콘 솔 프로그램 이다. 게임 이 라면 여 기 는 비교적 자주 사용 하 는 MVC 의 구조 에 따라 이 루어 진다. 그 중에서 - M: 모델 (즉 데이터 부분) 은 2 차원 배열 로 이 작은 게임 의 데이터 모델 을 실현 한다.배열 의 열 로 각각 기둥 A, B, C 를 표시 하고 배열 의 줄 로 원반 (예 를 들 어 int data arrray [10] [3]) - V: 보기 (즉 디 스 플레이 부분) 를 표시 합 니 다. 여 기 는 show 함 수 를 실현 하여 2 차원 배열 을 콘 솔 인터페이스 에 표시 합 니 다 - C: 제어 (즉 논리 부분). 여 기 는 재 귀 함수 로 원반 을 이동 하 는 과정 을 실현 합 니 다.
다음은 완전한 c 언어 코드 를 붙 입 니 다.
#include <stdio.h>
#include <stdlib.h>
/**< the data struct, this is M in MVC model */
typedef struct my_hanoi_tower_s
{
int row; /** the count of array row */
int column; /** the count of array column */
int column_name[3];
int data_array[10][3];
}my_hanoi_tower_t;
/** * *@brief show the hanoi tower data array. * *@param mht [in] the data struct. * *@return None. * *@see *@note this is V in MVC model */
void show(my_hanoi_tower_t* mht)
{
int i,j;
int n;
for (n = 0; n < mht->column; n++)
{
printf("%5c", mht->column_name[n]);/**< show the name of columns */
}
printf("
---------------------
"); /** show split line */
for (i = 0; i < mht->row; i++)
{
for(j = 0; j < mht->column; j++)
{
printf("%5d", mht->data_array[i][j]);
}
printf("
");
}
printf("
");
}
/** * *@brief initialize the hanoi tower data array . * *@param mht [in] the data struct. *@param n [in] the count of disc * *@return None. * *@see *@note this is M in MVC model */
void init(my_hanoi_tower_t* mht, int n)
{
int j = 1;
int i;
for (i = n; i > 0; i--)
{
/** the set number means disc size */
mht->data_array[mht->row - i][0] = j++; /** just initialize column 'A' */
}
mht->column_name[0] = 'A';
mht->column_name[1] = 'B';
mht->column_name[2] = 'C';
}
int get_zero_start_row(my_hanoi_tower_t* mht, int column)
{
int ret = -1;
int i;
for (i = mht->row - 1; i >= 0; i--)
{
if (mht->data_array[i][column] == 0)
{
ret = i;
break;
}
}
return ret;
}
int get_noe_zero_start_row(my_hanoi_tower_t* mht, int column)
{
int ret = -1;
int i;
for (i = 0; i < mht->row; i++)
{
if (mht->data_array[i][column] > 0)
{
ret = i;
break;
}
}
return ret;
}
void move_disc(my_hanoi_tower_t* mht, int from_col, int to_col, int from_row, int to_row)
{
int to_val = mht->data_array[to_row][to_col];
int from_val = mht->data_array[from_row][from_col];
mht->data_array[to_row][to_col] = from_val;
mht->data_array[from_row][from_col] = to_val;
printf("move: %c(%d) --> %c
", mht->column_name[from_col], from_val, mht->column_name[to_col]);
show(mht);
}
/** * *@brief the AI to auomatic process hanoi tower. * *@param mht [in] the data struct. * *@return None. * *@see *@note this is C in MVC model *@note : 1. , A C 。 2. A , A 1 ( ) B , A 2 C , B C 。 3. A 3 , A 1 2 ( 2 ) B ( C ), A 3 C , B A C 。 4. A n , A 1 n-1 ( n-1 ) B ( C ), A n C , B n-1 A C 。 */
void hanoi_AI(my_hanoi_tower_t* mht,int n, int a, int b, int c)
{
if (n < 1)
{
return ;
}
else if (1 == n)
{
int a_row = get_noe_zero_start_row(mht, a);
int c_row = get_zero_start_row(mht, c);
move_disc(mht, a, c, a_row, c_row);
}
else
{
hanoi_AI(mht, n - 1, a, c, b);
int a_row = get_noe_zero_start_row(mht, a);
int c_row = get_zero_start_row(mht, c);
move_disc(mht, a, c, a_row, c_row);
hanoi_AI(mht, n - 1, b, a, c);
}
}
int main(int argc, char* argv[])
{
my_hanoi_tower_t mht = {0};
mht.column = 3;
mht.row = 10;
printf("Hello world!
");
init(&mht, 3);
show(&mht);
hanoi_AI(&mht, 3, 0, 1, 2);
show(&mht);
system("pause");
return 0;
}
미로
미로 도 비교적 전형 적 인 작은 게임 이다. 그 중에서 자동 으로 미 로 를 걷 는 알고리즘 도 길 찾기 알고리즘 의 간단 한 초기 형 이 라 고 할 수 있다.
1. 미궁 의 표현 방식
이곳 의 미 로 는 위의 한 노 타 미니 게임 과 마찬가지 로 2 차원 배열 로 표시 된다.다른 것 은 미로 게임 에서 2 차원 배열 안에 몇 개의 서로 다른 데이터 가 있 을 수 있다 는 것 이다. 먼저 배열 의 대부분 요 소 는 0 이 고 '배경' 의 역할 을 한 다음 에 내부 에 2 요소 가 있 을 것 이다. 그들 은 배열 안의 서로 다른 곳 에 흩 어 져 '벽' 의 역할 을 하 는데 이 방향 이 현재 위치 에서 차단 되 어 통행 할 수 없다 는 것 을 나타 낸다.또 하나의 값 이 1 인 요소 가 있 는데 초기 화 된 후에 그 위 치 는 [0] [0] 에 있 고 미로 로 가 는 역할 을 나타 낸다.마치
// ---- x
// |
// |
// y
{
{ 1, 0, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 2, 2, 2, 2, 0, 0, 0, 0 },
{ 0, 0, 2, 0, 0, 0, 2, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 2, 0, 2, 2 },
{ 2, 0, 2, 0, 0, 0, 2, 0, 0, 2 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 2 },
{ 0, 2, 0, 0, 0, 2, 0, 2, 0, 0 },
{ 0, 2, 0, 2, 0, 0, 0, 0, 2, 0 },
{ 0, 0, 0, 0, 2, 0, 2, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
2. 수 동 미로
먼저 이 는 상대 적 으로 간단 하 다. 이런 상황 은 상대 적 으로 간단 하 다. 그 원 리 는 키보드 에서 입력 한 자 모 를 받 아 캐릭터 의 '1' 이 어떻게 이동 해 야 하 는 지 확인 하 는 것 이다. x, y 를 사용 하여 좌 표를 표시 하고 x 는 수평 에서 왼쪽 에서 오른쪽으로 순서대로 증가 하 는 것 이다 (즉 0 - > x). 배열 의 열 로 x 는 위 에서 아래로 순서대로 증가 하 는 것 이다 (즉 0 - > y).배열 의 줄 수로 표시 하 다.캐릭터 가 미로 에서 이동 하려 면 다음 과 같은 몇 가 지 를 주의해 야 합 니 다:
위의 몇 가지 제한 조건 이 있 으 면 나머지 는 구체 적 인 이동 이 이 루어 진다. 이것 은 비교적 간단 하 다. 바로 입력 한 자모 에 따라 어느 방향 으로 이동 해 야 하 는 지 판단 한 다음 에 이동 하고 자 하 는 새 좌 표를 위의 몇 가지 조건 에 만족 하 는 지 판단 하고 만족 하면 이동 하 며 만족 하지 않 으 면 제자리 에서 움 직 이지 않 는 다.구체 적 인 실현 코드 는 다음 과 같다.
/** * *@brief role move a step with direction. * *@param a [in] the 2D array. *@param x [io] input orignal x coordinate,output move result. *@param y [io] input orignal y coordinate,output move result. *@param direction [in] move direction. * *@return None. * *@see */
static void maze_move(int a[MAZE_ROW][MAZE_COLUMN],int* x, int* y, int direction)
{
int org_x = *x; //old coordinate x
int org_y = *y; // old coordinate y
int role_x = org_x;
int role_y = org_y;
const char* dir_name = "unknown";
switch (direction)
{
case 'w':// up
if ((role_y - 1) >= 0)
{
role_y--;
dir_name = "up";
}
break;
case 's': //down
if ((role_y + 1) < MAZE_ROW)
{
role_y++;
dir_name = "down";
}
break;
case 'a': //left
if ((role_x - 1) >= 0)
{
role_x--;
dir_name = "left";
}
break;
case 'd'://right
if ((role_x + 1) < MAZE_COLUMN)
{
role_x++;
dir_name = "right";
}
break;
default:
printf("unspport this command:%c
", direction);
break;
}
if ((org_x != role_x) || (org_y != role_y)) //coordinate has change,then move
{
printf("move:%s
", dir_name);
int temp = a[org_y][org_x];
a[org_y][org_x] = a[role_y][role_x];
a[role_y][role_x] = temp;
*x = role_x;
*y = role_y;
}
}
그 중 MAZEROW, MAZE_COLUMN 은 매크로 정의 로 배열 의 줄 과 열 을 나타 내 며 구체 적 인 수요 에 따라 값 을 정의 할 수 있 습 니 다.
3. AI 버 전의 미로
이 버 전 은 길 찾기 알고리즘 을 사용 하여 미로 에서 벗 어 나 는 경 로 를 자동 으로 계산 합 니 다. (물론 미로 가 막 다른 골목 이 라면 자동 으로 길 찾기 도 미로 에서 벗 어 나 는 경 로 를 찾 을 수 없습니다. 그리고 길 찾기 의 실현 도 재 귀적 인 버 전과 순환 버 전 으로 나 눌 수 있 습 니 다) 데이터 표현 에 있어 서 는 수 동 판 미로 와 마찬가지 로 2 차원 배열 로 이 루어 집 니 다. 물론 다른 점도 있 습 니 다.AI 버 전에 서 는 수 동판 에 더 해 똑 같은 (행렬 이 같은) 2 차원 배열 을 정의 해 자동 길 찾기 알고리즘 에 사용 하 는 것 이 고, 그 중에서 도 미로 데 이 터 를 나타 내 는 2 차원 배열 과 같이 데이터 가 초기 화 된다.
자동 으로 길 을 찾 으 려 면 미로 의 규칙 이나 실현 방식 을 분석 해 야 한다.
우선 각 방향 이 이동 할 수 있 는 지 를 판단 하 는 함수 입 니 다.
/** * *@brief try move a step(just got x,y coordinate,not really move). * *@param a [in] the 2D array. *@param x [io] input orignal x coordinate,output move result. *@param y [io] input orignal y coordinate,output move result. * *@return 1:can move, 0:cann't move. * *@see */
int try_move(int a[MAZE_ROW][MAZE_COLUMN], int* x, int *y)
{
int ret = 1;
int tempx = *x;
int tempy = *y;
//try order: right->down->left->up
if (((tempx + 1) < MAZE_COLUMN) && (a[tempy][(tempx + 1)] < BARRIER))
{//try right
*x = tempx + 1;
}
else if (((tempy + 1) < MAZE_ROW) && (a[(tempy + 1)][tempx] < BARRIER))
{//try down
*y = tempy + 1;
}
else if (((tempx - 1) >= 0) && (a[tempy][(tempx - 1)] < BARRIER))
{//try left
*x = tempx - 1;
}else if (((tempy - 1) >= 0) && (a[(tempy - 1)][tempx] < BARRIER))
{//try up
*y = tempy - 1;
}
else
{
ret = 0;
}
return ret;
}
그 중 MAZEROW, MAZE_COLUMN 은 매크로 정의 로 배열 의 줄 과 열 을 나타 내 며 구체 적 인 수요 에 따라 값 을 정의 할 수 있 습 니 다.매크로 BARRIER 는 미궁의 '벽' 을 나타 내 는데 그 값 은 2 이다. BARRIER 보다 작다 고 판단 하 는 이 유 는 BARRIER 보다 큰 매크로 기록 길 찾기 알고리즘 이 걸 어 온 경 로 를 정의 하고 이미 걸 어 온 경 로 를 반복 할 수 없 기 때문이다.
그 다음 에 재 귀적 길 찾기 함수:
/** * *@brief the AI of pathfinding (recursive implement) * *@param a [in] the 2D array. *@param x [in] the x coordinate of role. *@param y [in] the y coordinate of role. * *@return 1: find, 0: doesn't. * *@see */
int maze_pathfinding_ai_recursive(int a[MAZE_ROW][MAZE_COLUMN], int x, int y)
{
a[y][x] = AI_OBJ;
if (((MAZE_COLUMN - 1) == x) && ((MAZE_ROW - 1) == y)) //recursive end condition
{
return 1;
}
else
{
if (try_move(a, &x, &y)) //check try move.
{
return maze_pathfinding_ai_recursive(a, x, y);
}
}
return 0;
}
그 중 宏 AIOBJ 의 값 은 3 으로 길 찾기 알고리즘 이 지나 간 경로 와 중복 되 지 않도록 하 는 경로 (즉, 순환) 를 기록 합 니 다.
위 에 길 찾기 알고리즘 을 제공 하 는 것 은 재 귀 와 순환 두 가지 버 전이 있 고 순환 하 는 알고리즘 실현 방식 은 다음 과 같다.
/** * *@brief the AI of pathfinding (loop implement) * *@param a [in] the 2D array. *@param x [in] the x coordinate of role. *@param y [in] the y coordinate of role. * *@return 1: find, 0: doesn't. * *@see */
int maze_pathfinding_ai_loop(int a[MAZE_ROW][MAZE_COLUMN], int x, int y)
{
int ret = 0;
int loop_cnt = 0;
int max_loop = MAZE_ROW * MAZE_COLUMN; //maximum move steps, to avoid endless loop.
while (loop_cnt++ < max_loop)
{
//end condition,it is same with recursive ai.
if (((MAZE_COLUMN - 1) == x) && ((MAZE_ROW - 1) == y))
{
ret = 1;
break;
}
if (try_move(a, &x, &y)) //check try move
{
a[y][x] = AI_OBJ;
}
}
return ret;
}
마지막 으로 모든 미로 게임 의 코드 를 붙 입 니 다.
#include <stdio.h>
#include <stdlib.h>
//maze data array
#define MAZE_ROW 10
#define MAZE_COLUMN 10
//playing maze mode: 1: AI, 0: human
#define MAZE_PLAY_MODE 1
//pathfinding ai type(AI only): 1: recursive, 0: loop
#define MAZE_PATHFINDING_AI_TYPE 1
#define ROLE_OBJ 1
#define AI_OBJ 3 //this value must bigger than BARRIER
#define BARRIER 2
#define MAZE_PAD 0
//orignal coordinate
#define ROLE_ORG_X 0 //in array column
#define ROLE_ORG_Y 0 //in array row
#define show_obj(obj) printf("%4d ", obj)
// ---- x
// |
// |
// y
static int g_maze_data[MAZE_ROW][MAZE_COLUMN] =
{
{ 1, 0, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 2, 2, 2, 2, 0, 0, 0, 0 },
{ 0, 0, 2, 0, 0, 0, 2, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 2, 0, 2, 2 },
{ 2, 0, 2, 0, 0, 0, 2, 0, 0, 2 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 0, 2 },
{ 0, 2, 0, 0, 0, 2, 0, 2, 0, 0 },
{ 0, 2, 0, 2, 0, 0, 0, 0, 2, 0 },
{ 0, 0, 0, 0, 2, 0, 2, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
static int g_maze_ai_data[MAZE_ROW][MAZE_COLUMN];
/** * *@brief show all element of 2D array. * *@param a [in] the 2D array. * *@return None. * *@see */
void show(int a[MAZE_ROW][MAZE_COLUMN])
{
printf("
----------------------------------------------------
");
int i,j;
for (i = 0; i < MAZE_ROW; i++)
{
for (j = 0; j < MAZE_COLUMN; j++)
{
show_obj(a[i][j]);
}
printf("
");
}
printf("
");
}
/** * *@brief initialize maze ai data arrray with a 2D array. * *@param a [in] the 2D array. * *@return None. * *@see */
void init_ai_data(int a[MAZE_ROW][MAZE_COLUMN])
{
int i, j;
for (i = 0; i < MAZE_ROW; i++)
{
for (j = 0; j < MAZE_COLUMN; j++)
{
g_maze_ai_data[i][j] = a[i][j];
}
}
}
/** * *@brief role move a step with direction. * *@param a [in] the 2D array. *@param x [io] input orignal x coordinate,output move result. *@param y [io] input orignal y coordinate,output move result. *@param direction [in] move direction. * *@return None. * *@see */
static void maze_move(int a[MAZE_ROW][MAZE_COLUMN],int* x, int* y, int direction)
{
int org_x = *x; //old coordinate x
int org_y = *y; // old coordinate y
int role_x = org_x;
int role_y = org_y;
const char* dir_name = "unknown";
switch (direction)
{
case 'w':// up
if ((role_y - 1) >= 0)
{
role_y--;
dir_name = "up";
}
break;
case 's': //down
if ((role_y + 1) < MAZE_ROW)
{
role_y++;
dir_name = "down";
}
break;
case 'a': //left
if ((role_x - 1) >= 0)
{
role_x--;
dir_name = "left";
}
break;
case 'd'://right
if ((role_x + 1) < MAZE_COLUMN)
{
role_x++;
dir_name = "right";
}
break;
default:
printf("unspport this command:%c
", direction);
break;
}
if ((org_x != role_x) || (org_y != role_y)) //coordinate has change,then move
{
printf("move:%s
", dir_name);
int temp = a[org_y][org_x];
a[org_y][org_x] = a[role_y][role_x];
a[role_y][role_x] = temp;
*x = role_x;
*y = role_y;
}
}
/** * *@brief try move a step(just got x,y coordinate,not really move). * *@param a [in] the 2D array. *@param x [io] input orignal x coordinate,output move result. *@param y [io] input orignal y coordinate,output move result. * *@return 1:can move, 0:cann't move. * *@see */
int try_move(int a[MAZE_ROW][MAZE_COLUMN], int* x, int *y)
{
int ret = 1;
int tempx = *x;
int tempy = *y;
//try order: right->down->left->up
if (((tempx + 1) < MAZE_COLUMN) && (a[tempy][(tempx + 1)] < BARRIER))
{//try right
*x = tempx + 1;
}
else if (((tempy + 1) < MAZE_ROW) && (a[(tempy + 1)][tempx] < BARRIER))
{//try down
*y = tempy + 1;
}
else if (((tempx - 1) >= 0) && (a[tempy][(tempx - 1)] < BARRIER))
{//try left
*x = tempx - 1;
}else if (((tempy - 1) >= 0) && (a[(tempy - 1)][tempx] < BARRIER))
{//try up
*y = tempy - 1;
}
else
{
ret = 0;
}
return ret;
}
/** * *@brief the AI of pathfinding (recursive implement) * *@param a [in] the 2D array. *@param x [in] the x coordinate of role. *@param y [in] the y coordinate of role. * *@return 1: find, 0: doesn't. * *@see */
int maze_pathfinding_ai_recursive(int a[MAZE_ROW][MAZE_COLUMN], int x, int y)
{
a[y][x] = AI_OBJ;
if (((MAZE_COLUMN - 1) == x) && ((MAZE_ROW - 1) == y)) //recursive end condition
{
return 1;
}
else
{
if (try_move(a, &x, &y)) //check try move.
{
return maze_pathfinding_ai_recursive(a, x, y);
}
}
return 0;
}
/** * *@brief the AI of pathfinding (loop implement) * *@param a [in] the 2D array. *@param x [in] the x coordinate of role. *@param y [in] the y coordinate of role. * *@return 1: find, 0: doesn't. * *@see */
int maze_pathfinding_ai_loop(int a[MAZE_ROW][MAZE_COLUMN], int x, int y)
{
int ret = 0;
int loop_cnt = 0;
int max_loop = MAZE_ROW * MAZE_COLUMN; //maximum move steps, to avoid endless loop.
while (loop_cnt++ < max_loop)
{
//end condition,it is same with recursive ai.
if (((MAZE_COLUMN - 1) == x) && ((MAZE_ROW - 1) == y))
{
ret = 1;
break;
}
if (try_move(a, &x, &y)) //check try move
{
a[y][x] = AI_OBJ;
}
}
return ret;
}
void maze_walk_out(int real_data[MAZE_ROW][MAZE_COLUMN], int ai_data[MAZE_ROW][MAZE_COLUMN])
{
int x = 0;
int y = 0;
int loop_cnt = 0;
int max_loop = MAZE_ROW * MAZE_COLUMN; //maximum move steps, to avoid endless loop.
ai_data[ROLE_ORG_Y][ROLE_ORG_X] = ROLE_OBJ;
while (loop_cnt++ < max_loop)
{
//end condition,it is same with recursive ai.
if (((MAZE_COLUMN - 1) == x) && ((MAZE_ROW - 1) == y))
{
break;
}
/** move order: right->down->left->up. */
//try right
if (((x + 1) < MAZE_COLUMN) && (ai_data[y][(x + 1)] == AI_OBJ))
{
ai_data[y][(x + 1)] = MAZE_PAD; //reset ai path value.
maze_move(real_data, &x, &y, 'd'); //move right
show(real_data);
}
//try down
if (((y + 1) < MAZE_ROW) && (ai_data[(y + 1)][x] == AI_OBJ))
{
ai_data[(y + 1)][x] = MAZE_PAD;//reset ai path value.
maze_move(real_data, &x, &y, 's'); //move down
show(real_data);
}
//try left
if (((x - 1) >= 0) && (ai_data[y][(x - 1)] == AI_OBJ))
{
ai_data[y][(x - 1)] = MAZE_PAD;//reset ai path value.
maze_move(real_data, &x, &y, 'a'); //move left
show(real_data);
}
//try up
if (((y - 1) >= 0) && (ai_data[(y - 1)][x] == AI_OBJ))
{
ai_data[(y - 1)][x] = MAZE_PAD;//reset ai path value.
maze_move(real_data, &x, &y, 'w'); //move up
show(real_data);
}
}
}
/** * *@brief human play the game. * *@param None * *@return None * *@see */
void human_play()
{
int x = ROLE_ORG_X;
int y = ROLE_ORG_Y; //role, initialize coordinate
printf("
------------------------------------
");
printf("input:w,s,a,d to play the game:
");
printf("w --> up
");
printf("s --> down
");
printf("a --> left
");
printf("d --> right
");
printf("note: aways need to input the key of \'ENTER\' as end");
printf("
------------------------------------
");
while (1)
{
int ch = getchar();
getchar(); //skip the key of 'enter'
maze_move(g_maze_data,&x, &y, ch);
show(g_maze_data);
}
}
/** * *@brief AI play the game. * *@param None * *@return None * *@see */
void ai_play()
{
int ret = 0;
int x = ROLE_ORG_X;
int y = ROLE_ORG_Y;
init_ai_data(g_maze_data); //initialize ai data array.
#if MAZE_PATHFINDING_AI_TYPE //if 1, recursive implement
ret = maze_pathfinding_ai_recursive(g_maze_ai_data, x, y);
#else//if 0, loop implement.
ret = maze_pathfinding_ai_loop(g_maze_ai_data, x, y);
#endif
if (1 == ret)
{
printf("congratulations! you can walk out the maze!
");
printf("show AI data array
");
show(g_maze_ai_data);
printf("starting demonstrate the procedure of walk out maze...
");
maze_walk_out(g_maze_data, g_maze_ai_data);
}
else
{
printf("unfortunate! cann't find any path to walk out the maze!
");
}
//show(g_maze_data);
}
int main(void)
{
printf("show maze default data array
");
show(g_maze_data);
#if MAZE_PLAY_MODE //1:ai play mode
ai_play();
#else //0: human play mode.
human_play();
#endif
system("pause");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDOJ/HDU 1113 Word Amalgamation (사전 순서 ~ 지도)a dictionary, which consists of at least one and at most 100 words, one per line; a line containing XXXXXX, which signal...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.