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

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}; /* 記錄已走過的路 */

b）其實，我們編寫一個判斷函數(shù)，判斷當(dāng)前節(jié)點是否合法

int check_pos_valid(int x, int y)
{
    /* 節(jié)點是否出邊界 */
    if(x < 0 || x>= MAX_NUMBER_LENGTH || y < 0 || y >= MAX_NUMBER_LENGTH)
        return 0;

    /* 當(dāng)前節(jié)點是否存在路 */
    if(0 == gPath[x][y])
        return 0;

    /* 當(dāng)前節(jié)點是否已經(jīng)走過 */
    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;
}

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

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中所描述的算法只是尋找一條路，那么如果想遍歷所有的道路，算法應(yīng)該怎么修改呢？

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;
    }
}

思考題：

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