はじめに

ゲームコーディングシリーズは全3冊編成であり、本書で完成します。

vol.1とvol.2ではDirectXの運用を扱っています。最初の2冊とは異なりvol.3である本書では、ある程度DirectXから独立し、純粋なアルゴリズムを解説するように努めました。ですので、DirectX以外のSDK例えばCg、OpenGL、あるいはWin32APIのみを使用したゲームアプリケーションにももちろん有効な知識となると思います。また、特に基本アルゴリズムはゲーム以外にも用途があるとも思います。

ゲームコーディングシリーズは当初、1年程度で完成させるつもりでしたが結局2年近くかかってしまいました。

この理由は、書いているうちに「これは書かなくてはならないんじゃないだうか？」という事柄がどんどん増えていったことがまず第1にあります。それから、実は本書のサンプルプログラム自体は早い時期に完成していたのですが、他のプロジェクトを優先させたため、原稿作成がほとんど進まない状態が長く続いたのも完成を長引かせた原因です。

さて、本書の特徴を述べたいと思います。

ゲームコーディングシリーズに限らず、解説には努めて出力確認つまりサンプルプログラムを添えるのが筆者のスタイルです。もちろん本書にもほとんどの項目にサンプルをつけています。基本アルゴリズム編の本質部分のコードは、これ以上ないというレベルまで最適化を行ったコードなので、そのまま使用できると思います。逆に手を加えるとパフォーマンスが落ちる可能性があります。またA*やクアッド・オクトトリーサンプルではそれぞれの本質アルゴリズムをフレームワークから分離しクラスにまとめているので再利用し易いようにもなっています。

それから、本書の目的はDirectXの運用が目的ではないので、今回はある程度自由にコーディングさせてもらいました。vol.1やvol.2では一つのサンプル500行以内というコンセプトがありましたが、本書にはありません。不用なクラスもあるでしょうが、注目すべき場所はその都度示しているので、自分にとって不用な部分は無視すればいいだけの話です。今は必要じゃなくとも、いつか役立つ可能性もあると思い、あえて残しておきました。

なお、予定では本書でゲーム状態同期を解説するつもりでいましたが、考えてみると「はじめての3Dゲーム開発」でかなりのページを割いて解説していることに気付き、同じことを書くことになるので除きました。

サンプルをビルドするコンパイラですが、特に決まったコンパイラはありません。DirecrXにシビアに特化しているわけではないので、VC6でもVC2005でも、あるいはマイクロソフト以外のメーカーでも大丈夫です。もちろん読者側でそれぞれの設定を行える場合に限ります。Direct3Dを使用しているサンプルのコードはDirectXSDK9.0C系のコードです。コンパイラーがVisualC++6.0の場合、DirectXSDKは9.0cSummer2003あたりのものを使用してください。

サンプルプロジェクトは、VC2002,2003,2005の3つのバージョンを付けますがソース自体は全く同じものです。

最後に、vol.1から本シリーズを買ってくださっている方もいらっしゃると思います。ようやく最後のvol.3を出すことができました。遅れてしまったことについてお詫びを申し上げるとともに、無事にシリーズを完成できたことにお礼申し上げます。ありがとうございました。

筆者は今後当分の間、本業に戻ります。数年後に書籍ではない形での“成果物”を皆さんにお見せすることになると思います。　では！

汎用アルゴリズム

ここで解説している汎用アルゴリズムは基本アルゴリズムとも言われます。“基本”という言葉から“簡単”というイメージが浮かぶかもしれません。

しかし多くの場合、全く逆です。

コンピューターになんらかの仕事をさせる場合、仕事の種類に依存ぜず、多くの機会で登場するロジックであるという意味での“基本”であって、仕組みが“単純”ということではありません。また、最初の章に書いているからと言って、簡単なのであろうと思うのは危険です。

たしかに基本アルゴリズムは、コンピューターの誕生と同時に生み出された基本的な動作で、初期の頃に自然発生的に誕生した簡単なアルゴリズムも中にはあります。しかし、それだけではもちろんなく、その歴史が長いため、今まで多くの研究者がより高速なものを追求し、非常に難解なロジックで構成されているアルゴリズムも少なくありません。それらは我々がちょっと思いついたようなロジックとは違います。簡単なのは本当に初期の頃の誰もが考え付くようなロジックを使用したアルゴリズムだけです。

なぜこのようなことを述べるかというと、簡単なアルゴリズムと思い込んで、いざ理解しようとするとその極限まで洗練されたアルゴリズムをイメージしきれず、後の章に行く前に気落ち、あるいは挫折してしまう可能性が考えられるからです。

本編はむしろこの本の中で一番難解な章と言ってもいいくらいです。ですので、心して読破してくださるようお願いします。

また、この汎用アルゴリズム編が難しいと感じるのであれば後に進んでください。後の章のほうが簡単であることが多いのですから。

少なくとも私にとって、基本アルゴリズムは・・・

ベクトル解析よりも、

自前Xファイルの設計よりも、

LightWaveのオブジェクト・シーン→Xファイル変換よりも、

COMサーバーの実装よりも、

スキンアニメーションの実装よりも、

A*アルゴリズムよりも、

クックトランスシェーダーを実装するよりも、

・・・“はるかに”難しいです。

一見、高度かつ先進的な技術でも、難しく感じさせているのは実は“仕様の情報収集”作業であって、ロジックそのものではないことが少なくありません。“製作者側が持っている情報”を知らなければどんな天才でも分かるはずがなく、現実はまさに、それらの情報が伝わりにくいのが現状です。（そのために本書および類書があるわけですが）

それに対し基本アルゴリズムは、for文やif文と言った誰でも知っている概念のみで構成されているのも関らす、理解できないという状況が多くあります。ある意味、センス・能力が最も問われる分野です。本書がどれほど解説しても、何10ページを説明に割いたとしても、自分自身で考え、頭の中に独自のイメージを描かなければ、それ以上理解が進まないという瞬間は必ず来ます。こればっかりはどうしようもありません。

特にソートはこれ以上ソフィスティケートできないというところまで極度に精錬されきっているので、馬鹿にしているとかなりの高確率で返り討ちに遭うでしょう。

さて、最初の2つ、「リンクド・リスト」と「木」は「抽象データ構造」と呼ばれるように、アルゴリズムでありながら、データ構造でもありますから、基本アルゴリズムの中のさらに基本アルゴリズムとでも言えるでしょう。もちろん“アルゴリズム”なわけですから、マシン語に1体1的に対応するもっとも単純なデータ構造である配列とは異なり、プログラマーの工夫により実装できる（しなくてはならない）何らかの仕組みを持っています。

ソートやパターンマッチングに比べると単純で、この2つが理解できないということはあまり無いと思います。

まずはその2つから開始しましょう。

１章　リンクドリスト

同じ型のなんらかのデータないしはオブジェクトは配列にしますよね。

配列を使っていて「要素数を途中で増やせたらなぁ…」と思ったことは誰しもあるのではないでしょうか？

リンクド・リスト（Linked List）ならそれが出来ます。

また、配列内に新しいデータを挿入する場合、場所を空けるために前後の要素全てをいっせいに移動しなければならないことに非効率さを感じたことはないでしょうか？

これもリンクドリストなら効率的に出来ます。

リンクド・リストは抽象データ構造のなかでは最も単純なものです。その構造は1次元なので線形リストとも呼ばれ、（多次元の階層を持つリンクドリストもありますが除きます）、リンクドリストを解説する場合、配列と対比するとその仕組みや利点が明確になります。

配列の構造は誰もが分かっている単純なものでしょう。配列は単に宣言さえすればよく、型定義や事前準備は要りませんよね。また、要素へのアクセスは単に添え字で一発アクセスが可能です。

例え次のように。

INT a[10];

a[3]=12;

一方リンクドリストにおいて“要素”は“ノード”と呼ばれますが、まずはノードの構造体を定義しなくてはなりません。各ノードにどのようなデータを持たせるかはもちろん自由ですが、必ず次のノードへのポインターを持たせます。このポインターを“リンク”と呼び、これがリンクドリストと呼ばれる所以です。そうすることにより、任意のノードから他の全てのノードにアクセスあるいはノードのトラバース（走査）が可能になります。

配列の例と同様に要素（ノード）が10個のリンクドリストを機能させるためには次のようになります。

struct NODE

{

NODE* pNext;←次のノードへのポインタ

INT Data;←なんらかのデータ

};

NODE* a[10];

for(i=0;i<10;i++)

{

a[i]=new NODE;

a[i]->pNext=a[i+1];

}

a[3]->Data=12;

図1-1

リンクドリストにおいて各ノードは必ずしもメモリに順番どおりに配置されません。通常は全ての要素が隙間無くメモリに配置されることはほとんどありません。（あるタイミングにのみリンクドリストを初期化した瞬間は隙間無く配置される可能性は高いですが）それは、添え字で連番的にアクセスできないということを意味します。任意のノードにたどり着くまで順番にリンクを辿っていかなければなりません。（トラバースしなければなりません）。

図1-2

図1-3

リンクドリストの各ノードは通常バラバラにメモリ上に存在しますが、論理配置は連続しています。各ノードのメモリ上の位置に関らず1つの“リスト”としてまとめることがリンクドリストなのですから当然です。

各ノードを異なるタイミングで生成し、メモリ上の位置がまったく連続していなくてもリンクによって繋げることにより、任意のノードからリスト内の全てのノードにたどり着くことができます。言い方を変えれば異なるタイミングで生成できるので、ノードの追加が可能なのです。

さて、冒頭で既に述べましたが、リンクドリストの特徴として一般的に言われているのは次の２点です。

�@　動的にそのサイズを増減させることができる。配列では要素数を途中で増やすことはできませんが、リンクドリストは何時でもノードを増やしたり減らしたり自由に出来ます。

�A　ノード（配列で言うところの要素）を“挿入”するコストが安い（処理速度が速い）。

しかし、この“優れている”と言われる特徴の両方について大きな落とし穴があります。

というのは、�@は配列でもできるのでリンクドリストの特徴とは言えませんし、そして�Aも一見して素晴らしく見えますが、ある落とし穴があるからです。

ここであえて（筆者的な）結論を先に述べると、ゲームにおいてリンクドリストの使いどころはあまりありません。処理時間がどうでもいいのなら別ですが。リンクドリストは単に任意のノードにアクセスするのにすら時間がかかります。速いとされている挿入（及び削除）も“削除するためにはトラバースが必要”であり、挿入・削除の瞬間だけの実行速度の速さに騙されてはいけないのです。例えば先頭から7番目のノードを削除する場合、先頭から7回リンクを辿って初めて削除できるのです。

もっとも配列における挿入処理で場所を空けるために馬鹿正直に前後の要素全てをゴッソリ移動したりしたら、交換の処理コストは高いですからトラバースの分を考えてもリンクドリストのほうがあるかに高速になります。そんなことをしなくても配列での挿入にはこれを回避するトリックがあります。

そして動的なメモリ確保ですが、配列でも最初に十分なポインター型配列を作っておき、必要になったら必要な分だけメモリ確保すればいいだけのことです。ポインター分のメモリも固定的に確保しておきたくないというのであれば、ポインターのポインターを定義し、動的確保することだって出来ます。

配列における動的なメモリ確保、要素の追加、および挿入トリックについては2章で実際のコードを示します。

では、リンクドリストに関る処理を実際のコードで見ていきましょう。

1-1 ノードの追加（生成）

サンプルプロジェクト名　リンクドリスト（生成・追加）

ノードの生成は、ノードをリストに追加することでもあります。リンクドリストで最も基本的で重要な操作でしょう。

まずは、ノードを定義しなくてはなりません。ノードの定義はたとえば次のようにします。

struct NODE

{

INT Index;

NODE* pNext;

};

単純です。NODE* pNextとして必ず次のモードへのポインター（リンク）を持たせてさえすれば、あとは自由に好きなだけデータを持たせます。ここでは簡単のためIndexというINT型データを1個のみ定義していますが、言うまでもなくどのようなデータを何個でも持たせることができます。通常はそのような形になるでしょう。

ノードの型がどのようなものか分かったところで、実際にこのノードをどのように生成するのか解説しましょう。

まず、リストの先頭と尻尾（最初のノードと最後尾のノード）のポインターだけは事前に生成しておきます。準備としてはこれだけです。

サンプルでは、先頭をHead、尻尾をTailとしています。

NODE* Head = new NODE;

NODE* Tail = new NODE;

厳密に図示するとしたら次のようになりますが、混乱するので細かく図示しません。（そもそも、本当に細かく書こうとしたらキリが無いので）

図1-4

シンプルに図示すると次のようになります。

図1-5

Head->pNext=Tail;

Tail->pNext=NULL;

図1-6

追加と挿入は操作としては同じことです。ただ、挿入はすでにインスタンスが生成されている場合が考えられるので全くの同義ではありません。まずインスタンスをnewにより生成しリストに加えます（繋げます）。加える場所はどこでも構いませんが、通常は先頭の前後か尻尾の前後に繋げます。ここでは尻尾に繋げています。

Tail->pNext = new NODE;

図1-7

この時点で生成したインスタンスは“一瞬”だけ尻尾（Tail）の次のノード（リンク先）になっています。つまり、新たなノードが尻尾より後ろに位置してしまっています。

これを修正するために、その次の行ですぐに尻尾を本来の尻尾の位置に戻します。

Tail=Tail->pNext;

図1-8

以上で、ノードの生成及び追加にかかる解説は終了です。参考と確認のために、サンプルを眺めてください。

リンクドリスト（生成・追加）サンプルコード

#include <conio.h>

#include <stdio.h>

#include <windows.h>

//型定義

struct NODE

{

INT Index;

NODE* pNext;

};

//

//VOID main()

//エントリーポイント

VOID main()

{

INT Amount=0;

NODE* pTmp;

NODE* Head = new NODE;

NODE* Tail = new NODE;

Head->pNext=Tail;

Tail->pNext=NULL;

//生成と表示

while(!kbhit())

{

printf("\n追加生成：y 終了：n \n");

CHAR c=getch();

if(c=='y')

{

//生成

Tail->pNext = new NODE;

Tail->Index=Amount;

Tail=Tail->pNext;

Tail->pNext=NULL;

Amount++;

//表示

pTmp=Head->pNext;

while( pTmp->pNext != NULL)

{

printf("%d ",pTmp->Index);

pTmp=pTmp->pNext;

}

}

//終了

else if(c=='n')

{

break;

}

}

//全て開放

NODE* pTmp2;

pTmp2=Head->pNext;

pTmp=Head;

while( pTmp->pNext != NULL)

{

delete pTmp;

pTmp = pTmp2;

pTmp2 = pTmp2->pNext;

}

}

このサンプルは、ユーザーにキー入力を促し、yキーで新たなノードを生成し、リストに加えます。

確認として、Indexメンバに連番を入れてそれを表示するようにしていますが、生成の本質部分はわずかなコードです。またノードの総数を保持するAmountという変数を使用しています。通常はこのような変数が必要になります。

HeadとTailは機能としてはダミーのインスタンスです。

図1−9

ちなみに、尻尾を用意しなくてもリンクをつなげていくことができます。もっと言えば先頭すらなくてもリンクを作っていくことはできます。ただ、その場合、リストの操作に関るコードは数行多くなってしまい実行速度に影響します。また、サンプルではHeadとTailのインスタンスを生成していますが、インスタンスではなく単なるポインターであっても機能させることができます。この場合もやはりコードは数行多くなってしまいます。

1-2 ノードの挿入

サンプルプロジェクト名　リンクドリスト（挿入）

挿入と追加は似ていますが、ここで言う挿入とはリストの最後尾ではなくリストの途中に差し込むことです。単にどこでもいいから追加するというものではなく、データの順番等で意図した場所に差し込みたい場合に行う操作です。

単なる配列内に挿入する場合、前後の要素を一斉に移動して、挿入する地点を空けなければなりません。

しかし、リンクドリストにおいて挿入は非常に簡単に行えます。しかもリストの長さに依存せず、“挿入処理自体”は常に一定の実行速度で操作が完了するという特徴があります。（ただし、挿入するためには事前にトラバースが必要）

今、あるリストの途中でノードP1とノードP2が隣どうしであるなら、リンクは次のようになっています。

P1->Next=P2;

図1-10

そこにノードXを挿入する場合、

図1-11

まずP1のリンク先をXに繋ぎ換えます。

P1->Next=X;

図1-12

そして、XのリンクをP2に繋げます。

X->Next=P2;

図1-13

図1-14

これで完了です。これだけを見ると画期的とも言えるシンプルさです。

サンプルでは全く同じことを行っています。ノードX自体をnewする処理と、Indexに値を入れる処理で多少コードが多くなっていますが、挿入の原理は全く同じものです。

図1−15

先頭からn番目のノードと、その次のノードの間に挿入します。pTmpが指すノードとpTmp2が指すノードの間に生成したノードを入れています。

pTmp=Head;

for(i=0;i<n;i++)

{

pTmp=pTmp->pNext;

}

pTmp2=pTmp->pNext;

pTmp->pNext=new NODE;

pTmp->pNext->Index=Index;

pTmp->pNext->pNext=pTmp2;

事前のトラバースや本質ではない部分を省くと分かり易いと思います。

pTmp2=pTmp->pNext;

pTmp->pNext=new NODE;

pTmp->pNext->pNext=pTmp2;

いちおうサンプルの全コードを掲載しておきますので眺めてください。

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <windows.h>

//型定義

struct NODE

{

INT Index;

NODE* pNext;

NODE()

{

Index=0;

pNext=NULL;

}

};

//

//VOID main()

//エントリーポイント

VOID main()

{

INT Amount=0;

INT i=0;

INT n=0;

INT Index=0;

CHAR String[10]={NULL};

NODE* pTmp;

NODE* pTmp2;

NODE* Head = new NODE;

NODE* Tail = new NODE;

Head->pNext=Tail;

Tail->pNext=NULL;

//初期状態リストの生成と表示

//とりあえず10個生成。（ヘッドとテイルをあわせると12個）

while(Amount<10)

{

Tail->pNext = new NODE;

Tail->Index=Amount;

Tail=Tail->pNext;

printf("%3d ",Amount);

Amount++;

}

Tail->pNext=NULL;

//挿入と表示

while(!kbhit())

{

printf("\n追加:a 終了:e \n");

CHAR c=getch();

//ヘッドから数えてn番目に挿入

switch(c)

{

case 'a':

printf("そのノードの値を指定してください\n");

gets(String);

Index=atoi(String);

printf("どこに挿入しますか？（ゼロから）\n");

gets(String);

n=atoi(String);

pTmp=Head;

for(i=0;i<n;i++)

{

pTmp=pTmp->pNext;

}

pTmp2=pTmp->pNext;

pTmp->pNext=new NODE;

pTmp->pNext->Index=Index;

pTmp->pNext->pNext=pTmp2;

Amount++;

break;

//終了

case 'e':

goto out;

break;

}

//表示

{

//ノードが保持するインデックス

pTmp=Head->pNext;

while( pTmp->pNext != NULL)

{

printf("%3d ",pTmp->Index);

pTmp=pTmp->pNext;

}

}

}

out:

//全て開放

pTmp2=Head->pNext;

pTmp=Head;

while( pTmp->pNext != NULL)

{

delete pTmp;

pTmp = pTmp2;

pTmp2 = pTmp2->pNext;

}

}

1-3 ノードの削除

サンプルプロジェクト名　リンクドリスト（削除）

削除は挿入の逆操作であり、仕組みは挿入と同じです。つまり、削除自体はリンクを繋ぎ換えるだけという簡単なものです。

今、あるリストの途中でノードP1とノードP2の間にノードXがあるなら、リンクは次のようになっています。

P1->Next=X;

X->Next=P2;

図1-16

ノードXを削除する場合、まず

P1のリンク先をP2に繋ぎ換えます。これでXはリストから外され、もはやリンクを辿ってもXを見つけることはできなくなります。

P1->Next=P2;

図1-17

リストからの削除はこれだけです。挿入よりも1工程少なく1ステップで実現できます。

ただ、通常はメモリからも削除するので

delete X;

を実行します。

図1-18

これで完璧です。

サンプルでは次のコードにより、先頭からn番目のノードの次のノードを削除しています。

pTmp=Head;

for(i=0;i<n;i++)

{

pTmp=pTmp->pNext;

}

pTmp2=pTmp->pNext;

pTmp->pNext = pTmp->pNext->pNext;

delete pTmp2;

Amount--;

前半のループが終了した時点で、pTmpは先頭からn番目のノードを指しています。

その次のノードをpTmp2に一旦保存しておきます。

pTmp2=pTmp->pNext;

保存する理由は、その下の行でリストから外すともはやトラバースでポインタを見つけることができなくなるためです。

n番目のノードのリンク先を一個飛ばして張ります。つまり間のノード（Tmp2が指すノード）をリストから外します。

pTmp->pNext = pTmp->pNext->pNext;

保存しておいた（Tmp2が指すノードの）アドレスによりメモリからも削除します。

delete pTmp2;

いちおうサンプルの全コードを掲載しておきますので眺めてください。

図1−19

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <windows.h>

//型定義

struct NODE

{

INT Index;

NODE* pNext;

};

//

//VOID main()

//エントリーポイント

VOID main()

{

INT Amount=0;

INT i=0;

INT n=0;

INT Index=0;

CHAR String[10]={NULL};

NODE* pTmp;

NODE* pTmp2;

NODE* Head = new NODE;

NODE* Tail = new NODE;

Head->pNext=Tail;

Tail->pNext=NULL;

//初期状態リストの生成と表示

//とりあえず10個生成。（ヘッドとテイルをあわせると12個）

while(Amount<10)

{

Tail->pNext = new NODE;

Tail->Index=Amount;

Tail=Tail->pNext;

//printf("%3d ",Amount);

Amount++;

}

Tail->pNext=NULL;

//追加と表示

while(!kbhit())

{

//表示

{

//ノードが保持するインデックス

pTmp=Head->pNext;

while( pTmp->pNext != NULL)

{

printf("%3d ",pTmp->Index);

pTmp=pTmp->pNext;

}

}

printf("\n削除:d 終了:e \n");

CHAR c=getch();

//ヘッドから数えてn番目を削除

switch(c)

{

case 'd':

printf("何番目を削除しますか？\n");

gets(String);

n=atoi(String);

pTmp=Head;

for(i=0;i<n;i++)

{

pTmp=pTmp->pNext;

}

pTmp2=pTmp->pNext;

pTmp->pNext = pTmp->pNext->pNext;

delete pTmp2;

Amount--;

break;

//終了

case 'e':

goto out;

break;

}

}

out:

//全て開放

pTmp2=Head->pNext;

pTmp=Head;

while( pTmp->pNext != NULL)

{

delete pTmp;

pTmp = pTmp2;

pTmp2 = pTmp2->pNext;

}

}

1-4 ノードの全削除（メモリの開放）

そのリンクドリスト自体が不用になった場合は、そのリンクドリストが占めているメモリを全て開放するわけですが、これは次のコードのようになります。

NODE* pTmp, pTmp2;

//全て開放

pTmp=Head;

pTmp2=Head->pNext;

while( pTmp->pNext != NULL)

{

delete pTmp;

pTmp = pTmp2;

pTmp2 = pTmp2->pNext;

}

先頭から順に、個々のノードを開放しながらリンクを順に辿っていけばいいでしょう。

備考

次ノードへのリンクだけではなく“直前の”ノードへのリンクも持たせると逆方向トラバースが可能になります。（当たり前ですね）。また、仕様によっては尻尾のリンク先を先頭にするとよりコードがシンプルになるケースがあります。

ちなみに前者は双方向リンクドリスト、後者は循環リンクドリストと呼ばれています。

本章のリストは片方向リンクドリストと呼ばれるものです。片方向リンクドリストが理解できれば、それらのリンクドリストをコーディングすることは簡単であると言えます。

2章 同様の操作をポインターと配列だけで行う

「配列は構造上動的にその要素の数を増減できません。しかし、配列を使って動的に要素の数を増減させることは出来ます。」

本章の最初で書いたように、特にリンクドリストを使用しなくとも、複数オブジェクトのメモリ確保を伴う動的追加、および高速な挿入・削除は可能であり、むしろリンクドリストよりも高速です。

まずは動的確保について、2つの方法を解説します。

1つ目の方法は、十分な数のポインター配列を用意しておくというもので、筆者としてはこの方法だけで十分だと思っています。

2つ目の方法は、ポインター配列すら用意する必要がありません。

2-1事前にポインター配列を十分な数だけ用意する方法

サンプルプロジェクト名　配列での動的確保

データをまとめて宣言する場合において、通常は次のように配列宣言しますね。

SOMETHING Data[1000];

この場合、SOMETHING型のインスタンスを直に宣言してしまっているので、動的な伸縮は出来ません。

インスタンスをのものを配列にするのではなく、そのインスタンスの“ポインター“を配列宣言すると、動的に伸縮させることができます。

SOMETHING * pData[1000];

前者の場合は、宣言と同時にインスタンスが生成されるので、その後行うことはなにもありませんが、ポインター配列の場合は、まだインスタンスはメモリ上に存在しません。メモリ上にあるのはあくまでも1000個のポインターの羅列だけです。

ですので、機能させるためにはもちろんインスタンスを明示的に生成する必要があります。

pData[0]= new SOMETHING;

pData[1]= new SOMETHING;

・

・

まとめて生成する場合は

pData[0] = new SOMETHING [ (生成したい要素数) ]

また、今10個までのインスタンスを既に生成している場合に,さらに20個の要素を追加した場合は、上のような書き方が出来ないのでfor文を使用して

for(i=9;i<=9+20;i++)

{

pData[ i ] = new SOMETHING;

}

などとします。

図にすると次のようになります。

図2−1　インスタンスの配列

図2−2　ポインターの配列

サンプルでは、この手法をそのまま実装しています。

何でもいいのでとりあえず適当にSOMETHINGという構造体を定義し、そのインスタンスを動的に確保しています。

図2−3

#include <stdio.h>

#include <windows.h>

//

//なんらかのデータ型

struct SOMETHING

{

INT Index;

FLOAT Some;

DOUBLE Thing;

};

//

//VOID main()

//エントリーポイント

VOID main()

{

INT i;

//”ポインター”を1000個用意する

SOMETHING* pSome[1000];

//例えば100個分のインスタンスを生成する（メモリを確保する）

for( i=0;i<100;i++)

{

pSome[i]=(SOMETHING *) new SOMETHING;

}

//さらに追加して200個分のインスタンスを生成する（メモリを確保する）

for( i=99;i<300;i++)

{

pSome[i]=(SOMETHING *) new SOMETHING;

}

//これ移行は確認のためのもの

for( i=0;i<300;i++)

{

pSome[i]->Index=i;

printf("%d ",pSome[i]->Index);

}

}

ポインターを1000個用意していますので、1000個までの要素を動的確保できます。

最初の動的確保では、適当に100個の要素を追加しています。（インスタンスを生成しています）

それ以降は100個までのインスタンスを使用することができます。（インデックス的には99番目までです。）

そして、これも適当に200個の要素が追加で必要になったと想定し、200個のインスタンスを生成しています。この時点で合計300個の要素が利用可能になっています。300個以上の要素が必要になったら200個の要素を追加したときと同様のコードを書くことになります。

2-2 ポインター配列自体も動的に確保する方法（完全な動的確保）

サンプルプロジェクト名　配列での完全動的確保

前項の手法では、メモリの動的確保とは言え、事前に“多少”の固定的なメモリが必要でした。固定的なメモリとはポインタ自体のメモリ領域のことです。ポインターですから型のサイズには依存せず常に4バイト(32bitPCの場合)ですから、例えば何らかの型（構造体も含む）について1000個のポインターを用意したとしても4キロバイト以下で済みます。（ゲームでは、オブジェクトの個数は数千個オーダー、多くても数万個オーダーでしょう。）しかし、これを“多少”と考えるか“けっこうなサイズだよ”と考えるかは主観や状況によって意見が分かれる可能性があります。

では、1000個ではなく最大1億個になる可能性がある場合はどうでしょう？1億個だと用意しなければならないポインター用のメモリ領域は381メガバイトにもなります。ここまでになるともはや主観的な問題ではなく今のPC環境では明らかに問題です。またさらに、最大数が全く未知の場合、つまり1億個どころか10億、100億…それ以上の個数になる可能性がある場合はお手上げです。もっともそのようなデータになる場合は、インスタンスを生成した後にも耐えうるだけのメモリを搭載していなければならないわけで、そのような環境において、ポインター用のメモリ領域は依然として相対的に小さいということも十分考えれられます。

ただやはり、その時代のPC環境におけるメモリ搭載量において、ポインター用に確保しなくてはならないメモリ領域が相対的にも馬鹿にならない場合も考えたほうが安心ではあります。そのような場合に、ここでの手法が有効です。

この手法では事前に用意するものはポインターのポインター（4バイト）だけです。インスタンスはもちろん、それぞれのポインター自体も動的に生成します。

サンプルのコードで直接解説します。

#include <stdio.h>

#include <windows.h>

//

//なんらかのデータ型

struct SOMETHING

{

INT Index;

INT Some;

FLOAT Thing;

};

//

//VOID main()

//エントリーポイント

VOID main()

{

INT i;

//”ポインターのポインター”（先頭ポインターとして機能）のみを用意する

SOMETHING** ppSome;

//例えば100個分のインスタンスを生成する（メモリを確保する）

ppSome=(SOMETHING**) new SOMETHING*[100];

for( i=0;i<100;i++)

{

ppSome[i]=(SOMETHING *) new SOMETHING;

}

//さらに追加して200個分のインスタンスを生成する（メモリを確保する）

SOMETHING** ppTmp=ppSome;

ppSome=(SOMETHING**) new SOMETHING*[100 + 200];

memcpy(ppSome,ppTmp,sizeof(SOMETHING*) * 100);

delete ppTmp;

for( i=100;i<300;i++)

{

ppSome[i]=(SOMETHING *) new SOMETHING;

}

//これ移行は確認のためのもの

for( i=0;i<300;i++)

{

ppSome[i]->Index=i;

printf("%d ",ppSome[i]->Index);

}

}

前項と同じくSOMETHINGという構造体型を動的生成していくものとします。

事前に用意するものは、SOMETHING**型の変数（SOMETHINGポインターのポインター）だけです。

SOMETHING** ppSome;

例えば100個のインスタンスを最初に生成するとすると、

ppSome=(SOMETHING**) new SOMETHING*[100];

for( i=0;i<100;i++)

{

ppSome[i]=(SOMETHING *) new SOMETHING;

}

このように書けます。最初の生成は誰しもが難なく書けると思います。

少々面倒なのが、2回目以降の追加です。

SOMETHING** ppTmp=ppSome;

ppSome=(SOMETHING**) new SOMETHING*[100 + 200];

memcpy(ppSome,ppTmp,sizeof(SOMETHING*) * 100);

delete ppTmp;

for( i=100;i<300;i++)

{

ppSome[i]=(SOMETHING *) new SOMETHING;

}

1行ごとに文章で表現すると次のとおりです。

あるタイミングで生成した部分を1つのグループと考えると

�@まずは、今まで生成したグループ（100個分）と今回追加するグループ（200個分）を含めた合計300個分のポインターを用意します。追加分(200個)だけではないことに注意していください。理由はすぐに分かります。

ppSome=(SOMETHING**) new SOMETHING*[100 + 200];

�A最初の100個分のポインター群を300個の領域（の先頭）にコピーします。

memcpy(ppSome,ppTmp,sizeof(SOMETHING*) * 100);

�Bこの時点で、最初の100個のポインターグループは、もはや不用なので解放します。

delete ppTmp;

�Cあとは300個の領域の100から300の場所に200個のインスタンスを生成します。

for( i=100;i<300;i++)

{

ppSome[i]=(SOMETHING *) new SOMETHING;

}

図2−4

図2−5

図2−6

図2−7

このようにする理由は、メモリ（仮想メモリ）上に連続的にインスタンスを配置するためです。メモリ上に連続して配置されていなければ添え字で（インデックスで）連番的にアクセス出来なくなります。

具体的に述べると、最初の100個の生成と同じように200個の追加生成をしてしまっては、連番ではなくなる可能性があります。

というのは、個々のグループではメモリ上に連続して配置されます。つまり、0から99までは連続しています。そして100から299までも連続しています。しかし、異なるタイミングで生成したグループ同士が連続しているとは限りません。最初のグループの最後と追加グループの最初、つまり、99と100が連続しているとは限りません。したがって全体として連続しないことになり、使い物にならないからです。

図2−8

図2−9

3章 SK法レベル1#2 （配列における高速な挿入と削除）

サンプルプロジェクト名　配列で高速挿入・削除

SK法レベル1#2は大量のエンティティを超高速に処理することができ、カンパニーウォーズで採用している手法でもあります。この程度であれば似たようなロジックを考える人は少なくないかもしれません。SK法はトリックの論理ライブラリでありレベル2まで確立され、現在レベル3の研究中です。レベル1にはこの他にレベル1#3としてネットワークの同期ロジックがありますが、それはすでに「はじめての３Dゲーム開発」で詳細に解説しています。

さて、先にリンクドリストの特徴を述べた際、配列では、ある要素を挿入するのに前後の要素全てを一斉に移動しなければならないと述べました。素直に考えるとそうなりますし、配列の構造から原理的にはそれしかありません。

したがって、ここでの手法はトリック的な色合いが濃いもので、本当の意味での挿入・削除ではありません。

ここでのトリックは大抵の場合、挿入・削除が一定時間で行われ上手くいきますが、ある状況において、少々上手くいかない理由も後ほど述べます。しかし、そのような状況にしないことは容易です。

このトリックの実行速度は究極とも言える速さで“一定時間”です。表現を変えるとO(1)アルゴリズムです。

リンクドリストの挿入や削除が速いと言っても、トラバースの部分でリストの長さに影響され、実行速度は“線形時間”に留まります。O記法だとO(N)になります。

このトリックは、O(1)ですから要素の個数に依存せずに常に同じ処理時間です。要素数が10個の時と10兆個のときでも、挿入・削除にかかる時間は同じということです。もちろん、それらの処理に必要な処理全体での時間がO(1)ということです。

本節のサンプルですが、私の“人生の中”で、これほど単純なゲームは作ったことがありません。当然作り置きなどもありませんから、1からのフルスクラッチですが、このサンプルの制作には5時間かかっていません。ゲームの外見だけを見ると、大昔15歳の時に初めて作ったプログラムのほうがまだマシです。

しかし、中身はと言うと、配列の効率的操作と、その結果としてコードのシンプルさは15歳の頃とは雲泥の差があります。（もちろん、こちらのほうが優れているということです…念のため）

私的には（一般的にも）“ゲーム”とも呼べない代物ですが、配列の操作と、その結果を確認するにはいいサンプルだと思います。

図3−1

ENEMY e[ 10 ];

N=敵の総数;

for(i=0;i<N;i++)

{

if(消滅させるタイミングになった)

{

memcpy( &e[i],&e[N -1],sizeof(ENEMY));

N--;

}

}

図3−2

サンプルでは、オブジェクト（弾、敵）の削除は全てこの手法を使用しています。サンプルにおけるオブジェクトの削除は次の4種類があります。

自分の弾削除

敵の削除（自分の弾が当たった時）

敵の削除（画面外に出た時）

敵の弾の削除

次はそれぞれのコード片ですが、見ると分かるように、変数等は異なるものの、やっていること同じであることが分かるでしょう。

自分の弾削除

//自分の弾が画面外に出たら削除

if(Me.Shell[i].Pos.y<=0)

{

memcpy(&Me.Shell[i],&Me.Shell[Me.ShellAmt-1],sizeof(SHELL));

Me.ShellAmt--;

}

敵の削除（自分の弾が当たった時）

//自分の弾と敵の当たり判定

for(INT k=0;k<EnemyAmt;k++)

{

if( D3DXVec3Length(&(Enemy[k].Pos-Me.Shell[i].Pos)) <16)

{

memcpy(&Enemy[k],&Enemy[EnemyAmt-1],sizeof(CHARACTER));

EnemyAmt--;

}

}

敵の削除（画面外に出た時）

//敵が画面外に出たら削除

if(Enemy[i].Pos.y>600)

{

memcpy(&Enemy[i],&Enemy[EnemyAmt-1],sizeof(CHARACTER));

EnemyAmt--;

}

敵の弾の削除

//敵の弾が画面外に出たら削除

if(Enemy[i].Shell[k].Pos.y>600)

{

memcpy(&Enemy[i].Shell[k],&Enemy[i].Shell[Enemy[i].ShellAmt-1],sizeof(SHELL));

Enemy[i].ShellAmt--;

}

削除したい要素がある場所に最後尾の要素の中身をコピーし、総数を1減らしているだけです。これで上手く機能します。なお、最後尾にあるデータはゼロで初期化しなくても構いません。新たなオブジェクトが生成される際には、どのみち新たなデータで初期化されますから。

スペースインベンター　全ソース

//必要なヘッダーファイルのインクルード

#include <time.h>

#include <windows.h>

#include <d3dx9.h>

#include <dinput.h>

//必要なライブラリファイルのロード

#pragma comment(lib,"d3d9.lib")

#pragma comment(lib,"d3dx9.lib")

#pragma comment(lib,"dinput8.lib")

#pragma comment(lib,"dxguid.lib")

// 定数、マクロ定義

#define WINDOW_WIDTH 800

#define WINDOW_HEIGHT 600

#define SPRITE_WIDTH 32

#define SPRITE_HEIGHT 32

#define SAFE_RELEASE(p) { if(p) { (p)->Release(); (p)=NULL; } }

#define X_SPEED 1

#define Y_SPEED 2

#define SHELL_SPEED 4

#define MAX_ENEMY 20

//型定義

struct SHELL//弾

{

D3DXVECTOR3 Pos;

SHELL()

{

ZeroMemory(this,sizeof(SHELL));

}

};

struct CHARACTER//自分と敵

{

D3DXVECTOR3 Pos;

FLOAT AddX;

INT ShellAmt;

SHELL Shell[50];

CHARACTER()

{

ZeroMemory(this,sizeof(CHARACTER));

}

};

//グローバルなインスタンスを宣言

LPDIRECT3D9 pD3d;

LPDIRECT3DDEVICE9 pDevice;

LPDIRECT3DTEXTURE9 pTexture;

LPDIRECT3DTEXTURE9 pEnemyTexture;

LPDIRECT3DTEXTURE9 pShellTexture;

LPD3DXSPRITE pSprite;

LPDIRECTINPUT8 pDinput=NULL;

LPDIRECTINPUTDEVICE8 pKeyDevice=NULL;

FLOAT fPosX=0,fPosY=0;

CHARACTER Me,Enemy[MAX_ENEMY];

INT EnemyAmt=0;

//関数プロトタイプの宣言

LRESULT CALLBACK WndProc(HWND,UINT,WPARAM,LPARAM);

HRESULT InitD3d(HWND);

HRESULT InitDinput(HWND hWnd);

VOID Move();

VOID GenerateEnemy();

VOID MoveEnemy();

VOID DrawSprite();

VOID FreeDx();

//

//INT WINAPI WinMain( HINSTANCE hInst,HINSTANCE hPrevInst,LPSTR szStr,INT iCmdShow)

//アプリケーションのエントリー関数

INT WINAPI WinMain( HINSTANCE hInst,HINSTANCE hPrevInst,LPSTR szStr,INT iCmdShow)

{

HWND hWnd=NULL;

MSG msg;

// ウィンドウの初期化

static char szAppName[] = "Space Inventor スペースインベンター 宇宙の開発者";

WNDCLASSEX wndclass;

wndclass.cbSize = sizeof (wndclass) ;

wndclass.style = CS_HREDRAW | CS_VREDRAW ;

wndclass.lpfnWndProc = WndProc ;

wndclass.cbClsExtra = 0 ;

wndclass.cbWndExtra = 0 ;

wndclass.hInstance = hInst ;

wndclass.hIcon = LoadIcon (NULL, IDI_APPLICATION) ;

wndclass.hCursor = LoadCursor (NULL, IDC_ARROW) ;

wndclass.hbrBackground = (HBRUSH) GetStockObject (BLACK_BRUSH) ;

wndclass.lpszMenuName = NULL ;

wndclass.lpszClassName = szAppName ;

wndclass.hIconSm = LoadIcon (NULL,IDI_ASTERISK);

RegisterClassEx (&wndclass) ;

hWnd = CreateWindow (szAppName,szAppName,WS_OVERLAPPEDWINDOW,

0,0,WINDOW_WIDTH,WINDOW_HEIGHT,NULL,NULL,hInst,NULL);

ShowWindow (hWnd,SW_SHOW) ;

UpdateWindow (hWnd) ;

// ダイレクト３Dの初期化関数を呼ぶ

if(FAILED(InitD3d(hWnd)))

{

return 0;

}

// ダイレクトインプットの初期化関数を呼ぶ

if(FAILED(InitDinput(hWnd)))

{

return 0;

}

//オブジェクト初期設定

Me.Pos.x=400;

Me.Pos.y=520;

// メッセージループ

ZeroMemory( &msg, sizeof(msg) );

while( msg.message!=WM_QUIT )

{

if( PeekMessage( &msg, NULL, 0U, 0U, PM_REMOVE ) )

{

TranslateMessage( &msg );

DispatchMessage( &msg );

}

else

{

Move();

GenerateEnemy();

MoveEnemy();

DrawSprite();

}

Sleep(1);

}

//アプリケーションを終了する時には、Direct3Dオブジェクトをリリースする

FreeDx();

return (INT)msg.wParam ;

}

//

//LRESULT CALLBACK WndProc(HWND hWnd,UINT iMsg,WPARAM wParam,LPARAM lParam)

// ウィンドウプロシージャー関数

LRESULT CALLBACK WndProc(HWND hWnd,UINT iMsg,WPARAM wParam,LPARAM lParam)

{

switch(iMsg)

{

case WM_DESTROY:

PostQuitMessage(0);

break;

case WM_KEYDOWN:

switch((CHAR)wParam)

{

case VK_ESCAPE:

PostQuitMessage(0);

break;

}

break;

}

return DefWindowProc (hWnd, iMsg, wParam, lParam) ;

}

//

//HRESULT InitD3d(HWND hWnd)

//ダイレクト3Dの初期化後にスプライトとそれに伴うテクスチャの初期化

HRESULT InitD3d(HWND hWnd)

{

// 「Direct3D」オブジェクトの作成

if( NULL == ( pD3d = Direct3DCreate9( D3D_SDK_VERSION ) ) )

{

MessageBox(0,"Direct3Dの作成に失敗しました","",MB_OK);

return E_FAIL;

}

// 「DIRECT3Dデバイス」オブジェクトの作成

D3DPRESENT_PARAMETERS d3dpp;

ZeroMemory( &d3dpp, sizeof(d3dpp) );

d3dpp.BackBufferFormat =D3DFMT_UNKNOWN;

d3dpp.BackBufferCount=1;

d3dpp.SwapEffect = D3DSWAPEFFECT_DISCARD;

d3dpp.Windowed = TRUE;

if( FAILED( pD3d->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, hWnd,

D3DCREATE_HARDWARE_VERTEXPROCESSING,

&d3dpp, &pDevice ) ) )

{

if( FAILED( pD3d->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, hWnd,

D3DCREATE_SOFTWARE_VERTEXPROCESSING,

&d3dpp, &pDevice ) ) )

{

MessageBox(0,"DIRECT3Dデバイスの作成に失敗しました",NULL,MB_OK);

return E_FAIL;

}

}

//「テクスチャオブジェクト」の作成

if(FAILED(D3DXCreateTextureFromFileEx(pDevice,"Me.bmp",SPRITE_WIDTH*(16.0f /24.0f),SPRITE_HEIGHT*(16.0f /24.0f),0,0,D3DFMT_UNKNOWN,

D3DPOOL_DEFAULT,D3DX_FILTER_NONE,D3DX_DEFAULT,

0xff000000,NULL,NULL,&pTexture)))

{

MessageBox(0,"テクスチャの作成に失敗しました","",MB_OK);

return E_FAIL;

}

if(FAILED(D3DXCreateTextureFromFileEx(pDevice,"Enemy.bmp",SPRITE_WIDTH*(16.0f /24.0f),SPRITE_HEIGHT*(16.0f /24.0f),0,0,D3DFMT_UNKNOWN,

D3DPOOL_DEFAULT,D3DX_FILTER_NONE,D3DX_DEFAULT,

0xff000000,NULL,NULL,&pEnemyTexture)))

{

MessageBox(0,"テクスチャの作成に失敗しました","",MB_OK);

return E_FAIL;

}

if(FAILED(D3DXCreateTextureFromFileEx(pDevice,"Shell.bmp",SPRITE_WIDTH*(16.0f /24.0f),SPRITE_HEIGHT*(16.0f /24.0f),0,0,D3DFMT_UNKNOWN,

D3DPOOL_DEFAULT,D3DX_FILTER_NONE,D3DX_DEFAULT,

0xff000000,NULL,NULL,&pShellTexture)))

{

MessageBox(0,"テクスチャの作成に失敗しました","",MB_OK);

return E_FAIL;

}

// 「スプライトオブジェクト」の作成

if(FAILED(D3DXCreateSprite(pDevice,&pSprite)))

{

MessageBox(0,"スプライトの作成に失敗しました","",MB_OK);

return E_FAIL;

}

return S_OK;

}

//

//HRESULT InitDinput(HWND hWnd)

//ダイレクトインプットの初期化関数

HRESULT InitDinput(HWND hWnd)

{

HRESULT hr;

// 「DirectInput」オブジェクトの作成

if( FAILED( hr = DirectInput8Create( GetModuleHandle(NULL),

DIRECTINPUT_VERSION,IID_IDirectInput8, (VOID**)&pDinput, NULL ) ) )

{

return hr;

}

// 「DirectInputデバイス」オブジェクトの作成

if( FAILED( hr = pDinput->CreateDevice( GUID_SysKeyboard,

&pKeyDevice, NULL ) ) )

{

return hr;

}

// デバイスをキーボードに設定

if( FAILED( hr = pKeyDevice->SetDataFormat( &c_dfDIKeyboard ) ) )

{

return hr;

}

// 協調レベルの設定

if( FAILED(hr= pKeyDevice->SetCooperativeLevel(

hWnd,DISCL_NONEXCLUSIVE | DISCL_BACKGROUND )) )

{

return hr;

}

// デバイスを「取得」する

pKeyDevice->Acquire();

return S_OK;

}

//

//VOID Move()

//

VOID Move()

{

//　自分の操作

HRESULT hr=pKeyDevice->Acquire();

if((hr==DI_OK) || (hr==S_FALSE))

{

BYTE diks[256];

pKeyDevice->GetDeviceState(sizeof(diks),&diks);

if( Me.Pos.x>4 && diks[DIK_LEFT] & 0x80)

{

Me.Pos.x-=4;

}

if( Me.Pos.x<760 && diks[DIK_RIGHT] & 0x80)

{

Me.Pos.x+=4;

}

if(Me.Pos.y>4 && diks[DIK_UP] & 0x80)

{

Me.Pos.y-=4;

}

if(Me.Pos.y<540 && diks[DIK_DOWN] & 0x80)

{

Me.Pos.y+=4;

}

//弾生成

static INT time=clock();

if( (diks[DIK_SPACE] & 0x80) && (clock()-time>100 ) )

{

time=clock();

Me.Shell[Me.ShellAmt].Pos=Me.Pos;

if(Me.ShellAmt<48)

{

Me.ShellAmt++;

}

}

}

//自分の弾移動と当たり判定

for(INT i=0;i<Me.ShellAmt;i++)

{

//

Me.Shell[i].Pos.y-=SHELL_SPEED;

//自分の弾が画面外に出たら削除

if(Me.Shell[i].Pos.y<=0)

{

memcpy(&Me.Shell[i],&Me.Shell[Me.ShellAmt-1],sizeof(SHELL));

Me.ShellAmt--;

}

//自分の弾と敵の当たり判定

for(INT k=0;k<EnemyAmt;k++)

{

if( D3DXVec3Length(&(Enemy[k].Pos-Me.Shell[i].Pos)) <16)

{

memcpy(&Enemy[k],&Enemy[EnemyAmt-1],sizeof(CHARACTER));

EnemyAmt--;

}

}

}

}

//

//VOID GenerateEnemy()

//

VOID GenerateEnemy()

{

//敵生成

static INT time=clock();

if(clock()-time>100)

{

time=clock();

if(EnemyAmt<MAX_ENEMY-2)

{

Enemy[EnemyAmt].Pos.x=(rand() % 700) +32;

Enemy[EnemyAmt].Pos.y=rand() % 300;

rand()<16000 ? Enemy[EnemyAmt].AddX=-X_SPEED : Enemy[EnemyAmt].AddX=X_SPEED;

EnemyAmt++;

}

}

}

//

//VOID MoveEnemy()

//

VOID MoveEnemy()

{

//敵移動

for(DWORD i=0;i<EnemyAmt;i++)

{

Enemy[i].Pos.y+=Y_SPEED;

//敵が画面外に出たら削除

if(Enemy[i].Pos.y>600)

{

memcpy(&Enemy[i],&Enemy[EnemyAmt-1],sizeof(CHARACTER));

EnemyAmt--;

}

Enemy[i].Pos.x+=Enemy[i].AddX;

if(Enemy[i].Pos.x<=0 || Enemy[i].Pos.x>800-32)

{

Enemy[i].AddX*=-1;

}

if(D3DXVec3Length(&(Enemy[i].Pos - Me.Pos ) )<32)

{

//MessageBox(0,"ゲームオーバー","敵の当たった",MB_OK);

//PostQuitMessage(0);

}

}

//敵の弾発射

for(DWORD i=0;i<EnemyAmt;i++)

{

if(rand()<320)

{

if(Enemy[i].ShellAmt<48)

{

Enemy[i].Shell[Enemy[i].ShellAmt].Pos=Enemy[i].Pos;

Enemy[i].ShellAmt++;

}

}

//敵の弾移動と当たり判定

for(INT k=0;k<Enemy[i].ShellAmt;k++)

{

Enemy[i].Shell[k].Pos.y+=SHELL_SPEED;

//敵の弾が画面外に出たら削除

if(Enemy[i].Shell[k].Pos.y>600)

{

memcpy(&Enemy[i].Shell[k],&Enemy[i].Shell[Enemy[i].ShellAmt-1],sizeof(SHELL));

Enemy[i].ShellAmt--;

}

if(D3DXVec3Length(&(Enemy[i].Shell[k].Pos - Me.Pos)) < 16)

{

//MessageBox(0,"ゲームオーバー","敵の弾に当たった",MB_OK);

//PostQuitMessage(0);

}

}

}

}

//

//VOID DrawSprite()

//スプライトをレンダリングする

VOID DrawSprite()

{

INT i,k;

pDevice->Clear( 0, NULL, D3DCLEAR_TARGET,D3DCOLOR_XRGB(30,30,30), 1.0f, 0 );

if( SUCCEEDED( pDevice->BeginScene() ) )

{

pSprite->Begin(D3DXSPRITE_ALPHABLEND);

//自分

pSprite->Draw(pTexture,NULL,NULL,&Me.Pos,D3DCOLOR_ARGB(255,255,255,255));

//自分の弾

for( i=0;i<Me.ShellAmt;i++)

{

pSprite->Draw(pShellTexture,NULL,NULL,&Me.Shell[i].Pos,D3DCOLOR_ARGB(255,255,255,255));

}

//敵

for( i=0;i<EnemyAmt;i++)

{

pSprite->Draw(pEnemyTexture,NULL,NULL,&Enemy[i].Pos,D3DCOLOR_ARGB(255,255,255,255));

//敵の弾

for(k=0;k<Enemy[i].ShellAmt;k++)

{

pSprite->Draw(pShellTexture,NULL,NULL,&Enemy[i].Shell[k].Pos,D3DCOLOR_ARGB(255,255,255,255));

}

}

pSprite->End();

pDevice->EndScene();

}

pDevice->Present( NULL, NULL, NULL, NULL );

}

//

//VOID FreeDx()

// 作成したDirectXオブジェクトの開放

VOID FreeDx()

{

if(pKeyDevice)

{

pKeyDevice->Unacquire();

}

SAFE_RELEASE( pKeyDevice );

SAFE_RELEASE( pDinput );

SAFE_RELEASE( pTexture );

SAFE_RELEASE( pEnemyTexture );

SAFE_RELEASE( pShellTexture );

SAFE_RELEASE( pSprite );

SAFE_RELEASE( pDevice );

SAFE_RELEASE( pD3d );

}

うまく機能しない状況

最初に、ある状況において少々上手くいかないことがあると述べたました。その理由と回避方法を解説します。

例えば、10個のエンティティが生きているとして、あるフレームでその“全て”が核ミサイルにより消失したとしましょう。そのフレーム内で全てを削除しなくてはなりませんよね。

（Nは最初10）

　　　↓

for(i=0;i<N;i++)

{

memcpy( &e[i],&e[N -1],sizeof(ENEMY));

N--;

}

コードを頭の中でトレースしてください。Nが5までしか減らないことがわかるでしょうか？

そして次のフレームには5から2に減り、次で2から1、そしてようやく4フレーム目で全てが削除できます。

図にしてみましたので見てください。

図3-3

このように、そのフレーム内で全てを削除できません。

ただ、回転数自体は4フレームの合計で10回転しかしないので、処理速度が余計にかかるというものではありません。

これで問題になるのは、（見た目には一瞬ですが)以降のフレームでエンティティが残ってしまうことです。

これを解決するには、簡単で、次のようにwhile文でくくって、Nがゼロになるまで回せばいいだけです。

（Nは最初10）

　　　↓

while(N>0)

{

for(i=0;i<N;i++)

{

memcpy( &e[i],&e[N -1],sizeof(ENEMY));

N--;

}

}

繰り返しますが、回転数はあくまでも10回転です。速度が落ちることはありません。

4章　木

木（Tree トリー）はリンクドリストと同じくデータ構造です。リンクドリストが1次元であるのに対し、木は2次元以上の階層構造になります。配列やリンクドリストが“階層”になっているとき、その構造を木と呼びます。このことから、リンクドリストはリンクを一つしかもたない木であるとも言えます。

さて、実際に木構造であるものにはどのようなものがあるかというと、例えば、DirectXのXファイルは、アニメーションメッシュの各パーツメッシュやスキンアニメーションの各ボーンを木構造で格納します。ヒープソート（5章ソートの中で解説）はヒープと呼ばれる特殊な2分木によりソートを効率的に行います。また、クアッドトリー（8章）、オクトトリー（9章）もその名のとおり木です。

木には、枝（と葉）の数により幾つかの分類ができます。

まず、枝の数が不特定にあるものを自由木と呼びます。Xファイルは自由木によりメッシュやボーンを関連付けています。

図4-1　自由木

子を2つまで持つ木は2分木と呼びます。

ヒープソートは2分木により、ノードを繋げています。

図4-2　2分木

子を4つまで持つ木は4分木と呼びます。

クアッドトリーは4分木です。クアッド（quad）とは4分割という意味です。

図4-3　4分木

子を8つまで持つ木は8分木と呼びます。

オクトトリーは8分木です。オクト（oct）はoctanの略で8分割という意味です。

なお、綴りはoctreeであってocttreeではありません。そして発音は逆に「オクトリー」ではなく「オクト・トリー」とする人が多いです。

図4-4　8分木

n分木において、全てのノードが必ずn個の子を持つもの、つまり、びっしりノードが末端まで詰まっているものは特に完全n分木と呼びます。本章の図は自由木を除き、全て完全n分木を表しています。

5章　ソート

ソートとは「整列」のことであり、アルゴリズムの勉強そして授業では必ずと言っていいほど登場します。

ソートは、“アルゴリズム”とは何なのかということを肌で感じさせてくれるもの、そして、その醍醐味を経験するのに最適なロジックだと思います。

図5−1

この世にコンピューターの原型が生まれたと同時に生まれたアルゴリズムであり、言い方を変えれば、コンピューターに仕事をさせる際にすぐに必要とされたロジックです。そのようなロジックは今でもコンピューターの仕組みを理解するのにも役立ちます。

本章では、およそ考えられる全てのソートを解説します。もちろん全てのソートアルゴリズムについてソースコードがあり、それをビルド・実行し、さらに、全てのソートの性能を計測・比較できるような実装になっています。

図5−2

本書には14種類のソートのソースを添付していますが、（比較には、組み込みqsortと併せて15種類のソートを比較します）、その性能により、あるグループ分けが出来ます。O記法で表した時の、、の3つのグループです。が最も遅く、は中間、が最も速いグループです。

次図は、全ソートの実行時間の一覧表です。1000個から1000万個までの要素数を計測しています。単位はミリ秒で、もちろん大きい値のほうがそれだけ時間がかかったということであり、性能が低いことを意味します。

図5−3

これを見て、ある特徴が見えると思います。くっきりと性能差が分かれ、3つのグループになっていることがわかるでしょうか。O記表現を書き入れると次のようになります。

図5−4

系のソートでの1000万個の列でN/Aと書いてある欄は、実測値ではなく推定値です。“推定”と言っても、かなり実測値に近いと言えます。系のN/Aの部分だけの所要時間を合わせるとなんと520時間（21日間）！にもなってしまい、筆者が何も仕事を出来なくなるので実際に計測はしていません。1000万個のソートで、バブルソートが166時間なのに対し、逆写像ソートが1秒以下であることは脅威的な差ですね。

O記法の読み方

系のソートは最も遅いソートで、要素数が100万以上から使い物にならなくなります。（遅すぎて）

要素数が1000あったら、性能は大雑把に言って1,000×1,000=1,000,000程度になります。

系のソートは、よりは速いものの、よりは遅いソートです。

要素数が1000あったら、性能は大雑把に言って1,000×3=3,000程度になります。（1000=10の3乗、log1000=3）

系のソートは、最も速いソートです。

なお、ソートは事実上有り得ません。またソートは（kは値の範囲）、場合によってはよりも遅くなったり速くなったりするでしょうから、ここではに含めます。もっともソートの実装を見たことはありませんが。

ではまず、理解し易い系のソートから始めましょう。

5-1 系ソート

セレクションソート（Selection Sort）

「ソートプログラムを書いてください」と言われた時、ソートのコーディングに熟達していない限り、大抵の人が書くアルゴリズムが系のソートであり、なかでもこのセレクションソートである場合がほとんどだと思います。

ランダムな値が入っている配列a[100]をソートする場合、まず真っ先に考えるアルゴリズムは、2重にループさせることではないでしょうか。a[0]からa[99]のそれぞれに対し、さらに100回分のループをして、総当り的に順序を見つけようとするロジックです。100個に対しそれぞれ100回のステップが実行されますから、総ステップ数は100×100=10000ステップになりますよね。セレクションソートに限らず、これが系ソートの（要素数の二乗）である原因です。なかでもセレクションソートはロジックが非常に安易であり、書いてしまいがちなソートです。

なお、2重ループをすること自体は本質ではありません。実際O(N)系でも2重ループ自体は行いますが、本質はなんら工夫もなく2重ループをしてしまうことであり、2重ループそのものが中心原理になっている点です。平たく言えば力技です。

さて、セレクションソートの仕組みは、外側のループで逐次的に要素を1つずつ順に調べていき、現在調べている要素より小さい要素を内側のループ中で見つけ、小さい要素が見つかったらその都度交換していくというものです。

“セレクション”の由来は、内側のループ中で小さい要素を選択（選抜、選択して抜き出す）していく形になるからです。

コードは次のようになります。

#define INT_SWAP(a,b) INT tmp=a;a=b;b=tmp;

VOID SORTER::SelectionSort(INT* pData,INT Amount)

{

INT i,k;

DWORD dwMin;

for(i=0;i<Amount-1;i++)

{

dwMin=i;

for(k=i+1;k<Amount;k++)

{

if(pData[k] < pData[ i ] )

{

dwMin=k;

INT_SWAP(pData[dwMin],pData[i]);

}

}

}

}

利便性のためINT_SWAPというマクロを定義しました。定義を見れば明らかではありますが、INT型の2つの変数を入れ替える（交換する）ものです。このマクロは他のソートでも使用します。

ノームソート（Gnome Sort）

ノームソートのコードは、“最もシンプルな”コードです。ちなみにノームソートのノームは“妖精”を意味し、妖精が1列に並んだ花の鉢を行ったり来たりすることをソートの流れに例えたものだと言われています。

VOID SORTER::Gnome(INT* pData,INT Amount,INT Dammy)

{

for(INT i=0;i<Amount;)

{

if (i==0 || pData[i-1]<=pData[i])

{

i++;

}

else

{

INT_SWAP(pData[i-1],pData[i]);

i--;

}

}

}

コードはたったこれだけです。無理すれば一行で書けてしまうほど短いコードですね。

とりあえず、すぐにソート部分を書かなければならない場合でデータ数が1000個以内程度ならノームソートがお勧めです。

データ数が1000個程度までなら系のソートのほうが初期化時にメモリ確保のオーバーヘッドがある系ソートより速い可能性が高いからです。

バブルソート（Bubble Sort）

バブルソートはノームソートに負けないくらいシンプルなコードとなります。

VOID SORTER::BubbleSort(INT* pData,INT Amount,INT Dammy)

{

INT i,k;

for(i=Amount;i>1;i--)

{

for(k=1;k<i;k++)

{

if(pData[k-1] > pData[k])

{

INT_SWAP(pData[k-1],pData[k]);

}

}

}

}

バブルソートもノームソートと同様に、1000個程度のデータ数であれば使用しても問題ないので、すぐに書くにはお手軽なソートでしょう。

バブルソートの“バブル”の意味は、データの移動の様子に起因します。例えばソート前のデータにおいて最大値が先頭にあるとして、その最大値は1回のループで一つずつ位置をずらしながらだんだんと最後尾まで“浮き上がって”くるように移動します。これがバブルと称される理由です。

例）

次のような5つのデータをソートする場合、

5, 1, 2, 3, 4

“5”は次のように1ステップ（ループ1回転）に一つずつ移動します。

1,5,2,3,4　1ステップ

1,2,5,3,4　2ステップ

1,2,3,5,4　3ステップ

1,2,3,4,5　4ステップで終了。

泡がだんだんと上がってくることを連想させます。

シェーカーソート（Shaker Sort）

シェーカーソートはバブルソートの改良版です。

バブルソートの問題点は、先頭から調査するか最後尾から調査するかで、性能が極端に変化する可能性があることです。（これは他のセレクションソートに言えることでもあり、バブルソートに限ったことではないのですが）

例えば、次のような5つのデータをソートする場合、

5, 1, 2, 3, 4

データ交換の回数（交換の回数が性能をほぼ決定します）は4回です。つまり、次のように5が移動するのに4ステップ要します。

1,5,2,3,4　1ステップ

1,2,5,3,4　2ステップ

1,2,3,5,4　3ステップ

1,2,3,4,5　4ステップで終了。

では、次のようになっている場合はどうでしょう。

1,2,3,5,4

5の移動は1ステップで終了します。

1,2,3,4,5　1ステップで終了。

このようにデータの並びとバブルの進行方向の関係で性能が大きく左右されます。

これを回避するために、バブルの方向を交互に逆になるように改良したものがシェーカーソートです。シェーカーソートが双方向バブルソートとも呼ばれるのはそのためです。

VOID SORTER::Shaker(INT* pData,INT Amount,INT Dammy)

{

INT Left = 0, Right = Amount-1;

BOOL Swapped=TRUE;

while (Swapped)

{

Swapped = FALSE;

for (INT i = Left; i < Right; i++)

{

if (pData[i] > pData[i+1])

{

INT_SWAP(pData[i], pData[i+1]);

Swapped = TRUE;

}

}

for (INT i = Right; i > Left; i--)

{

if (pData[i] < pData[i-1])

{

INT_SWAP(pData[i], pData[i-1]);

Swapped = TRUE;

}

}

Left++;

Right--;

}

}

インサーションソート（Insertion Sort）

インサーションソートは、ちょうどカードゲームでのカード（あるいはマージャンの牌）を人間が並べ替える作業に似ています。セレクションやバブルソートにおいて、移動された要素はその位置で確定し、再度位置を変えることはありませんが、インサーションソートの場合、移動されて揃った部分でも、それで確定ではなく、その後再度並び替えが発生します。揃っている部分に新たなデータの挿入を繰り返すので、部分的な整列は並びは動的に変化していきます。これがインサーション（挿入）ソートと呼ばれる理由です。

例えば初期データが次のようになっているとすると、

5 2 4 3 1

インサーションソートは、次の4つのステップでソートを完了します。

2 5 4 3 1

2 4 5 3 1

2 3 4 5 1

1 2 3 4 5

第1ステップ

2,5の部分がとりあえずの整列区間です。

2 5 4 3 1

第2ステップ

2 4 5 3 1

4が挿入されます。

インサーションソートでは、整列区間はあくまで“とりあえず”なので、後からどんどん挿入が発生し、内容が変化します。現実のカードやパイを並べる様と似ています。このようなことはセレクションソート等では起きません。

この時点での仮の整列区間は2,3,4の部分です。

第3ステップ

2 3 4 5 1

同じように、新たに3が挿入されてまた内容が変化します。

第4ステップ

1 2 3 4 5

最後に1が挿入されて、この場合完成です。

VOID SORTER::InsertionSort(INT* pData,INT Amount,INT Dammy)

{

INT i=0,k=0,tmp=0;

for(i=1;i<Amount;i++)

{

k=i;

tmp=pData[i];

while(tmp < pData[k-1] && k>0)

{

pData[k]=pData[k-1];

k--;

}

pData[k]=tmp;

}

}

5-2 系ソート

系のソートは、よりは速いですが、よりは遅いソートです。

シェルソート（Shell Sort）

シェルソートの“シェル”は、開発者ドナルド・L・シェル（Donald.L. Shell）に由来し、インサーションソートの改良版です。

インサーションソートにおいて、要素1個分の間隔（隣り合った要素同士）でしか交換しないという性質はボトルネックになっています。

それを解消しようとするもので、一定の間隔をあけて幾つかの領域に分割し、それぞれの範囲内で挿入ソートを行うというものです。その間隔はギャップ（Gap）と呼ばれます。

ギャップは、最初が一番大きく、だんだんと狭めていきます。最終的にギャップが1以下になったとき、ソートが完了したことになります。

ギャップを1に固定するとインサーションソートと同じであることに気付くでしょうか？インサーションソートのコードと見比べるとすぐに分かります。

例えば初期データが次のようになっているとすると、

5 2 4 3 1

シェルソートは、次の6つのステップでソートを完了します。

3 2 4 5 1

3 1 4 5 2

1 3 4 5 2

1 3 4 5 2

1 3 4 5 2

1 2 3 4 5

“誌面上”はインサーションソートよりステップ数が多く見えますが、最深部のループにおける交換過程を表示していないためです。さらに要素数が極端に少なく、インサーションソートのウィークポイントが表面化していなかったということに留意してください。シェルソートはインサーションソートよりはるかに高速です。

クイックソート（Quick Sort）

クイックソートはチャールズ・アントニー・リチャード・ホーア（Charles Antony・Richard Hoare）卿が発明したアルゴリズムで（長い名前ですが一人です）、比較的人気のあるソートアルゴリズムのようです。

ただ、これはあくまで本書サンプルでの話ですが、クイックソートがとりわけ速いわけではなく、筆者としては人気の根拠が分かりません。

実装はシンプルで、分割統治で再帰的にソートしていきます。

分割統治の分割地点は“決め打ち”で、そのときのデータの半分地点で分割し、再帰してゆきます。（本書の場合）

VOID SORTER::QuickSort(INT* pData, INT Left, INT Right)

{

　　　INT Pivot = pData[ (Left + Right) / 2];

INT Low = Left-1,Hi = Right+1;

while (TRUE)

{

while (pData[++Low] < Pivot);

while (pData[--Hi] >Pivot) ;

if (Low >= Hi)

{

break;

}

SWAP(INT, pData[Low], pData[Hi]);

}

if (Left < Low)

{

QuickSort(pData, Left, Low - 1);

}

if (Right >Hi)

{

QuickSort(pData, Hi + 1, Right);

}

}

マージソート（Merge Sort）

マージソートは、ジョン・フォン・ノイマン（John von Neumann）が発明したアルゴリズムで、要はクイックソートの変形版です。

ほとんど整列しているデータあるいは、ほとんど同じデータに対してはクイックソートよりも高速です。（十分に乱雑なデータではクイックソートより低速です）

ただし、ワークエリアとして要素数分のメモリ領域が必要です。

INT* WA=new INT[Amount];

VOID SORTER::MergeSort(INT *pData,INT* WA,INT Left, INT Right)

{

INT i,k,n;

if(Right>Left)

{

INT Middle=(Left+Right)/2;

MergeSort(pData,WA,Left,Middle);

MergeSort(pData,WA,Middle+1,Right);

for(i=Middle+1;i>Left;i--)

{

WA[i-1]=pData[i-1];

}

for(k=Middle;k<Right;k++)

{

WA[Right+Middle-k]=pData[k+1];

}

for(n=Left;n<=Right;n++)

{

if(WA[i]<WA[k])

{

pData[n]=WA[i++] ;

}

else

{

pData[n]=WA[k--];

}

}

}

}

データ範囲を2分割し、それぞれの領域ではクイックソートを行います。それらの仕事は一旦ワークエリア上で行い、その後で2つの領域をマージ（結合）し、本来のデータ領域に上書きします。

ヒープソート（Heap Sort）

（あくまで本書では）ヒープソートは、全ての系ソートの中で最も平均性能が高いという結果になっています。要素数10000程度であれば、系であるラディックスソートよりも速いという結果も出ているくらいです。

平均性能を上げている最も大きな要因は、“ほとんど同じデータ”のソートが極端に速いということで、そして、それ以外の場合でも極端に遅いという場合が無いのも平均性能を高くしています。

ヒープとは「2分木」のデータ配列的表現です。（木については4章を参照）　（なお、ヒープメモリのヒープは意味が違います）

したがってある配列のデータ配置がヒープであるならば、2分木の性質を持ちますから、次のことが保障されます。

「あるノードがiにあるとすると、その子ノードは2i（左の子）と2i+1（右の子）に位置する」

逆に言うと、この性質（ヒープ条件と言います）を満たしていないのであれば、そのデータ配列はヒープではありません。

ヒープ条件が成り立つことによって、トラバースが容易に出来ます。

VOID SORTER::Heap(INT* pData,INT Amount,INT Dammy)

{

INT i,n,v;

INT Parent, LChild , RChild;

n = Amount, i = Amount>>1;

while(TRUE)

{

if (i > 0)

{

i--;

v = pData[i];

}

else

{

n--;

if (n <= 0)

{

return;

}

v = pData[n];

pData[n] = pData[0];

}

Parent = i;

LChild = (i<<1)+1;

while (LChild < n)

{

RChild =LChild+1;

if (RChild<n)

{

if(pData[RChild] > pData[LChild])

{

LChild++;

}

}

if (pData[LChild] <=v)

{

break;

}

pData[Parent] = pData[LChild];

Parent = LChild;

LChild = (LChild<<1) + 1;

}

pData[Parent] = v;

}

}

コームソート及びコームソート11（Comb Sort Comb Sort11）

コームソートはバブルソートの改良版で、スティーブン・レイシー（Stephen Lacey）とリチャード・ボックス（Richard Box）によって発明されたアルゴリズムです。

バブルソートでは要素1個分の間隔で比較しますが、コームソートは、一定の間隔で比較し、その範囲内ではバブルソートを行います。

一定の間隔はギャップ（Gap）と呼びます。

ここで読者は、「あれっ、どっかで聞いたような…」と思うでしょうか。そうです、シェルソートがインサーションソートに対して行った改良と同じです。

コームという名前は、ソートの流れを髪を櫛でとかす（コームComb）ことに例えたことに由来します。

コームソート

VOID SORTER::Comb(INT* pData,INT Amount,INT Dammy)

{

INT i,k;

INT Gap = Amount;

BOOL Swapped=FALSE;

while(TRUE)

{

Gap = (Gap * 10) / 13;

if (Gap < 1)

{

Gap=1;

}

Swapped = FALSE;

for (i = 0; i < Amount - Gap; i++)

{

k = i+Gap;

if (pData[i] > pData[k])

{

INT_SWAP(pData[i], pData[k]);

Swapped = TRUE;

}

}

if (Gap <= 1 && !Swapped)

{

break;

}

}

}

コームソート11

コームソートのギャップが9と10の場合に限って、ギャップを強制的に“11”に固定するとパフォーマンスが“やや”上がることが知られています。

そのような改良を加えたものはコームソート11と呼ばれます。通常のコームソートとの違いは、ギャップを強制的に11にする部分だけです。

VOID SORTER::Comb11(INT* pData,INT Amount,INT Dammy)

{

INT i,k;

INT Gap = Amount;

BOOL Swapped=FALSE;

while(TRUE)

{

Gap = (Gap * 10) / 13;

if (Gap == 9 || Gap == 10)//9と10の場合、強制的にギャップを11にする

{

Gap=11;

}

if (Gap < 1)

{

Gap=1;

}

Swapped = FALSE;

for (i = 0; i < Amount - Gap; i++)

{

k = i+Gap;

if (pData[i] > pData[k])

{

INT_SWAP(pData[i], pData[k]);

Swapped = TRUE;

}

}

if (Gap <= 1 && !Swapped)

{

break;

}

}

}

5-3 系ソート

バケットソート（Bucket Sort）

バケットソートは交換及び比較すらも発生しないため、超高速なソートアルゴリズムです。そして、本書の他のソート2つと比較して最も理解しやすいアルゴリズムです。なぜなら、他の2つはバケットソートを原型としているからです。バケットソートは他の2つに比べ原型のみなのでよりシンプルなのです。

３つのソートアルゴリズムにおける根底の原理は共通です。根底原理とは、「とり得る値の範囲分だけの“箱”を用意し、そこに要素を入れていく」というロジックです。これはピジョンホールソート（鳩の巣箱ソート）と呼ばれます。ピジョンホールソート自体はカテゴリー的な概念です。欧米では細かな入れ物に物を整理整頓することをピジョンホールと呼ぶところに由来します。

なかでもバケットソートは、ピジョンホールソートの原型とも言え、根底原理をそのまま素直に表現したものと言えます。これがバケットソートが最も理解しやすいという理由です。

他方、ラディックスソートはバケットソートの省メモリバージョンで、メモリ節約のためのロジックが加わるため、多少複雑になります。

そしてインバースマップソートは、ピジョンホールソートの一種なので、もちろん根底原理そのものはバケットやラディックスと同類ですが、箱に“入れるもの”が異なり、最も理解が困難でしょう。

さて、バケットソートの原理を具体的に解説しましょう。

大まかな流れ

まずは、大まかな流れを示します。

�@　バケット用意

とり得る値の範囲だけのバケット“箱”を用意します。要素数ではありません。

例えば、要素数が100個だけだとしても、各要素がDWORD値の全範囲を取り得るとしたら、約43億個（4294967296個）のバケットを用意しなくてはならず、

逆に要素数が1億あったとしても、各要素の値が0から100までの値しかとらないのであれば、バケットは101個あれば足りることになります。

�Aワークエリアを用意

要素数と同じだけの領域を確保します。したがって元データと同じ大きさの入れ物を用意するということです。ソートはワークエリア上で完成し、最終的にはワークエリアの内容を元データにコピーします。

�B　バケットに詰め込む

ある要素の値が添え字であるバケットのサイズをインクリメントしてゆきます。

つまり例えば、Data[100]の値が70だとしたら、Bucket[70]++とするということです。

巷にはバケットソートと言いつつ、そうではないものをたまに見かけます。そのようなソートはこの作業を行わないので、同じ値の要素があったときに対処できません。

バケットおよびそのサイズはワークエリアにデータを詰め込むときのオフセットとして機能します。

�C　要素を対応するバケットに詰め込んでゆく

�@〜�Bは言ってみれば準備部分であり、ここが実質的なソート部分です。もっともソートといっても、要素の値をインデックスとして、そのインデックスのワークエリアに事務的に詰め込んでいくので簡単です。（そして高速です）

�D　ワークエリアを元データにコピーする

これはそのままです。解説は不要でしょう。なお、当然関数内で確保したメモリ（バケット、ワークエリア）は開放します。

以上です。

詳細

では、VOID SORTER::Bucket関数のコードを見ながら、詳しくみていきましょう。

図を交えて解説します。

まずはコードの前半部分から、

VOID SORTER::Bucket(INT* pData,INT Amount,INT MaxRange)

{

INT i;

INT Range=MaxRange+1;

INT *BacketSize= (INT*)new INT[Range+1];

INT *DataWorkArea = (INT*)new INT[Amount];

ZeroMemory(BacketSize,sizeof(INT)*Range);

for(i=0; i<Amount; i++)

{

INT Index = pData[i]+1;

BacketSize[Index]++;

}

元データが次のようになっているとします

図5-5

データはそれぞれ0から10の値を取ることが分かっているとすると、用意するバケットは11個です。

最初はpData[0]からバケットサイズを計算します。pData[0]の値は7なので7+1=8、バケットのインデックス8の場所をインクリメントします。BucketSize[8]++

図5-6

以降同様にインクリメントしてゆきます。

図5-7

図5-8

図5-9

図5-10

これで、バケットサイズはとりあえず完了です。

これは言い換えると、「分布をとっている」ことでもあります。バケットソートが“分布数えソート”とも言われる理由はこのためです。

このあと、バケットサイズをオフセットとして機能させるために、ある工夫を施します。工夫とは、直前のバケットサイズの値をどんどん足していくというものです。

for(i=1;i<Range;i++)

{

BacketSize[i] += BacketSize[i-1];

}

図5-11

図5-12

図5-13

図5-14

これで全ての準備が完了です。いよいよソート作業に移ります。

for(i=0;i<Amount;i++)

{

INT Index = pData[i];

INT Stride = BacketSize[Index];

DataWorkArea[Stride] = pData[i];

BacketSize[Index]++;

}

準備が完了した直後に、それぞれは次のようになています。

図5-15

これを利用してソートを行います。

ソートと言っても、やっていることは参照と格納であり、比較や交換が発生しません。そのため高速な整列が可能です。

pData[]からDataWorlArea[]に、どんどん値を格納してゆきます。

pData[]のほうは先頭から尻尾まで順番に進みまずが、DataWorlArea[]はBucketSizeを参照し、該当するオフセット位置に格納されます。これはすなわちソートしていることになります。

右側にはプログラム中での変数がその時点で刻々とる値を書いています。コードと照らし合わせながら丁寧に追ってください。

図5-16

図5-17

図5-18

図5-19

図5-20

図5-21

図5-22

図5-23

図5-24

図5-25

DataWorkArea[]を見てください。お見事です。

あとは、DataWorkArea[]を元データであるpData[]にコピーして完成です。

memcpy(pData,DataWorkArea,sizeof(INT) * Amount);

delete (INT*)DataWorkArea;

delete (INT*)BacketSize;

}

ラディックスソート（Radix Sort）

ラディックスソートは、データを基数ごとに分割し、それぞれの基数グループではバケットソートを適用するというもので、ハロルド・H・シュワード（Harold H. Seward）によって発明されたアルゴリズムです。

基数は日常的な10ではなく、8bit単位で分けます。つまり256です。

したがってデータが32ビットであれば4分割されることになります。そして4つのそれぞれについてバケットソートを施します。

なぜ、基数で分けるのでしょう？

それはメモリを節約するためです。

バケットソートでは、DWORDであればそれがそのままとりうる値の範囲になるので、とりうる値の種類は43億種類にもなってしまいますが、8bitごとに分けられたそれぞれの領域でのデータの種類は256種類の範囲内で収まることが保障されるので、用意するバケットが256個で済むのが最大唯一のメリットです。

その代償として処理速度はバケットソートより低速になりますが、ピジョンホールソートなので超高速ソートに分類されることに変わりはありません。

VOID SORTER::Radix(INT* pData,INT Amount,INT Dammy)

{

INT i,j;

INT shift;

INT *temp=(INT*)new INT[Amount];

INT BucketSize[256], BucketOffset[256];

ワークエリアとして要素数分のメモリ領域（temp）と、バケット（BucektSize,BucketOffset）を用意します。

for(shift=0; shift<32; shift+=8)

{

32ビット値であることが分かっているので、shift<32とし、8ビットずつ進めます。shitf+=8

したがって、このループは4回転します。

ZeroMemory(BucketSize,sizeof(BucketSize));

for(j=0; j<Amount; j++)

{

i=(pData[j]>>shift)&255;

BucketSize[i]++;

temp[j]=pData[j];

}

この部分で行っていることは、32ビットのうち8ビット（4分の1部分）について分布を数えているというものです。分布数え自体はバケットソートと同じですね。

それともう一つこの部分で行っていることは、ワークエリアtemp[]に元データpData[]を単純にコピーしています。

BucketOffset[0]=0;

for(i=1; i<256; i++)

{

BucketOffset[i]=BucketOffset[i-1]+BucketSize[i-1];

}

この処理もバケットソートにおけるオフセットの初期化と同じです。

for(j=0; j<Amount; j++)

{

i=(temp[j]>>shift)&255;

pData[BucketOffset[i]]=temp[j];

BucketOffset[i]++;

}

この部分で行っていることは、4分割した領域から元データにコピーしています。単純にコピーするのではなく、バケットを参照してコピーしています。上手い具合に、同時にソートしていることになります。

画期的なロジックです。これはラディックスソート（の原理になっているバケットソート）が“安定ソートであるがゆえ”に成せる技です。

安定ソートとは、同じ値の要素の順番、前後の位置関係がソート前とソート後で崩れないソートのことを言います。

一方、非安定ソートとは、ソート後に同じ値の要素間の位置関係が不定のソートを言います。

もちろん非安定ソートでも、ソート自体が不安定（うまくいかない）ということではありません。同じ値同士の前後関係が変化したとしても通常は問題ないわけですから。

例えば、

ソート前が4,3,2,2,1であるとして

安定ソートでも非安定ソートでもちゃんと

1,2,2,3,4

となります。ただ、非安定ソートでは、ソート前の3番目の2と4番目の2の前後関係がずれるかもしれないということです。ですので最初の位置関係が崩れては困る場合は、非安定ソートを採用しないほうがいいでしょう。

}

delete temp;

}

これは何も言うことは無いでしょう。

インバースマップソート（Inverse-map Sort）

まず最初に言っておくと、このソートのコードが最も難しいです。根底原理そのものはさほどでもないですが、コードはかなり入り組んでいます。

インバースマップソートを理解するにあたり、バケットソートと対比すると理解の助けになる可能性があるので、ちょっとここでバケットソートの根底原理と比べてみましょう。

バケットソートの根底原理は、取り得る値の範囲だけ用意したバケットにデータの値を格納していくというものでしたね。

図5-26

バケットソートでは、バケットに入れるものは値でしたが、インバースマップでは“インデックス”を入れます。

図5-27

D[3]のインデックスは0、D[1]のインデックスは1、D[0]のインデックスは2、D[2]のインデックスは3です。

あとはD[M[i]]を書き出せば、それがソート結果です。

なお、Mの要素を最初に-1にしているのは、同じ値に対処するためのテクニックですが根底原理上は深く考える必要はありません。

さて、バケットソートのコードは図5-26ほど単純ではなかったですよね。それはなぜでしょう？

それは「同じ値の要素がある場合に対応する」コード上の工夫のためです。図5-26をそのままコードにしていいのなら、ワークエリアは要らなかったのですから。

インバースマップのコードにも全く同じことが言えます。「同じ値の要素がある場合に対応する」ために、かつ、高速性を追求するために、一寸の隙もない高度に研ぎ澄まされた非常に難解なコードになります。

VOID SORTER::InvMappingSort(INT* pData, INT Amount, INT MaxRange)

{

INT i,k;

INT *pDataWorkArea , *pRange;

INT *pDataCur, *pRangeCur, *pDataWorkAreaCur;

pRange = (INT *) new INT[MaxRange+1];

pDataWorkArea = (INT *) new INT[Amount];

memset(pRange,-1,sizeof(INT)*MaxRange+1);

//前半処理

INT Cur = Amount - 1;

pDataCur = pData + Cur;

pDataWorkAreaCur = pDataWorkArea + Cur;

INT *pTmp;

while(pDataCur >= pData)

{

pTmp = pRange+*pDataCur;

*pDataWorkAreaCur = *pTmp;

*pTmp = Cur;

pDataCur--;

pDataWorkAreaCur--;

Cur--;

}

//後半処理

pDataCur = pData;

pRangeCur = pRange;

k=0;

INT *pLastRange = pRange + MaxRange;

while( pRangeCur <= pLastRange)

{

i = *pRangeCur;

pRangeCur++;

while(i >= 0)

{

*pDataCur = k;

pDataCur++;

i = *(pDataWorkArea + i);

}

k++;

}

delete pDataWorkArea;

delete pRange;

}

VOID SORTER::InvMappingSort(INT* pData, INT Amount, INT MaxRange)

{

INT i,k;

INT *pDataWorkArea , *pRange;

INT *pDataCur, *pRangeCur, *pDataWorkAreaCur;

pRange = (INT *) new INT[MaxRange+1];

pDataWorkArea = (INT *) new INT[Amount];

用意するメモリ領域は、量的にはバケットソートと同一です。

取り得る値の範囲の個数だけバケットを用意します。ここではpRangeの指す領域がそれです。

そして、ワークエリアも用意します。ワークエリアのサイズは元データのサイズと同じです。

あと、ポインターを3つ用意します。

元データ内を移動するカーソルポインタ、pDataCur

バケット内を移動するカーソルポインタ、pRangeCur

ワークエリア内を移動するカーソルポインタ、pDataWorkAreaCur

がそうです。

memset(pRange,-1,sizeof(INT)*MaxRange+1);

バケットの要素全てを-1にしておきます。

//前半処理

INT Cur = Amount - 1;

pDataCur = pData + Cur;

pDataWorkAreaCur = pDataWorkArea + Cur;

INT *pTmp;

while(pDataCur >= pData)

{

pTmp = pRange+*pDataCur;

*pDataWorkAreaCur = *pTmp;

*pTmp = Cur;

pDataCur--;

pDataWorkAreaCur--;

Cur--;

}

この前半処理で行っていることは、「図5-27の処理」です。

while(pDataCur >= pData)

ループの進行方向は、データの尻尾→データの先頭です。

それと、ワークエリアを利用して「同じ値」がある場合にワークエリアを-1から次の値のインデックスに書き換えます。つまり“リンク”にします。

どうゆうことかと言うと、図で見たほうが早でしょう。まず次の3つ例を見てください。

図5-28

それぞれの元データに対して、ワークエリアがどのようになるかを示しています。

これを見て、何か法則性があると思いませんか？

同じ数がある場合、若い要素から、次に出てくる同じ値の要素への“インデックス”を入れます。つまり“リンク”します。それ以降にもまた同じ値があれば、どんどんリンクしていきます。こうすれば、同じ値が何個あっても対応できます。次図は分かり易く矢印で結んだものです。

図5-29

もしデータの要素が全て異なる値であれば、ワークエリアの全ての要素は-1のままです。

//後半処理

pDataCur = pData;

pRangeCur = pRange;

k=0;

INT *pLastRange = pRange + MaxRange;

while( pRangeCur <= pLastRange)

{

i = *pRangeCur;

pRangeCur++;

while(i >= 0)

{

*pDataCur = k;

pDataCur++;

i = *(pDataWorkArea + i);

}

k++;

}

後半部分では、実際に元データをソート結果に書き換えています。

while( pRangeCur <= pLastRange)

ループの進行方向は、バケットの先頭→末尾です。

内側にもループがあります。

while(i >= 0)

これは同じ値がある場合の対応です。

i = *(pDataWorkArea + i);

これがミソで、

ワークエリアが-1、すなわちそれ以降にもう同じ値が無いのであればループから抜け、

-1以外、すなわち“同じ値”がそれ以降にあるのであれば、iが次の“同じ値”への距離になるという上手い仕組みです。

delete pDataWorkArea;

delete pRange;

}

これは問題ないでしょう。

6章　パターンマッチング（文字列検索）

ある集合のなかに任意のパターンを見つけること、パターンと一致する部分があるかどうかを調べることをパターンマッチングと言います。

ここでは、大きなテキストの中から特定の文字列パターンと一致する部分を検索するというパターンマッチングを行います。

パターンマッチングのアルゴリズムは、ソートほどバリエーションがありません。

本書サンプルが実装するパターンマッチングのアルゴリズムは4つです。

力技（ブルート　アルゴリズム）

力技改良版（ラピッド　アルゴリズム）

KMP法（Knuth-Morris-Pratt　クヌース・モリス・プラット　アルゴリズム）

BM法（Boyer-Moore　ボイヤー・ムーア　アルゴリズム）

アルゴリズム間での性能差もソートほど顕著ではありません。

面白いことに、もっとも安易で簡単な力技アルゴリズムが劇的に遅いというわけではないことです。むしろ、KMP法より速い場合が多いという測定結果が出ました。KMP法が速いのはバイナリーパターンだけであり（速いといってもBM法には負けます）、その他では力技アルゴリズムにすら負けます。

そして場合によっては力技のほうがいい場合もあります。それについては6-5節で理由を述べます。

BM法は全ての状況において最速です。つまり、どのアルゴリズムを適用するかで悩む必要はないわけです。BM法ただ一つを覚えておけばいいでしょう。

力技アルゴリズムはパターンマッチングの概要を把握するのには有効だと思いますので、一応BM法以外のものも解説します。なお、KMP法は理解するメリットがないので解説は割愛し、サンプルコードだけとします。

共通事項

まず最初に、各アルゴリズムの解説中に使用する用語の定義を述べておきます。

パターン…サーチする文字列です。キーワードとも言います。

テキスト…パターンを含む（含まないかもしれない）大きな文字群です。このテキストの中からパターンを探します。

6-1 力技アルゴリズム（ブルートサーチ）

力任せのアルゴリズムをブルートフォース的アルゴリズムとかブルートアルゴリズムと言いますが、ここではパターンマッチングにおけるブルートアルゴリズムをみてみましょう。

おそらく、ほとんどの人が書くコードは次のようなブルートアルゴリズムでしょう。言い方を変えるとほとんどの人はこのアルゴリズムを書けるのではないでしょうか。

INT BruteSearch(CHAR *p, CHAR *a)

{

INT M = strlen(p);

INT N = strlen(a);

for(INT i=0;i<N;i++)

{

for(INT k=0;k<M;k++)

{

if(a[i+k] != p[k])

{

break;

}

}

if(k==M)//一致があった

{

return i;

}

}

return N;//一致なし

}

テキストの最初から、2重ループにより1文字づつ調査を進めていくという単純なものです。

ソートのときには、このような素直なコードは相対的に非常に遅いアルゴリズムでしたが、パターンマッチングにおいては、“悪くありません”。ただし、BM法が全ての面で速いということが分かっているのでブルートアルゴリズムを採用する理由がないことに変わりはありません。

6-2 力技改良版アルゴリズム（ラピッドサーチ）

ブルートアルゴリズムに若干の改良を施したものが次のコードです。同じく力技的なアルゴリズムで、安易であることにかわりはないのでラピッドサーチと呼ぶことにします。安易といっても、何度も述べているように積極的に非難されるような遅さではなく、むしろKMP法よりは速いです。

INT RapidSearch(CHAR *p, CHAR *a)

{

INT i,k;

INT M = strlen(p);

INT N = strlen(a);

for (i = 0,k = 0; k < M && i < N; i++, k++)

{

if (a[i] != p[k])

{

i -= k-1;

k = -1;

}

}

if (k == M)

{

return i-M;

}

else

{

return i;

}

}

6-3 BM法

BM法は、多くのテキストエディタで採用されている高速なアルゴリズムです。

原理のキーポイントは、

「（パターンの右端をまず比較し、）異なれば1文字以上の幅でスキップする。」

ということであり、それだけです。

力技において、不一致である場合のスキップ量（テキスト内の比較カーソルを進める歩幅）も1文字分でしたが、BM法ではもっと大きな幅でスキップします。それにより、非常に少ないステップ数になります。

極端に言うと、100文字のテキストで、パターンが10文字長だとすると、ブルートアルゴリズムの場合は、100回のステップ数になるのに対し、BM法は10回のステップしか要しません。（ただし最良の場合で）

コードは長いですが、この原理をコーディングしているに過ぎません。

コードは次のようになります。

#define MaxPatLength 100 //パターン文字列の最大長(100文字を越える場合は適宜この値を変更する）

//グローバル

INT Skip[256]; //スキップ量（256個のキャラクターまで対応、つまりANSI文字にのみ対応）

INT Shift[MaxPatLength];//シフト量

//

//INT BMSearch(CHAR *p, CHAR *a)

//ボイヤー・ムーア　サーチ

INT BMSearch(CHAR *p, CHAR *a)

{

INT i,k;

INT La=strlen(a);//テキストの長さ

INT Lp=strlen(p);//パターン文字列の長さ

INT Index=Lp-1;//パターン文字列の長さ-1。パターンの右端のインデックスを意味する

//前処理備部分

{

INT DeadEnd;//

INT Matches[MaxPatLength];//

for ( i = 0; i < 256; i++)

{

Skip[i] = Lp;

}

for ( i = 0; p[i] !=NULL ; i++)

{

Skip[p[i]] = Index - i;

}

//シフトの初期化

Shift[0] = 1;

for ( i = 1; i < Lp; i++)

{

Shift[i] = Lp;

}

//パターンの最終文字と同じ文字がパターン中にある場合に備えたシフトの補正

for ( i = 1; i < Lp; i++)

{

for ( k = 0; k < Lp - i && p[Index - k] == p[Index - i - k]; k++);

Matches[i] = k;

}

for ( i = Index; i > 0; i--)

{

Shift[Matches[i]] = i;

}

//別の可能性に備えたシフトの補正 （ほとんど該当しないが、本サンプル２進数サーチの時に該当する）

DeadEnd = 0;

for ( i = 0; i < Lp; i++)

{

if (Matches[i] == Index - i)

{

DeadEnd = i;

}

if (DeadEnd)

{

Shift[i] = DeadEnd;

}

}

}

//サーチ部分

{

INT RightPos=Index;//パターン右端に対応する”テキスト上”の位置

while (RightPos < La)

{

for ( i = 0; i < Lp && a[RightPos - i] == p[Index - i]; i++);

if (i == Lp)

{

return RightPos - Index;//一致したので、一致場所を返す。

}

RightPos = max(RightPos - i + Skip[a[RightPos - i]], RightPos + Shift[i]);

}

return La; //一致無し。テキストの最後尾位置を返す。

}

}

なお、BM法には“弁慶の泣き所”があります。それについては次節で解説しまが、それを差し引いても最速アルゴリズムであることに間違いはありません。

6-4　性能比較

実際にどれくらいの時間がかかるのか、そして4つのアルゴリズム間でどの程度の差があるのかを見てみましょう。

ランダム300万文字

まずはランダムな文字からなるテキスト300万文字から、「gamecording」というパターンをサーチする時間を見てみます。

パターンがある位置を最初、真ん中、最後の3通りについて調べています。

なおパターンはテキスト中にただ一箇所しか出現しないようにしています。

図6-1

全てにおいてBM法が圧勝です。また、全てにおいてKMP法が最下位であることが分かります。

類似300万文字

テキスト内の文字がランダムではなく、パターンに非常によく似た文字列ばかりである場合はどうでしょう。

例えば、

パターン「gamecoding」に対して、

テキストは「gamecodinaamecodingamecodinaamecoding…（300万文字）」などとなっている場合です。

図6-2

結果はランダムテキストと一緒です。

2進文字300万文字から2進数パターンの検索

パターンが2進数、つまり2つの状態しかとらない文字から成り、テキスト側も2進数である場合はどうでしょう。

図6-3

2進数では、KMP法とブルート系アルゴリズムが逆転します。2進数の検索はKMP法が有効である唯一の状況でしょう。

BM法にとって最悪なテキスト

ここまでは、BM法が全てにおいて最速でしたが、実はパフォーマンスが極端に落ちる状況があるにはあります。しかし、そのようなテキストはまず無いので心配はないと思います。

BM法が最悪になる特殊なケースとは、テキストが「パターンの右から2個目の文字ばかりから成る」場合です。

サンプルでは、パターンがgamecodingですから、右から2番目の文字は”n”です。テキストのほとんどが”n”の場合はBM法にとって最悪で他の3つのアルゴリズムと比較しても遅くなります。

なぜ、そのような場合に遅くなるのかというと、BM法の仕組みを理解していればおのずと分かります。

パターンの右から2番目の文字とテキスト上の文字が同じ文字である場合、「スキップ数がたった一文字分」にしかならないからです。したがって、一文字単位で調査を進める“力技と同じに”なってしまいます。そうなってはコードがシンプルな力技より遅くなるのは当然です。

図6-4

BM法が最も遅い結果になっています。

6-5　力技も“使える”アルゴリズム

章の最初で、「場合によっては力技のほうがいい場合もあります。」と述べましたね。というのは、BM法は確かに高速なアルゴリズムですが、それ故、やはりそこにはそれなりの代償が伴います。それに対し、力技アルゴリズムにはその代償を払う必要がないからです。

代償というのは、ワークエリア分のメモリ確保の必要性のことです。

BM法においては、テキスト内に出現しうる文字の種類だけワークエリアが必要になります。例えばANSI文字しかないテキストであることが分かっているのであれば256個、つまり256バイトのワークエリアが必要になります。256バイトであれはその代償は無視できます。しかし、日本語文字列である場合は、何万個もの文字分のメモリが必要になります。ワークエリアが大きいことによるサーチそのものの速度変化はありませんが、初期化時に時間がかかります。テキストが小さい場合は、初期化にかかる時間のほうが大きいことは有り得ます。ただし、O(N)系のソートのように何億個ものワークエリアを必要とするものではないので、その代償は小さいことは小さいです。

あとは、力技とBM法の速度差がソートにおけるそれよりは小さいことも、力技アルゴリズムが“使える”と言った理由です。

ワークエリアのために、テキストの文字セットを調べる工程が面倒だったり、ワークエリアを何らかの理由で確保したくない場合は、あるいはテキストが小規模でBM法による初期化時間のほうが長くなってしまう場合は“力技”を使用したほうがいいでしょう。

特定目的アルゴリズム

7章　A*

サンプルプロジェクト　ch07 Aスター

図7-0

A*のルーツ

平面上で2点間の最短経路を見つけるアルゴリズムは、パス検索アルゴリズム(Path Finding Algorithm)と言います。もちろん障害物を回避したパス（経路）で最短という意味です。

図7-1

障害物を考えなくてもいいのなら最短経路は2点を結ぶ直線なわけで、本章の解説も1行で終わってしまいます。

x+=(x<ゴールx座標)-(x>ゴールx座標);y+=(y<ゴールy座標)-(y>ゴールy座標);

の1行で済ませてしまうと次の図のようになります。

図7-2

…これではあまりにも安易ですよね。これなら小学生でも実装できますし、わざわざ本章を設ける必要はありません。

さて、コンピューター科学の分野で最初にパス検索アルゴリズムを発表したのは、オランダ人のEdsger Wybe Dijkstraです。

彼は、ドイツの権威ある数学雑誌Numerische Mathematikの中で「A note on two problems in connexion with graphs」としてパス検索アルゴリズムを1959年に発表しています。これは後にDijkstra’s Algorithmと呼ばれるようになります。

しかし、Dijkstraアルゴリズムは全てのパスを評価するという力技的なものであるので、確かに最短パスを見つけることが出来るものの、その実行時間が問題になります。

そこで、バカ正直に全ての可能性を計算してしまうDijkstraアルゴリズムに“ゴールまでの予測距離”（ヒューリスティック）を取り入れ、実行速度を上げたアルゴリズムの一般系が提唱されるようになります。そのアルゴリズムは「A アルゴリズム」と呼ばれます。さらにAアルゴリズムを最適化した様々なカスタムバージョンを総称してA*アルゴリズムと呼びます。Aアルゴリズム及び最初のA*アルゴリズムは、1968年にPeter Hart、Nils Nilsson、Bertram Raphaelらによって発表されました。

したがってDijkstraアルゴリズムはA(A*)アルゴリズムにおいて推測値を考慮しない場合の特殊形とも言えます。

なお、A*は「エー・スター」と発音します。

原理と実際の検索過程

原理はけっこう単純ですので、心配は要りません。

なお、一般的なA*とは微妙に異なる筆者独自の仕組みや表現があります。もっともA*自体がAアルゴリズムのカスタムバージョンの総称なので、“一般的なA*”というのも変な話であり、あえて断る必要もないのですが。

さて、まずA*の計算を高速にするためにフィールドを適当な単位に分割します。

図7-3

図7-4

ここで、一つのマス目を“セル”と呼ぶことにします。

セルはリンクドリストとして管理してもいいですし、配列で管理してもいいのですが、何れにしてもセル自身に幾つかの情報を持たせなくてはならないので、セル用の構造体を定義することになるでしょう。

具体的に、セル1個につき最低限持たせる情報は次の5つです。

1．コスト

2.ヒューリスティック

3.スコア

4．ステータス

5.親セルへのリンク

1．コストとは、現在位置（調査しているセル）から出発点（調査を開始した位置）に戻るために要する距離（マス目の数）です。

2.ヒューリスティックとは、現在位置からゴールまでの“推定”距離です。なぜ“推定”なのかというと、考えてもみてください、調査の途中で、ゴールまでの正確なマス数が分かるわけがありません。逆に言うと、もし途中でゴールまでのマス数が分かるのであれば、そもそも調査の必要がないわけです。ゴールまでのマス数を調べるのが目的でなのですから。

サンプルでは、推定距離を開始位置とゴールの間の直線距離により求めています。障害物は一切無視した直線距離です。

3.スコアとは、コストとヒューリスティックを単純に足した値です。次に移動するセルを決定するのにはスコアを基に判断します。調査は最小スコアのセルをどんどん移動していくことにより進めていきます。

4．ステータスとは、セルの状態です。セルは状態を持ち、その状態により重要な判断が可能になります。具体的には次の5つの状態をとります。

�@エンプティ（Empty）…未調査のセル。

�Aオープン（Open）…障害物が無く、通過できるセル。

�Bオブスタクル（Obstacle）…障害物があり、通過することが出来ないセル。

�Cクローズド（Closed）…今まで通過したセル。

�Dゴール(Goal)…ゴールセル。（したがってこのステータスが付くセルは一つのみ）

5.親セルへのリンクは、ゴールセルを見つけたとき、そのリンクを逆に辿ることにより、経路を作成する際に使用します。

調査前において、障害物以外の全てのセルはエンプティであり、コスト、ヒューリスティック、スコアともに値が入っていません。

図7-5

では、実際の調査過程を１ステップずつ見ながら、細かく解説します。あせらずじっくり読めば必ず理解できるはずです。（基本アルゴリズムよりもよっぽど簡単ですよ）

なお、図は全て実際に機能しているサンプルプログラムのキャプチャ画像ですので、これ以上現実的な図はありません。なんならサンプルを実行しながら読んでもらっても構いません。

セル上の文字情報も実際にサンプルが出力しているものであり、紙面上で重ね書きしているわけではありません。

サンプルでのセル上の情報の意味は次の図のとおりです。

図7-6

Cはコスト、hはヒューリスティック、Sはスコア、その下にあるハイフンを挟んだ2つの数字は座標です。図では13-19から22-12までありますね。これはカメラがフィールドの中心付近にあるためです。サンプルのフィールドはけっこう大きく、スクロールによりカメラを移動します。

座標の読み方は、（横座標）-（縦座標）です。横の座標値が右にいくほど増えているのが分かると思います。縦の座標が下に行くほど増えているのも同様です。

一番下の文字はステータスです。｢EMPTY｣｢OPEN｣｢OBSTACLE｣｢CLOSED｣｢GOAL｣の5つの何れかになります。

さぁ、実際に調査を開始していきましょう！

その時調査しているセルを起点として周囲8個のセルについて調べる工程を1ステップとすると、全24ステップで検索を終えます。

ステップ1つにつき1つの図を見ていきます。

まず、1ステップ目は次の図になります。

図7-7

調査開始点は自分がいる場所、座標15-14の位置です。そしてゴールは座標19-19です。

まずは開始点を中心として、周囲8セルを調べます。この場合、周囲には障害物が無いので8つのセルのステータスは全てOPEN（通過し得るセル）にします。そして、開始点は明らかに調査の必要がないので無条件でCLOSEDにします。

ステータス付けと同時に、スコアを計算（スコアリング）します。

コスト（c）は、開始点に戻るのに要する距離（セル数）です。言い換えると開始点からの距離（セル数）とも言えます。この場合、開始点からの距離は全てのセルで1なので、全てコストを1にします。

ヒューリスティック（h）は、ゴールまでの推定距離です。サンプルでは障害物を無視したゴールまでの単純な直線距離をヒューリスティックとしているので、座標15-15,16-15,16-14の3セルはヒューリスティックが5です。実際にゴールまでのセルを数えてみてください。自分自身もカウントするので、そのセルからゴールまでのセル数+1をヒューリスティックとしています。

同様に座標14-15,16-13はヒューリスティックが6、座標14-14,14-13,15-13はヒューリスティックが7です。

コストとヒューリスティックが求まれば、すなわちスコアは自動的に求まります。（スコアはコスト+ヒューリスティック）

あと、図では見えませんが、周囲8つのセルの親を基点セル（15-14）にします。

次に調べるセル位置を決定するには、“最もスコアが小さい”セルに移動します。したがって、スコアが6である3つのセル（15-15,16-15,16-14）が候補に挙がります。

候補となるセルが複数ある場合、どのセルをとってもいいことが分かっています。

サンプルでは、15-15のセルを次の調査の基点セルにします。

これで1つのステップが終了です。基本的にこれの繰り返しを行っていけば、ゴールまでの最短経路が見つかります。

簡単でしかも正確なパラダイムですね。

第2ステップです。第1ステップでの起点セルはCLOSEDにします。CLOSEDにする理由は、再度そのセルを通過してしまうというロスを無くすためです。

図7-8

ステップ1と同じようにスコアリングを行っています。ただし、起点が15-15なので、周囲8セルは当然ステップ1と異なります。

また、周囲8セルと言っても、そのうち6個はすでにステップ1で調査していてすでにステータス付けがされています。したがって、新たに調査するのは上3つだけです。

このステップにおける8セルと今までのOPENセルを含めた中で、スコアが最小なセルは、丁度右側の3つ（16-16,16-15,16-14）です。OPENになっているセル全ての中から最小のものを選びます。

例により3つのうちどれを次の起点にしても良く、サンプルでは16-15を起点にしています。

ステップ3です。

ステップ2の起点はCLOSEDにします。

スコアリング等、今までと同様の計算を行います。

また、次のセルの決定も同様です。サンプルでは17-16のセルを次のセルにします。

図7-9

ステップ4です。

ここで初めて今までと異なる状況になります。

図7-10

17-16の周りには、障害物が含まれます。周囲8セル中5個のセルが障害物です。A*の種類によってはこの時点でセルのステータスを障害物とするものもあると思いますが、本サンプルでは、初期化時においてフィールドをテキストファイルから読み込む時点で既に、OBSTACLE（障害物）にしています。

当然、障害物セルは“通過できないセル”なので次の基点セルになることもありません。したがってスコアリングすることは無意味なのでしません。

障害物以外のセル、すなわちOPENであるセルのうち最小なセルを次の基点セルにします。サンプルでは16-14を次の起点セルにしています。

見た目、逆行しているように感じるかもしれません。しかし既に述べたように、同じスコアであればどのセルを選択しても同じであり、一見逆に進んでいるように見えても、無駄になるわけではありません。

ステップ5です。起点セルは16-14

今までと同様です。

これ以降は、新しい状況は一切なく、すべて今まで説明したことを繰り返すだけですので、図だけ眺めてください。

図7-11

ステップ6です。起点セルは16-16

図7-12

ステップ7です。起点セルは17-15

図7-13

ステップ8です。起点セルは14-15です。ちょっと離れましたね。思い出してください、今まで調査した全てのOPENセルから最小を選ぶことを。

図7-14

ステップ9です。起点セルは16-13です

図7-15

ステップ10です。起点セルは14-16です

図7-16

ステップ11です。起点セルは15-16です

図7-17

ステップ12です。起点セルは17-14です

図7-18

ステップ13です。起点セルは15-13です

図7-19

ステップ14です。起点セルは14-13です

図7-20

ステップ15です。起点セルは14-14です

図7-21

ステップ16です。起点セルは17-13です

図7-22

ステップ17です。起点セルは18-14です

図7-23

ステップ18です。起点セルは19-15です

図7-24

ステップ19です。起点セルは19-16です

図7-25

ステップ20です。起点セルは20-16です

図7-26

ステップ21です。起点セルは19-17です

図7-27

ステップ22です。起点セルは20-17です

図7-28

ステップ23です。起点セルは21-17です

図7-29

ステップ24です。OPENセルの中に、GOALが含まれています。すなわち調査が完了しました。

あとは、そのGOALセルから親セルを逆走査してパスを作ればいいのです。

図7-30

サンプルの説明

キー操作

W,スペース,A,Dキー：主人公の移動。

矢印キー：カメラの移動

Z,Xキー：カメラの高さ調節（画面の大きさ）

リターンキー：パス計算開始

概要

このサンプルはA*により主人公を移動させるだけではなく、計算過程をリアルタイムで表示できます。

セル上にID3DXFONTを利用した文字で情報を表示します。

マップは1種類ではなく、いろいろなパターンを数種類用意しています。マップと言っても障害物の配置を表すテキストファイルです。

Entry.cppの545行あたりでテキストファイルを読み込んでいます。

//FILE *fp=fopen("パターン1.txt","r");

//FILE *fp=fopen("パターン2.txt","r");

//FILE *fp=fopen("パターン3.txt","r");

FILE *fp=fopen("迷路.txt","r");

//FILE *fp=fopen("更地.txt","r");

//FILE *fp=fopen("点在.txt","r");

//FILE *fp=fopen("閉じた場所.txt","r");

確認したいマップのコメントアウトを外し、その他をコメントアウトしてください。

ID3DXFONTのフォントを非常に大量にレンダリングしているので環境によってはかなり遅いかもしれません。動作確認だけであればフォントを表示しなくてもいいので、その場合はフォントのレンダリングを無効にしたほうがいいでしょう。RenderString関数の最初にreturnを追加すればフォントのレンダリングをオフにできます。

VOID RenderString(LPSTR szStr,INT iX,INT iY,D3DCOLOR Color)

{

return;

RECT rect={iX,iY,0・・・・・

コード解説

Aスターはクラスにまとめました。比較的短いコードなので、クラスの全コードを一応掲載します。

解説はポイント部分のみ行います。

A-Star.h

//必要なヘッダーファイルのインクルード

#include <windows.h>

#include <d3dx9.h>

//

#define SAFE_DELETE(p) { if(p) { delete (p); (p)=NULL; } }

#define SAFE_DELETE_ARRAY(p) { if(p) { delete[] (p); (p)=NULL; } }

#define SAFE_RELEASE(p) { if(p) { (p)->Release(); (p)=NULL; } }

//

//データ型定義

//enum ASTAR_STATUS

enum ASTAR_STATUS

{

ASTAR_EMPTY,

ASTAR_OPEN,

ASTAR_CLOSED,

ASTAR_OBSTACLE,

ASTAR_GOAL,

};

//struct CELL

struct CELL

{

POINT ptIndex;

POINT ptParent;

INT iCost;

INT iHeuristic;

INT iScore;

ASTAR_STATUS Status;

BOOL boRealPath;

VOID* ppv1;

VOID* ppv2;

};

//struct ASTAR_INIT

struct ASTAR_INIT

{

CELL* pCell;

DWORD dwCellWidth;

DWORD dwCellHeight;

};

//struct ASTAR_PARAM

struct ASTAR_PARAM

{

CELL* pCell;

POINT ptStartPos;

POINT ptGoalPos;

POINT ptCurrentPos;

};

//class ASTAR

class ASTAR

{

public:

ASTAR();

~ASTAR();

POINT* m_ptPath;

DWORD m_dwPathList;

HRESULT Init(ASTAR_INIT* );

HRESULT CalcPath(ASTAR_PARAM* );

protected:

CELL* m_pCell;

POINT* m_pOpenList;

DWORD m_dwOpenAmt;

POINT* m_pClosedList;

DWORD m_dwClosedAmt;

DWORD m_dwCellWidth;

DWORD m_dwCellHeight;

POINT m_ptVolute[9+1];

POINT m_ptGoal;

HRESULT CalcScore(ASTAR_PARAM*);

HRESULT MakePathFromClosedList(ASTAR_PARAM*);

INT CalcDistance(POINT*,POINT*);

HRESULT Reset();

};

A-Star.cpp

//必要なヘッダーファイルのインクルード

#include "A-Star.h"

//

//ASTAR::ASTAR()

//

ASTAR::ASTAR()

{

ZeroMemory(this,sizeof(ASTAR));

//volute（グルグル　笑）初期化。 ある座標の周り8方向　（起点セルの周囲8セルに移動する際に利用する）

m_ptVolute[0].x=0;

m_ptVolute[0].y=0;

m_ptVolute[1].x=-1;

m_ptVolute[1].y=1;

m_ptVolute[2].x=0;

m_ptVolute[2].y=1;

m_ptVolute[3].x=1;

m_ptVolute[3].y=1;

m_ptVolute[4].x=1;

m_ptVolute[4].y=0;

m_ptVolute[5].x=1;

m_ptVolute[5].y=-1;

m_ptVolute[6].x=0;

m_ptVolute[6].y=-1;

m_ptVolute[7].x=-1;

m_ptVolute[7].y=-1;

m_ptVolute[8].x=-1;

m_ptVolute[8].y=0;

/* 番号と座標の対応は、次のとおり

1 2 3

8 0 4

7 6 5

*/

}

//

//ASTAR::~ASTAR()

//

ASTAR::~ASTAR()

{

SAFE_DELETE_ARRAY(m_pOpenList);

SAFE_DELETE_ARRAY(m_pClosedList);

SAFE_DELETE_ARRAY(m_ptPath);

}

//

//HRESULT ASTAR::Init(ASTAR_INIT* pai)

//

HRESULT ASTAR::Init(ASTAR_INIT* pai)

{

m_dwCellWidth=pai->dwCellWidth;

m_dwCellHeight=pai->dwCellHeight;

m_pCell=pai->pCell;

m_pOpenList = (POINT*) new POINT[ m_dwCellWidth * m_dwCellHeight ];

if(!m_pOpenList)

{

return E_OUTOFMEMORY;

}

m_pClosedList = (POINT*) new POINT[ m_dwCellWidth * m_dwCellHeight ];

if(!m_pClosedList)

{

return E_OUTOFMEMORY;

}

m_ptPath = (POINT*) new POINT[ m_dwCellWidth * m_dwCellHeight ];

if(!m_ptPath)

{

return E_OUTOFMEMORY;

}

return S_OK;

}

//

//

//

HRESULT ASTAR::Reset()

{

DWORD dwMaxAmt=m_dwCellWidth * m_dwCellHeight;

for(DWORD i=0;i<dwMaxAmt;i++)

{

m_pCell[i].iCost=0;

m_pCell[i].iHeuristic=0;

m_pCell[i].iScore=0;

m_pCell[i].boRealPath=FALSE;

ZeroMemory(&m_pCell[i].ptParent,sizeof(POINT));

if(m_pCell[i].Status != ASTAR_OBSTACLE)

{

m_pCell[i].Status=ASTAR_EMPTY;

}

}

m_dwOpenAmt=0;

m_dwClosedAmt=0;

m_dwPathList=0;

ZeroMemory(m_ptPath,sizeof(POINT) * m_dwCellWidth * m_dwCellHeight );

return S_OK;

}

//

//HRESULT ASTAR::CalcPath(ASTAR_PARAM* pParam)

//

HRESULT ASTAR::CalcPath(ASTAR_PARAM* pParam)

{

//ゴールが適正な場所か（ゴールが障害物の内部になっていないか）

if(m_pCell[ pParam->ptGoalPos.y*m_dwCellWidth+pParam->ptGoalPos.x ].Status==ASTAR_OBSTACLE)

{

MessageBox(0,"obstacle","",MB_OK);

return E_FAIL;

}

Reset();

if(SUCCEEDED(CalcScore(pParam)))

{

MakePathFromClosedList(pParam);

}

else

{

MessageBox(0,"動けない","",MB_OK);

}

return S_OK;

}

//

//HRESULT ASTAR::CalcScore(ASTAR_PARAM* pParam)

//

HRESULT ASTAR::CalcScore(ASTAR_PARAM* pParam)

{

DWORD i;

INT iOffset;

POINT ptStart=pParam->ptStartPos;

POINT ptGoal=pParam->ptGoalPos;

POINT ptCurrentPos=pParam->ptCurrentPos;

//現在セルは無条件でクローズドにする

iOffset=ptCurrentPos.x*m_dwCellHeight+ptCurrentPos.y;

if(m_pCell[iOffset].Status != ASTAR_CLOSED)

{

m_pCell[iOffset].Status=ASTAR_CLOSED;

m_dwClosedAmt++;

}

//隣接8セルのスコアリング（オープンリスト作成）

for(i=1;i<=8;i++)

{

ptCurrentPos=pParam->ptCurrentPos;

ptCurrentPos.x+=m_ptVolute[i].x;

ptCurrentPos.y+=m_ptVolute[i].y;

//セルマップの範囲外に到達した場合

if(ptCurrentPos.x<0 || (DWORD)ptCurrentPos.x>m_dwCellWidth || ptCurrentPos.y<0 || (DWORD)ptCurrentPos.y>m_dwCellHeight)

{

continue;

}

iOffset=(INT)ptCurrentPos.x*m_dwCellHeight+(INT)ptCurrentPos.y;

//ゴールセルに到達した場合

if(ptCurrentPos.x == ptGoal.x && ptCurrentPos.y == ptGoal.y)

{

m_pCell[iOffset].ptParent=pParam->ptCurrentPos;//親セルへのリンク

m_pCell[iOffset].Status=ASTAR_GOAL;

m_ptGoal=m_pCell[iOffset].ptIndex;

return S_OK;

}

switch(m_pCell[iOffset].Status)

{

case ASTAR_EMPTY:

m_pCell[iOffset].iHeuristic=CalcDistance(&ptGoal,&ptCurrentPos);

//コストは親のコストに１を足したもの

{

m_pCell[iOffset].iCost=m_pCell [ pParam->ptCurrentPos.x*m_dwCellHeight +(INT)pParam->ptCurrentPos.y ].iCost+1;

}

m_pCell[iOffset].iScore=m_pCell[iOffset].iCost + m_pCell[iOffset].iHeuristic;

m_pCell[iOffset].Status=ASTAR_OPEN;

m_pOpenList[ m_dwOpenAmt ]=ptCurrentPos;

m_dwOpenAmt++;

//８セルの親を現在セルにする

{

m_pCell[iOffset].ptParent=pParam->ptCurrentPos;//親セルへのリンク

}

break;

case ASTAR_OPEN:

case ASTAR_CLOSED:

case ASTAR_OBSTACLE:

continue;

break;

}

}

//オープンリストを含めて最小スコアを、新たな起点セルにする　（クローズドリストの作成）

INT iMinScore=INT_MAX;

POINT ptNextCellIndex={0};

DWORD dwMinIndex=0;

for(i=0;i<m_dwOpenAmt;i++)

{

iOffset=m_pOpenList[ i ].x*m_dwCellHeight+ m_pOpenList[ i ].y;

if( m_pCell[iOffset].iScore < iMinScore && m_pCell[iOffset].Status == ASTAR_OPEN)

{

iMinScore=m_pCell[iOffset].iScore;

dwMinIndex=i;

}

}

iOffset=m_pOpenList[ dwMinIndex ].x*m_dwCellHeight+ m_pOpenList[ dwMinIndex ].y;

ptNextCellIndex=m_pCell[iOffset].ptIndex;

m_pClosedList[ m_dwClosedAmt ]=ptNextCellIndex;

//新たな起点セルによる再帰呼び出し

ASTAR_PARAM Param;

Param.ptStartPos=pParam->ptStartPos;

Param.ptGoalPos=pParam->ptGoalPos;

Param.ptCurrentPos=m_pOpenList[ dwMinIndex ];

Param.pCell=pParam->pCell;

return CalcScore(&Param);

}

//

//HRESULT ASTAR::MakePathFromClosedList(ASTAR_PARAM* pParam)

//

HRESULT ASTAR::MakePathFromClosedList(ASTAR_PARAM* pParam)

{

INT iOffset=0;

INT iBreak=0;

INT iMaxStep=m_dwCellWidth * m_dwCellHeight;

m_dwPathList=0;

// クローズドセル上で、ゴール地点からスタート地点まで親を辿った経路を最終的なパスとする

iOffset=m_ptGoal.x*m_dwCellHeight + m_ptGoal.y;

do

{

if(iBreak>iMaxStep)

{

MessageBox(0,"親のリンクがスタート地点まで繋がっていないか、リンクが循環しています","",MB_OK);

break;

}

iBreak++;

m_pCell[iOffset].boRealPath=TRUE;

iOffset=m_pCell[iOffset].ptParent.x*m_dwCellHeight + m_pCell[iOffset].ptParent.y;

//パスリストに記録（呼び出し元の利便性)

m_ptPath[m_dwPathList]=m_pCell[iOffset].ptIndex;

m_dwPathList++;

}

while(m_pCell[iOffset].ptIndex.x != pParam->ptStartPos.x || m_pCell[iOffset].ptIndex.y != pParam->ptStartPos.y);

return S_OK;

}

//

//INT ASTAR::CalcDistance(POINT* pptA,POINT* pptB)

//

INT ASTAR::CalcDistance(POINT* pptA,POINT* pptB)

{

INT iX=pptA->x - pptB->x;

INT iY=pptA->y - pptB->y;

return (INT)sqrtf( iX*iX + iY*iY );

}

定義部分の説明

enum ASTAR_STATUS

{

ASTAR_EMPTY,

ASTAR_OPEN,

ASTAR_CLOSED,

ASTAR_OBSTACLE,

ASTAR_GOAL,

};

5つのステータスを列挙型で定義しています。

次はセルの構造体定義です。

struct CELL

{

POINT ptIndex;

自分自身の座標です。2次元なのでPOINT型にしました。

POINT ptParent;

親の座標です。原理の解説中では親へのリンクと述べたので、

CELL* pParentという形を想像した読者もいるでしょう。しかし親の座標を保持します。なぜなら、座標をそのままインデックスとすれば親を特定できるからです。リンクだからといってポインターとは限りません。本サンプルは座標でも同様の機能を有します。

座標にすることにより、コードを少なからず削減できることが理由にもなっています。

INT iCost;

INT iHeuristic;

INT iScore;

コスト、ヒューリスティック、スコアを保持する変数です。

ASTAR_STATUS Status;

ステータスを保持する変数です。

BOOL boRealPath;

調査が完了したときに、経路上にあるセルにおいて、このフラグがTRUEになります。つまり、このフラグが1であるセルを並べると経路になります。

VOID* ppv1;

VOID* ppv2;

};

ppv1は、呼び出し側（Aスタークラスの外）の何らかのデータを指すポインターです。汎用性を考えこのようにしました。本サンプルでは、Main.cpp側でのThing（メッシュ）を指します。ただし、クラス内でメッシュ等のDirectX依存オブジェクトを使用するなどということをやってしまうと、非常に使いづらいクラスになってしまうので、そうゆうわけではありません。

このポインターを利用するのは、Main.cpp側だけです。コードをシンプルにするためにこうしました。A-Starには本質的に関係ありませんので、深く考えないでください。

ppv2は定義しているだけで、使用していません。

//struct ASTAR_INIT

struct ASTAR_INIT

{

CELL* pCell;

DWORD dwCellWidth;

DWORD dwCellHeight;

};

A-Starクラスを初期化する際に初期化パラメータデータを橋渡しするための構造体です。筆者はよくこのような形でクラスの初期化を行います。

//struct ASTAR_PARAM

struct ASTAR_PARAM

{

CELL* pCell;

POINT ptStartPos;

POINT ptGoalPos;

POINT ptCurrentPos;

};

この構造体は特に定義しなくてもいいものですが、パラメーターをまとめることにより、クラス内および外部からクラスへのパラメーターを渡す部分のコードを減らすことができるので、定義しました。

クラス本体の定義について説明します。

//class ASTAR

class ASTAR

{

public:

ASTAR();

~ASTAR();

コンストラクタ、デストラクタです。

POINT* m_ptPath;

最終的に検索した最短経路セル群へのポインターです。呼び出し側は、このポインターにより経路を知ることになりますので、パブリックにします。クラス内で利用することはありません。

DWORD m_dwPathList;

最終パスを形成するセルの個数です。

HRESULT Init(ASTAR_INIT* );

クラスの初期化関数です。最初に一度しか実行されません。

HRESULT CalcPath(ASTAR_PARAM* );

パス計算関数です。呼び出し側がパスを計算したときに呼ばれます。サンプルではリターンキーを押したときに呼ばれます。なお、厳密に言えばこの関数は本当の仕事をするプライベート関数をコールするだけのラッパー関数です。

本来の仕事はCalcScore関数とMakePathFromClosedList関数の2つが行います。

これ以降はクラス内部で使用するプライベート変数及び関数です。

protected:

CELL* m_pCell;

全てのセルの先頭ポインターです。

POINT* m_pOpenList;

オープンリストの先頭ポインターです。

DWORD m_dwOpenAmt;

オープンリスト内のセルの個数です。

POINT* m_pClosedList;

クローズドリストの先頭ポインターです。

DWORD m_dwClosedAmt;

クローズドリスト内のセルの個数です。

DWORD m_dwCellWidth;

DWORD m_dwCellHeight;

ウィッズはセルが横に何個必要か、その個数です。

ハイトは縦の個数です。

したがってこの2つをかけた個数がセルの総数になります。

POINT m_ptVolute[9+1];

任意の座標の周囲8方向を参照する際の利便性のためこの変数を使用します。

単に起点座標に足すオフセットです。取り得る値は0,1,-1の何れかです。

m_ptVolute[0]は(0,0)なので中心です。（起点座標と同じ座標）

m_ptVolute[1]は左上

m_ptVolute[2]は上

m_ptVolute[3]は右上

m_ptVolute[4]は左

・・・

というように、起点の周りをグルグル回る座標を得たい場合、このようなオフセットテーブルを用意しておくと便利です。

POINT m_ptGoal;

ゴールの座標を保持する変数です。

HRESULT CalcScore(ASTAR_PARAM*);

この関数が主要な仕事を行う、クラスの最重要関数です。

スコアを計算し、ゴールまでのクローズドリストを作成します。

HRESULT MakePathFromClosedList(ASTAR_PARAM*);

CalcScoreが終了し、クローズドリストが作成されたら、この関数により最終的なパスが作成されます。

INT CalcDistance(POINT*,POINT*);

ヒューリスティック値を求める関数です。内容は単純に2点間の直線距離を求めているだけです。

HRESULT Reset();

あたらなパス検索を行う際に、前回の計算内容等を消去し、新たな検索が可能になるようにします。

実装部分の説明

ASTAR::ASTAR()

{

ZeroMemory(this,sizeof(ASTAR));

//volute（グルグル　笑）初期化。 ある座標の周り8方向　（起点セルの周囲8セルに移動する際に利用する）

m_ptVolute[0].x=0;

m_ptVolute[0].y=0;

m_ptVolute[1].x=-1;

m_ptVolute[1].y=1;

m_ptVolute[2].x=0;

m_ptVolute[2].y=1;

m_ptVolute[3].x=1;

m_ptVolute[3].y=1;

m_ptVolute[4].x=1;

m_ptVolute[4].y=0;

m_ptVolute[5].x=1;

m_ptVolute[5].y=-1;

m_ptVolute[6].x=0;

m_ptVolute[6].y=-1;

m_ptVolute[7].x=-1;

m_ptVolute[7].y=-1;

m_ptVolute[8].x=-1;

m_ptVolute[8].y=0;

/* 番号と座標の対応は、次のとおり

1 2 3

8 0 4

7 6 5

*/

}

Volute「渦巻き」状のオフセットとしてm_ptVolute[]を初期化します。

分かり易いようにこのような書き方をしましたが、通常は次のようにループによりもっとスマートに書いたほうがいいでしょう。

DWORD Index=0;

for(INT i=-1;i<=1;i++)

{

for(INT k=-1;k<=1;k++)

{

m_ptVolute[Index].x=i;

m_ptVolute[Index].y=k;

}

}

このコードで初期化した場合、ここでの初期化とは微妙に異なるオフセットになりますが、A*計算には影響は及びません。

ASTAR::~ASTAR()

{

SAFE_DELETE_ARRAY(m_pOpenList);

SAFE_DELETE_ARRAY(m_pClosedList);

SAFE_DELETE_ARRAY(m_ptPath);

}

デストラクタです。クラス内で確保したヒープメモリを開放しています。

HRESULT ASTAR::Init(ASTAR_INIT* pai)

{

m_dwCellWidth=pai->dwCellWidth;

m_dwCellHeight=pai->dwCellHeight;

m_pCell=pai->pCell;

m_pOpenList = (POINT*) new POINT[ m_dwCellWidth * m_dwCellHeight ];

if(!m_pOpenList)

{

return E_OUTOFMEMORY;

}

m_pClosedList = (POINT*) new POINT[ m_dwCellWidth * m_dwCellHeight ];

if(!m_pClosedList)

{

return E_OUTOFMEMORY;

}

m_ptPath = (POINT*) new POINT[ m_dwCellWidth * m_dwCellHeight ];

if(!m_ptPath)

{

return E_OUTOFMEMORY;

}

return S_OK;

}

クラスの初期化関数です。最初に一度だけ呼ばれ、やっていることは

セルの個数、つまりフィールドのサイズと外部で用意されているセルバッファのポインターを記録しています。

また、オープンリスト、クローズドリスト、および最終的なパスを格納するバッファのメモリ確保をしています。

HRESULT ASTAR::CalcPath(ASTAR_PARAM* pParam)

この関数は、単なるラッパー関数です。外部からはこの関数によりパス計算を開始します。本質的にパス検索を行うのは以降で解説するプライベート関数です。

次の関数がクラスの90%以上の仕事を行う関数です。

この関数は一回の呼び出しで、現在セルの周囲8セル分の調査を行いますが、一旦呼び出すと再帰しながらゴールまでの計算を全て行います。

HRESULT ASTAR::CalcScore(ASTAR_PARAM* pParam)

{

DWORD i;

INT iOffset;

POINT ptStart=pParam->ptStartPos;

POINT ptGoal=pParam->ptGoalPos;

POINT ptCurrentPos=pParam->ptCurrentPos;

//現在セルは無条件でクローズドにする

iOffset=ptCurrentPos.x*m_dwCellHeight+ptCurrentPos.y;

if(m_pCell[iOffset].Status != ASTAR_CLOSED)

{

m_pCell[iOffset].Status=ASTAR_CLOSED;

m_dwClosedAmt++;

}

現在の起点セルは無条件でクローズドにできます。

//隣接8セルのスコアリング（オープンリスト作成）

for(i=1;i<=8;i++)

{

ptCurrentPos=pParam->ptCurrentPos;

ptCurrentPos.x+=m_ptVolute[i].x;

ptCurrentPos.y+=m_ptVolute[i].y;

ptCurrentPosは現在セルの座標を保持しています。それにm_ptVolute[]を加算すれば周囲8セルの座標が得られます。

iOffset=(INT)ptCurrentPos.x*m_dwCellHeight+(INT)ptCurrentPos.y;

iOffsetを計算しておきます。iOffsetは全セルの中で現在調べているセル（起点セルの周囲のどれか）のオフセットです。

//ゴールセルに到達した場合

if(ptCurrentPos.x == ptGoal.x && ptCurrentPos.y == ptGoal.y)

{

m_pCell[iOffset].ptParent=pParam->ptCurrentPos;//親セルへのリンク

m_pCell[iOffset].Status=ASTAR_GOAL;

m_ptGoal=m_pCell[iOffset].ptIndex;

return S_OK;

}

調査中にステータスがGOALであるセルが出現した場合は、調査の完了を意味します。

後で親リンクを辿る処理のための準備をして、再帰から脱出するためリターンします。

switch(m_pCell[iOffset].Status)

{

case ASTAR_EMPTY:

m_pCell[iOffset].iHeuristic=CalcDistance(&ptGoal,&ptCurrentPos);

//コストは親のコストに１を足したもの

{

m_pCell[iOffset].iCost=m_pCell [ pParam->ptCurrentPos.x*m_dwCellHeight +(INT)pParam->ptCurrentPos.y ].iCost+1;

}

m_pCell[iOffset].iScore=m_pCell[iOffset].iCost + m_pCell[iOffset].iHeuristic;

m_pCell[iOffset].Status=ASTAR_OPEN;

m_pOpenList[ m_dwOpenAmt ]=ptCurrentPos;

m_dwOpenAmt++;

//８セルの親を現在セルにする

{

m_pCell[iOffset].ptParent=pParam->ptCurrentPos;//親セルへのリンク

}

break;

case ASTAR_OPEN:

case ASTAR_CLOSED:

case ASTAR_OBSTACLE:

continue;

break;

}

}

ステータスがEMPTYの場合に限り、調査を行います。

case文にその他のステータスも記述しているのは拡張性のためであり、本サンプルに限っては無駄です。

//オープンリストを含めて最小スコアを、新たな起点セルにする　（クローズドリストの作成）

INT iMinScore=INT_MAX;

POINT ptNextCellIndex={0};

DWORD dwMinIndex=0;

for(i=0;i<m_dwOpenAmt;i++)

{

iOffset=m_pOpenList[ i ].x*m_dwCellHeight+ m_pOpenList[ i ].y;

if( m_pCell[iOffset].iScore < iMinScore && m_pCell[iOffset].Status == ASTAR_OPEN)

{

iMinScore=m_pCell[iOffset].iScore;

dwMinIndex=i;

}

}

現在の周囲8セル及びそれまでのオープンリストのセルを含め、その中で最小スコアであるセルを調べています。

iOffset=m_pOpenList[ dwMinIndex ].x*m_dwCellHeight+ m_pOpenList[ dwMinIndex ].y;

セルリストから最小スコアセルを参照するためのオフセットを再計算します。

ptNextCellIndex=m_pCell[iOffset].ptIndex;

m_pClosedList[ m_dwClosedAmt ]=ptNextCellIndex;

次の起点セルを最小スコアセルにして、

//新たな起点セルによる再帰呼び出し

ASTAR_PARAM Param;

Param.ptStartPos=pParam->ptStartPos;

Param.ptGoalPos=pParam->ptGoalPos;

Param.ptCurrentPos=m_pOpenList[ dwMinIndex ];

Param.pCell=pParam->pCell;

return CalcScore(&Param);

自分自身を再帰的に実行します。

次の関数は、調査が終了したあと、最終的なパスを作成する関数です。

ゴールセルからどんどん親セルを辿っていき、開始セルに到達すればパスの完成です。

単に逆トラバースするだけなので、なにも難しいことはありません。

HRESULT ASTAR::MakePathFromClosedList(ASTAR_PARAM* pParam)

{

INT iOffset=0;

INT iBreak=0;

INT iMaxStep=m_dwCellWidth * m_dwCellHeight;

m_dwPathList=0;

// クローズドセル上で、ゴール地点からスタート地点まで親を辿った経路を最終的なパスとする

iOffset=m_ptGoal.x*m_dwCellHeight + m_ptGoal.y;

do

{

if(iBreak>iMaxStep)

{

MessageBox(0,"親のリンクがスタート地点まで繋がっていないか、リンクが循環しています","",MB_OK);

break;

}

iBreak++;

m_pCell[iOffset].boRealPath=TRUE;

iOffset=m_pCell[iOffset].ptParent.x*m_dwCellHeight + m_pCell[iOffset].ptParent.y;

//パスリストに記録（呼び出し元の利便性)

m_ptPath[m_dwPathList]=m_pCell[iOffset].ptIndex;

m_dwPathList++;

}

while(m_pCell[iOffset].ptIndex.x != pParam->ptStartPos.x || m_pCell[iOffset].ptIndex.y != pParam->ptStartPos.y);

return S_OK;

}

次の関数は、ヒューリスティックを計算します。

INT ASTAR::CalcDistance(POINT* pptA,POINT* pptB)

{

INT iX=pptA->x - pptB->x;

INT iY=pptA->y - pptB->y;

return (INT)sqrtf( iX*iX + iY*iY );

}

単純な直線距離です。x,y座標は整数なのでこのように計算してもセル数が割り出せます。

以上でA*の解説は終了です。

A*は便利ですが、使い方を誤ると少々酷いことになるかもしれません。要はバランスなのですが、自分のゲームにおいてどの程度までセルの解像度を高くするか、あまり低くすると実際の障害物をすり抜けてしまいますし、逆に不必要に解像度を高くするとメモリを大量に食い、同時に速度も極端に低下するでしょう。

ちなみに、拙書「はじめての3Dゲーム開発」ではA*に依らない筆者オリジナルのパス検索「KamPass」を解説しています。自作ゲームであるカンパニーウォーズではKamPassを使用しA*は一切使用していませんが、800を超えるユニットのパス検索を行っています。

8章　クアッドトリーによる平面分割

図8-1

図8-2

サンプルプロジェクト　ch08 クアッドトリー領域分割

4章で登場したクアッドトリーを利用して2次元フィールドを分割すれば、無駄な計算を省略することができます。

ここでは、50体の相手メッシュの中でレイを当てる必要のあるメッシュをクアッドトリーにより選別します。

選別が無ければそのまま50体に総当りでレイを計算してしまい、非常に時間がかかります。

そこで、クアッドトリーにより好きなだけ平面を分割し、自分がいる単位領域に居る相手メッシュにのみレイ計算を行うおことで高速化を図ります。

選別だけが目的なら境界ボリュームのほうがいい？

最初に言っておきますが、ある一定の領域に居るメッシュにのみ選別するということだけが目的であれば、なにもクアッドトリーを使用する必要はありません。

単純に、全ての相手メッシュの距離と自分の距離を比較して、意図した距離内に居る相手メッシュを選別すればいいのですから。それはすなわち境界球です。あるいは境界ボックスにより選別を行えば、より精度の高い選別も行えるでしょう。

特に次章で解説するオクトトリーであれば境界ボリュームを使用するほうがかなり速いと思います。

ではなぜクアッドトリーやオクトトリーを使用するのか？

それらの木を使用すれば選別だけではなく他に色々な情報を持たせることが出来るからです。本書のサンプルは選別しか行っていませんが、木構造であることによりなんらかの拡張が容易になります。

別の状況、たとえば対象メッシュが動かない場合（3DCGのオフラインレンダリングなどがそうですが）においては、最初に個々の領域内にあるポリゴンを木のノードに格納します。その計算は最初のタイミングに一回だけです。

そうすれば、それ以降のレイトレースにおいて、範囲内判定の計算をすることなく単純にその領域ノードが保持するポリゴンインデックスを参照すれいいので境界ボリュームよりも高速です。ただ本章サンプルおよび一般的なゲームにおいては対象メッシュは通常移動しますから、領域に保持するデータは常に変化し、木による選別のメリットが表面化しないだけです。木による選別はどちらかというと、それこそ個々のメッシュにおけるレイ判定に有効です。なにもしなければメッシュを構成する全てのポリゴンに対しレイ交差判定を行いますが、木により範囲を絞ることにより高速化できます。しかしその場合でも頂点が動く（スキンメッシュ）場合は、本サンプルと同様の状況になります。

別の用途としては、ちょうどサンプルがそうですが、なんらかのガイド（グリッド）をレンダリングしたい場合もあるでしょう。その場合、クアッドトリーやオクトトリーであれば比較的簡単であることはサンプルを見ていただければ分かります。

サンプルの説明

サンプルは、“プニョ”というキャラクターとして作成したメッシュの衝突検出の所要時間を比較します。

所要時間は1フレームにおける所要時間です。

赤いプニョが1個だけあり、それを主人公とします。残りの白いプニョは50個あり、レイを当てる候補対象メッシュ（相手メッシュ）です。

衝突検出はレイによる検出方法とし、レイは主人公から6本飛ばしています。ただし、レイが相手メッシュに交差している場合でもメッセージ等は出ません。目的はあくまでも時間を計測することなので衝突を判断するコードは書いていません。

6本のレイを50個のメッシュ対し交差判定するので、かなり重たい処理です。

まずは、領域による相手メッシュの選別をしない場合、50個のメッシュ全てについてレイ判定を6回行ってしまいます。筆者のマシンでのフレームレートは45fpsでした。

図8-3

サンプル起動直後、なにもしなければ平面（フィールド）の分割レベルは“1”なので平面は4分割されています。

このレベルで、“選別”を行ってみます。画面上では“範囲テストあり（なし）”というメッセージが表示されます。

図8-4

フレームレートが71fpsに上昇しました。これは50個中12個に対象が絞られたのでフレームレートが上昇したのです。

さらに分割レベルを上げて、絞込みをきつくしてみます。

図8-5

対象メッシュが12個から7個に減ったのでフレームレートは71fpsから74fpsに上がりますした。

さらに分割レベルを2段階上げてみます。

図8-6

フレームレートは80fpsまで上がりました。対象はゼロです。筆者のマシンではレイ判定を全くしない状態と同じフレームレートになっています。

使用法

キーボードとの対応は次のとおりです。

F1キー：範囲テストのオン・オフ。

リターンキー：範囲テストを行っている場合、どのメッシュが対象なのか番号と個数を表示・非表示します。

矢印キー：主人公メッシュの移動。

Zキー：分割レベルを下げます。ただしレベル0以下には出来ません。

Xキー：分割レベルを上げます。ただし頂点バッファのキャパシティ関係でレベル8以上には出来ません。

スペースキー：グリッド（分割線）の表示・非表示します。

コード解説

DirectXの運用が目的ではないので、今回はある程度自由にコーディングさせてもらいます。不用なクラスもあるでしょうが、自分にとって不用な部分は無視すればいいだけの話です。今は必要じゃなくとも、いつか役立つ可能性もあると思い、あえて残しておきました。

音で判断する場合も、たまにあります。その場合DirectSoundクラスが便利です。サンプルでは実装はしていますが、使用は一切していません。（wavファイルのロード方法が分かるようにコメントアウトして残している部分はあります）

注目すべき部分

関連するのは、次の5つのファイルだけです。

QuadTree.h

QuadTree_Init.cpp

QuadTree.cpp

Capplication.h

Capplication.cpp

特にQuadTreeクラスが本質です。

あと、多少Direct3Dクラスも関係するかもしれませんが、本質ではありません。

グリッド表示関係

グリッドの表示関連は全てQuadTree_Init.cpp内で行っています。

グリッド表示関係は、本質的には不要な部分です。判定をするにあたりグリッドが表示されている必要があるわけではなく、可視化して開発者が確認することが目的です。

グリッドはライン単位でレンダリングします。まず初期化時に全てのラインを初期化してしまいます。つまりラインの頂点群を全て計算して、バッファに保存します。

レンダリングの際は、Direct3DクラスのCDIRECT3D::RenderWireCell関数にそのバッファを渡します。Direct3Dクラス側は単純にDrawPirimitiveUPにおけるD3DPT_LINELIST手順で頂点群をラインとしてレンダリングします。

工夫しているところと言えば、4分割するのにラインを“2本しか”使用していないというところでしょうか。

なにも工夫しないで単純に考えると、4分割することにより増えるラインは4x4=16本になりますが、それでは爆発的なライン数ひいては頂点数になってしまいます。

次の図を見てください。

図8-7

上の考えかたは、「4分割だから子を4個作る。」というもので、子1個につき4本のラインが必要なので全部で16本のラインとなってしまいます。

下の考え方は、文字通り「分割する線を引く」というもので、これであれば2本の線で4分割できます。本サンプルは下の方法により分割していきます。

例えば本サンプルで分割レベル3の状態では、末端セルは64個になります。

安易な方法でラインを作成すると256本にもなります。

図8-8

ところが、2本の分割線で4分割していくと、同じ分割レベル3、末端セル64個でも必要なラインは42本で足ります。

図8-9

木構造と再帰を組み合わせて、スマートにコーディングできました。木であることがライン作成時にも役立つわけです。

QuadTree_Init.cppでの流れを図示すると次のようになります。

図8-10

範囲テスト関係

範囲テスト関係は全てQuadTree.cpp内に実装しています。

やっていることは比較的単純で、しかも、木の再帰コードなのでコードは非常にすっきりコンパクトになっています。

QuadTree.cpp内のコードは、コメントを含め62行しかないので全コードを載せます。

#include "QuadTree.h"

//

//BOOL QUAD_TREE::CellTestSub(CELL* pNode,D3DXVECTOR3* pvPos,CELL** ppCurrentNode)

//

BOOL QUAD_TREE::CellTestSub(CELL* pNode,D3DXVECTOR3* pvPos,CELL** ppCurrentNode)

{

*ppCurrentNode=NULL;

//そのセルの範囲外なら、そのセルの子孫セルの範囲内なわけがないので、子の調査には進まない

if(pvPos->x < pNode->vMin.x || pvPos->x > pNode->vMax.x

|| pvPos->z < pNode->vMin.z || pvPos->z >pNode->vMax.z)

{

return FALSE;

}

*ppCurrentNode=pNode;

//子ノードを再帰で調べる

if(pNode->pChild[0]!=NULL)

{

//完全4分木なのでpChild[0]がNULLでなければ、その他3つの子もNULLではない

if(CellTestSub(pNode->pChild[0],pvPos,ppCurrentNode))

{

return TRUE;

}

if(CellTestSub(pNode->pChild[1],pvPos,ppCurrentNode))

{

return TRUE;

}

if(CellTestSub(pNode->pChild[2],pvPos,ppCurrentNode))

{

return TRUE;

}

if(CellTestSub(pNode->pChild[3],pvPos,ppCurrentNode))

{

return TRUE;

}

}

return TRUE;

}

//

//HRESULT QUAD_TREE::CellTest(D3DXVECTOR3*pvMyPos,D3DXVECTOR3* pvTargetPos,BOOL* pboInside)

//

HRESULT QUAD_TREE::CellTest(D3DXVECTOR3*pvMyPos,D3DXVECTOR3* pvTargetPos,BOOL* pboInside)

{

//自分がいるセル

CELL *pMyCell=NULL;

CellTestSub(m_pRootNode,pvMyPos,&pMyCell);

//相手がいるセル

CELL *pTargetCell=NULL;

CellTestSub(m_pRootNode,pvTargetPos,&pTargetCell);

//2つのセルのアドレスが同じ（同じセル）ならTRUEを返す

if(pMyCell == pTargetCell)

{

*pboInside=TRUE;

}

else

{

*pboInside=FALSE;

}

return S_OK;

}

どうですか？　非常に短いとは思いませんか？

本サンプルではむしろ、判定にとって必要ではない可視化のためのコード（QuadTree_Init.cpp内コード）が多くなっている格好になっています。

さて、クラス外部かた範囲テストを行うには、まずCellTest関数をコールします。CellTest関数は再帰しません。サブ関数CellTestSubにより自分と相手のノード（位置しているセル）を特定します。

それが分かれば、自分と相手のノードが同じか異なるかで、おなじ領域にいるかどうか判断できます。

CellTestSub関数は再帰しながらノードを走査していき、指定された座標のノードを見つけ、そのアドレスを返します。

したがって、ノードを走査しているCellTestSubのほうがどちらかというと本質部分です。

走査しながらその座標が範囲内かどうかの判断は次の図のように行っていきます。

図8-11

9章　オクトトリーによる空間分割

図9-1

図9-2

サンプルプロジェクト　ch09 オクトトリー領域分割

オクトトリーはクアッドトリーと本質的には全く同じです。

子ノードを4つから8つに増やしたというボリュームの変更のみと考えて差し支えありません。

実際、このサンプルは１から作成したのではなくクアッドトリーサンプルの子ノードを8つに増やしただけあり、あとの変更点といえば平面から空間になるのでクアッドトリーでは一定値にしていたY成分を判断に加えたことくらいです。作成には2時間もかかっていません。そのうち半分以上は動作確認の時間なので実質的には30分程度で出来上がったサンプルです。

コードを見てもらえれば、構造は100%同じであることがわかるでしょう。

子ノードが8つあるため、冗長になるのでコードは載せません。

オクトトリーについて解説することはなにもありません。全てクアッドトリーの章で解説しています。

原理、グリッドの作成、サンプルの内容、ファイルと処理内容の対応、関数の繋がり、キー操作、全てはクアッドトリーと同じです。

なお、分割レベルの上限はクアッドトリーサンプルより低くしています。当然ですが、同じ分割レベルにおける頂点の数は立方体のほうが増えるからです。

10章　階層OBBによる衝突判定

図10-1

サンプルプロジェクト　ch10 階層OBB

OBBは境界ボリュームの中では最も精度が高いものですが、さらにジオメトリの形状にフィットさせたい場合はOBBを階層構造にすることになるでしょう。

部分ごとにそれぞれOBBを持たせることにより、こまかな判定が可能になるのは想像できるでしょう。当然、部分を細かくしていけば精度は上がっていきます。

図10-2

サンプルのキー操作

矢印キー及びインサート、デリートキー：物体B（灰色アニメーションメッシュ）の前後左右上下の移動

スペースキー：ボックスの表示・非表示

コード解説

ちょうどDirect3Dのアニメーションメッシュが自由木による階層構造なので、本サンプルはその流れを利用しOBBを個々のパーツメッシュに持たせています。

OBBそのものに関る解説はGAME CODING vol.1で解説していますので割愛します。

OBBを階層にするのは、Direct3Dアニメーションの手順とまったく同じです。

パーツメッシュの初期化はCreateFrame関数、パーツOBBの初期化はCreateFrameBBox関数

パーツメッシュのレンダリングはDrawFrame関数、パーツOBBのレンダリングはRenderBBoxTree関数

というようになっていて、それぞれの関数の階層走査構造はそれぞれ似ています。

それぞれの関数において、単に“パーツメッシュ”と“OBBメッシュ”が異なるだけと思ってもいいでしょう。

そして結果として、それぞれのパーツメッシュにボックス(OBB)をくっつけた格好になると言ったら分かり易いでしょうか。

OBBの初期化もレンダリングもパーツメッシュにおける初期化とレンダリングとほとんど同じです。

パーツメッシュは親ノードの姿勢を次々と継承してくわけですが、それと全く同じ継承をOBBにもかけます。そうすればそれぞれのOBBは対応するパーツメッシュに見合った姿勢になってくれるというわけです。

Main.h

//必要なヘッダーファイルのインクルード

#include<stdio.h>

#include <windows.h>

#include <d3dx9.h>

//必要なライブラリファイルのロード

#pragma comment(lib,"d3d9.lib")

#pragma comment(lib,"d3dx9.lib")

// シンボル定義及びマクロ

#define WINDOW_WIDTH 800

#define WINDOW_HEIGHT 600

#define SAFE_DELETE(p) { if(p) { delete (p); (p) = NULL; } }

#define SAFE_DELETE_ARRAY(p) { if(p) { delete[] (p); (p) = NULL; } }

#define SAFE_RELEASE(p) { if(p) { (p)->Release(); (p) = NULL; } }

#define THING_AMOUNT 2

//ユーザー定義データ型

struct BBOX

{

D3DXVECTOR3 vMax;

D3DXVECTOR3 vMin;

D3DXVECTOR3 vPivot;

D3DXVECTOR3 vWorldPivot;

D3DXVECTOR3 vAxisX;

D3DXVECTOR3 vAxisY;

D3DXVECTOR3 vAxisZ;

FLOAT fLengthX;

FLOAT fLengthY;

FLOAT fLengthZ;

D3DXMATRIX mRotation;

TCHAR Name[MAX_PATH+1];

BBOX()

{

ZeroMemory(this,sizeof(BBOX));

vAxisX=D3DXVECTOR3(1,0,0);

vAxisY=D3DXVECTOR3(0,1,0);

vAxisZ=D3DXVECTOR3(0,0,1);

}

};

struct THING

{

LPD3DXFRAME pFrameRoot;

LPD3DXANIMATIONCONTROLLER pAnimController;

LPD3DXMESH pMesh;

LPD3DXMESH* ppBBoxMesh;

D3DMATERIAL9* pMeshMaterials;

D3DMATERIAL9* pBBoxMeshMaterials;

LPDIRECT3DTEXTURE9* pMeshTextures;

DWORD dwNumMaterials;

D3DXVECTOR3 vecPosition;

D3DXMATRIX matRotation;

D3DXMATRIX matWorld;

DWORD dwCurrentNode;

DWORD dwNumNode;

BBOX* pBBox;

FLOAT fYaw;

FLOAT fPitch;

THING()

{

ZeroMemory(this,sizeof(THING));

D3DXMatrixIdentity(&matRotation);

D3DXMatrixIdentity(&matWorld);

}

};

//派生フレーム構造体 (それぞれのメッシュ用の最終ワールド行列を追加する）

struct MYFRAME: public D3DXFRAME

{

D3DXMATRIX CombinedTransformationMatrix;

};

//派生メッシュコンテナー構造体(

//コンテナーがテクスチャを複数持てるようにポインターのポインターを追加する）

struct MYMESHCONTAINER: public D3DXMESHCONTAINER

{

LPDIRECT3DTEXTURE9* ppTextures;

};

//Xファイル内のアニメーション階層を読み下してくれるクラスを派生させる。

//ID3DXAllocateHierarchyは派生すること想定して設計されている。

class MY_HIERARCHY: public ID3DXAllocateHierarchy

{

public:

MY_HIERARCHY(){

dwNumNode=0;

}

STDMETHOD(CreateFrame)(THIS_ LPCSTR , LPD3DXFRAME *);

STDMETHOD(CreateMeshContainer)(THIS_ LPCTSTR ,CONST D3DXMESHDATA* ,CONST D3DXMATERIAL* ,

CONST D3DXEFFECTINSTANCE* , DWORD , CONST DWORD *, LPD3DXSKININFO , LPD3DXMESHCONTAINER *);

STDMETHOD(DestroyFrame)(THIS_ LPD3DXFRAME );

STDMETHOD(DestroyMeshContainer)(THIS_ LPD3DXMESHCONTAINER );

DWORD dwNumNode;

};

//関数プロトタイプの宣言

LRESULT CALLBACK WndProc(HWND,UINT,WPARAM,LPARAM);

HRESULT InitD3d(HWND);

HRESULT InitThing(THING *,LPSTR,D3DXVECTOR3*);

VOID Render();

VOID RenderThing(THING*);

RenderBBoxTree(THING* ,LPD3DXFRAME,LPD3DXMATRIX);

HRESULT InitBBox(LPDIRECT3DDEVICE9 ,THING* );

HRESULT CreateFrameBBox(LPDIRECT3DDEVICE9 ,LPD3DXFRAME ,THING* );

BOOL OBBCollisionDetection(DWORD*,DWORD*,THING* ,THING* );

BOOL OBBCollisionDetectionEachBBox(BBOX* ,BBOX* );

BOOL CompareLength(BBOX* ,BBOX* ,D3DXVECTOR3* ,D3DXVECTOR3* );

VOID RenderMeshContainer(LPD3DXMESHCONTAINER , LPD3DXFRAME );

VOID UpdateFrameMatrices(LPD3DXFRAME , LPD3DXMATRIX );

VOID DrawFrame(LPD3DXFRAME );

VOID RenderString(LPSTR ,INT,INT);

VOID FreeDx();

Main.cpp

#include "Main.h"

//グローバルなインスタンスを宣言

LPDIRECT3D9 pD3d = NULL;

LPDIRECT3DDEVICE9 pDevice = NULL;

LPD3DXFONT pFont = NULL;

BOOL boRenderBox=TRUE;

THING Thing[THING_AMOUNT+1];

MY_HIERARCHY cHierarchy;

TCHAR szMeshFilename[MAX_PATH+1];

//

//INT WINAPI WinMain( HINSTANCE hInst,HINSTANCE hPrevInst,LPSTR szStr,INT iCmdShow)

//アプリケーションのエントリー関数

INT WINAPI WinMain( HINSTANCE hInst,HINSTANCE hPrevInst,LPSTR szStr,INT iCmdShow)

{

HWND hWnd = NULL;

MSG msg;

// ウィンドウの初期化

static char szAppName[] = "矢印、インサート、デリートキー：移動　スペースキー：表示トグル";

WNDCLASSEX wndclass;

wndclass.cbSize = sizeof (wndclass);

wndclass.style = CS_HREDRAW | CS_VREDRAW;

wndclass.lpfnWndProc = WndProc;

wndclass.cbClsExtra = 0;

wndclass.cbWndExtra = 0;

wndclass.hInstance = hInst;

wndclass.hIcon = LoadIcon (NULL, IDI_APPLICATION);

wndclass.hCursor = LoadCursor (NULL, IDC_ARROW);

wndclass.hbrBackground = (HBRUSH) GetStockObject (BLACK_BRUSH);

wndclass.lpszMenuName = NULL;

wndclass.lpszClassName = szAppName;

wndclass.hIconSm = LoadIcon (NULL, IDI_APPLICATION);

RegisterClassEx (&wndclass);

hWnd = CreateWindow (szAppName,szAppName,WS_OVERLAPPEDWINDOW,

0,0,WINDOW_WIDTH,WINDOW_HEIGHT,NULL,NULL,hInst,NULL);

ShowWindow (hWnd,SW_SHOW);

UpdateWindow (hWnd);

// ダイレクト３Dの初期化関数を呼ぶ

if(FAILED(InitD3d(hWnd)))

{

return 0;

}

// メッセージループ

ZeroMemory( &msg, sizeof(msg) );

while( msg.message!=WM_QUIT )

{

if( PeekMessage( &msg, NULL, 0U, 0U, PM_REMOVE ) )

{

TranslateMessage( &msg );

DispatchMessage( &msg );

}

else

{

Render();

}

}

// メッセージループから抜けたらオブジェクトを全て開放する

FreeDx();

// OSに戻る（アプリケーションを終了する）

return (INT)msg.wParam;

}

//

//LRESULT CALLBACK WndProc(HWND hWnd,UINT iMsg,WPARAM wParam,LPARAM lParam)

// ウィンドウプロシージャ関数

LRESULT CALLBACK WndProc(HWND hWnd,UINT iMsg,WPARAM wParam,LPARAM lParam)

{

switch(iMsg)

{

case WM_DESTROY:

PostQuitMessage(0);

return 0;

case WM_KEYDOWN:

switch((CHAR)wParam)

{

case VK_ESCAPE:

PostQuitMessage(0);

return 0;

case VK_SPACE:

boRenderBox==TRUE ? boRenderBox=FALSE : boRenderBox=TRUE;

break;

case VK_LEFT:

Thing[1].vecPosition.x-=0.2f;

break;

case VK_RIGHT:

Thing[1].vecPosition.x+=0.2f;

break;

case VK_UP:

Thing[1].vecPosition.z+=0.2f;

break;

case VK_DOWN:

Thing[1].vecPosition.z-=0.2f;

break;

case VK_INSERT:

Thing[1].vecPosition.y+=0.2f;

break;

case VK_DELETE:

Thing[1].vecPosition.y-=0.2f;

break;

}

break;

}

return DefWindowProc (hWnd, iMsg, wParam, lParam);

}

//

//HRESULT InitD3d(HWND hWnd)

//ダイレクト3Dの初期化関数

HRESULT InitD3d(HWND hWnd)

{

// 「Direct3D」オブジェクトの作成

if( NULL == ( pD3d = Direct3DCreate9( D3D_SDK_VERSION ) ) )

{

MessageBox(0,"Direct3Dの作成に失敗しました","",MB_OK);

return E_FAIL;

}

// 「DIRECT3Dデバイス」オブジェクトの作成

D3DPRESENT_PARAMETERS d3dpp;

ZeroMemory( &d3dpp, sizeof(d3dpp) );

d3dpp.BackBufferFormat =D3DFMT_UNKNOWN;

d3dpp.BackBufferCount=1;

d3dpp.SwapEffect = D3DSWAPEFFECT_DISCARD;

d3dpp.Windowed = TRUE;

d3dpp.EnableAutoDepthStencil = TRUE;

d3dpp.AutoDepthStencilFormat = D3DFMT_D16;

if( FAILED( pD3d->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, hWnd,

D3DCREATE_HARDWARE_VERTEXPROCESSING,

&d3dpp, &pDevice ) ) )

{

if( FAILED( pD3d->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, hWnd,

D3DCREATE_SOFTWARE_VERTEXPROCESSING,

&d3dpp, &pDevice ) ) )

{

MessageBox(0,"HALモードでDIRECT3Dデバイスを作成できません\nREFモードで再試行します",NULL,MB_OK);

if( FAILED( pD3d->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_REF, hWnd,

D3DCREATE_HARDWARE_VERTEXPROCESSING,

&d3dpp, &pDevice ) ) )

{

if( FAILED( pD3d->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_REF, hWnd,

D3DCREATE_SOFTWARE_VERTEXPROCESSING,

&d3dpp, &pDevice ) ) )

{

MessageBox(0,"DIRECT3Dデバイスの作成に失敗しました",NULL,MB_OK);

return E_FAIL;

}

}

}

}

// Xファイル毎にメッシュを作成する

InitThing(&Thing[0],"monster.x",&D3DXVECTOR3(0,0,10));

InitThing(&Thing[1],"monster2.x",&D3DXVECTOR3(0,0,0));

// メッシュごとのバウンディングボックス（境界球）の作成

InitBBox(pDevice,&Thing[0]);

InitBBox(pDevice,&Thing[1]);

// Zバッファー処理を有効にする

pDevice->SetRenderState( D3DRS_ZENABLE, TRUE );

// カリングはしない

pDevice->SetRenderState(D3DRS_CULLMODE, D3DCULL_NONE);

// ライトを有効にする

pDevice->SetRenderState( D3DRS_LIGHTING, TRUE );

// アンビエントライト（環境光）を設定する

pDevice->SetRenderState( D3DRS_AMBIENT, 0x00555555 );

// スペキュラ（光沢反射）を有効にする

pDevice->SetRenderState(D3DRS_SPECULARENABLE,TRUE);

//ボックスを透明にレンダリングしたいのでアルファブレンディングを設定する

pDevice->SetRenderState ( D3DRS_ALPHABLENDENABLE, TRUE );

pDevice->SetRenderState ( D3DRS_SRCBLEND, D3DBLEND_SRCALPHA );

pDevice->SetRenderState ( D3DRS_DESTBLEND, D3DBLEND_INVSRCALPHA );

pDevice->SetRenderState( D3DRS_ALPHATESTENABLE, TRUE );

//文字列レンダリングの初期化

if(FAILED(D3DXCreateFont(pDevice,0,10,FW_REGULAR, NULL, FALSE,SHIFTJIS_CHARSET,

OUT_DEFAULT_PRECIS,PROOF_QUALITY,FIXED_PITCH | FF_MODERN, "tahoma", &pFont))) return E_FAIL;

return S_OK;

}

//

//HRESULT InitThing(THING *pThing,LPSTR szXFileName,D3DXVECTOR3* pvecPosition)

//

HRESULT InitThing(THING *pThing,LPSTR szXFileName,D3DXVECTOR3* pvecPosition)

{

cHierarchy.dwNumNode=0;

// メッシュの初期位置

memcpy(&pThing->vecPosition,pvecPosition,sizeof(D3DXVECTOR3));

// Xファイルからメッシュをロードする

if( FAILED(

D3DXLoadMeshHierarchyFromX(szXFileName, D3DXMESH_MANAGED, pDevice, &cHierarchy,

NULL, &pThing->pFrameRoot, &pThing->pAnimController)))

{

MessageBox(NULL, "Xファイルの読み込みに失敗しました",szXFileName, MB_OK);

return E_FAIL;

}

pThing->dwNumNode=cHierarchy.dwNumNode;

return S_OK;

}

//

//VOID Render()

//Xファイルから読み込んだメッシュをレンダリングする関数

VOID Render()

{

// ビュートランスフォーム（ワールド座標→カメラ座標への変換）

D3DXVECTOR3 vecEyePt( 15.0f, 15.0f,-10.0f ); //カメラ（視点）位置

D3DXVECTOR3 vecLookatPt( 0, 5 , 5 );//注視位置

D3DXVECTOR3 vecUpVec( 0.0f, 1.0f, 0.0f );//上方位置

D3DXMATRIX matView;

D3DXMatrixLookAtLH( &matView, &vecEyePt, &vecLookatPt, &vecUpVec );

pDevice->SetTransform( D3DTS_VIEW, &matView );

// プロジェクショントランスフォーム（カメラ座標→スクリーン座標への変換）

D3DXMATRIX matProj;

D3DXMatrixPerspectiveFovLH( &matProj, D3DX_PI/4, (FLOAT)WINDOW_WIDTH/(FLOAT)WINDOW_HEIGHT, 0.1f, 100.0f );

pDevice->SetTransform( D3DTS_PROJECTION, &matProj );

pDevice->Clear( 0, NULL, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER,

D3DCOLOR_XRGB(0,0,0), 1.0f, 0 );

if( SUCCEEDED( pDevice->BeginScene() ) )

{

for(DWORD i=0;i<THING_AMOUNT;i++)

{

RenderThing(&Thing[i]);

}

DWORD IndexA,IndexB;

if( OBBCollisionDetection(&IndexA,&IndexB,&Thing[0],&Thing[1]) )

{

TCHAR sz[200];

RenderString("衝突しています\n境界ボリュームが重なっているということです",10,10);

sprintf(sz,"物体A側のボックス:%s \n物体B側のボックス:%s",Thing[0].pBBox[IndexA].Name,Thing[1].pBBox[IndexB].Name);

RenderString(sz,10,50);

}

pDevice->EndScene();

}

pDevice->Present( NULL, NULL, NULL, NULL );

Thing[0].pAnimController->AdvanceTime(0.0001,NULL);

Thing[1].pAnimController->AdvanceTime(0.00005,NULL);

}

//

//VOID RenderThing(THING* pThing)

//

VOID RenderThing(THING* pThing)

{

//ワールドトランスフォーム（ローカル座標→ワールド座標への変換）

D3DXMATRIX matWorld,matPosition;

D3DXMatrixIdentity(&matWorld);

D3DXMatrixTranslation(&matPosition,pThing->vecPosition.x,pThing->vecPosition.y,

pThing->vecPosition.z);

D3DXMatrixMultiply(&matWorld,&matWorld,&matPosition);

pThing->matWorld=matWorld;

// ライトをあてる 白色で光沢反射ありに設定

D3DXVECTOR3 vecDirection(-1,-0.5,0);

D3DLIGHT9 light;

ZeroMemory( &light, sizeof(D3DLIGHT9) );

light.Type = D3DLIGHT_DIRECTIONAL;

light.Diffuse.r = 1.0f;

light.Diffuse.g = 1.0f;

light.Diffuse.b = 1.0f;

light.Specular.r=1.0f;

light.Specular.g=1.0f;

light.Specular.b=1.0f;

D3DXVec3Normalize( (D3DXVECTOR3*)&light.Direction, &vecDirection );

light.Range = 200.0f;

pDevice->SetLight( 0, &light );

pDevice->LightEnable( 0, TRUE );

UpdateFrameMatrices(pThing->pFrameRoot, &matWorld);

DrawFrame(pThing->pFrameRoot);

//　そのThingに関るバウンディングボックスのレンダリング

if(boRenderBox)

{

pThing->dwCurrentNode=0;

RenderBBoxTree(pThing,pThing->pFrameRoot,&matWorld);

}

}

//

//

//　バウンディングボックスのレンダリング

RenderBBoxTree(THING* pThing,LPD3DXFRAME pFrameBase ,LPD3DXMATRIX pParentMatrix)

{

MYFRAME *pFrame = (MYFRAME*)pFrameBase;

if (pFrame->pFrameSibling != NULL)

{

RenderBBoxTree(pThing,pFrame->pFrameSibling,pParentMatrix);

}

if (pFrame->pFrameFirstChild != NULL)

{

RenderBBoxTree(pThing,pFrame->pFrameFirstChild,&pFrame->CombinedTransformationMatrix);

}

if (pParentMatrix != NULL)

{

D3DXMatrixMultiply(&pFrame->CombinedTransformationMatrix, &pFrame->TransformationMatrix, pParentMatrix);

}

else

{

pFrame->CombinedTransformationMatrix = pFrame->TransformationMatrix;

}

if(pFrame->pMeshContainer !=NULL)

{

pDevice->SetTexture( 0,NULL );

pDevice->SetMaterial( pThing->pBBoxMeshMaterials);

//オブジェクト空間で原点が中心とは限らないので、補正

D3DXMATRIX mWorld;

D3DXVECTOR3 vPivot=pThing->pBBox[pThing->dwCurrentNode].vPivot;

D3DXMatrixTranslation(&mWorld,vPivot.x,vPivot.y,vPivot.z);

pDevice->SetTransform( D3DTS_WORLD, &(mWorld*pFrame->CombinedTransformationMatrix) );

//ワールド座標系としてのボックス中心を保存しておく(それぞれのボックスの回転行列がOBB判定の際に必要なため）

D3DXVec3TransformCoord(&vPivot,&vPivot,&pFrame->CombinedTransformationMatrix);

pThing->pBBox[pThing->dwCurrentNode].vWorldPivot=vPivot;

//姿勢行列の回転部分のみ抽出(それぞれのボックスの回転行列がOBB判定の際に必要なため）

D3DXMATRIX m,m2;

m2=pFrame->CombinedTransformationMatrix;

D3DXMatrixIdentity(&m);

m._11=m2._11;

m._12=m2._12;

m._13=m2._13;

m._21=m2._21;

m._22=m2._22;

m._23=m2._23;

m._31=m2._31;

m._32=m2._32;

m._33=m2._33;

pThing->pBBox[pThing->dwCurrentNode].mRotation=m;

//レンダリング

pThing->ppBBoxMesh[pThing->dwCurrentNode]->DrawSubset(0);

pThing->dwCurrentNode++;

}

}

//

//VOID RenderMeshContainer(LPD3DXMESHCONTAINER pMeshContainerBase, LPD3DXFRAME pFrameBase)

//フレーム内のそれぞれのメッシュをレンダリングする

VOID RenderMeshContainer(LPD3DXMESHCONTAINER pMeshContainerBase, LPD3DXFRAME pFrameBase)

{

MYMESHCONTAINER *pMeshContainer = (MYMESHCONTAINER*)pMeshContainerBase;

MYFRAME *pFrame = (MYFRAME*)pFrameBase;

UINT iMaterial;

pDevice->SetTransform(D3DTS_WORLD, &pFrame->CombinedTransformationMatrix);

for (iMaterial = 0; iMaterial < pMeshContainer->NumMaterials; iMaterial++)

{

pDevice->SetMaterial( &pMeshContainer->pMaterials[iMaterial].MatD3D );

pDevice->SetTexture( 0, pMeshContainer->ppTextures[iMaterial] );

pMeshContainer->MeshData.pMesh->DrawSubset(iMaterial);

}

}

//

//VOID DrawFrame(LPD3DXFRAME pFrame)

//複数のメッシュから成るフレームをレンダリングする。

VOID DrawFrame(LPD3DXFRAME pFrame)

{

LPD3DXMESHCONTAINER pMeshContainer;

pMeshContainer = pFrame->pMeshContainer;

while (pMeshContainer != NULL)

{

RenderMeshContainer(pMeshContainer, pFrame);

pMeshContainer = pMeshContainer->pNextMeshContainer;

}

if (pFrame->pFrameSibling != NULL)

{

DrawFrame(pFrame->pFrameSibling);

}

if (pFrame->pFrameFirstChild != NULL)

{

DrawFrame(pFrame->pFrameFirstChild);

}

}

//

//VOID UpdateFrameMatrices(LPD3DXFRAME pFrameBase, LPD3DXMATRIX pParentMatrix)

//フレーム内のメッシュ毎にワールド変換行列を更新する

VOID UpdateFrameMatrices(LPD3DXFRAME pFrameBase, LPD3DXMATRIX pParentMatrix)

{

MYFRAME *pFrame = (MYFRAME*)pFrameBase;

if (pParentMatrix != NULL)

{

D3DXMatrixMultiply(&pFrame->CombinedTransformationMatrix, &pFrame->TransformationMatrix, pParentMatrix);

}

else

{

pFrame->CombinedTransformationMatrix = pFrame->TransformationMatrix;

}

if (pFrame->pFrameSibling != NULL)

{

UpdateFrameMatrices(pFrame->pFrameSibling, pParentMatrix);

}

if (pFrame->pFrameFirstChild != NULL)

{

UpdateFrameMatrices(pFrame->pFrameFirstChild, &pFrame->CombinedTransformationMatrix);

}

}

//

//VOID RenderString(LPSTR szStr,INT iX,INT iY)

// 情報表示用ルーチン

VOID RenderString(LPSTR szStr,INT iX,INT iY)

{

RECT rect={iX,iY,0,0};

//文字列のサイズを計算

pFont->DrawText(NULL,szStr,-1,&rect,DT_CALCRECT,NULL);

// そのサイズでレンダリング

pFont->DrawText(NULL,szStr,-1,&rect,DT_LEFT | DT_BOTTOM,0xff00ff00);

}

//

//HRESULT MY_HIERARCHY::CreateFrame(LPCTSTR Name, LPD3DXFRAME *ppNewFrame)

//フレームを作成する

HRESULT MY_HIERARCHY::CreateFrame(LPCTSTR Name, LPD3DXFRAME *ppNewFrame)

{

HRESULT hr = S_OK;

MYFRAME *pFrame;

*ppNewFrame = NULL;

pFrame = new MYFRAME;

if (pFrame == NULL)

{

return E_OUTOFMEMORY;

}

pFrame->Name=new TCHAR[lstrlen(Name) + 1];

if (!pFrame->Name)

{

return E_FAIL;

}

strcpy(pFrame->Name,Name);

D3DXMatrixIdentity(&pFrame->TransformationMatrix);

D3DXMatrixIdentity(&pFrame->CombinedTransformationMatrix);

pFrame->pMeshContainer = NULL;

pFrame->pFrameSibling = NULL;

pFrame->pFrameFirstChild = NULL;

*ppNewFrame = pFrame;

pFrame = NULL;

delete pFrame;

return S_OK;

}

//

//HRESULT MY_HIERARCHY::CreateMeshContainer

//メッシュコンテナーを作成する

HRESULT MY_HIERARCHY::CreateMeshContainer(LPCSTR Name, CONST D3DXMESHDATA* pMeshData,

CONST D3DXMATERIAL* pMaterials, CONST D3DXEFFECTINSTANCE* pEffectInstances,

DWORD NumMaterials, CONST DWORD *pAdjacency, LPD3DXSKININFO pSkinInfo,

LPD3DXMESHCONTAINER *ppMeshContainer)

{

dwNumNode++;

HRESULT hr;

MYMESHCONTAINER *pMeshContainer = NULL;

INT iFacesAmount;

INT iMaterial;

LPDIRECT3DDEVICE9 pDevice = NULL;

LPD3DXMESH pMesh = NULL;

*ppMeshContainer = NULL;

pMesh = pMeshData->pMesh;

pMeshContainer = new MYMESHCONTAINER;

if (pMeshContainer == NULL)

{

return E_OUTOFMEMORY;

}

ZeroMemory(pMeshContainer, sizeof(MYMESHCONTAINER));

pMeshContainer->Name=new TCHAR[lstrlen(Name) + 1];

if (!pMeshContainer->Name)

{

return E_FAIL;

}

strcpy(pMeshContainer->Name,Name);

pMesh->GetDevice(&pDevice);

iFacesAmount = pMesh->GetNumFaces();

// 当該メッシュが法線を持たない場合は法線を追加する

if (!(pMesh->GetFVF() & D3DFVF_NORMAL))

{

pMeshContainer->MeshData.Type = D3DXMESHTYPE_MESH;

hr = pMesh->CloneMeshFVF( pMesh->GetOptions(),

pMesh->GetFVF() | D3DFVF_NORMAL,

pDevice, &pMeshContainer->MeshData.pMesh );

if (FAILED(hr))

{

return E_FAIL;

}

pMesh = pMeshContainer->MeshData.pMesh;

D3DXComputeNormals( pMesh, NULL );

}

else

{

pMeshContainer->MeshData.pMesh = pMesh;

pMeshContainer->MeshData.Type = D3DXMESHTYPE_MESH;

pMesh->AddRef();

}

pMeshContainer->NumMaterials = max(1, NumMaterials);

pMeshContainer->pMaterials = new D3DXMATERIAL[pMeshContainer->NumMaterials];

pMeshContainer->ppTextures = new LPDIRECT3DTEXTURE9[pMeshContainer->NumMaterials];

pMeshContainer->pAdjacency = new DWORD[iFacesAmount*3];

if ((pMeshContainer->pAdjacency == NULL) || (pMeshContainer->pMaterials == NULL))

{

return E_OUTOFMEMORY;

}

memcpy(pMeshContainer->pAdjacency, pAdjacency, sizeof(DWORD) * iFacesAmount*3);

memset(pMeshContainer->ppTextures, 0, sizeof(LPDIRECT3DTEXTURE9) * pMeshContainer->NumMaterials);

if (NumMaterials > 0)

{

memcpy(pMeshContainer->pMaterials, pMaterials, sizeof(D3DXMATERIAL) * NumMaterials);

for (iMaterial = 0; iMaterial < NumMaterials; iMaterial++)

{

if (pMeshContainer->pMaterials[iMaterial].pTextureFilename != NULL)

{

TCHAR strTexturePath[MAX_PATH];

strcpy( strTexturePath, pMeshContainer->pMaterials[iMaterial].pTextureFilename );

if( FAILED( D3DXCreateTextureFromFile( pDevice, strTexturePath,

&pMeshContainer->ppTextures[iMaterial] ) ) )

pMeshContainer->ppTextures[iMaterial] = NULL;

pMeshContainer->pMaterials[iMaterial].pTextureFilename = NULL;

}

}

}

else

{

pMeshContainer->pMaterials[0].pTextureFilename = NULL;

memset(&pMeshContainer->pMaterials[0].MatD3D, 0, sizeof(D3DMATERIAL9));

pMeshContainer->pMaterials[0].MatD3D.Diffuse.r = 0.5f;

pMeshContainer->pMaterials[0].MatD3D.Diffuse.g = 0.5f;

pMeshContainer->pMaterials[0].MatD3D.Diffuse.b = 0.5f;

pMeshContainer->pMaterials[0].MatD3D.Specular = pMeshContainer->pMaterials[0].MatD3D.Diffuse;

}

*ppMeshContainer = pMeshContainer;

pMeshContainer = NULL;

if (pMeshContainer != NULL)

{

DestroyMeshContainer(pMeshContainer);

}

SAFE_RELEASE( pDevice );

return S_OK;

}

//

//HRESULT MY_HIERARCHY::DestroyFrame(LPD3DXFRAME pFrameToFree)

//フレームを破棄する

HRESULT MY_HIERARCHY::DestroyFrame(LPD3DXFRAME pFrameToFree)

{

SAFE_DELETE_ARRAY( pFrameToFree->Name );

SAFE_DELETE( pFrameToFree );

return S_OK;

}

//

//HRESULT MY_HIERARCHY::DestroyMeshContainer(LPD3DXMESHCONTAINER pMeshContainerBase)

//メッシュコンテナーを破棄する

HRESULT MY_HIERARCHY::DestroyMeshContainer(LPD3DXMESHCONTAINER pMeshContainerBase)

{

INT iMaterial;

MYMESHCONTAINER *pMeshContainer = (MYMESHCONTAINER*)pMeshContainerBase;

SAFE_DELETE_ARRAY( pMeshContainer->Name );

SAFE_DELETE_ARRAY( pMeshContainer->pAdjacency );

SAFE_DELETE_ARRAY( pMeshContainer->pMaterials );

if (pMeshContainer->ppTextures != NULL)

{

for (iMaterial = 0; iMaterial < pMeshContainer->NumMaterials; iMaterial++)

{

SAFE_RELEASE( pMeshContainer->ppTextures[iMaterial] );

}

}

SAFE_DELETE_ARRAY( pMeshContainer->ppTextures );

SAFE_RELEASE( pMeshContainer->MeshData.pMesh );

SAFE_DELETE( pMeshContainer );

return S_OK;

}

//

//VOID FreeAnim(LPD3DXFRAME pFrame)

//階層内、全てのDirectXオブジェクトをリリースする

VOID FreeAnim(LPD3DXFRAME pFrame)

{

if(pFrame->pMeshContainer != NULL)

{

cHierarchy.DestroyMeshContainer(pFrame->pMeshContainer);

}

if (pFrame->pFrameSibling != NULL)

{

FreeAnim(pFrame->pFrameSibling);

}

if (pFrame->pFrameFirstChild != NULL)

{

FreeAnim(pFrame->pFrameFirstChild);

}

}

//

//VOID FreeDx()

// 作成したDirectXオブジェクトの開放

VOID FreeDx()

{

SAFE_RELEASE( pFont );

for(DWORD i=0;i<THING_AMOUNT;i++)

{

FreeAnim(Thing[i].pFrameRoot);

cHierarchy.DestroyFrame(Thing[i].pFrameRoot);

SAFE_RELEASE( Thing[i].pAnimController);

for(DWORD k=0;k<Thing[i].dwNumNode;k++)

{

SAFE_RELEASE( Thing[i].ppBBoxMesh[k]);

}

SAFE_DELETE_ARRAY(Thing[i].pBBox);

}

SAFE_RELEASE( pDevice );

SAFE_RELEASE( pD3d );

}

OBB.cpp

#include "Main.h"

//

//HRESULT InitBBox(LPDIRECT3DDEVICE9 pDevice,THING* pThing)

//ボックスの計算およびボックスを可視化するためにボックスメッシュを作成する

HRESULT InitBBox(LPDIRECT3DDEVICE9 pDevice,THING* pThing)

{

pThing->pBBox=(BBOX*) new BBOX[pThing->dwNumNode];

pThing->ppBBoxMesh=(LPD3DXMESH*) new LPD3DXMESH[pThing->dwNumNode];

for(DWORD i=0;i<pThing->dwNumNode;i++)

{

pThing->ppBBoxMesh[i]=NULL;

}

CreateFrameBBox(pDevice,pThing->pFrameRoot,pThing);

//ボックスメッシュのマテリアル　白色、半透明、光沢強

pThing->pBBoxMeshMaterials = new D3DMATERIAL9;

pThing->pBBoxMeshMaterials->Diffuse.r=1.0f;

pThing->pBBoxMeshMaterials->Diffuse.g=1.0f;

pThing->pBBoxMeshMaterials->Diffuse.b=1.0f;

pThing->pBBoxMeshMaterials->Diffuse.a=0.3f;

pThing->pBBoxMeshMaterials->Ambient=pThing->pBBoxMeshMaterials->Diffuse;

pThing->pBBoxMeshMaterials->Specular.r=1.0f;

pThing->pBBoxMeshMaterials->Specular.g=1.0f;

pThing->pBBoxMeshMaterials->Specular.b=1.0f;

pThing->pBBoxMeshMaterials->Emissive.r=0.1f;

pThing->pBBoxMeshMaterials->Emissive.g=0.1f;

pThing->pBBoxMeshMaterials->Emissive.b=0.1f;

pThing->pBBoxMeshMaterials->Power=120.0f;

return S_OK;

}

//

//

///

HRESULT CreateFrameBBox(LPDIRECT3DDEVICE9 pDevice,LPD3DXFRAME pFrame,THING* pThing)

{

if (pFrame->pFrameSibling != NULL)

{

CreateFrameBBox(pDevice,pFrame->pFrameSibling,pThing);

}

if (pFrame->pFrameFirstChild != NULL)

{

CreateFrameBBox(pDevice,pFrame->pFrameFirstChild,pThing);

}

if(pFrame->pMeshContainer == NULL)

{

return S_OK;

}

D3DXVECTOR3 vMax,vMin;

//ロックして最大最小を得る

LPDIRECT3DVERTEXBUFFER9 pVB=NULL;

BYTE* pVertices = NULL;

LPD3DXMESH pMesh=pFrame->pMeshContainer->MeshData.pMesh;

if(FAILED(pMesh->GetVertexBuffer( &pVB )))

{

return E_FAIL;

}

if(FAILED(pVB->Lock( 0, 0, (VOID**)&pVertices, 0 )))

{

SAFE_RELEASE( pVB );

return E_FAIL;

}

if(FAILED(D3DXComputeBoundingBox( (D3DXVECTOR3*)pVertices, pMesh->GetNumVertices(),

D3DXGetFVFVertexSize(pMesh->GetFVF()), &vMin,&vMax )))

{

pVB->Unlock();

return E_FAIL;

}

pVB->Unlock();

SAFE_RELEASE( pVB );

//

pThing->pBBox[pThing->dwCurrentNode].vMax=vMax;

pThing->pBBox[pThing->dwCurrentNode].vMin=vMin;

pThing->pBBox[pThing->dwCurrentNode].vPivot=(vMax+vMin) /2;

strcpy(pThing->pBBox[pThing->dwCurrentNode].Name,pFrame->Name);

D3DXVECTOR3 vLength;

vLength=vMax-vMin;

SAFE_RELEASE(pThing->ppBBoxMesh[pThing->dwCurrentNode]);

if(FAILED(D3DXCreateBox(pDevice,vLength.x,vLength.y,vLength.z,&pThing->ppBBoxMesh[pThing->dwCurrentNode],NULL)))

{

return E_FAIL;

}

//軸ベクトルと軸の長さ（この場合ボックスの辺の長さ）を初期化する

pThing->pBBox[pThing->dwCurrentNode].fLengthX=(vMax.x-vMin.x) / 2;

pThing->pBBox[pThing->dwCurrentNode].fLengthY=(vMax.y-vMin.y) / 2;

pThing->pBBox[pThing->dwCurrentNode].fLengthZ=(vMax.z-vMin.z) / 2;

pThing->dwCurrentNode++;

return S_OK;

}

//

//

//OBBによる衝突判定。衝突している場合はTRUEを、離れている場合はFALSEを返す。

BOOL OBBCollisionDetection(DWORD* pIndexA,DWORD* pIndexB,THING* pThingA,THING* pThingB)

{

for(DWORD i=0;i<pThingA->dwNumNode;i++)

{

for(DWORD k=0;k<pThingB->dwNumNode;k++)

{

if(OBBCollisionDetectionEachBBox(&pThingA->pBBox[i],&pThingB->pBBox[k]))

{

*pIndexA=i;

*pIndexB=k;

return TRUE;

}

}

}

return FALSE;

}

//

//BOOL OBBCollisionDetection(THING* pThingA,THING* pThingB)

//

BOOL OBBCollisionDetectionEachBBox(BBOX* pBBoxA,BBOX* pBBoxB)

{

//ボックスの距離ベクトル（中心と中心を結んだベクトル）

D3DXVECTOR3 vDistance = pBBoxB->vWorldPivot - pBBoxA->vWorldPivot;

//分離軸

D3DXVECTOR3 vecSeparate;

//それぞれのローカル基底軸ベクトルに、それぞれの回転を反映させる

pBBoxA->vAxisX=D3DXVECTOR3(1,0,0);

pBBoxA->vAxisY=D3DXVECTOR3(0,1,0);

pBBoxA->vAxisZ=D3DXVECTOR3(0,0,1);

pBBoxB->vAxisX=D3DXVECTOR3(1,0,0);

pBBoxB->vAxisY=D3DXVECTOR3(0,1,0);

pBBoxB->vAxisZ=D3DXVECTOR3(0,0,1);

D3DXVec3TransformCoord(&pBBoxA->vAxisX,&pBBoxA->vAxisX,&pBBoxA->mRotation);

D3DXVec3TransformCoord(&pBBoxA->vAxisY,&pBBoxA->vAxisY,&pBBoxA->mRotation);

D3DXVec3TransformCoord(&pBBoxA->vAxisZ,&pBBoxA->vAxisZ,&pBBoxA->mRotation);

D3DXVec3TransformCoord(&pBBoxB->vAxisX,&pBBoxB->vAxisX,&pBBoxB->mRotation);

D3DXVec3TransformCoord(&pBBoxB->vAxisY,&pBBoxB->vAxisY,&pBBoxB->mRotation);

D3DXVec3TransformCoord(&pBBoxB->vAxisZ,&pBBoxB->vAxisZ,&pBBoxB->mRotation);

//ボックスAのローカル基底軸を基準にした、”影”の算出（3パターン）

{

//X軸を分離軸とした場合

if(!CompareLength(pBBoxA,pBBoxB,&pBBoxA->vAxisX,&vDistance)) return FALSE;

//Y軸を分離軸とした場合

if(!CompareLength(pBBoxA,pBBoxB,&pBBoxA->vAxisY,&vDistance)) return FALSE;

//Z軸を分離軸とした場合

if(!CompareLength(pBBoxA,pBBoxB,&pBBoxA->vAxisZ,&vDistance)) return FALSE;

}

//ボックスBのローカル基底軸を基準にした、”影”の算出（3パターン）

{

//X軸を分離軸とした場合

if(!CompareLength(pBBoxA,pBBoxB,&pBBoxB->vAxisX,&vDistance)) return FALSE;

//Y軸を分離軸とした場合

if(!CompareLength(pBBoxA,pBBoxB,&pBBoxB->vAxisY,&vDistance)) return FALSE;

//Z軸を分離軸とした場合

if(!CompareLength(pBBoxA,pBBoxB,&pBBoxB->vAxisZ,&vDistance)) return FALSE;

}

//お互いの基底軸同士の外積ベクトルを基準にした、”影”の算出（9パターン）

{

//ボックスAのX軸

{

//と　ボックスBのX軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisX,&pBBoxB->vAxisX);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

//と　ボックスBのY軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisX,&pBBoxB->vAxisY);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

//と　ボックスBのZ軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisX,&pBBoxB->vAxisZ);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

}

//ボックスAのY軸

{

//と　ボックスBのX軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisY,&pBBoxB->vAxisX);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

//と　ボックスBのY軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisY,&pBBoxB->vAxisY);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

//と　ボックスBのZ軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate,&pBBoxA->vAxisY,&pBBoxB->vAxisZ);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

}

//ボックスAのZ軸

{

//と　ボックスBのX軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisZ,&pBBoxB->vAxisX);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

//と　ボックスBのY軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisZ,&pBBoxB->vAxisY);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

//と　ボックスBのZ軸との外積ベクトルを分離軸とした場合

D3DXVec3Cross( &vecSeparate, &pBBoxA->vAxisZ,&pBBoxB->vAxisZ);

if(!CompareLength(pBBoxA,pBBoxB,&vecSeparate,&vDistance)) return FALSE;

}

}

return TRUE;

}

//

//BOOL CompareLength(BBOX* pboxA,BBOX* pboxB,D3DXVECTOR3* pvecSeparate,D3DXVECTOR3* pvecDistance)

//「距離」が「２つの影の合計」より大きい場合（非衝突）はFALSE 等しいか小さい場合（衝突）はTRUE

// この関数は、OBBCollisionDetection関数のみに呼び出されるサブルーチン

BOOL CompareLength(BBOX* pboxA,BBOX* pboxB,D3DXVECTOR3* pvecSeparate,D3DXVECTOR3* pvecDistance)

{

//”分離軸上での”ボックスＡの中心からボックスＢの中心までの距離

FLOAT fDistance=fabsf( D3DXVec3Dot( pvecDistance, pvecSeparate) );

//分離軸上でボックスAの中心から最も遠いボックスAの頂点までの距離

FLOAT fShadowA=0;

//分離軸上でボックスBの中心から最も遠いボックスBの頂点までの距離

FLOAT fShadowB=0;

//それぞれのボックスの”影”を算出

fShadowA = fabsf( D3DXVec3Dot( &pboxA->vAxisX, pvecSeparate ) * pboxA->fLengthX)+

fabsf( D3DXVec3Dot( &pboxA->vAxisY, pvecSeparate ) * pboxA->fLengthY)+

fabsf( D3DXVec3Dot( &pboxA->vAxisZ, pvecSeparate ) * pboxA->fLengthZ);

fShadowB = fabsf( D3DXVec3Dot( &pboxB->vAxisX, pvecSeparate ) * pboxB->fLengthX)+

fabsf( D3DXVec3Dot( &pboxB->vAxisY, pvecSeparate ) * pboxB->fLengthY)+

fabsf( D3DXVec3Dot( &pboxB->vAxisZ, pvecSeparate ) * pboxB->fLengthZ);

if(fDistance > fShadowA + fShadowB)

{

return FALSE;

}

return TRUE;

}

11章　プログレッシブメッシュを利用した判定用ジオメトリ

サンプルプロジェクト　ch11 判定用Pメッシュ

ハイポリゴンのメッシュに対しレイ判定をするということは重たい処理です。ポリゴンが多ければ多いほどレイと三角形の判定回数が増えるので当然です。

そこで、バカ正直にそのままのメッシュに対しレイを当てるのではなく、そのジオメトリの“プログレッシブメッシュ”にレイを当てるとフレームレートを稼ぐことが出来ます。

プログレッシブメッシュは、本来のオリジナルジオメトリからポリゴン数を削減した低ポリゴンバージョンを段階的にいくつか持ちます。その段階数を多くすれば各レベルのメッシュ間でのポリゴン量の増減幅は少なくなりますが同時にプログレッシブメッシュ全体のメモリ使用量が増加します。逆に段階数を少なくすれば各レベルのメッシュ間でのポリゴン数の差は大きくなり、同時にプログレッシブメッシュ全体としてのメモリ量は相対的に少なくなります。ただし通常のメッシュよりは当然メモリ使用量は大きくなることに変わりは有りません。なお、このような“段階”はLOD（Level Of Detail）と呼ばれます。

何れにしても、それらのベストバランスを望むのであれば、その時の状況により最適なレベル数を見つけるということになるでしょう。

本サンプルでは、Direct3DのD3DXIntersect関数によりレイを当てています。D3DXIntersectが引数にとるのはBaseMeshオブジェクトですから、プログレッシブメッシュ（の各レベルごとのメッシュ）でも判定は可能です。

次の4枚の図はサンプルのキャプチャ画像です。これらから明らかなように、詳細レベルの低いメッシュほどfpsが高いことが確認できます。

サンプルの説明

図11-1

図11-2

図11-3

図11-4

レベル0はfpsが最も高いですが、形状がオリジナルとかなり異なるので、さすがに使えません。

一方、レベル1以降は見た目がほとんど（というかまったく）変わらないように見えます。したがってこの場合はレベル1のメッシュを判定に使用するのがベストでしょう。

もちろん、いろいろなメッシュについて常にレベル1がベストであるということは無いと思います。四角っぽいメッシュであればレベル0で十分な場合もあるでしょうし、人体などのメッシュはレベル3あたりからじゃないと使えない場合もあると思います。さらに本サンプルでは分割数を5にしていますが、分割数によっても同じメッシュでベストなレベルが変わってくるかもしれません。

キー操作

Z,Xキー：レベルの減少・増加

矢印キー：レイの移動

コード解説

例によって自由気ままに作成したプロジェクトなのでファイル数が多くなっていますが、注目する部分はもちろんDirect3Dクラス及びアプリケーションクラスのみです。ただ、そもそもDirectXの運用の解説ではなくLOD管理によるレイ判定の高速化が本質なので、コードの解説はあまり意味がありません。

概要と流れだけ解説しますが、このコード自体は何かに流用できるでしょう。（交点の算出部分など）

まず、Xファイルを通常のメッシュとして読み込みます。

そのメッシュからプログレッシブメッシュを作成します。

レイとの交差判定には、そのプログレッシブメッシュ内の各レベルメッシュを使用します。

本サンプルでは、レンダリングにもプログレッシブメッシュ内のメッシュを使用していますが、本来はもとのメッシュをレンダリングすべきです。判定用のメッシュはレンダリングすることが目的ではなく、判定に使用することが目的なわけですから、可視化して確認するとき以外はレンダリングする必要はありません。

つまり普通は

レンダリングは通常メッシュ（オリジナルのメッシュ）を使用し、

衝突判定等にはプログレッシブメッシュ内の低ポリゴンメッシュを使用する。

という形になります。

実際のコードの流れは次のとおりです。

CAPPLICATION::Initialize()→CDIRECT3D::Init()　ウィンドウの作成とDirect3Dの初期化。

↓

CAPPLICATION::Initialize()→ CDIRECT3D::InitPThing()　Xファイルのロード。プログレッシブメッシュの作成。

↓

CAPPLICATION::RenderScene()　レンダリング。

なお、CDIRECT3D::InitThing()とCDIRECT3D::InitPThing()がありますが、CDIRECT3D::InitThing()（Pが付いていないほう）はプログレッシブメッシュを生成しない通常メッシュに特化したものであるので使用していません。

12章　パッチファイル

サンプルプロジェクト　ch12 パッチプログラム　パッチデータ作成

サンプルプロジェクト　ch12 パッチプログラム　パッチプログラム本体

パッチプログラムあるいはパッチファイルと呼ばれるものは、既存プログラムに対し何らかのアップデートあるいはバグフィックスを事後的に施すプログラムのことです。

バグフィックスが目的であればパッチ（ほころびをあてがう）であり、アップデートの場合であればパッチ（飾りを付け足す）という意味になり、どちらにしてもパッチとは便利な言葉ですね。

ウィンドウズの“サービスパック”もパッチプログラムと言えます。

ここではパッチプログラムを実際に作ってみましょう。

パッチプログラムが本題であるので、「パッチをかける方のプログラム」は他愛もないものを用意しました。コンソールアプリで、1分もあれば作れるような代物です。

図12-1

それをパッチプログラムによりアップデートします。アップデートと言っても次のように変化させるだけです。

図12-2

しかし、本サンプルで他愛もないのはもちろん「パッチを適用するモジュール側」であって、パッチプログラム自体は別のもっと大きなプログラムにも使用できます。（規模、複雑さに関らず機能します。）

このパッチプログラムは「カンパニーウォーズ2004」のアップデートで使用していたものであり、性能は実証済みです。ただし、カンパニーウォーズ2004のパッチはレジストリの参照機能がありますが本サンプルでは省いています。

レジストリの追加・削除等については13章の「インストーラー」で解説します。

読者は、なんらかのプログラムを2つ用意し（全く異なるプログラムでも可）2つのプログラムについてのパッチを作成してみてください。

原理

ここではパッチをかける前のプログラムを旧モジュール、新しいプログラムを新モジュールと呼びます。新モジュールはパッチをかけて出来上がった新しいアップデートモジュールと同一であるとも言えます。

パッチプログラムの作成は、大きく2段階のフェーズに分かれます。

1段目は、新旧モジュールの差分データを作成すること。

2段目は、差分データをリソースとして内部に取り込んだ実行ファイル、すなわちパッチプログラムを作成します。

つまり1段目の差分データ作成用の実行ファイルもあるわけです。したがって本サンプルのプロジェクトは2つあります。１つは差分データ作成用の実行ファイルをビルドするプロジェクト、2つ目でようやくパッチプログラムをビルドするプロジェクトです。

差分データの作成

差分データの作成は、「パッチデータ作成」プロジェクトのほうで行います。

実は、本章の目的の90%以上はこの差分データの作成にあります。

差分データというと2つのモジュールの“違う部分のみ”という印象を受けると思いますが、正確に言うともう少し情報を持っています。

さて、差分データはどう作成するのでしょう？　またどのような形が効率的なのでしょう？

効率的かは別として、すぐに思いつくのは次のような方法でしょう。

図12-3

一瞬これでも上手くいくと感じますが、すぐに重大な欠陥に気付きます。

たとえば、先頭バイトのたった1バイトが異なっていると、残りのバイトが同一だとしても差分データのサイズは新モジュールと同一のサイズになってしまいます。

図12-4

この図では9バイトしかありませんが、例えば1メガバイトである場合はどうでしょう。たった1バイトの違い、ほんの1バイト分ズレているだけでサイズは最悪1メガバイトになってしまいます。しかもデータ的には全く同じであっても関係ありません。1メガ中の1バイトですから99.999904%同一のプログラムの差分が最悪で新モジュールと同一になるというのは明らかに無駄ですよね。

サイズの問題もそうですが、実はそんなんことよりももっと深刻な問題があることに気付くでしょうか？

このようにして出来たパッチデータはモジュールそのものといってもいい代物です。したがってそれを内包したパッチプログラムを配布するということは“新モジュールを配布している”ようなものです。つまり、パッチプログラムの意味が全く無くなるばかりではなく、旧モジュールを持たない人物による違法コピーを助長する結果になりかねません。

そこで、本サンプルではこのような手法はとらず、「ブロック」という概念を用いています。

生のバイナリーデータを差分データとするのではなく、「一致している部分」、そして「不一致な部分」の「情報」をブロックという論理単位に格納します。一致してい部分において、ブロックに入れるのはあくまでも「情報」言うなればインデックスであり、生のバイナリーデータを直接格納しません。パッチプログラムがパッチを行う際には、旧モジュール内の当該ブロックが指す部位からバイナリーデータを再利用します。ただし、不一致部分については生のバイナリーデータを使います。

差分ファイルに格納されるのは基本的に“ブロック”です。ブロック構造体のサイズはせいぜい17バイトですから、生のバイナリを格納するよりもかなりコンパクトになります。

ブロックの指す範囲は可変長です。サンプルではデフォルトで16バイト〜160バイトにしています。これはソース上で変更可能です。ですので直感的には、最悪でも生のバイナリーに比べ16分の1のサイズ、最高で160分の1になることになります。ただ、ブロック構造体そのもののサイズがあるので実際には多少異なります。

図12-5

パッチプログラムの作成

差分データが出来てさえいれば、パッチプログラムの作成は至極簡単です。

差分データをリソースとしてパッチプログラム内に内包し、差分データに格納されているデータの順番に機械的にデータのコピーを行えばいいだけです。

要するに、「単純に差分データの作成とデータの流れを逆にすれば」新モジュールが出来上がります。

図12-6

また、

「エンドユーザーが持っている旧モジュールから使えるところは最大限流用して、不一致部分は仕方が無いのでバイナリーで用意する。」

ということです。

コード解説

差分データの作成

差分データの作成フェーズは、「パッチデータ作成」プロジェクトのほうです。

ファイルのオープンやファイルダイアログ表示等の部分はどうでも良い部分であり、重要なのはCreateData関数及びFindMatching関数だけです。

CreateData関数は文字通り、差分データを作成します。

一致・不一致部分の調査、一致部分に対するブロックの作成を行ったあと、sptファイルに落とします。

なおsptという拡張子は筆者が適当に考えたものなので適宜変更しても構いません。datでも何でもいいです。

FindMatching関数はCreateData関数内部からのみコールされるサブルーチンです。その名のとおり一致部分を見つけます。

struct BLOCK

{

BYTE bFlag;

DWORD dwNewAddress;

DWORD dwOldAddress;

DWORD dwSize;

};

CreateData()関数

BOOL CreateData()

{

DWORD loop1,loop2,loop3,loop4;

BYTE temp;

DWORD dwBlock=0;

DWORD dwSize;

DWORD dwAdd;

DWORD dwTemp;

HRESULT hr=0;

DWORD dwTotalSize=0;

DWORD ratio=g_dwNewSize/100;

if(ratio==0) ratio=1;

dwMaxSize=sizeof(BLOCK)*10;

dwMinSize=sizeof(BLOCK);

printf("\n比較単位 %dバイト",dwMaxSize);

printf("\n比較単位の最小縮小値 %dバイト",dwMinSize);

printf("\n************　２つのファイルを比較しています ****************\n");

// まず、最初に一致するブロックを調べる

dwAdd=0;

loop4=0;

loop2=0;

dwSize=dwMaxSize;

for(loop1=0;loop1<g_dwNewSize;loop1++)

{

if((loop1!=0) && ((loop1 % ratio)==0))

{

printf(".");

}

if((loop1!=0) && ((loop1 % (ratio*10))==0))

{

printf(" %d%%完了　ブロック数 %d",loop1/ratio,dwBlock);

dwTemp=0;

for(loop3=0;loop3<g_dwNewSize;loop3++)

{

if(g_Buffer[loop3]==1) dwTemp++;

}

printf(" 一致率：%3.2f %%",((double)dwTemp/(double)g_dwNewSize)*100);

printf(" %d秒、%d分\n",(clock()-timer)/1000,((clock()-timer)/1000)/60);

}

dwSize=dwMaxSize;

if(g_Buffer[loop1]==0)

{

jump:;

hr=FindMatching(loop1,loop2,dwSize,g_dwOldSize,g_dwNewSize,&dwSize,&dwAdd);

switch(hr)

{

case HR_TOOFAR2:

loop2++;

goto jump;

break;

case HR_TOOFAR:

loop2=0;

break;

case HR_OVERRANGE:

loop2=0;

break;

case HR_ALREADYCHECKED:

loop2=0;

break;

case HR_UNMATCH:

loop2++;

goto jump;

break;

case HR_MATCH:

ChildBlock[dwBlock].dwOldAddress=loop2;

ChildBlock[dwBlock].dwNewAddress=loop1;

ChildBlock[dwBlock].dwSize=dwSize;

FillBuffer(ChildBlock[dwBlock].dwNewAddress,ChildBlock[dwBlock].dwOldAddress,ChildBlock[dwBlock].dwSize);

dwBlock++;

loop2=loop1;

break;

case HR_SIZETOOBIG:

loop2=0;

break;

}

}

}

// 一致ブロックを成形する（重なってる物でブロック開始点が先にあるものを残す）

printf("\n****************圧縮処理中***********************\n");

temp=1;

while(temp==1)

{

temp=0;

for(loop1=0;loop1<dwBlock;loop1++)

{

for(loop2=0;loop2<dwBlock;loop2++)

{

if(loop1 == loop2) continue;

if((ChildBlock[loop1].bFlag!=ERACE) && (ChildBlock[loop2].bFlag!=ERACE)

&& (ChildBlock[loop1].dwNewAddress<=ChildBlock[loop2].dwNewAddress)

&& ((ChildBlock[loop1].dwNewAddress+ChildBlock[loop1].dwSize)>=ChildBlock[loop2].dwNewAddress))

{

if((ChildBlock[loop2].dwNewAddress-ChildBlock[loop1].dwNewAddress)

==(ChildBlock[loop2].dwOldAddress-ChildBlock[loop1].dwOldAddress))// 吸収するときは吸収される側のOldAddressが連続性がある必要がある（連続してない可能性があるので）

{

temp=1;

ChildBlock[loop2].bFlag=ERACE;

ChildBlock[loop1].dwSize=

(ChildBlock[loop2].dwNewAddress+ChildBlock[loop2].dwSize)-ChildBlock[loop1].dwNewAddress;

}

}

}

}

}

printf("\n圧縮前のブロック数＝%d\n",dwBlock);

temp=1;

while(temp==1)

{

temp=0;

for(loop1=0;loop1<dwBlock;loop1++)

{

if(ChildBlock[loop1].bFlag==ERACE)

{

temp=1;

ExchangeBlock(loop1,dwBlock-1);

dwBlock--;

}

}

}

printf("\n圧縮後のブロック数＝%d\n",dwBlock);

dwTemp=0;

for(loop1=0;loop1<g_dwNewSize;loop1++)

{

if(g_Buffer[loop1]==1) dwTemp++;

}

printf("\n一致率：%3.2f %%\n",((double)dwTemp/(double)g_dwNewSize)*100);

// sptファイルを作成する

// (出力モジュールのための一致データ部分は古いモジュールからもってくる)

//（注意）”ここで書き込んだ順番”で、パッチプログラム作成側で読み込むこと。

_chdir(dir);//プログラムがどこにあろうと、sptファイルはプロジェクトフォルダに出力する。（適宜変更すること）

FILE *fp;

fp=fopen("PatchData.spt","wb");

if(fp==NULL) return FALSE;

fwrite(&g_dwNewSize,sizeof(DWORD),1,fp);// 新モジュールサイズ

fwrite(&dwBlock,sizeof(DWORD),1,fp);// 一致ブロック数

for(loop1=0;loop1<dwBlock;loop1++)

{

fwrite(&ChildBlock[loop1],sizeof(BLOCK),1,fp);

}

g_dwUnmatchSize=0;

for(loop1=0;loop1<g_dwNewSize;loop1++)

{

if(g_Buffer[loop1]==0)

{

g_dwUnmatchSize++;

}

}

fwrite(&g_dwUnmatchSize,sizeof(DWORD),1,fp);

for(loop1=0;loop1<g_dwNewSize;loop1++)

{

if(g_Buffer[loop1]==0)

{

fwrite(&g_bNewData[loop1],1,1,fp);

}

}

fclose(fp);

return TRUE;

}

FindMatching関数

HRESULT FindMatching(DWORD StartNew,DWORD StartOld,DWORD dwSize,DWORD dwOldSize

,DWORD dwNewSize,DWORD *Size,DWORD *dwAdd)

{

DWORD loop1,loop2;

DWORD temp;

if((StartNew<StartOld) && ((StartOld-StartNew)>(g_dwNewSize/10))) return HR_TOOFAR;

if((StartNew>StartOld) && ((StartNew-StartOld)>(g_dwNewSize/10))) return HR_TOOFAR2;

if(StartOld>=g_dwOldSize) return HR_OVERRANGE;

if(StartNew>=g_dwNewSize) return HR_OVERRANGE;

if(StartNew+dwSize>=g_dwNewSize)

{

return HR_SIZETOOBIG;

}

if(StartOld+dwSize>=g_dwOldSize)

{

return HR_SIZETOOBIG;

}

loop2=StartOld;

temp=0;

for(loop1=StartNew;loop1<StartNew+dwSize;loop1++)

{

if((g_bNewData[loop1]!=g_bOldData[loop2]) || (g_OldBuffer[loop2]==1))

{

if(temp<dwMinSize)

{

*dwAdd=temp;

return HR_UNMATCH;

}

else

{

*Size=temp;

return HR_MATCH;

}

}

loop2++;

temp++;

}

return HR_MATCH;

}

CreateData関数は、実行速度について改善の余地があるでしょう。4メガバイト程度のプログラム間での差分データを作成するのに1,2時間はかかります。

パッチデータの作成にかかる時間はエンドユーザーには無関係であるので、力技でコーディングしたのが理由です。また、パッチの作成作業というものが、そうそう何回も行うものではないというのも力技で良かった理由でもあります。

ただ、“ソースの見易さ”はむしろ力技のほうが優れています。もっとも5年前にコーディングしているときには本で解説するなどとは思っていなかったのですが…

ちょうど本書では、ソートやパターンマッチングにおいて色々なアルゴリズムを解説しているので、それらのテクニックを駆使して高速化するのも有意義かと思います。

その仕事は読者に任せます。頑張って高速化が出来たら是非教えてください。

ms@kamaada7.com

www.kamada7.com

もちろん、ソースを見せてくださいとは言いません。「ここまで高速化したよ！」とだけ教えてもらえればそれだけで嬉しいです。

パッチプログラムの作成

原理でも述べたように、パッチプログラム本体のほうは、大したことありません。機械的にデータを連結するだけです。

ポイントはOpenResource()関数とCreateModule()関数です。

struct BLOCK

{

BYTE bFlag;

DWORD dwNewAddress;

DWORD dwOldAddress;

DWORD dwSize;

};

ブロック構造体の定義は、差分データ作成側と全く同一でなければなりません。そうでないと読み込みの際にバイトがズレて予期しない結果になります。

OpenResource()関数はリソースつまり差分データを開き、そのデータを全てグローバル変数に格納するのが仕事です。

そしてCreateModule()はそれらのグローバル変数をもとに新モジュールを生成します。

BOOL OpenResource()

{

HRSRC hrs=NULL;

HGLOBAL hg=NULL;

BYTE *p_res=NULL;

FILE *fp;

DWORD loop1,loop2;

hrs=FindResource(NULL,"PATCH","SPT");

if(!hrs)

{

printf("\nリソースが見つかりませんでした。\n");

return FALSE;

}

hg=LoadResource(NULL,hrs);

if(!hg)

{

printf("\nリソースを読み込めませんでした。\n");

return FALSE;

}

DWORD dwResSize=SizeofResource(NULL,hrs);

p_res=(BYTE*)LockResource(hg);

if(!p_res)

{

printf("\nリソースをロックできませんでした。\n");

return FALSE;

}

//ファイルサイズをデータ(spt)から取得

memcpy(&g_dwNewSize,p_res,sizeof(DWORD));

p_res+=sizeof(DWORD);

//ファイルサイズ分のメモリ確保

g_bBuffer=new BYTE[g_dwNewSize];

g_bNewData=new BYTE[g_dwNewSize];

g_bOldData=new BYTE[g_dwNewSize];

ZeroMemory(g_bBuffer,g_dwNewSize);

ZeroMemory(g_bNewData,g_dwNewSize);

ZeroMemory(g_bOldData,g_dwNewSize);

//一致数（ブロック数）を(spt)から取得

memcpy(&g_dwNumMatch,p_res,sizeof(DWORD));

p_res+=sizeof(DWORD);

//ブロックのメモリ確保

Block=new BLOCK[g_dwNumMatch];

//ブロックの読み込み

for(loop1=0;loop1<g_dwNumMatch;loop1++)

{

memcpy(&Block[loop1],p_res,sizeof(BLOCK));

p_res+=sizeof(BLOCK);

}

//不一致サイズをデータ(spt)から取得

memcpy(&g_dwUnmatchSize,p_res,sizeof(DWORD));

p_res+=sizeof(DWORD);

//不一致サイズ分のメモリ確保

g_bUnmatchData=new BYTE[g_dwUnmatchSize];

//不一致部分のデータを読み込む

for(loop1=0;loop1<g_dwUnmatchSize;loop1++)

{

memcpy(&g_bUnmatchData[loop1],p_res,sizeof(BYTE));

p_res+=sizeof(BYTE);

}

for(loop1=0;loop1<g_dwNumMatch;loop1++)

{

for(loop2=Block[loop1].dwNewAddress;loop2<Block[loop1].dwNewAddress+Block[loop1].dwSize;loop2++)

{

g_bBuffer[loop2]=1;

}

}

return TRUE;

}

BOOL CreateModule()

{

DWORD loop1,loop2;

DWORD temp;

FILE *fp;

for(loop1=0;loop1<g_dwNumMatch;loop1++) // 一致部分について、旧モジュールからデータを得る

{

temp=Block[loop1].dwNewAddress;

for(loop2=Block[loop1].dwOldAddress;loop2<Block[loop1].dwOldAddress+Block[loop1].dwSize;loop2++)

{

g_bNewData[temp]=g_bOldData[loop2];

temp++;

}

}

loop2=0;

for(loop1=0;loop1<g_dwNewSize;loop1++) // 不一致部分について、sptファイルからデータを読み込む

{

if(g_bBuffer[loop1]==0)

{

g_bNewData[loop1]=g_bUnmatchData[loop2];

loop2++;

}

}

_chdir(dir);

fp=fopen(g_szFileName,"wb");

if(fp==NULL)

{

return FALSE;

}

fwrite(g_bNewData,g_dwNewSize,1,fp);

fclose(fp);

return TRUE;

}

13章　その他Tips

13-1　アスキーとワイド文字の判別

図13-1

図13-2

サンプルプロジェクト名　ch13 その他　半角と全角の混在

ANSI文字（ASCII文字とも呼ばれる）は、7ビットコードで表現される文字です。いわゆる“半角文字”と思っても構いません。コードはたった7ビットなので取り得る値は0から127までですが、32番から126番までが英数字・記号を含む可視できる文字で、それ以外は制御文字と言って、たいていは“黒い四角”などとしてしか見えません。

ANSI文字コードのキャパシティではもちろん日本語のように膨大な種類の文字は表せないので、日本語は（初期の頃）JIS日本語コードにより表現されました。

JIS日本語コードは、半角と全角の混在を2バイトの“開始コード”と2バイトの“終了コード”により判別します。しかし、その方法だと最悪一つの日本語文字に対し6バイトも要してしまいます。

そこで新たに考え出されたのが“シフトJIS日本語コード”です。シフトJISは半角文字には1バイト、全角文字には2バイトしか要しません。しかも、開始、終了コードなど無くとも半角と全角が混在していても判別できます。

その仕組みはどうなっているのでしょう？

半角の場合は、そのまま表示します。これはいいでしょう。

そして全角文字には、先頭1バイトが128以上の値になるので、それにより全角であることが判断できます。

半角は128以上である必要がない、128以上の値にはなり得ないのでこのような判別が可能になります。

図13-3

ソースは非常に短く、たったこれだけです。

VOID main()

{

BYTE c[3]={0};

FILE* fp=fopen("Text.txt","rt");

if(fp != NULL)

{

while(!feof(fp) )

{

fread(&c[0],1,1,fp);

if(c[0]>=128)←ここだけがポイント！

{

fread(&c[1],1,1,fp);

printf("%s",c);

}

else

{

printf("%c",c[0]);

}

}

fclose(fp);

}

}

第1バイトが128以上であるなら日本語なので2バイト読み込み、それ以外であればANSIということなので1バイトしか読み込みません。

なお、MS-DOSやウィンドウズはシフトJISコードを採用していますが、UNIX系はEUCコードを採用しています。EUCコードの場合、先頭バイトは0xA1（161）以上になります。

13-2　彩度を下げる

図13-4　通常（カラー）

図13-5　白黒に（紙面で判るかな？）

サンプルプロジェクト名　ch13 その他　彩度を落とす

彩度は、一般的に次の公式により求めます。

彩度=0.299*R+0.587*G+0.114*B;

（R,G,BはRGB各成分）

このようにR、G、B成分を均等に増減させるというわけではないことに注意してください。

サンプルではDirect3Dのピクセルシェーダーを使用して、メッシュの彩度を落としています。

念のためコードを掲載しますが、ポイントはシェーダーコード内、次の部分だけです。

float Y=0.299*R+0.587*G+0.114*B;

ChromaShader.fx

///////////////////////////////////////////////////////////////////////////////////

//型定義

///////////////////////////////////////////////////////////////////////////////////

struct VS_OUT

{

float4 Position : POSITION;

float3 Light : TEXCOORD0;

float3 Normal : TEXCOORD1;

float3 View : TEXCOORD2;

};

///////////////////////////////////////////////////////////////////////////////////

//グローバル

///////////////////////////////////////////////////////////////////////////////////

float4 Color;

float Chroma;

texture Tex;

float4x4 matWVP;

float4x4 matWorld;

float4 vecLightDir;

float4 vecEye;

float4 Diffuse={0,0,0,0};

sampler Sampler = sampler_state

{

Texture = (Tex);

MinFilter = LINEAR;

MagFilter = LINEAR;

MipFilter = NONE;

AddressU = Clamp;

AddressV = Clamp;

};

///////////////////////////////////////////////////////////////////////////////////

//バーテックス・シェーダー

///////////////////////////////////////////////////////////////////////////////////

VS_OUT VS(float4 Pos : POSITION, float3 Normal : NORMAL)

{

VS_OUT Out = (VS_OUT)0;

Out.Position = mul(Pos, matWVP);

Out.Light = vecLightDir;

float3 PosWorld = normalize(mul(Pos, matWorld));

Out.View = vecEye - PosWorld;

Out.Normal = mul(Normal, matWorld);

return Out;

}

///////////////////////////////////////////////////////////////////////////////////

//ピクセル・シェーダー

///////////////////////////////////////////////////////////////////////////////////

float4 PS(VS_OUT In,float4 Col : COLOR,float2 TexCoord : TEXCOORD) : COLOR

{

float3 Normal = normalize(In.Normal);

float3 LightDir = normalize(In.Light);

float3 ViewDir = normalize(In.View);

float4 NL = saturate(dot(Normal, LightDir));

float3 Reflect = normalize(2 * NL * Normal - LightDir); //反射ベクトルの公式通り

float4 specular = pow(saturate(dot(Reflect, ViewDir)), 4);

float4 Color=tex2D(Sampler,TexCoord );

float R=Color.r;

float G=Color.g;

float B=Color.b;

float Y=0.299*R+0.587*G+0.114*B;

float4 TexTerm;

float4 PhongTerm;

float4 FinalColor;

TexTerm.r=R+ (Y-R) * ((100-Chroma)/100);

TexTerm.g=G+ (Y-G) * ((100-Chroma)/100);

TexTerm.b=B+ (Y-B) * ((100-Chroma)/100);

TexTerm.a=1;

PhongTerm=Diffuse * NL + specular;

FinalColor=TexTerm + PhongTerm;

return FinalColor;

}

///////////////////////////////////////////////////////////////////////////////////

// テクニック

///////////////////////////////////////////////////////////////////////////////////

technique tecChroma

{

pass p0

{

PixelShader = compile ps_2_0 PS();

}

}

なおバーテックスシェーダーは一応実装はしていますが、実際には使用していません。

Main.cpp側

//彩度の変更

pEffect->SetTechnique("tecChroma");

pEffect->Begin( NULL, 0 );

pEffect->SetFloat("Chroma",Chroma);

//ワールド・ビュー・プロジェクション行列を渡す

D3DXMATRIX mW,mV,mP;

mW=pThing->matWorld;

pDevice->GetTransform(D3DTS_VIEW,&mV);

pDevice->GetTransform(D3DTS_VIEW,&mV);

pEffect->SetMatrix("matWVP",(D3DXMATRIX*)&(mW*mV*mP));

//ワールド行列を渡す

pEffect->SetMatrix("matWorld",&mW);

//ライトの方向ベクトルを渡す ＜保留＞正確には、実際に使用しているライトの位置をいれること

pEffect->SetVector("vecLightDir",&D3DXVECTOR4(-1,-1,-1,0));

//視点位置（カメラ位置）を渡す

pEffect->SetVector("vecEye",(D3DXVECTOR4*)&D3DXVECTOR4(g_fCameraX,g_fCameraY,g_fCameraZ,0));

// レンダリング

for( DWORD i=0; i<pThing->dwNumMaterials; i++ )

{

pEffect->SetFloatArray("Diffuse", (FLOAT*)&pThing->pMeshMaterials[i] .Diffuse,3);

pEffect->SetTexture("Tex",pThing->pMeshTextures[i]);

pEffect->BeginPass(0);

pThing->pMesh->DrawSubset( i );

pEffect->EndPass();

}

pEffect->End();

}

13-3　メモリーリーク

Direct3Dコードを書くとき、“2つの場所でのメモリーリーク”について考えなくてはなりません。

一つは、通常の場所でのメモリーリーク。つまりアプリケーション内でのヒープ確保(new等)と開放（delete等）を対で適正に行っているかということです。

このメモリーリークは次のように適当な場所に_CrtSetDbgFlag()コードを挿入し、デバッグ実行すれば検出することができます。

INT WINAPI WinMain( HINSTANCE hInstance, HINSTANCE, LPSTR, INT )

{

//メモリーリーク表示

_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

例えば、

DWORD* dwVal=new DWORD[3];

などとしたとき、delete dwVal;をしないと、デバッグ終了時に出力ウィンドウは次のようにメモリーリークを報告します。

図13-6

DOWRD3個なので4×3=12Byteが開放されていないということを報告しています。

そして、もう一つあります。DirectXサーバーがどこかに確保したメモリーのリークです。

当然アプリ内でdeleteなどは出来ません。そもそもいつ確保しているのかも（良い意味で）不明です。

とは言っても開放してやるのはアプリ側からのなんらかの指令によります。具体的に言うと“COMオブジェクトの参照カウントを適正にゼロ”にしてやることであり、またアプリにはその責任があります。言うなればアプリ側からは間接的にしかＣＯＭサーバーのメモリ開放を行えないわけです。

COMオブジェクトには必ずReleaseメソッドが実装されています。アプリ側は参照カウントがゼロになりようにRelease()メソッドをコールすることになります。Releaseメソッドをある程度安全に行うようにSAFE_RELEASE()マクロが定義されているのは良く見かけるでしょう。

（なお、COMの詳細についてはゲームコーディングvol.1で分かり易く解説しています。）

DirectXサーバー側でのメモリーリークの検出はコントロールパネルでの設定に依存します。

次のように、Break On MemoryLeakにチェックを入れておけば検出できます。逆に言うとこの設定をしていないとメモリーリークが起きても分かりません。

図13-7

アプリ終了時に次のようなメッセージを出します。このメッセージはデバッグ実行、デバッグ無し実行に関らず出てくれます。

図13-8

なお、DirectX SDK February2006をインストールするとコントロールパネルのDireectXアイコンが消え、しかもVisualStudi2005上での設定パネルでもほとんどのチェックボックスが選択不可状態になってしまうという現象を確認しています。

December2005以前にSDKではここような現象は起きませんので、もし今後この現象が解消されないようであれば、December2005以前にSDKを再インストールしたほうがいいでしょう。

13-4　インストーラー（飛ぶ鳥後を濁さず！）

昔はインストーラーを自分で作成する必要・意義がありましたが、最近ではVisualStudioでウィンドウズインストーラーを簡単に作成することが出来るのでそれを利用することが多いと思います。

ただ、VisualStudioでも完全自動で作ってくれるわけではないので、“インストール”とはそもそも何なのか？　どのような処理があるのか？を大体でも知っていることは大切です。

インストールの主要な目的は当然ファイルをコピーすることです。言うまでも無くこれは必ず行いますよね。

そして、それ以外の設定はオプションではありますが、ユーザーの利便性のために普通は次のことを行います。

メディアからハードディスクへのファイルコピー（必須）

スタートメニューに当該アプリのエントリーを登録

デスクトップ上に当該アプリへのショートカットを配置

コントロールパネル登録（ソフトウェアの追加・削除に当該アプリのエントリーを登録）

何らかのレジストリ登録（その他、アプリ独自の情報）

メディアからハードディスクへのファイルコピーはWin32API のCopyFile関数で行い、

ショートカット関係はIshellLinkインターフェイスとIpersistFileインターフェイスにより行います。ショートカットはスタートメニュー及びデスクトップ上に配置します。（デスクトップ上への配置はユーザーが選択できるようにします）

レジストリの登録はRegSetValueEx関数で行い、特にコントロールパネル内の「ソフトウェアの追加・削除」から自分のゲームをアンインストールできるようにするために、

RegSetValueEx(hkey,"UninstallString",0,REG_SZ,(CONST BYTE*)str,lstrlen(str));

などとしてレジストリ設定します。