C++算法之尋路算法
尋路是游戲設計中需要使用到一種功能，那么我們怎么樣以一個點作為起始點，快速地尋找到目標點呢？其實尋路的方法不難。一種簡單有效的方法就是回溯法。如 果我們從一個點出發，那么這個點周圍肯定有若干條路，只要有一條路存在，我們就一直走下去，直到發現沒有路走為止；要是發現路走不下去了怎么辦，那就只好 回頭了，我們只能從剩下的選項中繼續選擇一條路，繼續嘗試。如果很不幸，所有的嘗試都結束了，還是沒有發現目標節點，那只能說明，我們真的無路可走。a）首先，我們用矩陣表示地圖：其中1表示路，0表示沒有路，2表示終點，起始地點為（1,0）
#define MAX_NUMBER_LENGTH 6static 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}; / 記錄已走過的路 /
</pre> 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;}
</pre> 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;}
</pre> 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"); }}
</pre> 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; }}
</pre>
思考題：
上面的題目介紹了尋路的方法，介紹了如何遍歷所有的可能路徑。當然你可以從這所有的尋找路徑中尋找出一條最短的路徑。但是朋友們可以思考一下，有沒有一種方法，可以一下子尋找到最優的路徑呢？