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

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

/* 
*       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 
*/  

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

我們可以把時光回到到達的前幾個步驟？我們?yōu)槭裁匆x方向朝下的點，而不選水平方向的點？原因不復(fù)雜，就是因為所有點中，當時我們要選的這個點和目標點之間距離最短。那么這中間，路徑的選擇有沒有發(fā)生改變呢？其實是有可能的，因為選路的過程本省就是一個pk的過程，我們所能做的就是尋找當時那個離目標最近的點而已，而這個點是時刻變化的，所以最后選出來的路應(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)該怎么修改呢？當然首先定義一個數(shù)據(jù)結(jié)構(gòu)？

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

然后呢，尋找到和目標點距離最短的那個點，

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

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

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 /){

  /* 更新列表 */  

  /* 尋找最近點 */  

};
}

總結(jié)：

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

（2）A*的目標是已知的

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