A*在游戲尋路算法里使用很廣，可是感覺很多介紹它的文章故意讓人看不懂。
仔細看了看gamedev.net的一片文章(A* Pathfinding for Beginners
http://www.gamedev.net/reference/articles/article2003.asp
)，對A*更了解了一點，寫點東西記錄一下。
A*是一種啟發式的算法，所謂的"啟發式"，就是對每一個搜索的位置進行評估，也就是把找的位置離目標的距離當成找點的一個依據，然后猜測這個點是否最佳("啟發式"就是猜測)。
為了找到最佳的那個點
可以規定：
G = 從起點，沿著產生的路徑，移動到網格上指定方格的距離。
H = 從網格上那個方格移動到終點B的預估移動距離。
F = G + H
F最小的點可以認為是該選的點。
引用一下原文的翻譯：
我們令水平或者垂直移動的耗費為10，對角線方向耗費為14。我們取這些值是因為沿對角線的距離是沿水平或垂直移動耗費的的根號2（別怕），或者約1.414倍。為了簡化，我們用10和14近似。比例基本正確，同時我們避免了求根運算和小數。
既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節點的G值，然后依照它相對父節點是對角線方向或者直角方向(非對角線)，分別增加14和10。例子中這個方法的需求會變得更多，因為我們從起點方格以外獲取了不止一個方格。
H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數量總和，忽略對角線方向。然后把結果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區數，在那里你不能沿對角線方向穿過街區。很重要的一點，我們忽略了一切障礙物。這是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發式的原因。想知道更多？你可以在這里找到方程和額外的注解。
第一步搜索的結果可以在下面的圖表中看到。F,G和H的評分被寫在每個方格里。正如在緊挨起始格右側的方格所表示的，F被打印在左上角，G在左下角，H則在右下角。
引用一下原文的翻譯：
我們做如下操作開始搜索：
???1，從點A開始，并且把它作為待處理點存入一個“開啟列表”。開啟列表就像一張購物清單。盡管現在列表里只有一個元素，但以后就會多起來。你的路徑可能會通過它包含的方格，也可能不會?；旧?，這是一個待檢查方格的列表。
???2，尋找起點周圍所有可到達或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格。也把他們加入開啟列表。為所有這些方格保存點A作為“父方格”。當我們想描述路徑的時候，父方格的資料是十分重要的。后面會解釋它的具體用途。
???3，從開啟列表中刪除點A，把它加入到一個“關閉列表”，列表中保存所有不需要再次檢查的方格。
為了繼續搜索，我們簡單的從開啟列表中選擇F值最低的方格。然后，對選中的方格做如下處理：
???4，把它從開啟列表中刪除，然后添加到關閉列表中。
???5，檢查所有相鄰格子。跳過那些已經在關閉列表中的或者不可通過的(有墻，水的地形，或者其他無法通過的地形)，把他們添加進開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節點。
???6，如果某個相鄰格已經在開啟列表里了，檢查現在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話，G值是否會更低一些。如果不是，那就什么都不做。
??????另一方面，如果新的G值更低，那就把相鄰方格的父節點改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個方格）。最后，重新計算F和G的值。如果這看起來不夠清晰，你可以看下面的圖示。
這樣就可以找到最佳路徑了。
在gameres上看見一個問題帖：
什么時候該用?Object?object;
什么時候該用?Object?*object;
?????????????object=new?Object();
感覺看起來沒什么區別，其實不一樣：前一個是棧對象，后一個是堆對象。
引用一下別人對棧對象、堆對象的解釋：
棧對象的優勢是在適當的時候自動生成，又在適當的時候自動銷毀，不需要程序員操心；而且棧對象的創建速度一般較堆對象快，因為分配堆對象時，會調用?operator?new操作，operator?new會采用某種內存空間搜索算法，而該搜索過程可能是很費時間的，產生棧對象則沒有這么麻煩，它僅僅需要移動棧頂指針就可以了。但是要注意的是，通常?？臻g容量比較小，一般是1MB～2MB，所以體積比較大的對象不適合在棧中分配。特別要注意遞歸函數中最好不要使用棧對象，因為隨著遞歸調用深度的增加，所需的?？臻g也會線性增加，當所需棧空間不夠時，便會導致棧溢出，這樣就會產生運行時錯誤。
堆對象，其產生時刻和銷毀時刻都要程序員精確定義，也就是說，程序員對堆對象的生命具有完全的控制權。我們常常需要這樣的對象，比如，我們需要創建一個對象，能夠被多個函數所訪問，但是又不想使其成為全局的，那么這個時候創建一個堆對象無疑是良好的選擇，然后在各個函數之間傳遞這個堆對象的指針，便可以實現對該對象的共享。另外，相比于?？臻g，堆的容量要大得多。實際上，當物理內存不夠時，如果這時還需要生成新的堆對象，通常不會產生運行時錯誤，而是系統會使用虛擬內存來擴展實際的物理內存。
所以
當你知道你要使用的類型擁有準確數量時使用
Object?object;當你不知道你要創建的類型有多少個時使用
Object?*object;
?????????????????????????????????????? object=new?Object();
四元數常?？梢栽?D的書上看到。
但我的那本3D圖形學書上，在沒講四元數是干什么的之前，就列了幾張紙的公式，
大概因為自己還在上高中，不知道的太多，看了半天沒看懂。。。
終于，在gameres上看到了某強人翻譯的一個“4元數寶典 ”（原文是日本人寫的。。。），感覺很好，分享下。
★旋轉篇：
我將說明使用了四元數（si?yuan?shu,?quaternion）的旋轉的操作步驟
（１）四元數的虛部，實部和寫法
所謂四元數，就是把4個實數組合起來的東西。
4個元素中，一個是實部，其余3個是虛部。
比如，叫做Q的四元數，實部t而虛部是x,y,z構成，則像下面這樣寫。
Q?=?(t;?x,?y,?z)?
又，使用向量?V=(x,y,z)，
Q?=?(t;?V)??
也可以這么寫。
正規地用虛數單位i,j,k的寫法的話，
Q?=?t?+?xi?+?yj?+?zk?
也這樣寫，不過，我不大使用
（２）四元數之間的乘法
虛數單位之間的乘法?
ii?=?-1,?ij?=?-ji?=?k?(其他的組合也是循環地以下同文)?
有這么一種規則。（我總覺得，這就像是向量積（外積），對吧）?
用這個規則一點點地計算很麻煩，所以請用像下面這樣的公式計算。
A?=?(a;?U)?
B?=?(b;?V)?
AB?=?(ab?-?U·V;?aV?+?bU?+?U×V)
不過，“U·V”是內積，「U×V」是外積的意思。
注意：一般AB<>BA所以乘法的左右要注意！
（3）3次元的坐標的四元數表示
如要將某坐標(x,y,z)用四元數表示，
P?=?(0;?x,?y,?z)?
則要這么寫。
?
另外，即使實部是零以外的值，下文的結果也一樣。用零的話省事所以我推薦。
（４）旋轉的四元數表示
以原點為旋轉中心，旋轉的軸是(α,?β,?γ)
（但?α^2?+?β^2?+?γ^2?=?1），?
（右手系的坐標定義的話，望向向量(α,?β,?γ)的前進方向反時針地）?
轉θ角的旋轉，用四元數表示就是，
Q?=?(cos(θ/2);?α?sin(θ/2),?β?sin(θ/2),?γ?sin(θ/2))?
R?=?(cos(θ/2);?-α?sin(θ/2),?-β?sin(θ/2),?-γ?sin(θ/2))?
(另外R?叫?Q?的共軛四元數。）?
那么，如要實行旋轉，
則?R?P?Q?=?(0;?答案)?
請像這樣三明治式地計算。這個值的虛部就是旋轉之后的點的坐標值。
?（另外，實部應該為零。請驗算看看）?
例子代碼
///?Quaternion.cpp?
///?(C)?Toru?Nakata,?toru-nakata@aist.go.jp?
///?2004?Dec?29?
??
#include?<math.h>?
#include?<iostream.h>?
??
///?Define?Data?type?
typedef?struct?
{?
??????????????double?t;?//?real-component?
??????????????double?x;?//?x-component?
??????????????double?y;?//?y-component?
??????????????double?z;?//?z-component?
}?quaternion;?
??
//// Bill 注：Kakezan 在日語里是 “乘法”的意思
quaternion?Kakezan(quaternion?left,?quaternion?right)?
{?
??????????????quaternion?ans;?
??????????????double?d1,?d2,?d3,?d4;?
??
??????????????d1?=??left.t?*?right.t;?
??????????????d2?=?-left.x?*?right.x;?
??????????????d3?=?-left.y?*?right.y;?
??????????????d4?=?-left.z?*?right.z;?
??????????????ans.t?=?d1+?d2+?d3+?d4;?
??
??????????????d1?=??left.t?*?right.x;?
??????????????d2?=??right.t?*?left.x;?
??????????????d3?=??left.y?*?right.z;?
??????????????d4?=?-left.z?*?right.y;?
??????????????ans.x?=??d1+?d2+?d3+?d4;?
??
??????????????d1?=??left.t?*?right.y;?
??????????????d2?=??right.t?*?left.y;?
??????????????d3?=??left.z?*?right.x;?
??????????????d4?=?-left.x?*?right.z;?
??????????????ans.y?=??d1+?d2+?d3+?d4;?
??
??????????????d1?=??left.t?*?right.z;?
??????????????d2?=??right.t?*?left.z;?
??????????????d3?=??left.x?*?right.y;?
??????????????d4?=?-left.y?*?right.x;?
??????????????ans.z?=??d1+?d2+?d3+?d4;?
??????????????
??????????????return?ans;?
}?
??
////?Make?Rotational?quaternion?
quaternion?MakeRotationalQuaternion(double?radian,?double?AxisX,?double?AxisY,?double?AxisZ)?
{?
??????????????quaternion?ans;?
??????????????double?norm;?
??????????????double?ccc,?sss;?
??????????????
??????????????ans.t?=?ans.x?=?ans.y?=?ans.z?=?0.0;?
??
??????????????norm?=?AxisX?*??AxisX?+??AxisY?*??AxisY?+??AxisZ?*??AxisZ;?
??????????????if(norm?<=?0.0)?return?ans;?
??
??????????????norm?=?1.0?/?sqrt(norm);?
??????????????AxisX?*=?norm;?
??????????????AxisY?*=?norm;?
??????????????AxisZ?*=?norm;?
??
??????????????ccc?=?cos(0.5?*?radian);?
??????????????sss?=?sin(0.5?*?radian);?
??
??????????????ans.t?=?ccc;?
??????????????ans.x?=?sss?*?AxisX;?
??????????????ans.y?=?sss?*?AxisY;?
??????????????ans.z?=?sss?*?AxisZ;?
??
??????????????return?ans;?
}?
??
////?Put?XYZ?into??quaternion?
quaternion?PutXYZToQuaternion(double?PosX,?double?PosY,?double?PosZ)?
{?
??????????????quaternion?ans;?
??
??????????????ans.t?=?0.0;?
??????????????ans.x?=?PosX;?
??????????????ans.y?=?PosY;?
??????????????ans.z?=?PosZ;?
??
??????????????return?ans;?
}?
??
/////?main?
int?main()?
{?
??????????????double?px,?py,?pz;?
??????????????double?ax,?ay,?az,?th;?
??????????????quaternion?ppp,?qqq,?rrr;?
??
??????????????cout?<<?"Point?Position?(x,?y,?z)?"?<<?endl;?
??????????????cout?<<?"??x?=?";?
??????????????cin?>>?px;?
??????????????cout?<<?"??y?=?";?
??????????????cin?>>?py;?
??????????????cout?<<?"??z?=?";?
??????????????cin?>>?pz;?
??????????????ppp?=?PutXYZToQuaternion(px,?py,?pz);?
??
??????????????while(1)?{?
????????????????????????????cout?<<?"\nRotation?Degree???(Enter?0?to?Quit)?"?<<?endl;?
????????????????????????????cout?<<?"??angle?=?";?
????????????????????????????cin?>>?th;?
????????????????????????????if(th?==?0.0)?break;?
??
????????????????????????????cout?<<?"Rotation?Axis?Direction???(x,?y,?z)?"?<<?endl;?
????????????????????????????cout?<<?"??x?=?";?
????????????????????????????cin?>>?ax;?
????????????????????????????cout?<<?"??y?=?";?
????????????????????????????cin?>>?ay;?
????????????????????????????cout?<<?"??z?=?";?
????????????????????????????cin?>>?az;?
??
??
????????????????????????????th?*=?3.1415926535897932384626433832795?/?180.0;?///?Degree?->?radian;?
??
????????????????????????????qqq?=?MakeRotationalQuaternion(th,?ax,?ay,?az);?
????????????????????????????rrr?=?MakeRotationalQuaternion(-th,?ax,?ay,?az);?
??
????????????????????????????ppp?=?Kakezan(rrr,?ppp);?
????????????????????????????ppp?=?Kakezan(ppp,?qqq);?
??
????????????????????????????cout?<<?"\nAnser?X?=?"?<<?ppp.x?
??????????????????????????????????????????<<??"\n??????Y?=?"?<<?ppp.y?
??????????????????????????????????????????<<??"\n??????Z?=?"?<<?ppp.z?<<?endl;?
??
??????????????}?
??
??????????????return?0;?
}??
http://staff.aist.go.jp/toru-nakata/quaternion.html
http://bbs.gameres.com/showthread.asp?threadid=73511
在gameres上看到的，感覺很創意。。。
實現方法
準備兩個攝像機，對準同一點，交替渲染紅和綠的畫面，帶上紅綠眼鏡
即可觀察到4D的場景了！
大家可以看看那這里，有源代碼(C++&D3d實現的)
http://bbs.gameres.com/showthread.asp?threadid=73818
一個4D的例子
這周六數學競賽，周日物理競賽。
感覺暑假后對那些沖量矩啊，角動量啊，惠斯通電橋啊，無線網格啊，的感覺都好模糊了。。。
不過，個人認為重在享受這個過程，有沒有拿到省一等獎是次要的。
祝自己好運。。。