程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之尋路)

一步一步寫算法(之尋路)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    尋路是游戲設計中需要使用到一種功能,那麼我們怎麼樣以一個點作為起始點,快速地尋找到目標點呢?其實尋路的方法不難。一種簡單有效的方法就是回溯法。如果我們從一個點出發,那麼這個點周圍肯定有若干條路,只要有一條路存在,我們就一直走下去,直到發現沒有路走為止;要是發現路走不下去了怎麼辦,那就只好回頭了,我們只能從剩下的選項中繼續選擇一條路,繼續嘗試。如果很不幸,所有的嘗試都結束了,還是沒有發現目標節點,那只能說明,我們真的無路可走。

 

    a)首先,我們用矩陣表示地圖:其中1表示路,0表示沒有路,2表示終點,起始地點為(1,0)

 

 

#define MAX_NUMBER_LENGTH 6  

 

static int gPath[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = { 

    {0 , 0, 0, 0, 1, 1}, 

    {1,  1, 0, 0, 1, 0}, 

    {0 , 1, 1, 1, 1, 0}, 

    {0 , 0, 1, 0, 1, 2}, 

    {0 , 0, 1, 0, 1, 0}, 

    {0 , 0, 1, 1, 1, 0} 

}; 

 

static int gValue[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = {0}; /* 記錄已走過的路*/ 

#define MAX_NUMBER_LENGTH 6

 

static int gPath[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = {

       {0 , 0, 0, 0, 1, 1},

       {1,  1, 0, 0, 1, 0},

       {0 , 1, 1, 1, 1, 0},

       {0 , 0, 1, 0, 1, 2},

       {0 , 0, 1, 0, 1, 0},

       {0 , 0, 1, 1, 1, 0}

};

 

static int gValue[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = {0}; /* 記錄已走過的路*/

 

 

 

 

    b)其實,我們編寫一個判斷函數,判斷當前節點是否合法

 

int check_pos_valid(int x, int y) 

    /* 節點是否出邊界*/ 

    if(x < 0 || x>= MAX_NUMBER_LENGTH || y < 0 || y >= MAX_NUMBER_LENGTH) 

        return 0; 

 

    /* 當前節點是否存在路*/ 

    if(0 == gPath[x][y]) 

        return 0; 

 

    /* 當前節點是否已經走過*/ 

    if('#' == gValue[x][y]) 

        return 0; 

 

    return 1; 

int check_pos_valid(int x, int y)

{

       /* 節點是否出邊界*/

       if(x < 0 || x>= MAX_NUMBER_LENGTH || y < 0 || y >= MAX_NUMBER_LENGTH)

              return 0;

 

       /* 當前節點是否存在路*/

       if(0 == gPath[x][y])

              return 0;

 

       /* 當前節點是否已經走過*/

       if('#' == gValue[x][y])

              return 0;

 

       return 1;

}

    c)接著,我們編寫一個遞歸的尋找算法即可

 

 

int find_path(int x, int y) 

    if(check_pos_valid(x,y)) 

    { 

        if(2 == gPath[x][y]){ 

            gValue[x][y] = '#'; 

            return 1; 

        } 

 

        gValue[x][y] = '#'; 

        if(find_path(x, y-1)) 

            return 1; 

 

        if(find_path(x-1, y)) 

            return 1; 

 

        if(find_path(x, y+1)) 

            return 1; 

 

        if(find_path(x+1, y)) 

            return 1; 

        gValue[x][y] = 0; 

        return 0; 

    } 

 

    return 0; 

int find_path(int x, int y)

{

       if(check_pos_valid(x,y))

       {

              if(2 == gPath[x][y]){

                     gValue[x][y] = '#';

                     return 1;

              }

 

              gValue[x][y] = '#';

              if(find_path(x, y-1))

                     return 1;

 

              if(find_path(x-1, y))

                     return 1;

 

              if(find_path(x, y+1))

                     return 1;

 

              if(find_path(x+1, y))

                     return 1;

              gValue[x][y] = 0;

              return 0;

       }

 

       return 0;

}

    d)為了驗證我們的算法是否正確,可以編寫一個打印函數

 

void print_path() 

    int outer; 

    int inner; 

 

    for(outer = 0; outer < MAX_NUMBER_LENGTH; outer++){ 

        for(inner = 0; inner < MAX_NUMBER_LENGTH; inner++){ 

            printf("%c ", gValue[outer][inner]); 

        } 

        printf("\n"); 

    } 

void print_path()

{

       int outer;

       int inner;

 

       for(outer = 0; outer < MAX_NUMBER_LENGTH; outer++){

              for(inner = 0; inner < MAX_NUMBER_LENGTH; inner++){

                     printf("%c ", gValue[outer][inner]);

              }

              printf("\n");

       }

}

 

 

    e)上面c中所描述的算法只是尋找一條路,那麼如果想遍歷所有的道路,算法應該怎麼修改呢?

 

 

void find_path(int x, int y) 

    if(check_pos_valid(x,y)) 

    { 

        if(2 == gPath[x][y]){ 

            gValue[x][y] = '#'; 

            print_path(); 

            gValue[x][y] = 0; 

            return ; 

        } 

 

        gValue[x][y] = '#'; 

        find_path(x, y-1); 

        find_path(x-1, y); 

        find_path(x, y+1); 

        find_path(x+1, y); 

        gValue[x][y] = 0; 

    } 

void find_path(int x, int y)

{

       if(check_pos_valid(x,y))

       {

              if(2 == gPath[x][y]){

                     gValue[x][y] = '#';

                     print_path();

                     gValue[x][y] = 0;

                     return ;

              }

 

              gValue[x][y] = '#';

              find_path(x, y-1);

              find_path(x-1, y);

              find_path(x, y+1);

              find_path(x+1, y);

              gValue[x][y] = 0;

       }

}

思考題:

 

    上面的題目介紹了尋路的方法,介紹了如何遍歷所有的可能路徑。當然你可以從這所有的尋找路徑中尋找出一條最短的路徑。但是朋友們可以思考一下,有沒有一種方法,可以一下子尋找到最優的路徑呢?

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved