在前面的博客當(dāng)中，其實(shí)我們已經(jīng)討論過尋路的算法。不過，當(dāng)時(shí)的示例圖中，可選的路徑是唯一的。我們挑選一個(gè)算法，就是說要把這個(gè)唯一的路徑選出來，怎么選呢？當(dāng)時(shí)我們就是采用窮盡遞歸的算法。然而，今天的情形有點(diǎn)不太一樣了。在什么地方呢？那就是今天的路徑有n條，這條路徑都可以達(dá)到目的地，然而我們在挑選的過程中有一個(gè)要求，那就是挑選的路徑距離最短？有沒有什么辦法呢？

那么，這時(shí)候就要A算法就可以排上用場了。A算法和普通的算法有什么區(qū)別呢？我們可以用一個(gè)示例說明一下：

/* 
*       0  0  0  0  0 
*       1  1  1  1  1 
*       1  0  0  0  1   
*       1  0  0  0  1    
*       A  1  1  1  1 
*/  

這是一個(gè)5*5的數(shù)組。假設(shè)我們從array[1][0]出發(fā)，目標(biāo)為A點(diǎn)。我們發(fā)現(xiàn)，在圖中有兩種方法可以到達(dá)目的地，但是往下直達(dá)的方法最短。那么怎么找到這個(gè)最短的算法呢？朋友們可以好好思考一下。

我們可以把時(shí)光回到到達(dá)的前幾個(gè)步驟？我們?yōu)槭裁匆x方向朝下的點(diǎn)，而不選水平方向的點(diǎn)？原因不復(fù)雜，就是因?yàn)樗悬c(diǎn)中，當(dāng)時(shí)我們要選的這個(gè)點(diǎn)和目標(biāo)點(diǎn)之間距離最短。那么這中間，路徑的選擇有沒有發(fā)生改變呢？其實(shí)是有可能的，因?yàn)檫x路的過程本省就是一個(gè)pk的過程，我們所能做的就是尋找當(dāng)時(shí)那個(gè)離目標(biāo)最近的點(diǎn)而已，而這個(gè)點(diǎn)是時(shí)刻變化的，所以最后選出來的路應(yīng)該是這樣的。

/* 
*       0  0  0  0  0 
*       1  0  0  0  0 
*       1  0  0  0  0   
*       1  0  0  0  0    
*       A  0  0  0  0 
*/  

算法編程算法，應(yīng)該怎么修改呢？當(dāng)然首先定義一個(gè)數(shù)據(jù)結(jié)構(gòu)？

typedef struct _VALUE  
{  
    int x;  
    int y;  
}VALUE; 

然后呢，尋找到和目標(biāo)點(diǎn)距離最短的那個(gè)點(diǎn)，

int find_most_nearest_neigh(VALUE data[], int length, int x, int y)  
{  
    int index;  
    int number;  
    int current;  
    int median;  

    if(NULL == data || 0 == length)  
        return -1;  

    current = 0;  
    number = (int) sqrt((data[0].x - x) * (data[0].x - x)+ (data[0].y - y) *  (data[0].y - y));  

    for(index = 1; index < length; index ++){  
        median = (int) sqrt((data[index].x - x) * (data[index].x - x)+ (data[index].y - y) *  (data[index].y - y));  

        if(median < number){  
            number = median;  
            current = index;  
        }  
    }  

    return current;  
}  

尋找到這個(gè)點(diǎn)，一切都好辦了，那么現(xiàn)在我們就需要重新對data進(jìn)行處理，畢竟有些點(diǎn)需要彈出，還有一些新的點(diǎn)需要壓入處理的。

VALUE updata_data_for_queue(VALUE data, int length, int newLen)
{
int index;
int count;
int max;
VALUE pData;

if(NULL == data || 0 == length || NULL == newLen)  
    return NULL;  

max = length << 2;  
pData = (VALUE*)malloc(max * sizeof(VALUE));  
memset(pData, 0, max * sizeof(VALUE));  

count = 0;  
for(index = 0; index < length; index ++){  
    if(check_pos_valid(data[index].x, data[index].y - 1)){  
        pData[count].x = data[index].x;  
        pData[count].y = data[index].y -1;  
        count ++;  
    }  

    if(check_pos_valid(data[index].x -1, data[index].y)){  
        pData[count].x = data[index].x -1;  
        pData[count].y = data[index].y;  
        count ++;   
    }  

    if(check_pos_valid(data[index].x, data[index].y + 1)){  
        pData[count].x = data[index].x;  
        pData[count].y = data[index].y +1;  
        count ++;  
    }  

    if(check_pos_valid(data[index].x + 1, data[index].y)){  
        pData[count].x = data[index].x + 1;  
        pData[count].y = data[index].y;  
        count ++;   
    }  
}  

*newLen = count;  
return pData;  

}

有了上面的函數(shù)之后，那么find_path就十分簡單了。

void find_path(int x, int y)
{
while(/ 最短距離不為0 /){

  /* 更新列表 */  

  /* 尋找最近點(diǎn) */  

};
}

總結(jié)：

（1）A*的重點(diǎn)在于設(shè)計(jì)權(quán)重判斷函數(shù)，選擇最佳下一跳

（2）A*的目標(biāo)是已知的

（3）A*尤其適合于網(wǎng)格型的路徑查找