c 자국 (6): 배열 과 재 귀 를 결합 하여 응용 하 는 작은 게임

목차
  • 목록
  • 개술
  • 이 한 노 타 하노이 타 워
  • 한 노 타 를 알고리즘 문제 화 설명 으로 바 꾸 기
  • 분석
  • a 가 n 1 일 때
  • b 가 n2 일 때
  • c 가 n 3 일 때
  • d 가 n N 일 때
  • 실현
  • 3 미궁
  • 미궁 의 표현 방식
  • 수 동 미로
  • AI 버 전의 미로


  • 개술
    앞에서 각각 배열 과 재 귀 를 서술 했다. 그들 은 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).배열 의 줄 수로 표시 하 다.캐릭터 가 미로 에서 이동 하려 면 다음 과 같은 몇 가 지 를 주의해 야 합 니 다:
  • 이동 하고 자 하 는 새로운 좌표 에서 x, y 의 값 은 모두 0 보다 작 으 면 안 된다 (그렇지 않 으 면 경 계 를 넘 는 다).
  • 이동 하고 자 하 는 새 좌표 에서 x, y 의 값 은 모두 크 면 안 됩 니 다. 배열 의 최대 줄 과 열 은 1 을 줄 여야 합 니 다. 예 를 들 어 미로 에서 배열 int a [M] [N] 을 사용 하면 새 좌표 에 x < N 또는 x < = (N - 1), y < M 또는 y < = (M - 1)
  • 가 있어 야 합 니 다.
  • 배열 이 벽 을 나타 내 는 요소 (예 를 들 어 위의 2 차원 배열 중의 '2') 의 좌표 로 이동 할 수 없다. 예 를 들 어 위의 2 차원 배열 에서 캐릭터 는 좌표 (2, 0), 즉 2 차원 배열 의 [0] [2] 위치
  • 로 이동 할 수 없다.
  • 매번 한 단위 의 좌표 만 이동 할 수 있다
  • 이동 방향 은 위, 아래, 왼쪽, 오른쪽
  • 만 가능 합 니 다.
    위의 몇 가지 제한 조건 이 있 으 면 나머지 는 구체 적 인 이동 이 이 루어 진다. 이것 은 비교적 간단 하 다. 바로 입력 한 자모 에 따라 어느 방향 으로 이동 해 야 하 는 지 판단 한 다음 에 이동 하고 자 하 는 새 좌 표를 위의 몇 가지 조건 에 만족 하 는 지 판단 하고 만족 하면 이동 하 며 만족 하지 않 으 면 제자리 에서 움 직 이지 않 는 다.구체 적 인 실현 코드 는 다음 과 같다.
    /** * *@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 차원 배열 과 같이 데이터 가 초기 화 된다.
    자동 으로 길 을 찾 으 려 면 미로 의 규칙 이나 실현 방식 을 분석 해 야 한다.
  • 우선, 제한 조건 을 무시 한 상황 에서 모든 좌표 점 에서 4 가지 이동 방식, 위, 아래, 왼쪽, 오른쪽
  • 이 있 을 수 있다.
  • 그 다음 에 이동 하 는 과정 은 현재 좌표 의 배열 요소 와 계 산 된 새로운 좌표 의 배열 요 소 를 교환 하 는 것 이다
  • .
  • 다시 한 번 이동 과정 에서 의 제한 조건 과 수 동 판 은 같다
  • 그 다음 에 초기 화 된 후에 캐릭터 는 왼쪽 상단 (좌 표 는 (0, 0) 이 고 배열 의 위 치 는 [0] [0] [0] 이다. 미로 에서 벗 어 나 는 표 지 는 오른쪽 아래 (좌 표 는 (MAZE COLUMN - 1, MAZE ROW - 1) 이 고 배열 의 위 치 는 [MAZE ROW - 1] [MAZE COLUMN - 1]) 이기 때문에 이동 여 부 를 판단 하 는 순 서 는 오른쪽, 아래, 왼쪽, 위
  • 이다.
  • 마지막 으로 이동 을 방지 해 야 할 때 후퇴 하 는 상황 이 발생 한다. 즉, 위치 A 에서 위치 B 로 이동 한 후 새로운 이동 점 C 를 계산 할 때 다시 A 위치의 좌표 에 떨 어 뜨리 지 못 하 게 하고 그렇지 않 으 면 사순환
  • 이 발생 한다.
    우선 각 방향 이 이동 할 수 있 는 지 를 판단 하 는 함수 입 니 다.
    /** * *@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; }

    좋은 웹페이지 즐겨찾기