TopCoder初心者向け 総当たり特集

TopCoder

この日記は、tanzakuさん主催のCompetitive Programming Advent Calendar - PARTAKEの記事です。普段、TopCoderのニコニコ生放送（http://com.nicovideo.jp/community/co78570)をしているのですが、最近は簡単な問題をじっくり解説するということが減ってきたので、今回は基本的な総当たりを取り上げてみることにします。これがちゃんとできれば、TopCoderのDivision 2はすぐに脱出できると思います。TopCoder以外の一般のプログラムでも、総当たりは使うことがあると思いますし、ぜひ使いこなせるようになりましょう。

forループを使った総当たり

問題1 FizzBuzzを数える
A以上B以下の整数で、3か5で割り切れるものは、何個ありますか？

入力・制約条件
int A: Aは、0≦A≦1000000を満たす整数
int B: Bは、A≦B≦1000000を満たす整数

例1
入力:A=5,B=10
出力:4
5,10が5で割り切れ、6,9が3で割り切れます。つまり、5,6,9,10の4つ。

例2
入力:A=14,B=16
出力:1
15は3でも5でも割りきれます。2重にカウントしないように注意です。

「もしかしたら数式１個だけで答えが求められる？かぶって数えないようにするには、 3と5の公倍数は15だから、うーん…」
と悩んだ人も多いかもしれません。その読みは正しいのですが、もっと楽をすることができます。制約条件に注目すると、A,Bともに100万までなので、forループで総当たりすることができます。

int problem1(int A,int B)
{
	int result = 0;
	for (int i = A; i <= B; i++) // i<B と間違う人は意外と多いです。チャレンジフェーズの狙いめです。
	{
		if(i%3==0 || i%5==0) // 割り切れるの判定には、"余り=0"を使います。
		{
			result++;
		}
	}
	printf("%d\n",result);
	return result;
}

TopCoderの問題の場合は、TopCoderのコンピューターで2秒以内に実行が終わらないと、不正解となってしまいます(TLE:Time Limit Exceededと呼んでます）。forループの中身にもよりますが、1000万回のループなら余裕、1億回のループならまぁなんとか間に合うというかんじです。

  • プログラムを書く前に制約条件をみて、forループで総当たりができないか判断しましょう。
  • プログラムを書いた後は、必ずテストをしましょう。この問題なら、Aに小さい値、Bに大きい値が入るケースがもっとも時間がかかるので、A=0,B=1000000を入力して、TLEしないかをチェックしましょう。

多重のforループを使った総当たり

問題2 FizzBuzzを数える(2)
xは0以上X以下の整数、yは0以上Y以下の整数、zは0以上Z以下の整数とします。
x+y*y+z*z*z*zが3か5で割り切れる、(x,y,z)の組み合わせは、何通りありますか？

入力・制約条件
int X: Xは、0≦X≦100を満たす整数
int Y: Yは、0≦Y≦100を満たす整数
int Z: Zは、0≦Z≦100を満たす整数

例1
入力:X=100,Y=100,Z=100
出力:481408

変数が3つに増えましたが、このような場合はforループを多重にすることで、(x,y,z)のすべての組み合わせを試すことができます。forループのループ回数は、X,Y,Zの最大が100なので、100*100*100で100万回程度。余裕で2秒以内に実行できます。

int problem2(int X,int Y,int Z)
{
	int result = 0;
	for (int x = 0; x <= X; x++)
	{
		for (int y = 0; y <= Y; y++)
		{
			for (int z = 0; z <= Z; z++)
			{
				// オーバーフローにはくれぐれも注意しましょう。
				// tmpは100*100*100*100=1億程度はいきますが、
				// intは21億ぐらいまで取れるので、オーバーフローしません。
				const int tmp = x + y*y + z*z*z*z;
				if(tmp%3==0 || tmp%5==0)
				{
					result++;
				}
			}
		}
	}
	printf("%d\n",result);
	return result;
}

ビットを使った総当たり

問題3 絵の具選び

7色（赤、橙、黄、緑、青、藍、紫）の絵の具があります。そのうち3色を選んで、絵を描くことにしました。
絵の具の選び方は何通りありますか？

高校数学で、組み合わせを習えば、Combination(7,3)=(7*6*5)/(3*2*1)=35通りと簡単に出せますが、忘れている人も多いかと思います。さて、この問題は総当たりなら、どう解くと良いでしょう？
まず、問題2と同じように、forループで書くと以下のように7重のループになります。

int problem3nagai()
{
	int result = 0;
	for (int aka = 0; aka <= 1; aka++) // =0 その色を選ばない, =1 選ぶ
	{
		for (int daidai = 0; daidai <= 1; daidai++)
		{
			for (int ki = 0; ki <= 1; ki++)
			{
				for (int midori = 0; midori <= 1; midori++)
				{
					for (int ao = 0; ao <= 1; ao++)
					{
						for (int ai = 0; ai <= 1; ai++)
						{
							for (int murasaki = 0; murasaki <= 1; murasaki++)
							{
								const int num_colors = aka+daidai+ki+midori+ao+ai+murasaki;
								if(num_colors==3)
								{
									result++;
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%d\n",result);
	return result;
}

もし解答が思い浮かばなかったら、この解答でも問題ないのですが、この解答では、

  • コード量が多いので、書き間違う可能性が増える。
  • このコードでは7色にしか対応できない。「N色」のように色数が変数で与えられたら、対応できない。

という欠点があります。
こういう場合は、以下のように、ビットを使ったforループで書くと良いでしょう。

int problem3()
{
	// MAX_COLORS=20ぐらいまでなら、
	// forループは2^20*20=20971520回なので、2秒以内に間に合うと思います。
	const int MAX_COLORS = 7;
	int result = 0;
	for (int all = 0; all < (1<<MAX_COLORS); all++)
	{
		int num_colors = 0;
		for (int color = 0; color < MAX_COLORS; color++)
		{
			if( all & (1<<color) )
			{
				num_colors++;
			}
		}
		if(num_colors==3)
		{
			result++;
		}
	}
	printf("%d\n",result);
	return result;
}


意味的には、先ほどのforの多重ループのコードと全く一緒です。2進数とビットについてはわからないと以下の説明が分からないかもしれません。各自勉強しましょう。
まず、最初のforループで全ての色パターンを列挙します。allに色パターンが入ります。allは最大で2のMAX_COLORS乗つまり(1＜＜MAX_COLORS)と書くことができます。

次のforループでは、あるallについて、何色使っているかを求めます。変数colorがそれぞれの色に対応しています。1＜＜colorで、ある色を表すことができます。colorをループさせることで、1色ずつ調べていきます。もし、all & (1＜＜color)なら、その色が使用されているということなので、num_colorsを1ずつ足していきます。最終的には、allの色パターンで使用されている色数が、num_colorsに入ります。これが3になるかどうかをチェックすれば良いです。

ちなみに、この問題は深さ優先探索や、動的計画法など、いろいろな解法がありますので、ぜひ考えてみてください。また、ビットのチェック方法、ビットの数え方も、いろいろなやり方があるので、考えたり他の人のコードを読んだりしましょう。

ビットを使った総当たり（応用）

問題4 0-1ナップサック問題
品物がN種類（重量weight[i]、価値 value[i]、0≦i＜N）があります。
ナップサックには、合計で重量Wまで、品物をつめることができます。
それぞれの品物は最大で1つだけしか選べません。
あなたは、詰める品物の価値の合計が最大になるように、ナップサックに品物を詰めたいです。
そのときの価値の合計を最大値はいくらでしょう？

入力・制約条件

int N: Nは、1≦N≦20を満たす整数
int W: Wは、0≦N≦10000000を満たす整数
vector  weight: weightの要素数はN個。1≦weight[i]≦10000000 を満たす整数
vector  value:  valueの要素数はN個、 1≦value[i] ≦10000000  を満たす整数

例1
入力:N=5,W=10,weight={1,2,3,4,3} value={2,5,10,2,6}
出力:23
0番目・1番目・2番目・4番目のを詰めると、重量1+2+4+3=10、価値2+5+10+6=23でベストです。

一気に難問がでてきたように見えます。「ナップサック問題」と聞いて、wikipedia(http://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)を読んで
「NP完全だし、これは無理orz」
とか、最強最速アルゴリズマーの解説を読んで(http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html)
「動的計画法、分からん」
とか、びびらないようにしましょう。
以上の解説は、もちろん正しいですが、この問題ではNが20と少ないです。2^20=1048576。これにループの分をかけても1048576*20=20971520と1億以下。これなら、総当たりをすることができます。

int problem4(int N, int W, vector <int> weight, vector <int> value)
{
	int max_value = -1;
	for (int all = 0; all < (1<<N); all++)
	{
		int sum_weight = 0;
		int sum_value = 0;
		for (int i = 0; i < N; i++)
		{
			if (all>>i & 1) // ビットのチェックの別方法。
			{
				sum_weight += weight[i];
				sum_value  += value[i];
			}
		}
		if(sum_weight<=W)
		{
			max_value = max(max_value,sum_value);
		}
	}

	printf("%d\n",max_value);
	return max_value;
}


N=20とN=50では、数字はさほど変わらないようにみえますが、N=50だと56294995342131200になり、全く間に合いません。制約条件をチェックするとき、変数の最大値は必ずチェックしましょう。

まとめ

たった4問だけでも結構長くなってしまいました。本当は、

  • 条件を使ってforループを減らせる場合(a+b+c+d=1000なのでa,b,cだけforループすれば,dのforループはいらない)
  • 一部の変数だけ総当たりをする( (sin(log(a))-b)^2の最大値を求める。a,bともに大きい数字をとるとき、aとbでどっちを総当たり？）
  • 幅優先探索を使った総当たり（数字1と2と3を使って、正の整数を作ります(例:23,11,2,12312312322)。

このような正の整数の中でN番目に小さい数はいくらですか？）

  • 深さ優先探索を使った総当たり（順列とか。辞書順とか）

と多数のボツネタがありますが、今後のAdvent Calendarで誰かが書いてくれるのを期待します！

明日12/3のCompetitive Programming Advent Calendarは、@uwitenpenさんと@y_mazunさんです。お二方とも強豪コーダーなので期待してます。お楽しみに！

TopCoderで2年間プログラムしてみた

TopCoder

ニコニコ生放送「TopCoderでプログラムしてみた」
(http://com.nicovideo.jp/community/co78570)は、おかげさまで2周年を迎えることができました。この放送は、視聴者コメントに支えられている放送です（皆さんも私の放送よりコメントのほうに期待しているかもしれません（汗））。視聴者のみなさんには本当に感謝しています。ありがとうございます！
さて、今日は、2周年記念として、過去の放送であった質問について、ブログ上でちゃんと答えてみようと思います。

  1. TopCoderって何ですか？
  2. TopCoderはプログラミング初心者でも始められますか？
  3. TopCoderはプログラミング能力向上に役立ちますか？
  4. TopCoderを初めてみたいけど…。

１．TopCoderって何ですか？

世界中の人とプログラミング勝負できます。世界大会や賞金もあります(http://news.livedoor.com/article/detail/5075495/)。詳しくはこちら(http://dic.nicovideo.jp/a/topcoder)

２．TopCoderはプログラミング初心者でも始められますか？

初心者向けのプログラミングの本（薄い本で良い）を１冊読めれば、間違いなく始められると思います。さすがに知識ゼロからだと、きついかもしれません。プログラミング初心者は、いきなり大きいコードを書くのは難しいと思いますが、TopCoderのアルゴリズム部門では、短くて数行、長くても100行ぐらいなので、練習にはいいと思います。
以下のように、他の人の書いたコードや、解説記事も見れます

特に他の人のコードがたくさん見れるのは勉強になります。１つの問題でも、解き方・コードの書き方はたくさんあるので、それで良い点を取り入れていきましょう。（chokudaiさんの意見とかぶってますが、気にしないｗ）

３．TopCoderはプログラミング能力向上に役立ちますか？

TopCoderのアルゴリズム部門・マラソン部門（＝2週間で、できるだけ良い結果を出すプログラムを作成）について、向上しそうな能力について挙げていきます。

正確なコーディング（テストも含めて）

TopCoderでは全ての入力に対して、正しい出力をしないと、0点になります。1個でも間違えばアウト。TopCoderをやり始めた人は、アルゴリズムよりも「俺はこんな簡単なプログラムも正しく書けないのか…」となることが多いと思います。どう書けば間違いにくいか、どこをテストすれば良いかが身につくと思います。
（個人的には、正当性の重要さというのは、他のソフトウェアの品質の要素（可読性・拡張性・移植性etc)よりも重要だと思うので、もっと注目されていいと思います。）

メモリや処理速度を意識したコーディング

アルゴリズム部門では、メモリ64MB（スタックメモリ8MB）で、2秒以内にプログラムが終了しないと、0点になります。必然的に意識せねばなりません。これは、組み込みやゲームプログラミングなどでは非常に重要です。ここで注意したいのが、「メモリ消費量ができるだけ少なくて、めっちゃ高速なプログラムを書くべき」という意味ではなく、「与えられたメモリや処理時間を上手に使って、無難なコーディングをする」という意味です。（実際、仕事でもこの点を勘違いしている人は多くいます。）例えば、巡回セールスマン問題でも、巡回する都市が8程度なら、総当りのプログラムで計算時間は間に合いますし、そのほうが簡単で間違いません。そういった「ちょうどよい」感覚を身につけることができます。

デバッグ

TopCoderのチャレンジフェーズでは、他の人のコードのバグを見つけると、ボーナス点がもらえます。他の人のバグを見つける能力はアップします。世の中の人はどういう間違いをするのかも分かります。また、「ここらへんが怪しい」ではなく、「実際にこの値で動かなくなる」というのを示さないといけないので、そういうスキルも身につきます。
ただ、デバッグについては、例えば「マルチスレッドのデバッグ」「ネットワークのデバッグ」といった応用デバッグスキルは、アルゴリズム部門では、身につきません。そういうデバッグもしたい人は、TopCoderのBug Race部門にチャレンジしてみてください。

アルゴリズム

もちろんアルゴリズムスキルも身につきます。ただアルゴリズム知識というよりは、「基本的なアルゴリズムを理解していて、それを応用できるか？」という点が学べます。ここが重要なポイントです。極端な話、応用がないのなら、てきとーにインターネットでライブラリを落としてきて使えば終了なのですが、TopCoderではそれはほぼ通用しません。逆に、基本的なアルゴリズムを上手に使えれば、こんなすごいことができるというのも、実感できると思います。

結果重視の姿勢

マラソンマッチ部門は2週間あるので、時間の余裕があり、自由度も高いです。そこで、自分の好きなアルゴリズム・好きなワークフローでやりたくなるのですが、どんなに最先端のアルゴリズムを使おうが、どんなに正しいワークフローを使おうが、結果がでないと負けは負けです。自分の技術的な興味や、「なんかすごいことをやりました！」という印象よりも、結果が重要な点が、仕事にも通じるところがあるので、とてもやりがいがあります。また、結果を出した人の問題への考え方や取り組み方がとても参考になります。

Twitterでの情報網が広がる

これはスキルではないですが、大きなメリットです。TopCoderには、いろんな人が集まっています。年齢層も職業も専門もとても幅広いです。自分はゲームプログラミングと土木工学だけなのですが、他の専門の方の話が聴けるのが、とても新鮮でタメになっています。興味のある方は、kinabaさんのTopCoderのリストをフォローするのが手っ取り早いと思います（http://twitter.com/#!/kinaba/topcoder-jp）

まとめ（身につかないスキル・その他）

もちろんTopCoderだけやっていれば、プログラミングに必要な能力全てが身につくかといったら、そんなことはありません（ま、実際にTopCoderをやっていてそんな誤解をしてる人は、ツイッターを見てる限りいませんが）。例えば、以下のスキルは身につかないと思います。
・チーム開発のスキル（TopCoderは個人戦なので）
・設計スキル（アルゴリズム部門は少ないコーディングで済むので。ただ他の部門では、伸ばせる可能性はあります）

まぁ、プログラミングのジャンルというのは幅広く、また必要なジャンルというのは人によって全然違います。本業（一番好きなこと）で必要なスキルは各自しっかりやった上で、TopCoderで基本的なスキルを上げていくのがベストではないでしょうか？

あと、「別に役立たなくてOK、楽しめればOK」という考えも全然アリだと思います。実際、自分もそうだったりします（笑）。TopCoderは、お金の掛からない趣味としても、本当に優れています（hogeover30さん談）。


４．TopCoderを初めてみたいけど…。

英語が苦手です

これは、よくある質問です。確かに問題文が英語なのがやっかいですね。でも、Yahoo翻訳など自動翻訳サイトもたくさんありますし、問題文やサンプルケースを読めばなんとなく分かる問題も多いです。「英語を勉強したいけど、身近な理由がないので、やる気が起きない」人は、これをきっかけに、英語に興味をもち、英語力アップを目指すのもいいかもしれません。「TopCoderの問題文を読んでるだけで英語の総合力アップ」とはいかないですが、解説記事も含めて読めば、十分に読解の勉強になります。

アルゴリズムが苦手です（あまりアルゴリズムを知りません）

知っているアルゴリズムはゼロで全く問題ないです。アルゴリズムの本を１冊読んでから始めるぐらいなら、すぐに始めてしまいましょう。

時間がありません。

これは特に社会人プログラマーにとっては重要かもしれません。以下の２パターンがあると思います。

  • 時間の融通がききません
    • Practice Roomはいつでも使えるので、好きな時間にできます。
    • TopCoderのアルゴリズム部門の開始時間は、かなりバラついています。回によって異なるのですが、火曜午前10:00・水曜午後8:00・水曜午前0:00・日曜午前1:00のときが多いです。カレンダーはこちら（http://community.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth）。火曜午前10:00は学生以外は難しいと思いますが、仕事が遅い社会人でも深夜開催の回であれば参加できるのではないでしょうか？
    • TopCoderのマラソンマッチ部門は、期間が２週間程度なので、期間内の空いた時間にできます。
  • 時間が足りません。
    • TopCoderのアルゴリズム部門でかかる時間は、コーディングフェーズ75分+休憩5分+チャレンジフェーズ15分=95分と、長時間かかる訳ではありません。毎回参加したとしても、月3回*95分で、月4時間30分程度です。

時間もなく、時間の融通もきかない人は、多分本業が相当忙しい状態だと思うので、まずはTopCoderよりも、本業に集中したほうが良いと思います。

まとめ

自分がTopCoderを始めたのは、「日本にいたときより仕事時間が短いので、空いた時間もプログラミングして、能力が鈍らないようしたい。リフレッシュも兼ねて、家では違うことをやってみよう。」という理由からでしたが、今は「楽しいから」やっているのがメインになってますね。楽しむことで継続できるし、継続で力もつきつつある（はず）ので、まぁ、良しとしましょうｗ。
そんなわけで、TopCoderにまだ参加していない方、お待ちしてます！初心者の方も、気軽に生放送にいらしてください（http://com.nicovideo.jp/community/co78570）。ぜひ楽しくコーディングで対戦しましょう！Have fun and good luck!

ゲームエンジンアーキテクチャー読書メモ

ゲームプログラミング

とりあえず気になった部分をメモって、あとで詳しくみていく。

  • イベント（メッセージ）全般
  • データドリブン全般
  • 2.1 Googleでコードリポジトリをセットアップする
    • おぉ、自宅で使ってみよう
  • 2.4 メモリリークの破壊と検出
    • そういうツールあるのか。調べてみよう。
  • 3.2 浮動小数点のエンディアン変換のワナ(type panning)
    • 知りませんでした
  • 3.3 エラーの捕捉と処理
    • 議論の余地あり
  • 4.4.5 LERP or SLERP
    • ゲーム数学一般は他の本で分かるので、こういう記事を増やしてほしかった。LERP派
  • 4.5.6. デュアルクォータニオン
    • スキニング問題（肘など大きく曲げたとき）の解消しかしらん。もう忘れたし、他にも有用な例があるかもしれないので、リンク先みとく。
  • 4.7 SSE m128
    • m128だと、仮にVector4をm128に持たせたして、C言語で一般的には有利なアドレス渡しfunc(const Vector4& v)をやると、レジスタ渡しにならないので実は損という話を書いてほしかったけど、自分でも確かめよう。
  • 4.8 乱数生成
    • メルセンヌツイスターって、なんかライセンスの問題なかったっけ？
    • 線形合同法で作った乱数のテストほう
  • 5.1 サブシステムのスタートアップとシャットダウン
    • 全般的にいいこと言ってる。ただもうちょっと具体的にstatic Class hogeと書くことの危険性について書いてほしかった。P202の初期化の順番なんかはさりげなく書かれているけど、参考になる。個人的には、ゲーム本体のプログラムでは、リードエンジニア以外singleton禁止とかでもいい気がする。
  • 5.2.1 動的メモリ割り当ての最適化
    • 実はmallocがなぜ遅いのかの理由を知らなかった。コードをみたかんじ、SDKが提供しているのと、そんなかわらん気がしたけど、記憶違いかな？。
    • 「ユーザモードからカーネルモードへのコンテキストスイッチが発生し、リクエストを処理し、戻るためのコンテキストスイッチが発生する。」すいません。知りません。ゲーム機のOSでも、こんなことやってる？
  • 5.2.1.1
    • 断片化即死、両側からメモリ確保は見たことあるなぁ。悪くないと思う。
  • 5.2.1.4 単一フレームと二重バッファ型メモリアロケータ
    • 使ったことないなぁ。おもしろい。
  • 5.3.2.1 プレインクリメントvsポストインクリメント
    • ん・・・分からん。イテレータではプレインクリメント++pが有利とな。
  • 5.3.4 独自仕様のコンテナクラスを作成
    • 自分としてはSTLありでもいいが、メモリの確保先ヒープだけははっきり分かるような形にしたい。
    • この記事では、「自前で作ったコンテナクラスは、標準よりデバッガで値を見づらいので、工夫が必要」ということが書いてない。EASTLよさげ。
    • Boostを使いたい人は、どの機能を使いたいのか知りたい。
  • 5.4 文字列
    • String+CRCにするのは必須でしょう。開発版ではstringは残しておきたい。ただ、開発版でもゲームデータを保存したデータをロードするとき、Stringの部分がすでに失われてしまうので、ロードしたデータはCRC値だけなのでデバッグしづらい。ここらへんでよい工夫ないかなぁ。
  • 6.2.1.1 アセットのリビジョン管理
    • シンボリックリンクを使う方法はうまいなぁ。
  • 6.2.2.4 リソースGUID
  • GUIDはハッシュ値でもいいけど、名前かパス名はどこかに保存しておかないと、バグを探すのが大変（最近の問題w）
  • 6.
    • P278は当たり前そうだが、できていないところ多し。
    • アンチャーテッドの場合、ゲームで使うファイルはどのように分けているのか？アーカイブファイルはどのぐらいの大きさなのか？
    • といった部分を
    • 場合によっては、まだ読み込んでいない小さいファイルA,B,Cをバラで読むより、A,B,C,D,Eと余計なデータまで含まれた1個のアーカイブを読み込んだほうが速い。そのへんはリソースエディタで設定できるのか？
    • 最近はハードディスクもあるので、前よりは悩みが減っているのだが。
    • チャンクにすると断片化しても問題ないけど、ゲーム中のアセットのリロード（ゲーム中にキャラデータを一部差し替えて確かめたいとか）がとてもしづらくなるのでは？
  • 7.5.5 ブレークポイントの処理
    • タイマーのプログラムを書いたことがないので、あまり気にしてなかった・・・
  • 7.6 マルチプロセッサのゲームループ
    • [20]を読んでみよう。
  • 7.6.5 ジョブ
    • タスクモデルのほうが、損な気がする。特に技術力がないと向かない。
      • うまく振り分けるのが難しい。スリープ多くなりがち
      • マルチスレッドの問題を避けるための準備が必要。スレッドの役割が多いので、スレッド間のやりとりは避けられない。となると、イベント駆動（メッセージ）にして、スレッドセーフにしないとだめ。ここでバグを埋め込む可能性がいくらでもある。仮にバグがなくなったとしても、基本的にはイベント駆動のほうがデバッグが難しく、面倒なことも多い。
    • ジョブモデルであれば、計算時間がかかり、独立したような関数を任せればいいだけなので、楽。
  • 9.
    • うちのスタジオの人は、読んでほしいなぁ。こういう基本的な機能が実は重要ということに気づいてない人が多いので。
  • 9.2 デバッグ描画API
    • ここらへんは、トリプルバッファにすると、難易度が意外と高くなるので注意！
  • デバッグ用の機能をどこにおくかという部分は議論の余地がある
    1. ゲーム内に軽めの（アンチャーテッドと同じ）
    2. ゲーム内に本格コンソール（Capcomのエンジンとか）
    3. ゲーム外（ウィンドウズ）
  • 10. 省略（他の本読めば分かるので）
  • 11.4.3 ローカルクロックとグローバルクロックの比較
    • 常にグローバルクロック派だから悩んだことはないなぁ。ローカルクロックかつ、プレイヤーとNPCが並列実行されているときにおこる問題？
  • 11.4.4.1 アニメーションのリターゲッティング
    • 前にちょこっとどっかのページでみたけど、P516に文献あり。SIGGRAPH 2008
  • 11.4.6 メタチャンネル
    • UVの変化や足跡やサウンドなどはすぐに思いつくけど、時間とともに変化するマテリアル・ライティングのパラメータをアニメーションにもたせるってやったことないなぁ。どういう応用があるんだろうか。