・メリット
スタートからゴールまでの最短の経路を導き出すことができます。
・デメリット
計算負荷が高いです、スタート地点とゴール地点が離れるほど処理が重くなります。
早速Wikipediaやネットのソースコードを見ながら作ったC++コードを以下に掲載します。
クラスメンバへの直接アクセスや、インデントが深い、処理に無駄がある等、
簡略化したらかなり悲惨なコードになり、公開をスゴくためらいましたが思い切って載せます。
キャラクターのAI処理や経路探査に興味がある人の助けになれれば幸いです、超救われます。
//-----------------------------------------------
// A*アルゴリズムによる経路地点クラス
//-----------------------------------------------
class CAStarPoint
{
public:
// コンストラクタ
CAStarPoint( void )
: m_vPos(D3DXVECTOR3(0.0f,0.0f,0.0f))
, m_eStatus(NONE)
, m_fG(0.0f)
, m_fH(0.0f)
, m_pParent(NULL)
{
}
// デストラクタ
~CAStarPoint( void ){}
// 親を設定しコストgを計算
void SetParent( CAStarPoint* _pParent )
{
D3DXVECTOR3 vVec = m_vPos - _pParent->m_vPos;
m_fG = _pParent->m_fG + D3DXVec3Length(&vVec);
m_pParent = _pParent;
}
// コストhを計算
void SetHCost( CAStarPoint* _pPoint )
{
D3DXVECTOR3 vVec =_pPoint->m_vPos - m_vPos;
m_fH = D3DXVec3Length(&vVec);
}
//private:
//===============================================
// 地点データ
//===============================================
D3DXVECTOR3 m_vPos; // 座標
//===============================================
// 経路データ
//===============================================
// 地点の状態定数
enum EStatus
{
NONE, // 設定なし
OPEN, // オープン
CLOSED // クローズ
};
EStatus m_eStatus; // 探査状態
std::list<CAStarPoint*> m_ltAdjacent; // 隣接ノードのリスト
float m_fG; // スタートノードからこの地点までの移動コストの推定値
float m_fH; // この地点からゴールノードまでの移動コストの推定値
CAStarPoint* m_pParent; // 親のポインタ
};
//-----------------------------------------------
// 経路を検索する 成功時はTRUE 失敗はFALSEを返す
//-----------------------------------------------
BOOL RouteSearch(
std::list<CAStarPoint*>& _ltOut, // 経路を格納するリスト
CAStarPoint* _pStart,// スタート地点
CAStarPoint* _pGoal)// ゴール地点
{
// 1. Open,Closeリストを用意
std::list<CAStarPoint*> ltOpen; // 計算中のノードが格納される
std::list<CAStarPoint*> ltClose; // 計算済みのノードが格納される
// 2. スタート地点をOpenリストに追加
_pStart->m_fG = 0.0f;
_pStart->SetHCost(_pGoal);
_pStart->m_eStatus = CAStarPoint::OPEN;
ltOpen.push_back(_pStart);
// 3. Openリストが空の時は探索失敗
while( ltOpen.size() > 0 )
{
// 4. Openリストの中から最短でゴールに行けるかもしれない地点pNを取得
CAStarPoint* pN = NULL;
{
float f1 = FLT_MAX;
std::list<CAStarPoint*>::iterator it = ltOpen.begin();
while( it != ltOpen.end() )
{
float f2 = (*it)->m_fG + (*it)->m_fH;
if ( f2 < f1 )
{
f1 = f2;
pN = (*it);
}
++it;
}
}
// 5. pNがゴール地点だった時は経路を作成して終了
if ( pN == _pGoal )
{
// ゴール地点の親の親の親の…とポインタをたどって行くと
// 親がNULLに設定されているスタート地点に戻ってこれる
CAStarPoint* pPoint = _pGoal;
while( pPoint )
{
_ltOut.push_front(pPoint);
pPoint = pPoint->m_pParent;
}
return TRUE;
}
// pNがゴールで地点ではなかったらクローズする
ltOpen.remove( pN );
pN->m_eStatus = CAStarPoint::CLOSED;
ltClose.push_back(pN);
// 6. pNに隣接する地点を調べる
std::list<CAStarPoint*>::iterator it = pN->m_ltAdjacent.begin();
while( it != pN->m_ltAdjacent.end() )
{
switch ( (*it)->m_eStatus )
{
case CAStarPoint::NONE:
// オープンする
(*it)->SetParent(pN);
(*it)->SetHCost(_pGoal);
(*it)->m_eStatus = CAStarPoint::OPEN;
ltOpen.push_back((*it));
break;
case CAStarPoint::OPEN:
{
// 隣接地点に設定されている親ポインタをpNに変更したら
// コストが少なくなる時はデータを更新する
D3DXVECTOR3 vVec = (*it)->m_vPos - pN->m_vPos;
float f = pN->m_fG + (*it)->m_fH + D3DXVec3Length(&vVec);
if ( f < ( (*it)->m_fG+(*it)->m_fH ) )
{
(*it)->SetParent(pN);
}
}
break;
case CAStarPoint::CLOSED:
{
// 隣接地点に設定されている親ポインタをpNに変更したら
// コストが少なくなる時はデータを更新し再度オープンする
D3DXVECTOR3 vVec = (*it)->m_vPos - pN->m_vPos;
float f = pN->m_fG + (*it)->m_fH + D3DXVec3Length(&vVec);
if ( f < ( (*it)->m_fG+(*it)->m_fH ) )
{
(*it)->SetParent(pN);
ltClose.remove( (*it) );
(*it)->m_eStatus = CAStarPoint::OPEN;
ltOpen.push_back((*it));
}
}
break;
}
++it;
} // end while
} // end while
return FALSE;
}
以上がプログラムになります。
経路地点クラスに座標をセットし、隣接ノードをつなぎ合わせた後、RouteSearch()にスタート地点とゴール地点を渡せば、第１引数のリストに経路が格納される作りになっています。
※ブラウザでの見易さ重視のため全角空白が多用されています、コピペする場合は注意してください。
PR
[1回]
COMMENT