隨筆檔案

   很早以前就在Gameres上學(xué)習(xí)過(guò)了A*的原理，但那時(shí)候也僅僅是看了遍原理，稍微了理解了下，當(dāng)時(shí)雖然感覺(jué)A*并不復(fù)雜，但還是有幾個(gè)關(guān)鍵點(diǎn)沒(méi)能弄得清楚，比如更小G值的重新計(jì)算，趁著這幾天工作清閑，正好把最原始的A*算法給寫(xiě)了一便

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

   創(chuàng)建的繪制區(qū)大小為400 * 400，也就是說(shuō)一共有160000個(gè)象素點(diǎn)，其實(shí)僅僅演示初級(jí)的A*根本不需要這么大的區(qū)域，但是為了以后的優(yōu)化代碼能夠顯示出速度上的差異，我便故意用了這么大的繪制區(qū)

   基本的思想也相當(dāng)簡(jiǎn)單，利用一個(gè)vector管理這160000個(gè)象素，也就是利用一維數(shù)組模擬二維數(shù)組的道理，然后單個(gè)vector元素里保存如下：win32的POINT結(jié)構(gòu)變量一個(gè)，用來(lái)存儲(chǔ)繪制的點(diǎn)位置信息，枚舉類型一個(gè)，用來(lái)表示當(dāng)前的結(jié)構(gòu)處于什么狀態(tài)，指向本身結(jié)構(gòu)的指針一個(gè)，用于指向父象素，整型index值，保存當(dāng)前結(jié)構(gòu)在16000個(gè)象素點(diǎn)的下標(biāo)，G,H,F3個(gè)整型，（這3個(gè)整型用來(lái)干什么，我想知道A*的都一眼就看出了）

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

從點(diǎn)POINT(2,2)搜尋到POINT(398,398)



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