Lameije Corporation

ナビゲーションデータの作成

概要

ナビゲーションメッシュによる3D環境内の移動で使用するナビゲーションデータ作成の一例です。

ナビゲーションデータとは？

ナビゲーションデータとは、ナビゲーションメッシュによる3D環境内の移動でも説明したように、キャラクターが移動可能なセルの位置と、セル同士の接続を保存したデータです。

ナビゲーションデータの元となるナビゲーションメッシュの作成ルールなどについては、ナビゲーションメッシュによる3D環境内の移動を参照してください。

メッシュの構造

ナビゲーションデータを作成するには、元となるモデル（以下メッシュ）を読み込んでその情報を取得しますが、実際に情報を取得する前に、メッシュの構造を理解しておくと良いと思いますので、その構造を図1に示しました。（DirectX の ID3DXMesh を前提で記述しています）

ナビゲーションデータの作成では、隣接性データを使用するとセル同士の接続が比較的簡単に調べられるので、隣接性データについても記述します。

(図1)

頂点バッファには、メッシュに含まれる全ての頂点が保存されています。ナビゲーションデータの作成では頂点座標しか使用しませんが、頂点には頂点座標以外にも法線やUV値などが含まれている事もあるので、頂点バッファを読み進めるには、1つの頂点に必要なバイト数を調べて、そのバイト数ずつずらしながら読み進めます。頂点に格納される情報の順番には決まりがあり、必ず最初に座標(x,y,z)が格納され、続いて法線、UVというように続きます（実際には他にも多くの情報が格納できます)。

インデックスバッファには、面（ポリゴン）を構成する頂点バッファのインデックスが、1つの面に対して3つずつ格納されています。インデックス1つはWORD型なので、sizeof(WORD) * 3 バイトずらせば、次のポリゴンのインデックス情報に移動できます。

隣接性データには、ポリゴンに隣接するポリゴンのインデックスが、1つの面に対して3つずつ格納されています。隣接ポリゴンのインデックス1つはDWORD型なので、sizeof(DWORD) * 3 バイトずらせば、次のポリゴンの隣接情報に移動できます。また、隣接ポリゴンのインデックスが 0xffff の場合は、隣接ポリゴンがない事になります。隣接性データはメッシュのインデックスに基づいて、ID3DXMesh::GenerateAdjacency で生成されます。

メッシュの構造は以上のようになっていますので、これを踏まえた上でメッシュからナビゲーションデータを作成してみます。

セル情報読み込み

まずはじめに、ナビゲーションデータの元となるメッシュを読み込み、全てのポリゴンの位置をセル情報として保存します。セル情報は、セルを管理するクラスなどを作成して管理すると良いと思います。

//ポリゴンの頂点情報
struct TRIANGLE{
    D3DXVECTOR3 m_avec3Vertex[3];        //ポリゴンを構成する頂点
};

//ナビゲーションメッシュのセルを管理するクラス
class CNavigationCell
{
    private:
        TRIANGLE m_triCell;                      //セルの頂点情報
        CNavigationCell* m_alpLinkCell[3];       //リンク先のセルのポインタ
        DWORD m_adwLinkCellIndex[3];             //リンク先のセルのインデックス

    public:
        //コンストラクタ
        CNavigationCell(void);
        //デストラクタ
        ~CNavigationCell(void) {}

        //セルを初期化
        void Initialize(D3DXVECTOR3* p_lpvec3V0, D3DXVECTOR3* p_lpvec3V1, D3DXVECTOR3* p_lpvec3V2);
        //リンクを設定
        void SetLink(int p_iLineIndex, DWORD p_dwLinkCellIndex, CNavigationCell* p_lpLinkCell);
        //セルの頂点情報を取得
        const TRIANGLE* GetCellVertices(void){ return &m_triCell; }
        //リンク先セルのインデックスを取得
        DWORD GetLinkCellIndex(int p_iLineIndex){ return m_adwLinkCellIndex[p_iLineIndex]; }
};

//------------------------------------------------------------------------------
//コンストラクタ
//------------------------------------------------------------------------------
CNavigationCell::CNavigationCell(void)
{
    for(int i = 0; i <= 2; ++i){
        m_alpLinkCell[i] = NULL;
        m_adwLinkCellIndex[i] = 0xffffffff;
    }
}

//------------------------------------------------------------------------------
//セルを初期化
//
//引数
//    p_lpvec3V0        [in]セルを構成するポリゴンの頂点0
//    p_lpvec3V1        [in]セルを構成するポリゴンの頂点1
//    p_lpvec3V2        [in]セルを構成するポリゴンの頂点2
//
//戻り値
//    なし
//------------------------------------------------------------------------------
void CNavigationCell::Initialize(D3DXVECTOR3* p_lpvec3V0,
                                    D3DXVECTOR3* p_lpvec3V1,
                                    D3DXVECTOR3* p_lpvec3V2)
{
    m_triCell.m_avec3Vertex[0] = *p_lpvec3V0;
    m_triCell.m_avec3Vertex[1] = *p_lpvec3V1;
    m_triCell.m_avec3Vertex[2] = *p_lpvec3V2;
}

//------------------------------------------------------------------------------
//リンクを設定
//
//引数
//    p_iLineIndex        [in]隣接セルを設定するこのセルの辺のインデックス(0～2)
//    p_dwLinkCellIndex   [in]接続先隣接セルのインデックス
//    p_lpLinkCell        [in]接続先隣接セルのCNavigationCellクラスのアドレス
//
//戻り値
//    なし
//------------------------------------------------------------------------------
void CNavigationCell::SetLink(int p_iLineIndex, DWORD p_dwLinkCellIndex, CNavigationCell* p_lpLinkCell)
{
    m_alpLinkCell[p_iLineIndex] = p_lpLinkCell;
    m_adwLinkCellIndex[p_iLineIndex] = p_dwLinkCellIndex;
}

クラスを作成したら、ナビゲーションメッシュの頂点バッファとインデックスバッファをロックし、それらの情報を基にセルを初期化します。

CNavigationCell** alpNaviCell;    //ナビゲーションメッシュのセル情報リスト
ID3DXMesh* lpNaviMesh;            //ナビゲーションメッシュ
DWORD dwNumFaces;                 //面の数
DWORD dwBytesPerVertex;           //1頂点に必要なバイト数
BYTE* lpbyVB;                     //頂点バッファ
WORD* lpwIB;                      //インデックスバッファ
D3DXVECTOR3* alpvec3Vertex[3];    //面の頂点情報

//情報取得
dwNumFaces = lpNaviMesh->GetNumFaces();
dwBytesPerVertex = lpNaviMesh->GetNumBytesPerVertex();

//セル情報保存用のメモリ確保
alpNaviCell = new CNavigationCell*[dwNumFaces];

//バッファのロック
lpNaviMesh->LockVertexBuffer(D3DLOCK_READONLY, reinterpret_cast<VOID**>(&lpbyVB));
lpNaviMesh->LockIndexBuffer(D3DLOCK_READONLY, reinterpret_cast<VOID**>(&lpwIB));

//セル情報読み込み
for(DWORD dwFace = 0; dwFace < dwNumFaces; ++dwFace){
    alpNaviCell[dwFace] = new CNavigationCell();

    //頂点の格納されているアドレスを取得
    alpvec3Vertex[0] =
        reinterpret_cast<D3DXVECTOR3*>(lpbyVB + (lpwIB[dwFace * 3 + 0] * dwBytesPerVertex));
    alpvec3Vertex[1] =
        reinterpret_cast<D3DXVECTOR3*>(lpbyVB + (lpwIB[dwFace * 3 + 1] * dwBytesPerVertex));
    alpvec3Vertex[2] =
        reinterpret_cast<D3DXVECTOR3*>(lpbyVB + (lpwIB[dwFace * 3 + 2] * dwBytesPerVertex));

    //セルを初期化
    alpNaviCell[dwFace]->Initialize(alpvec3Vertex[0], alpvec3Vertex[1], alpvec3Vertex[2]);
}

//バッファをアンロック
lpNaviMesh->UnlockIndexBuffer();
lpNaviMesh->UnlockVertexBuffer();

セル同士の接続を設定

全てのセル情報を読み込んだら、次にセル同士の接続を調べて設定します。 DirectXではポリゴンの隣接情報を取得することができるので、この情報を利用するとセル同士の接続は簡単に調べられます。

DWORD* adwAdjacency;            //隣接性データ
DWORD dwAdjacencyIndex;         //隣接ポリゴンのインデックス

//隣接性データに必要なメモリを確保
adwAdjacency = new DWORD[dwNumFaces * 3]; ……… ①

//隣接性データ取得
lpNaviMesh->GenerateAdjacency(0.010f, adwAdjacency); ……… ②

//セルの接続を設定
for(DWORD dwFace = 0; dwFace < dwNumFaces; ++dwFace){
    for(int iLine = 0; iLine <= 2; ++iLine){
        //隣接ポリゴンのインデックスを取得
        dwAdjacencyIndex = adwAdjacency[dwFace * 3 + iLine];

        if(dwAdjacencyIndex != 0xffff){
            //隣接ポリゴンが存在する
            alpNaviCell[dwFace]->SetLink(iLine, dwAdjacencyIndex, alpNaviCell[dwAdjacencyIndex]);
        }
    }
}

//隣接性データのメモリを解放
delete[] adwAdjacency;

隣接性データを取得するには、必要なバッファをあらかじめ確保しておかなければなりません。隣接性データはポリゴン1つに対して sizeof(DWORD) * 3 必要ですので、それを踏まえて①のようにバッファを確保します。

隣接性データのバッファを確保したら、②のように隣接性データを取得しますが、この例の 0.010f の意味は、頂点同士の距離がここで指定した値未満であれば、隣接頂点としてみなすという数値になります。ですので 0.0f を指定すると、完全に一致している頂点の場合のみ隣接頂点とみなされるようになります。

隣接性データが取得出来たら、あとは全てのポリゴンの隣接ポリゴンを調べ、セルの接続を設定します。

以上全ての処理が終了すると、alpNaviCellにのセル情報とセル同士の接続情報が完成したことになります。

ナビゲーションデータの保存

せっかくナビゲーションデータが完成したので、これをファイルに保存して、ゲームではこのファイルをロードするだけで、ナビゲーションデータが出来上がるようにします。もちろん、ファイルの保存方法はこれでなくてはいけないという事はないので、これはほんの一例です。この例では次のようなファイルフォーマットで保存をしてみます（エラー処理は省いています）。

const DWORD NVD_HEADER = 'N' | ('V' << 8) | ('D' << 16) | (' ' << 24);
const WORD NVD_VERSION = 100;
HANDLE hFile;                      //ファイルハンドル
DWORD dwBytesWrite;                //書き込まれたバイト数
const TRIANGLE* lpTriangle;        //セルの頂点情報
DWORD dwAdjacencyIndex;            //隣接セルのインデックス

//ファイルオープン
hFile = CreateFile("navidata.nvd", GENERIC_WRITE, 0, NULL,
                    CREATE_ALWAYS, FILE_ATTRIBUTE_ARCHIVE, NULL);

//ヘッダとバージョンを書き込み
WriteFile(hFile, &NVD_HEADER, sizeof(DWORD), &dwBytesWrite, NULL);
WriteFile(hFile, &NVD_VERSION, sizeof(WORD), &dwBytesWrite, NULL);

//セル数を書き込み
WriteFile(hFile, &dwNumFaces, sizeof(DWORD), &dwBytesWrite, NULL);

//セル情報書き込み
for(DWORD dwFace = 0; dwFace < dwNumFaces; ++dwFace){
    lpTriangle = alpNaviCell[dwFace]->GetCellVertices();

    //セルの頂点を書き込み
    for(int i = 0; i <= 2; ++i){
        WriteFile(hFile, &lpTriangle->m_avec3Vertex[i].x, sizeof(float), &dwBytesWrite, NULL);
        WriteFile(hFile, &lpTriangle->m_avec3Vertex[i].y, sizeof(float), &dwBytesWrite, NULL);
        WriteFile(hFile, &lpTriangle->m_avec3Vertex[i].z, sizeof(float), &dwBytesWrite, NULL);
    }

    //隣接セルのインデックスを書き込み
    for(int i = 0; i <= 2; ++i){
        dwAdjacencyIndex = alpNaviCell[dwFace]->GetLinkCellIndex(i);
        WriteFile(hFile, &dwAdjacencyIndex, sizeof(DWORD), &dwBytesWrite, NULL);
    }
}

//ファイルクローズ
CloseHandle(hFile);

ナビゲーションデータの読込

先ほどファイルに保存したナビゲーションデータのファイルをロードして、ナビゲーションデータを復元します（エラー処理は省いています）。

const DWORD NVD_HEADER = 'N' | ('V' << 8) | ('D' << 16) | (' ' << 24);
const WORD NVD_VERSION = 100;
HANDLE hFile;                      //ファイルハンドル
DWORD dwNvdHeader;                 //ナビゲーションデータファイルのヘッダ
WORD wNvdVersion;                  //ナビゲーションデータファイルのバージョン
DWORD dwBytesRead;                 //読み込まれたバイト数
DWORD dwNumFaces;                  //面の数
TRIANGLE Triangle;                 //セルの頂点情報
CNavigationCell** alpNaviCell;     //ナビゲーションメッシュのセル情報リスト

//ファイルオープン
hFile = CreateFile("navidata.nvd", GENERIC_READ, 0, NULL,
                    OPEN_EXISTING, FILE_ATTRIBUTE_ARCHIVE, NULL);

//ヘッダを読み込み
ReadFile(hFile, &dwNvdHeader, sizeof(DWORD), &dwBytesRead, NULL);
if(dwNvdHeader != NVD_HEADER){
    //知らないファイルなのでエラー
    //...
}

//バージョンを読み込み
ReadFile(hFile, &wNvdVersion, sizeof(WORD), &dwBytesRead, NULL);
if(wNvdVersion != NVD_VERSION){
    //知らないバージョンなのでエラー
    //...
}

//セル数を読み込み
ReadFile(hFile, &dwNumFaces, sizeof(DWORD), &dwBytesRead, NULL);

//セル情報保存用のメモリ確保
alpNaviCell = new CNavigationCell*[dwNumFaces];

//セル情報読み込み
for(DWORD dwFace = 0; dwFace < dwNumFaces; ++dwFace){
    alpNaviCell[dwFace] = new CNavigationCell();

    //セルの頂点を読み込み
    for(int i = 0; i <= 2; ++i){
        ReadFile(hFile, &Triangle.m_avec3Vertex[i].x, sizeof(float), &dwBytesRead, NULL);
        ReadFile(hFile, &Triangle.m_avec3Vertex[i].y, sizeof(float), &dwBytesRead, NULL);
        ReadFile(hFile, &Triangle.m_avec3Vertex[i].z, sizeof(float), &dwBytesRead, NULL);
    }
    alpNaviCell[dwFace]->Initialize(&Triangle.m_avec3Vertex[0],
                                    &Triangle.m_avec3Vertex[1],
                                    &Triangle.m_avec3Vertex[2]);

    //隣接セルのインデックスを読み込み
    for(int i = 0; i <= 2; ++i){
        ReadFile(hFile, &dwAdjacencyIndex, sizeof(DWORD), &dwBytesRead, NULL);
        if(dwAdjacencyIndex != 0xffffffff){
            alpNaviCell[dwFace]->SetLink(i, dwAdjacencyIndex, NULL);
        }
    }
}

//ファイルクローズ
CloseHandle(hFile);

//隣接情報を再構築
for(DWORD dwFace = 0; dwFace < dwNumFaces; ++dwFace){
    for(int i = 0; i <= 2; ++i){
        dwAdjacencyIndex = alpNaviCell[dwFace]->GetLinkCellIndex(i);
        if(dwAdjacencyIndex != 0xffffffff){
            alpNaviCell[dwFace]->SetLink(i, dwAdjacencyIndex, alpNaviCell[dwAdjacencyIndex]);
        }
    }
}

ナビゲーションデータファイルから情報を読み込む場合、隣接セルのインデックスを読み込んだ時にはまだリンク先セルのクラスが作成されていない場合があるので、とりあえずリンク先のポインタは NULL として保留しておき、全てのデータを読み込んだ後に、隣接情報を再構築しています。

もちろんこれは一例ですので、隣接セルのインデックスを読み込んだ時に、リンク先セルのクラスが既に作成されているようにするのも良いと思います。

最後に

ここでは、必要最低限のデータの生成しか行っていないので、実際にゲームで使用するにはこれ以外の付加情報が必要になる事もあると思います。

また、この例で作成したセルのクラスには、ナビゲーションメッシュに合わせてキャラクターを移動する際に利用できるメソッドが実装されていないので、実際にナビゲーションメッシュを利用してキャラクターを移動させるには、もう少しメソッドの追加などが必要です。

誤りなどを見つけましたら、ご連絡ください。

(文： 2008/8/6 ラメイジュ田中)

この文章は、予告なく改編される場合がございます。

この文章の無断での転用を禁止いたします。

このページへのリンクは大歓迎です。