隨筆檔案

   很早以前就在Gameres上學習過了A*的原理，但那時候也僅僅是看了遍原理，稍微了理解了下，當時雖然感覺A*并不復雜，但還是有幾個關鍵點沒能弄得清楚，比如更小G值的重新計算，趁著這幾天工作清閑，正好把最原始的A*算法給寫了一便

   寫A*原理的代碼，自然最好得有一個直觀的演示，A*走的是方格陣，GDI 的Setpixel函數正好可以滿足我畫方格的要求，利用最基本的VC8創建的一個小小的窗口，然后利用Setpixel在上面畫障礙畫尋找出來的路線，倒也是很合適

   創建的繪制區大小為400 * 400，也就是說一共有160000個象素點，其實僅僅演示初級的A*根本不需要這么大的區域，但是為了以后的優化代碼能夠顯示出速度上的差異，我便故意用了這么大的繪制區

   基本的思想也相當簡單，利用一個vector管理這160000個象素，也就是利用一維數組模擬二維數組的道理，然后單個vector元素里保存如下：win32的POINT結構變量一個，用來存儲繪制的點位置信息，枚舉類型一個，用來表示當前的結構處于什么狀態，指向本身結構的指針一個，用于指向父象素，整型index值，保存當前結構在16000個象素點的下標，G,H,F3個整型，（這3個整型用來干什么，我想知道A*的都一眼就看出了）

   具體怎么寫的我也不多說了，相信大家不會比我陌生，大概花了2天多一點的上班時間（斷斷續續寫的，期間還要處理其他工作上的事情），終于把最基本的A*算法給完成，利用最后找出來的路線點，能成功在客戶區繪制出繞過障礙的A-B之間的最短路徑了
 
  最基本的東西算是完成了，但是這也只是最基本的第一步，最重要的一點是什么呢？當然是優化，A*搜索對于非常多的方格的時候，時間上的消耗是非常大的，所以算法就這一個，而針對這個算法而產生的優化算法，網上真是數不勝數了，所以下面要做的一步重要工作，就是優化算法，提高搜索速度了，我事先準備好的160000個象素點，終于能夠派上他的用場了

從點POINT(2,2)搜尋到POINT(398,398)



如果對A*尋路基礎算法原理不清楚并且有興趣的朋友，可以去gameres上看一下這篇文章
http://data.gameres.com/message.asp?TopicID=25439