電腦遊戲製作開發設計論壇

[avatar996]

來源文章網址：http://tw.myblog.yahoo.com/mmogc3d-mmogc3d
撰寫人：勇者大人


最近準備開始做３Ｄ地圖上的人物移動時，就去找出以前寫的路徑搜尋程式碼，
然後使用前稍微再測試一下看看，發現，怎麼執行結果怪怪的。。。
仔細檢查許久後，確定真的有ｂｕｇ啦～
原來是。。。以前曾有稍微改過，但是沒有經過仔細的測試。。。
難怪會遺留下ｂｕｇ。。。真是的。。。
不過，現在已經除掉嚕。。。也經過詳細的檢查了。

此路徑搜尋演算法是採用漩渦式的探測，每次尋路時都盡量向終點移動，
每移動一格，都會將移動路徑用數字紀錄在一個虛擬地圖內。
（此虛擬地圖可以自行設定大小，能決定尋路的遠近喔）
若是遇到死路，則開始從走過的路倒退，直到找到新路徑出現。
若是已找到的路徑超過５１２格，則判定為無路，不再搜尋。
若是虛擬地圖設太小而終點太遠，則判定為無路，不再搜尋。
所以將虛擬地圖設大，可以找到更遠的終點，
但是也更花搜尋時間和虛擬地圖記憶體。

若是順利找到了終點，則開始進行路線最佳化。
最佳化原理是，用路線的每一格編號來進行判斷，編號越大的，
有可能會是最短路線。（但不保證是）
例如現在這格編號是１，然後再開始搜尋該鄰近８格，
如果編號大於１，則先紀錄起來，直到鄰近８格都檢查過。。。
假設如果最後找到最大的編號是１０，則會將路線的２～９編號格剃除，
而路線編號就會是１，１０，１１，１２，１３。。。

我這樣說明可能不清楚，大家也很難懂吧，那請多包涵了～


這裡有路徑搜尋程式碼可以下載：
http://avatar996.myweb.hinet.net/AV_PathTest-20071224.zip


若是有興趣的話，可以研究看看喔！
這並非是最好的路徑搜尋演算法，只能算是最容易實現的演算法。
而搜尋效能還不錯喔～　我以前做的動作ＲＰＧ南俠展昭痞子龍就是用該演算法，
非常好用，人物移動搜尋路徑時完全不會太慢。