【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：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;
}
}
思考題：
上面的題目介紹了尋路的方法，介紹了如何遍歷所有的可能路徑。當然你可以從這所有的尋找路徑中尋找出一條最短的路徑。但是朋友們可以思考一下，有沒有一種方法，可以一下子尋找到最優的路徑呢？
