李錦俊(mybios)的blog

游戲開發 C++ Cocos2d-x OpenGL DirectX 數學計算機圖形學 SQL Server

C++博客 :: 首頁 :: 聯系 :: 聚合

:: 管理

86 Posts :: 0 Stories :: 370 Comments :: 0 Trackbacks

公告

QQ:30743734
EMain:mybios@qq.com

常用鏈接

留言簿(16)

我參與的團隊

隨筆分類(94)

隨筆檔案(86)

收藏夾(4)

高手BLOG(4)

編程網站

CodeGuru
GameDev.net
OGRE 3D
SourceForge.net
The Code Project
VCer.net
VC知識庫
打開視界技術社區

友情鏈接

中文愛百科
可信賴的中文百科全書。

搜索

積分與排名

積分 - 370171
排名 - 67

閱讀排行榜

評論排行榜

【轉貼】A*算法的泛型抽象實現

#ifndef?__ASTAR_SERACH_ALGO_H__

#define ?__ASTAR_SERACH_ALGO_H__

#include? < Algorithm >

????

namespace ?fredazsq

{????

namespace ?linghuye

{????

????

/**/ /* ************************************************

**?尋路節點

************************************************ */

template < typename?TNodeLocation >

struct ?TAXNode

{????

???? float ???????G,?F;

????TNodeLocation??pos;

????TAXNode * ???pParentNode;

???? bool ???????bClosed;???????? // ?使用狀態表明節點處于開放或關閉列表.

????

???? bool ? operator < ( const ?TAXNode & ?node)? const

???? {????

???????? return ?pos? < ?node.pos;

????} ????

} ;????

????

/**/ /* *****************************************************************************

**??封裝A*尋路算法

*******************************************************************************

**??作為棋盤信息提供類TField必須實現下列函數:

**??1.?bool?IsFieldThrough(TNodeLocation?pos)?const;????????????????????????????????????在?pos?位置是否為空,可通行.

**??2.?float?EvaluateStepCost(TNodeLocation?posFrom,?TNodeLocation?posTo,?TNodeLocation?posLastStep)?const;????????計算pos1,pos2到單步代價.

**??3.?float?EvaluateProbableCost(TNodeLocation?posFrom,?TNodeLocation?posTo)?const;????計算pos1,pos2到估算代價.

**??4.?TNodeLocation*?QueryNeiborLocations(TNodeLocation?pos,?int&?nNodeCount);?const????詢問pos的相鄰可通節點集

*******************************************************************************

**??TNodeLocation,節點位置

**??1.支持<,==,=操作符,如int.

*******************************************************************************

**??0.?初始化時傳入棋盤信息提供類的實例引用.

**??1.?使用主函數SearchPath進行搜索,使用QueryResultPath取得結果.

***************************************************************************** */

template < class ?TField,? class ?TNodeLocation >

struct ?CAStar2DAlgo

{????

public :

????typedef?std::vector < TNodeLocation > ????CResultPath;

????typedef?TAXNode < TNodeLocation > ????????CAXNode;

????typedef?std:: set < CAXNode > ????????????CAXNodeSet;

????

???? struct ?CAXNodePriorityQueue???????????? // ?優先隊列?

???? {????

????????std::vector < CAXNode *> ?m_heap;

????????

???????? static ? bool ?AXNodeCostSortPred(CAXNode * ?n1,?CAXNode * ?n2)

???????? {????

???????????? return ?(n1 -> G? + ?n1 -> F)? > ?(n2 -> G? + ?n2 -> F);

????????}

????????

???????? void ?push(CAXNode * ?pNode)

???????? {

????????????m_heap.push_back(pNode);

????????????std::push_heap(m_heap.begin(),?m_heap.end(),? & CAXNodePriorityQueue::AXNodeCostSortPred);

????????}

????????

????????CAXNode * ?pop()

???????? {????

????????????CAXNode * ?pNode? = ?m_heap.front();

????????????std::pop_heap(m_heap.begin(),?m_heap.end(),? & CAXNodePriorityQueue::AXNodeCostSortPred);

????????????m_heap.pop_back();

???????????? return ?pNode;

????????}

????????

???????? bool ?empty()

???????? {

???????????? return ?m_heap.empty();

????????}

????????

???????? void ?resort(CAXNode * ?pNode)

???????? {????

????????????std::vector < CAXNode *> ::iterator?it? = ?std::find(m_heap.begin(),?m_heap.end(),?pNode);

????????????std::push_heap(m_heap.begin(),?it,? & CAXNodePriorityQueue::AXNodeCostSortPred);

????????}

????????

???????? void ?clear()

???????? {

????????????m_heap.clear();

????????}

????} ;????

????????

public :????

???? const ?TField & ?m_field;

????TNodeLocation??m_posTarget;

????CAXNode * ?m_ptrTargetNode;???????????????????? // ?Result?Node

????????

????CAXNodeSet?m_setNodes;???????????????????????? // ?All?nodes?in?use?

????CAXNodePriorityQueue?m_queOpenNodes;???????? // ?Cost?sorted?open?list

????????

public :????

????CAStar2DAlgo( const ?TField & ?field)?:?m_field(field),?m_ptrTargetNode(NULL)

???? {????????

????} ????

????????

???? ~ CAStar2DAlgo()

???? {????

????} ????

????????

???? void ?Reset()

???? {????

????????m_setNodes.clear();

????????m_queOpenNodes.clear();

????????m_ptrTargetNode? = ?NULL;

????} ????

????????

public :????

????inline?CAXNode * ?ClaimNode(TNodeLocation?pos,?CAXNode * ?pParentNode? = ?NULL)

???? {????

????????CAXNode?node;

????????node.pos? = ?pos;

????????node.F? = ?node.G? = ? 0 ;

????????node.bClosed? = ? false ;???? // ?Default?is?open

????????node.pParentNode? = ?pParentNode;

???????? return ? & ( * m_setNodes.insert(node).first);

????} ????

????????

???? bool ?SearchPath(TNodeLocation?posStart,?TNodeLocation?posTarget)

???? {????

????????CAXNode * ?pCurNode;

????????m_posTarget? = ?posTarget;

????????

???????? // ?Add?start?node?into?open?list

????????CAXNode * ?pStartNode? = ?ClaimNode(posStart);

????????m_queOpenNodes.push(pStartNode);

????????

???????? while ( ! m_queOpenNodes.empty())

???????? {????

???????????? // ?Pick?lowest?cost?node

????????????pCurNode? = ?m_queOpenNodes.pop();

????????????

???????????? // ?Check?search?target

???????????? if (pCurNode -> pos? == ?m_posTarget)

???????????? {

????????????????m_ptrTargetNode? = ?pCurNode;

???????????????? return ? true ;

????????????}

????????????

???????????? // ?Switch?node?from?OpenList?to?CloseList

????????????pCurNode -> bClosed? = ? true ;

????????????ProcessNeighborNodes(pCurNode);

????????}

????????

???????? return ? false ;

????}

????????

???? void ?ProcessNeighborNodes(CAXNode * ?pCurNode)

???? {????

????????CAXNode?tempNode;

???????? int ?nNodeCount? = ? 0 ;

????????TNodeLocation * ?pLocs? = ?m_field.QueryNeiborLocations(pCurNode -> pos,?nNodeCount);

????????TNodeLocation?posLastStep? = ?pCurNode -> pParentNode ? ?pCurNode -> pParentNode -> pos?:?pCurNode -> pos;

????????

???????? // ?For?each?neibors?

???????? for ( int ?i? = ? 0 ;?i? < ?nNodeCount;? ++ i)

???????? {????

????????????tempNode.pos? = ?pLocs[i];

???????????? if (m_field.IsFieldThrough(tempNode.pos))

???????????? {????

????????????????CAXNodeSet::iterator?it? = ?m_setNodes.find(tempNode);

???????????????? if (it? == ?m_setNodes.end())

???????????????? {????

????????????????????CAXNode * ?pNewNode? = ?ClaimNode(tempNode.pos,?pCurNode);

????????????????????pNewNode -> G? = ?pCurNode -> G? + ?m_field.EvaluateStepCost(pCurNode -> pos,?pNewNode -> pos,?posLastStep);

????????????????????pNewNode -> F? = ?m_field.EvaluateProbableCost(pNewNode -> pos,?m_posTarget);

????????????????????m_queOpenNodes.push(pNewNode);

????????????????} ????

???????????????? else ? if ( ! it -> bClosed)

???????????????? {????

????????????????????CAXNode & ?node? = ? * it;

???????????????????? float ?G? = ?pCurNode -> G? + ?m_field.EvaluateStepCost(pCurNode -> pos,?node.pos,?posLastStep);

???????????????????? if (G? < ?node.G)

???????????????????? {????

????????????????????????node.G? = ?G;

????????????????????????node.pParentNode? = ?pCurNode;

????????????????????????m_queOpenNodes.resort( & node);

????????????????????}

????????????????}

????????????}

????????}

????}

????

???? /**/ /* *****************************************************************

????**??取回最終結果

????***************************************************************** */

???? bool ?QueryResultPath(CResultPath & ?path)

???? {????

???????? if ( ! m_ptrTargetNode)? return ? false ;

????????

????????CAXNode * ?pNode? = ?m_ptrTargetNode;

???????? while (pNode)

???????? {????

????????????path.push_back(pNode -> pos);

????????????pNode? = ?pNode -> pParentNode;

????????}

???????? return ? true ;

????}

} ;

/**/ /* ******************************************************************************

**??TNodeLocation,節點位置

**??1.支持<,==?操作符號.

******************************************************************************* */

template < typename?TNodeLocation >

struct ?CShisenFieldImpl

{????

????TNodeLocation * ?QueryNeiborLocations(TNodeLocation?pos,? int & ?nRetCount)? const

???? {????

???????? static ? const ? int ?dy[ 4 ]? = ? {? 1 ,? 0 ,? 0 ,? - 1 ?} ;

???????? static ?TNodeLocation?posNeibors[ 4 ];???? // ?Single?thread

????????????????

????????nRetCount? = ? 4 ;

???????? for ( int ?i? = ? 0 ;?i? < ? 4 ;?i ++ )

???????? {

????????????posNeibors[i].x? = ?pos.x? + ?dx[i];

????????????posNeibors[i].y? = ?pos.y? + ?dy[i];

????????}

???????? return ?posNeibors;

????}

????

???? float ?EvaluateStepCost(TNodeLocation?posFrom,?TNodeLocation?posTo,?TNodeLocation?posLast)? const

???? {????

???????? if (((posFrom.x - posTo.x)?? && ??(posLast.y - posFrom.y))?? || ??

???????????((posFrom.y - posTo.y)?? && ??(posLast.x - posFrom.x)))

???????? {????

???????????? return ? 100 ;

????????}

???????? else ? return ? 1 ;

????}

????

???? float ?EvaluateProbableCost(TNodeLocation?pos1,?TNodeLocation?pos2)? const

???? {

???????? return ? 0 ;

????}

????

/**/ /* ????平滑優化

????float?EvaluateStepCost(MY_POSITION?posFrom,?MY_POSITION?posTo,?MY_POSITION?posLast)?const

????{????

????????int?cx1?=?posTo.x?-?posFrom.x;

????????int?cy1?=?posTo.y?-?posFrom.y;

????????int?cx2?=?posFrom.x?-?posLast.x;

????????int?cy2?=?posFrom.y?-?posLast.y;

????????return?((cx1?==?cx2??&&??cy1?==?cy2)??0?:?10)?+?((cx1??&&??cy1)??14?:?10);

????}

*/ ????

} ;????

????

/**/ /* ******************************************************************************

**??最小路徑

****************************************************************************** */

template < typename?TNodeLocation >

struct ?CShortestPathFieldImpl

{????

????TNodeLocation * ?QueryNeiborLocations(TNodeLocation?pos,? int & ?nRetCount)? const

???? {????

???????? static ? const ? int ?dx[ 4 ]? = ? {? 0 ,? - 1 ,? 1 ,?? 0 ?} ;

???????? static ? const ? int ?dy[ 4 ]? = ? {? 1 ,?? 0 ,? 0 ,? - 1 ?} ;

???????? static ?TNodeLocation?posNeibors[ 4 ];???? // ?Single?thread

????????????????

????????nRetCount? = ? 4 ;

???????? for ( int ?i? = ? 0 ;?i? < ? 4 ;?i ++ )

???????? {

????????????posNeibors[i].x? = ?pos.x? + ?dx[i];

????????????posNeibors[i].y? = ?pos.y? + ?dy[i];

????????}

???????? return ?posNeibors;

????}

????

???? float ?EvaluateStepCost(TNodeLocation?posFrom,?TNodeLocation?posTo,?TNodeLocation?posLast)? const

???? {????

???????? return ? 1 ;

????}

????

???? float ?EvaluateProbableCost(TNodeLocation?pos1,?TNodeLocation?pos2)? const

???? {

???????? return ? 0 ;

????}

} ;

/**/ /* ******************************************************************************

**??最小路徑

****************************************************************************** */

template < typename?TNodeLocation >

struct ?CGamePathFieldImpl

{????

????TNodeLocation * ?QueryNeiborLocations(TNodeLocation?pos,? int & ?nRetCount)? const

???? {????

???????? static ? const ? int ?dx[ 8 ]? = ? {? - 1 ,? 0 ,? 1 ,? - 1 ,? 1 ,? - 1 ,?? 0 ,?? 1 ?} ;

???????? static ? const ? int ?dy[ 8 ]? = ? {?? 1 ,? 1 ,? 1 ,?? 0 ,? 0 ,? - 1 ,? - 1 ,? - 1 ?} ;

???????? static ?MY_POSITION?posNeibors[ 8 ];

????????

????????nRetCount? = ? 8 ;

???????? for ( int ?i? = ? 0 ;?i? < ? 8 ;?i ++ )

???????? {

????????????posNeibors[i].x? = ?pos.x? + ?dx[i];

????????????posNeibors[i].y? = ?pos.y? + ?dy[i];

????????}

???????? return ?posNeibors;

????}

????

???? float ?EvaluateStepCost(TNodeLocation?posFrom,?TNodeLocation?posTo,?TNodeLocation?posLast)? const

???? {????

???????? if (posFrom.x - posTo.x?? && ??posFrom.y - posTo.y)

???????? {

???????????? return ? 14 ;

????????}

???????? else ? return ? 10 ;

????}

????

???? float ?EvaluateProbableCost(TNodeLocation?posFrom,?TNodeLocation?posTo)? const

???? {

???????? return ?(abs(posFrom.x - posTo.x)? + ?abs(posFrom.y - posTo.y))? * ? 10 ;

????}

} ;

} // ?namespace?linghuye

} // ?namespace?fredazsq

#endif // __FIELD_SERACH_ALGO_H__

posted on 2006-11-19 01:40 李錦俊(mybios) 閱讀(1455) 評論(0) 編輯收藏引用所屬分類: 數學、幾何和圖形學

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 【轉貼】Ogre的官僚主義批判【轉貼】使用非2次方冪的圖像紋理的問題【轉貼】高級碰撞檢測技術【轉貼】A算法的泛型抽象實現【轉貼】A尋路算法（簡明教程）【轉貼】幾個物體的移動補間插值函數【原創】《3D數學基礎：圖形與游戲開發》讀書筆記1 【原創】計算Bezier曲線的線性插值點的函數【轉貼】了解凹凸映射Bump Map技術的內幕【轉貼】OCTREE 教程

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

李錦俊(mybios)的blog

公告

常用鏈接

留言簿(16)

我參與的團隊

隨筆分類(94)

隨筆檔案(86)

收藏夾(4)

編程網站

友情鏈接

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜