Mercurial > hg > Papers > 2011 > koba-sigss
changeset 6:7b20f8b4d697
add presen base.
line wrap: on
line diff
--- a/paper/sigss-paper.tex Mon Feb 14 18:25:00 2011 +0900 +++ b/paper/sigss-paper.tex Sun Mar 06 17:29:49 2011 +0900 @@ -1,1 +1,1 @@ -%% 1. 「論文」 %% v1.6 [2009/11/03] \documentclass{ieicej} %\documentclass[invited]{ieicej} % 招待論文 %\documentclass[comment]{ieicej} % 解説論文 \usepackage{graphicx} %\usepackage{latexsym} %\usepackage[fleqn]{amsmath} %\usepackage[psamsfonts]{amssymb} \setcounter{page}{1} \field{} \jtitle{GameFrameWork Cerium における Sequential な Game Program の分割と 動作の検証} \etitle{Division and verification of Sequential Game Program on GameFrameWork Cerium } \authorlist{% \authorentry{小林 佑亮}{Yusuke KOBAYASHI}{ryukyu}% <= 記述しないとエラーになります \authorentry{多賀野 海人}{Kaito TAGANO}{ryukyu} \authorentry{金城 裕}{Yutaka KINJO}{ryukyu} \authorentry{河野 真治}{Shinji KONO}{ryukyu} } \affiliate[ryukyu]{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室} {Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus.} %\affiliate[所属ラベル]{和文所属}{英文所属} %\paffiliate[]{} %\paffiliate[現在の所属ラベル]{和文所属} \begin{document} \begin{abstract} 本稿では Task に分割されたゲームプログラムのテストを行う。ゲームにおける ランダム要素であるプレイヤー入力と乱数の固定化を行い、分割プログラムと シーケンシャルプログラムの動作が同一であることを確認する。 さらに高速なテスト処理環境を構築する。 \end{abstract} \begin{keyword} ゲーム テスト Cell Cerium \end{keyword} \begin{eabstract} We test divided game program. We immobilize random element that player input and random numbers, and check behavior of divided program and sequential program. At that we constract fast testing environment. \end{eabstract} \begin{ekeyword} game test Cell Cerium \end{ekeyword} \maketitle \section{はじめに} 我々は、これまで家庭用ゲーム機上におけるゲームプログラミングをサポートする オープンな開発フレームワークの研究を行ってきた。現在は PlayStation3 上での開発を行っている。 PlayStation3 のアーキテクチャは Cell Broadband Engine と呼ばれ、複数の CPU で構成される。我々は、このような Many Core Architecture を用いた 並列プログラムの開発フレームワークとして Cerium Game Engine を開発した。 Cerium では、プログラムを Task という単位に分割し、これを各 CPU に送ることで 並列実行を実現している。 Cerium はゲームプログラムをサポートしたフレームワークである。 ゲームプログラムの特徴としては、プレイヤーのゲームパッドからの入力やコード内 に埋め込まれた乱数などの非決定的な要素が多く、バグの再現性が低いことが 挙げられる。 また、Cerium におけるゲーム開発ではプログラムを Task に分割するが、 Task 間でのパラメータの同期や Task 処理の実行順序によって単純に シーケンシャルに書かれたゲームプログラムを Task に分割して処理させても、 元のプログラムを逐次実行させた時と同じ動作をすることは保証されない。 そこで本研究ではシーケンシャルなゲームプログラムと Task に分割した ゲームプログラムの動作が同一であることを確認するためのテスト手法を提案する。 シーケンシャルに書かれたゲームプログラムとそれを Task に分割したゲーム プログラムをテストモデルとし、プレイヤー入力や乱数などの非決定的な要素の 固定化により、バグの再現性を保つ。 \section{Cell BE と Cerium} \subsection{Cell Broadband Engine} Cell Broadband Engine は SCEI と IBM によって開発された CPU である。 2 thread の PPE(PowerPC Processor Element)と、8個の SPE (Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、 高速リングパスであるEIB(Element Interface Bus)で構成されている。 Cerium の動作環境である PS3 Linux では PPE と 6個の SPE が使用できる。 (図\ref{fig:cell}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/cell.eps} \end{center} \caption{Cell Broadband Engine} \label{fig:cell} \end{figure} \subsection{Game Framework Cerium} Cerium は我々が提案したゲーム開発フレームワークで、独自の Rendering Engine を持つ。Cerium は C++ で実装されており、画像の読み込みや入力デバイスは SDL を用いて行っている。以下に Cerium を構成する 3 つの機能を列挙する。 \begin{description} \item[{\bf SceneGraph:}] オブジェクトのパラメータやポリゴン情報を tree 構造 のノードで管理する \item[{\bf RenderingEngine:}] 3 種類の Task によって並列に描画処理を行う \item[{\bf TaskManager:}] Task を動的に各 CPU (PPE,SPE) に割り振る \end{description} \subsection{Cerium の Task} Cerium で使用される Task への分割単位はサブルーチンまたは関数としている。 Task には様々な API が用意されており、実行する CPU の選択や入出力される データの設定、Task の依存関係などがセット出来るようになっている。 \begin{table} \caption{Task Manager の API} \begin{tabular}{c|l} \hline \hline create\_task & Task を生成する \\ \hline run & 実行 Task Queue の実行\\ \hline set\_inData & Task への入力データのアドレスを追加 \\ \hline set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline set\_param & Task に 32 bit の情報を追加 \\ \hline wait\_for & Task 同士の依存関係をセット \\ \hline set\_cpu & Task を実行する CPU(PPE,SPE0〜5) の設定 \\ \hline set\_post & Task が終了した後 PPE 側で実行される関数の登録 \\ \hline \end{tabular} \label{tb:tm_api} \end{table} \section{ゲームプログラムのテストの特徴} 多くのゲームでは多数のオブジェクトが存在し、プレイヤーのコントローラー入力や ゲームの進行状況によって新たなオブジェクトが生成される。生成された オブジェクトは他のオブジェクトの座標などのパラメータに影響され、衝突判定を 行ったり、挙動が変化する。 \if0 (図\ref{fig:game}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/game.eps} \end{center} \caption{ゲームオブジェクトの相互作用} \label{fig:game} \end{figure} \fi この為、ゲームプログラムでは遷移する状態が膨大であり、一般的なテスト駆動の ように遷移する状態が仕様の範囲内に収まるのかチェックするようなテストは 向かない。ゲームプログラムは実際にプレイヤーがゲームをプレイすることが 重要なテストとなる。 \subsection{プレイヤーの入力の不定性} プレイヤーの入力は常に非決定的であり、例え同じ人間が同じゲームの同じ場面を プレイしたとしても毎回全く同じ入力をする可能性は極めて低い。 こうした事からプレイヤーは制御不能なランダム要素であると考えられ、 ゲームプログラムテストにおけるバグの再現性を低下させている。 \subsection{ゲームにおける乱数} ゲームにおける乱数は、オブジェクトの振る舞いに多様性を持たせたり、ランダムな 配置を実現する為に使われ、ゲームのボリュームや面白さを広げる役割を担ってきた。 予測不能な乱数はゲームプレイにおいては面白さを牽引する要因となるが、 テスト環境では、こうした乱数のランダム性はデバッグをする上でバグの再現を 困難にする。乱数生成器を無効にするか、定数でシードすることによってバグの 再現性を下げることなく、テストすることが出来る \subsection{SPE における乱数生成の非決定性}\label{sec:spe_random} 通常のシーケンシャルなプログラムでは、乱数を必要とする処理系が 1 つの乱数列 から順番に乱数を取得し、使用する。しかし並列プログラムではこの処理系は Task として SPE に送られる。乱数列は SPE 毎に独自に生成されるため、各 Task が 受け取る乱数は逐次実行した時とは異なる値となってしまう。また、SPE 内でも Task 同士に依存関係を持たせない限り、Task の実行順序が保証されないので こちらも受け取る乱数が不定となる原因となる。(図\ref{fig:spe_random}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.35]{images/spe_random.eps} \end{center} \caption{SPE 内での乱数の生成} \label{fig:spe_random} \end{figure} \section{テストモデルとなるシューティングゲーム} \subsection{Super Dandy} Super Dandy は我々が PlayStation でのゲーム開発を行っていた 1998 年に 開発されたシューティングゲームである。SuperDandy は開発する環境が変わる度に 移植されており、過去には PlayStation2 Linux、OpenGL バージョンも作られた。 (図\ref{fig:dandy}) \begin{figure}[hb] \begin{center} \includegraphics[scale=0.15]{images/dandy.eps} \end{center} \caption{Super Dandy} \label{fig:dandy} \end{figure} Super Dandy が伝統的に移植されてきた背景には、全 5 ステージのある程度の ボリュームのあるゲームであること、衝突判定やオブジェクト管理、ステージクリア によるシーン切り替えなど、基本的なゲームとしての要素が入っていること、 そして動作結果を過去の環境と比較することで新たな環境のチューニングが行える ことが挙げられる。 \subsection{Task Dandy(Super Dandy Task version)}\label{sec:taskdandy} 本研究を進めるにあたり、Super Dandy を Cerium の Task で書き換えた Task Dandy を作成した。Task Dandy はできるだけ元の Super Dandy のコード やデータ構造を流用し、比較、テストが容易に行えるように設計した。 並列実行には Amdahl 則があり、使用する CPU を増やしても、元のプログラムの 並列化率が低ければその性能を活かすことはできない。この為、Super Dandy に おいて処理の大部分を占めているオブジェクトの動作 (Move) と 衝突判定 (Collision) を Task Dandy では Task として書き直している。 Super Dandy では Move や Collision は state\_update() や collision\_detect() という関数で行っている。Task Dandy では、この処理の代わりに Move Task や Collision Task を生成している。また、obj\_draw() はオブジェクトの描画を行う 関数であったが、Task Dandy では SceneGraph の tree を生成している。 ゲームの処理を抜けると、さきほど生成した SceneGraph の tree から描画処理を 行う 3 つの Task を生成する。 (図\ref{fig:taskdandy}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/taskdandy.eps} \end{center} \caption{Super Dandy と Task Dandy の処理} \label{fig:taskdandy} \end{figure} \section{テスト環境の構築} \subsection{テストログに記述する情報とそのタイミング} シーケンシャルなプログラムを Task に分割した際に、新たに発生するバグとして、 本研究では以下の項目に焦点を当てた。 \begin{itemize} \item Task 間のデータの同期 \item Task の実行順序 \item Task の定義 \end{itemize} このうち、Task の定義については、Task の中身が非常に小さい為(Super Dandy なら 20〜100 行程度)、Task の inData や outData を調べるといった従来のテスト 手法でも十分にテストが可能である。その他の 2 つについては、いずれも衝突判定 の際に生じるバグである。 (図\ref{fig:test_log}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{images/test_log.eps} \end{center} \caption{Task Dandy で起こりうるバグ} \label{fig:test_log} \end{figure} そこで、オブジェクトが被弾した時、そしてオブジェクトが生成された時にテスト ログを取ることで効率的にバグを発見することができると考えた。以下に実際に 収集したテストログの例を示す。 \begin{verbatim} F64: CREATE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -128.000000 F85: DELETE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -44.000000 vx= 0.000000 vy= 4.000000 [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 \end{verbatim} それぞれのパラメータの詳細は次のとおりである。 \begin{itemize} \item {\bf F64,F85: }生成、もしくは被弾した時の経過フレーム。 \item {\bf CREATE,DELETE:} CREATE ならオブジェクトが生成された、DELETE なら オブジェクトが被弾した事を表す。 \item {\bf NAME: }オブジェクトの種類と ID。ID はオブジェクトの種類毎に 0 から順番に付けられるのでどのオブジェクトの情報なのかを特定できる。 \item {\bf COORD: }オブジェクトのxy座標とxy方向の速度。 \item {\bf BULLET: }その瞬間に画面内に存在した弾の数。差異があれば同期が 取れていないことを示す。 \end{itemize} これにより、フレーム単位でどのオブジェクトが生成、または被弾したのか知ること ができる。trace モードでプレイヤーの入力を固定し、各バージョンでテストログを 取り、その差異を調べることでバグが発生している時間や場所を特定することが できる。 \subsection{プレイヤー入力の固定化}\label{sec:fix_input} ゲームにおいてプレイヤーからの入力は制御不能なランダム要素であり、 バグを再現することを困難にする。そこでプレイヤーからの入力を1フレーム毎に 記録し、バイナリデータとして書き出す Capture モードと書き出されたバイナリ データを読み込み、プレイヤーの入力を再現する Trace モードを実装した。 \section{SPE における乱数の固定化}\label{sec:ppe_random} SPE 内で乱数を生成すると、毎回異なる値を生成してしまう。 そこであらかじめ PPE 内で乱数列を生成し、inData として Task に渡しておく。 Task Dandy では Task の生成、定義がされるタイミングは Super Dandy における Move 関数や Collision 関数が実行されるタイミングと同じである為、渡される乱数 は Super Dandy と同じ乱数となる。 (図\ref{fig:ppe_random}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/ppe_random.eps} \end{center} \caption{PPE 内での乱数の生成と乱数の受け渡し} \label{fig:ppe_random} \end{figure} \subsection{描画処理を行わないビデオモード}\label{sec:video_none} Task Dandy ではゲームの処理や Task 生成を行った後、Rendering Engine を用いて 3 つの Task を用いて画面の描画処理を行っている。 しかし、プレイヤーの入力をバイナリデータから読み出す場合、処理の詳細が 知りたい場合を除いて画面の描画処理は不要となる。そこでテスト用に画面の 描画処理を行わないモードを Cerium に実装した。これは、Cerium 内で描画用の Task を生成する処理を行わないことで多くの処理時間を要する描画処理を行わずに テストを行うことができるビデオモードである。 (図\ref{fig:video_none}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/video_none.eps} \end{center} \caption{描画処理を行わないビデオモード} \label{fig:video_none} \end{figure} \section{バグ検出実験} \subsection{開発した環境における検出方法} まずはじめに OpenGL バージョンの Super Dandy を Capture モードでプレイする。 プレイはエンディングまで行い、プレイヤーの入力データを保存する。 Task Dandy を Trace モードで実行し、入力データを読み込ませる。 そして各バージョンそれぞれから得られたテストログを比較、考察し、 バグの発生していると思われる箇所を特定する。 この方法で実際にテストを行い、以下のようなテストログが取れた。 \begin{verbatim} super dandy >> F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 << task dandy F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F109: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 \end{verbatim} ここで Super Dandy と Task Dandy の 2 つのログを比較したときの特徴を 洗いだすと以下のようになる。 \begin{itemize} \item Super Dandy では別フレームで被弾した敵オブジェクトが Task Dandy では 同フレーム内で被弾している \item 同フレーム内で被弾したときの弾丸の数が一致している \item それ以外のログは Super Dandy と Task Dandy 共に一緒である \end{itemize} こうした結果から 2 つのオブジェクト間で弾丸データの同期が取れていない、と いう仮説を立てた。Collision Task 間でデータを同期させるには、Collision Task を同じ CPU に送り、予め衝突判定に必要なパラメータの領域を LS に確保し、 その領域のパラメータで衝突判定を行う方法が考えられる。 \if0 (図\ref{fig:collision_reflect}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{images/collision_reflect.eps} \end{center} \caption{共用領域による Collision Task の同期} \label{fig:collision_reflect} \end{figure} \fi 以上のことをふまえて Collision Task を書き換え、再び同じプレイヤー入力で テストログを出力させた。以下にその結果を示す。 \begin{verbatim} super dandy>> F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 << task dandy F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 \end{verbatim} この結果よりオブジェクトの処理の結果がフレーム単位で同じであることがわかる。 衝突判定時のテストログ出力から得られた同期バグ検出は有効であった。 \section{Task への乱数受け渡しによるバグの再現性の検証} Task への乱数受け渡しの手法が期待通りの動きをするかどうか、多数の隕石 オブジェクトが生成されるステージで全ての隕石オブジェクトが生成されるのを 観察し、検証した。この隕石オブジェクトは以下のような実装になっている \begin{verbatim} int sf = random() % 4; if ((sf == 0) || (sf == 1)) { p->x = -35; p->y = random() % (120 - 35); p->vx = (random() % 4 + 1); p->vy = random() % 3 + 1; } else if(sf == 2) { .... } else if(sf == 3) { .... } \end{verbatim} このオブジェクトは乱数によって 3 種類の処理に分かれる。処理の中では xy 座標 、xy 方向の速度が決定し、次の状態へ遷移する、という動作になっている。 そこで、この処理が行われた直後のオブジェクトの座標を記録し、Super Dandy、 Task Dandy 双方のデータに違いがあるかどうか調べた。 以下はその結果である。 \begin{verbatim} super dandy >> ... [ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 ... [ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 ... [ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 ... << task dandy [ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 [ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 [ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 ... \end{verbatim} ID はそのオブジェクト固有の値である。SPE で並列実行させた場合、実行順序は バラバラになっているが、xy 座標、速度の値は逐次実行した場合と一致している ことがわかる。Task への乱数受け渡しは有効に働いていることがわかる。 \subsection{ビデオモードによる実行時間の比較} 描画を行わないビデオモードと通常のビデオモードで実行時間を計測し、 その差がどの程度あるのかを比較した。実行時間の計測には Unix 環境で使用できる time コマンドを使用し、計測モデルとして OpenGL で動作している Super Dandy と Task Dandy を使用した。それぞれ 1200x800 で画面描画を行うバージョンを用意 し、さらに 描画を行わないビデオモードで Task Dandy を動かし、テストした。 以下が計測結果である。 \begin{table}[h] \caption{ビデオモードによる実行時間の比較} \begin{tabular}{c||c|c|c} \hline \hline & OpenGL & Task & Task(no video) \\ \hline \hline 実行時間 & 336.09 sec & 6643.16 sec & 385.17 sec \\ \hline \end{tabular} \label{tb:test_time} \end{table} まず、OpenGL と Cerium の描画ありバージョンでは大きな実行時間の差が出ている。 これは、Task Dandy においてゲームの Task と 描画の Task が生成されており、 その処理時間が発生しているためと考えられる。また、OpenGL は GPU を用いた描画処理が可能であり、Cerium では Task を用いた ソフトウェアレンダリングとなっている為、ここまでの描画時間の差が出たと 思われる。 次に描画処理を行わないバージョンだが、描画処理を行った場合に比べて大幅に 処理時間が短縮されている。描画処理を行わない場合、Task となっているのは ゲーム内の Move と Collision だが、描画の Task に比べればそれほど大きな処理 にはなっていないのがわかる。 \section{まとめ} Capture と Trace によるプレイヤー入力の固定化、生成される乱数の固定化、 および画面描画を行わないビデオモードの実装によってバグの再現性の向上、 そしてテスト時間の短縮を実現することができた。また、テストログの出力により、 Task 間の同期問題のバグを修正することも出来た。 しかし、今回のテストでは Task Dandy の数ある状態遷移の一部をテストしかされて いない。さらに異なるバグを発見する為には、多種多様なゲームのプレイヤー入力を Capture、Trace する必要がある。しかし、これを人間によって行うには大きな労力 を伴う。このプレイヤー入力をある程度自動的に生成できる実装が必要となる。 %% 謝辞 \ack %\bibliographystyle{sieicej} %\bibliography{myrefs} \begin{thebibliography}{99}% 文献数が10未満の時 {9} \bibitem{kono} 河野 真治, PS3 上でのゲームプログラミング, 第51回プログラミング・シンポジウム, 2010. \bibitem{gongo} 宮國 渡, Cell 用の Fine-Grain Task Manager の実装, 琉球大学理工学研究科情報工学専攻 平成20年度学位論文, 2009. \bibitem{akira} 神里 晃, Cell を用いたゲームフレームワークの提案, 琉球大学理工学研究科情報工学専攻 平成19年度学位論文, 2008. \bibitem{yutaka} 金城 裕, Fine grain Task Manager Cerium のチューニング, 日本ソフトウェア科学会第27回大会論文集, 2010. \bibitem{gems1} Mark DeLoura, Game Programming Gems, Born Digital Inc, 東京, 2002. \bibitem{test} Kent Beck, テスト駆動開発入門, テクノロジックアート, 東京, 2008. \end{thebibliography} %% 付録 \appendix %% \section{} \if0 \begin{biography} \profile{}{}{} %\profile{会員種別}{名前}{紹介文}% 顔写真あり %\profile*{会員種別}{名前}{紹介文}% 顔写真なし \end{biography} \fi \end{document} \ No newline at end of file +%% 4. 「技術研究報告」 \documentclass[technicalreport]{ieicej} \usepackage{graphicx} %\usepackage{latexsym} %\usepackage[fleqn]{amsmath} %\usepackage[psamsfonts]{amssymb} \setcounter{page}{1} \field{} \jtitle{GameFrameWork Cerium における Sequential な Game Program の分割と 動作の検証} \jsubtitle{} \etitle{Division and verification of Sequential Game Program on GameFrameWork Cerium } \esubtitle{} \authorlist{% \authorentry{小林 佑亮}{Yusuke KOBAYASHI}{ryukyu}% <= 記述しないとエラーになります \authorentry{多賀野 海人}{Kaito TAGANO}{ryukyu} \authorentry{金城 裕}{Yutaka KINJO}{ryukyu} \authorentry{河野 真治}{Shinji KONO}{ryukyu} } \affiliate[ryukyu]{琉球大学 理工学研究科 情報工学専攻 並列信頼研究室} {Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus.} %\affiliate[所属ラベル]{和文所属}{英文所属} %\paffiliate[]{} %\paffiliate[現在の所属ラベル]{和文所属} \begin{document} \begin{jabstract} 本稿では Sequential なゲームプログラムを 逐次実行した時と、Task に 分割し実行した時の動作が同一であることを確認する為のテスト手法を 提案する。ランダム要素であるプレイヤー入力と乱数の固定化を行うことで バグの再現性を向上させ、さらに高速にテストを行える環境を構築する。 \end{jabstract} \begin{jkeyword} ゲーム テスト Cell Cerium \end{jkeyword} \begin{eabstract} We test divided game program. We immobilize random element that player input and random numbers, and check behavior of divided program and sequential program. At that we constract fast testing environment. \end{eabstract} \begin{ekeyword} game test Cell Cerium \end{ekeyword} \maketitle \section{はじめに} 我々は、これまで家庭用ゲーム機上におけるゲームプログラミングをサポートする オープンな開発フレームワークの研究を行ってきた。現在は PlayStation3 上での開発を行っている。 PlayStation3 のアーキテクチャは Cell Broadband Engine と呼ばれ、複数の CPU で構成される。我々は、このような Many Core Architecture を用いた 並列プログラムの開発フレームワークとして Cerium Game Engine を開発した。 Cerium では、プログラムを Task という単位に分割し、これを各 CPU に送ることで 並列実行を実現している。 Cerium はゲームプログラムをサポートしたフレームワークである。 ゲームプログラムの特徴としては、プレイヤーのゲームパッドからの入力やコード内 に埋め込まれた乱数などの非決定的な要素が多く、バグの再現性が低いことが 挙げられる。 また、Cerium におけるゲーム開発ではプログラムを Task に分割するが、 Task 間でのパラメータの同期や Task 処理の実行順序によって単純に シーケンシャルに書かれたゲームプログラムを Task に分割して処理させても、 元のプログラムを逐次実行させた時と同じ動作をすることは保証されない。 そこで本研究ではシーケンシャルなゲームプログラムと Task に分割した ゲームプログラムの動作が同一であることを確認するためのテスト手法を提案する。 シーケンシャルに書かれたゲームプログラムとそれを Task に分割したゲーム プログラムをテストモデルとし、プレイヤー入力や乱数などの非決定的な要素の 固定化により、バグの再現性を保つ。 \section{Cell BE と Cerium} \subsection{Cell Broadband Engine} Cell Broadband Engine は SCEI と IBM によって開発された CPU である。 2 thread の PPE(PowerPC Processor Element)と、8個の SPE (Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、 高速リングパスであるEIB(Element Interface Bus)で構成されている。 Cerium の動作環境である PS3 Linux では PPE と 6個の SPE が使用できる。 (図\ref{fig:cell}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/cell.eps} \end{center} \caption{Cell Broadband Engine} \label{fig:cell} \end{figure} \subsection{Game Framework Cerium} Cerium は我々が提案したゲーム開発フレームワークで、独自の Rendering Engine を持つ。Cerium は C++ で実装されており、画像の読み込みや入力デバイスは SDL を用いて行っている。以下に Cerium を構成する 3 つの機能を列挙する。 \begin{description} \item[{\bf SceneGraph:}] オブジェクトのパラメータやポリゴン情報を tree 構造 のノードで管理する \item[{\bf RenderingEngine:}] 3 種類の Task によって並列に描画処理を行う \item[{\bf TaskManager:}] Task を動的に各 CPU (PPE,SPE) に割り振る \end{description} \subsection{Cerium の Task} Cerium で使用される Task への分割単位はサブルーチンまたは関数としている。 Task には様々な API が用意されており、実行する CPU の選択や入出力される データの設定、Task の依存関係などがセット出来るようになっている。 \begin{table} \caption{Task Manager の API} \begin{tabular}{c|l} \hline \hline create\_task & Task を生成する \\ \hline run & 実行 Task Queue の実行\\ \hline set\_inData & Task への入力データのアドレスを追加 \\ \hline set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline set\_param & Task に 32 bit の情報を追加 \\ \hline wait\_for & Task 同士の依存関係をセット \\ \hline set\_cpu & Task を実行する CPU(PPE,SPE0〜5) の設定 \\ \hline set\_post & Task が終了した後 PPE 側で実行される関数の登録 \\ \hline \end{tabular} \label{tb:tm_api} \end{table} \section{ゲームプログラムのテストの特徴} 多くのゲームでは多数のオブジェクトが存在し、プレイヤーのコントローラー入力や ゲームの進行状況によって新たなオブジェクトが生成される。生成された オブジェクトは他のオブジェクトの座標などのパラメータに影響され、衝突判定を 行ったり、挙動が変化する。 \if0 (図\ref{fig:game}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/game.eps} \end{center} \caption{ゲームオブジェクトの相互作用} \label{fig:game} \end{figure} \fi この為、ゲームプログラムでは遷移する状態が膨大であり、一般的なテスト駆動の ように遷移する状態が仕様の範囲内に収まるのかチェックするようなテストは 向かない。ゲームプログラムは実際にプレイヤーがゲームをプレイすることが 重要なテストとなる。 \subsection{プレイヤーの入力の不定性} プレイヤーの入力は常に非決定的であり、例え同じ人間が同じゲームの同じ場面を プレイしたとしても毎回全く同じ入力をする可能性は極めて低い。 こうした事からプレイヤーは制御不能なランダム要素であると考えられ、 ゲームプログラムテストにおけるバグの再現性を低下させている。 \subsection{ゲームにおける乱数} ゲームにおける乱数は、オブジェクトの振る舞いに多様性を持たせたり、ランダムな 配置を実現する為に使われ、ゲームのボリュームや面白さを広げる役割を担ってきた。 予測不能な乱数はゲームプレイにおいては面白さを牽引する要因となるが、 テスト環境では、こうした乱数のランダム性はデバッグをする上でバグの再現を 困難にする。乱数生成器を無効にするか、定数でシードすることによってバグの 再現性を下げることなく、テストすることが出来る \subsection{SPE における乱数生成の非決定性}\label{sec:spe_random} 通常のシーケンシャルなプログラムでは、乱数を必要とする処理系が 1 つの乱数列 から順番に乱数を取得し、使用する。しかし並列プログラムではこの処理系は Task として SPE に送られる。乱数列は SPE 毎に独自に生成されるため、各 Task が 受け取る乱数は逐次実行した時とは異なる値となってしまう。また、SPE 内でも Task 同士に依存関係を持たせない限り、Task の実行順序が保証されないので こちらも受け取る乱数が不定となる原因となる。(図\ref{fig:spe_random}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.35]{images/spe_random.eps} \end{center} \caption{SPE 内での乱数の生成} \label{fig:spe_random} \end{figure} \section{テストモデルとなるシューティングゲーム} \subsection{Super Dandy} Super Dandy は我々が PlayStation でのゲーム開発を行っていた 1998 年に 開発されたシューティングゲームである。SuperDandy は開発する環境が変わる度に 移植されており、過去には PlayStation2 Linux、OpenGL バージョンも作られた。 (図\ref{fig:dandy}) \begin{figure}[hb] \begin{center} \includegraphics[scale=0.15]{images/dandy.eps} \end{center} \caption{Super Dandy} \label{fig:dandy} \end{figure} Super Dandy が伝統的に移植されてきた背景には、全 5 ステージのある程度の ボリュームのあるゲームであること、衝突判定やオブジェクト管理、ステージクリア によるシーン切り替えなど、基本的なゲームとしての要素が入っていること、 そして動作結果を過去の環境と比較することで新たな環境のチューニングが行える ことが挙げられる。 \subsection{Task Dandy(Super Dandy Task version)}\label{sec:taskdandy} 本研究を進めるにあたり、Super Dandy を Cerium の Task で書き換えた Task Dandy を作成した。Task Dandy はできるだけ元の Super Dandy のコード やデータ構造を流用し、比較、テストが容易に行えるように設計した。 並列実行には Amdahl 則があり、使用する CPU を増やしても、元のプログラムの 並列化率が低ければその性能を活かすことはできない。この為、Super Dandy に おいて処理の大部分を占めているオブジェクトの動作 (Move) と 衝突判定 (Collision) を Task Dandy では Task として書き直している。 Super Dandy では Move や Collision は state\_update() や collision\_detect() という関数で行っている。Task Dandy では、この処理の代わりに Move Task や Collision Task を生成している。また、obj\_draw() はオブジェクトの描画を行う 関数であったが、Task Dandy では SceneGraph の tree を生成している。 ゲームの処理を抜けると、さきほど生成した SceneGraph の tree から描画処理を 行う 3 つの Task を生成する。 (図\ref{fig:taskdandy}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/taskdandy.eps} \end{center} \caption{Super Dandy と Task Dandy の処理} \label{fig:taskdandy} \end{figure} \section{テスト環境の構築} \subsection{テストログに記述する情報とそのタイミング} シーケンシャルなプログラムを Task に分割した際に、新たに発生するバグとして、 本研究では以下の項目に焦点を当てた。 \begin{itemize} \item Task 間のデータの同期 \item Task の実行順序 \item Task の定義 \end{itemize} このうち、Task の定義については、Task の中身が非常に小さい為(Super Dandy なら 20〜100 行程度)、Task の inData や outData を調べるといった従来のテスト 手法でも十分にテストが可能である。その他の 2 つについては、いずれも衝突判定 の際に生じるバグである。 (図\ref{fig:test_log}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{images/test_log.eps} \end{center} \caption{Task Dandy で起こりうるバグ} \label{fig:test_log} \end{figure} そこで、オブジェクトが被弾した時、そしてオブジェクトが生成された時にテスト ログを取ることで効率的にバグを発見することができると考えた。以下に実際に 収集したテストログの例を示す。 \begin{verbatim} F64: CREATE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -128.000000 F85: DELETE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -44.000000 vx= 0.000000 vy= 4.000000 [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 \end{verbatim} それぞれのパラメータの詳細は次のとおりである。 \begin{itemize} \item {\bf F64,F85: }生成、もしくは被弾した時の経過フレーム。 \item {\bf CREATE,DELETE:} CREATE ならオブジェクトが生成された、DELETE なら オブジェクトが被弾した事を表す。 \item {\bf NAME: }オブジェクトの種類と ID。ID はオブジェクトの種類毎に 0 から順番に付けられるのでどのオブジェクトの情報なのかを特定できる。 \item {\bf COORD: }オブジェクトのxy座標とxy方向の速度。 \item {\bf BULLET: }その瞬間に画面内に存在した弾の数。差異があれば同期が 取れていないことを示す。 \end{itemize} これにより、フレーム単位でどのオブジェクトが生成、または被弾したのか知ること ができる。trace モードでプレイヤーの入力を固定し、各バージョンでテストログを 取り、その差異を調べることでバグが発生している時間や場所を特定することが できる。 \subsection{プレイヤー入力の固定化}\label{sec:fix_input} ゲームにおいてプレイヤーからの入力は制御不能なランダム要素であり、 バグを再現することを困難にする。そこでプレイヤーからの入力を1フレーム毎に 記録し、バイナリデータとして書き出す Capture モードと書き出されたバイナリ データを読み込み、プレイヤーの入力を再現する Trace モードを実装した。 \section{SPE における乱数の固定化}\label{sec:ppe_random} SPE 内で乱数を生成すると、毎回異なる値を生成してしまう。 そこであらかじめ PPE 内で乱数列を生成し、inData として Task に渡しておく。 Task Dandy では Task の生成、定義がされるタイミングは Super Dandy における Move 関数や Collision 関数が実行されるタイミングと同じである為、渡される乱数 は Super Dandy と同じ乱数となる。 (図\ref{fig:ppe_random}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/ppe_random.eps} \end{center} \caption{PPE 内での乱数の生成と乱数の受け渡し} \label{fig:ppe_random} \end{figure} \subsection{描画処理を行わないビデオモード}\label{sec:video_none} Task Dandy ではゲームの処理や Task 生成を行った後、Rendering Engine を用いて 3 つの Task を用いて画面の描画処理を行っている。 しかし、プレイヤーの入力をバイナリデータから読み出す場合、処理の詳細が 知りたい場合を除いて画面の描画処理は不要となる。そこでテスト用に画面の 描画処理を行わないモードを Cerium に実装した。これは、Cerium 内で描画用の Task を生成する処理を行わないことで多くの処理時間を要する描画処理を行わずに テストを行うことができるビデオモードである。 (図\ref{fig:video_none}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.4]{images/video_none.eps} \end{center} \caption{描画処理を行わないビデオモード} \label{fig:video_none} \end{figure} \section{バグ検出実験} \subsection{開発した環境における検出方法} まずはじめに OpenGL バージョンの Super Dandy を Capture モードでプレイする。 プレイはエンディングまで行い、プレイヤーの入力データを保存する。 Task Dandy を Trace モードで実行し、入力データを読み込ませる。 そして各バージョンそれぞれから得られたテストログを比較、考察し、 バグの発生していると思われる箇所を特定する。 この方法で実際にテストを行い、以下のようなテストログが取れた。 \begin{verbatim} super dandy >> F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 << task dandy F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F109: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 \end{verbatim} ここで Super Dandy と Task Dandy の 2 つのログを比較したときの特徴を 洗いだすと以下のようになる。 \begin{itemize} \item Super Dandy では別フレームで被弾した敵オブジェクトが Task Dandy では 同フレーム内で被弾している \item 同フレーム内で被弾したときの弾丸の数が一致している \item それ以外のログは Super Dandy と Task Dandy 共に一緒である \end{itemize} こうした結果から 2 つのオブジェクト間で弾丸データの同期が取れていない、と いう仮説を立てた。Collision Task 間でデータを同期させるには、Collision Task を同じ CPU に送り、予め衝突判定に必要なパラメータの領域を LS に確保し、 その領域のパラメータで衝突判定を行う方法が考えられる。 \if0 (図\ref{fig:collision_reflect}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.3]{images/collision_reflect.eps} \end{center} \caption{共用領域による Collision Task の同期} \label{fig:collision_reflect} \end{figure} \fi 以上のことをふまえて Collision Task を書き換え、再び同じプレイヤー入力で テストログを出力させた。以下にその結果を示す。 \begin{verbatim} super dandy>> F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 << task dandy F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000.. [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 \end{verbatim} この結果よりオブジェクトの処理の結果がフレーム単位で同じであることがわかる。 衝突判定時のテストログ出力から得られた同期バグ検出は有効であった。 \section{Task への乱数受け渡しによるバグの再現性の検証} Task への乱数受け渡しの手法が期待通りの動きをするかどうか、多数の隕石 オブジェクトが生成されるステージで全ての隕石オブジェクトが生成されるのを 観察し、検証した。この隕石オブジェクトは以下のような実装になっている \begin{verbatim} int sf = random() % 4; if ((sf == 0) || (sf == 1)) { p->x = -35; p->y = random() % (120 - 35); p->vx = (random() % 4 + 1); p->vy = random() % 3 + 1; } else if(sf == 2) { .... } else if(sf == 3) { .... } \end{verbatim} このオブジェクトは乱数によって 3 種類の処理に分かれる。処理の中では xy 座標 、xy 方向の速度が決定し、次の状態へ遷移する、という動作になっている。 そこで、この処理が行われた直後のオブジェクトの座標を記録し、Super Dandy、 Task Dandy 双方のデータに違いがあるかどうか調べた。 以下はその結果である。 \begin{verbatim} super dandy >> ... [ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 ... [ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 ... [ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 ... << task dandy [ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 [ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 [ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 ... \end{verbatim} ID はそのオブジェクト固有の値である。SPE で並列実行させた場合、実行順序は バラバラになっているが、xy 座標、速度の値は逐次実行した場合と一致している ことがわかる。Task への乱数受け渡しは有効に働いていることがわかる。 \subsection{ビデオモードによる実行時間の比較} 描画を行わないビデオモードと通常のビデオモードで実行時間を計測し、 その差がどの程度あるのかを比較した。実行時間の計測には Unix 環境で使用できる time コマンドを使用し、計測モデルとして OpenGL で動作している Super Dandy と Task Dandy を使用した。それぞれ 1200x800 で画面描画を行うバージョンを用意 し、さらに 描画を行わないビデオモードで Task Dandy を動かし、テストした。 以下が計測結果である。 \begin{table}[h] \caption{ビデオモードによる実行時間の比較} \begin{tabular}{c||c|c|c} \hline \hline & OpenGL & Task & Task(no video) \\ \hline \hline 実行時間 & 336.09 sec & 6643.16 sec & 385.17 sec \\ \hline \end{tabular} \label{tb:test_time} \end{table} まず、OpenGL と Cerium の描画ありバージョンでは大きな実行時間の差が出ている。 これは、Task Dandy においてゲームの Task と 描画の Task が生成されており、 その処理時間が発生しているためと考えられる。また、OpenGL は GPU を用いた描画処理が可能であり、Cerium では Task を用いた ソフトウェアレンダリングとなっている為、ここまでの描画時間の差が出たと 思われる。 次に描画処理を行わないバージョンだが、描画処理を行った場合に比べて大幅に 処理時間が短縮されている。描画処理を行わない場合、Task となっているのは ゲーム内の Move と Collision だが、描画の Task に比べればそれほど大きな処理 にはなっていないのがわかる。 \section{まとめ} Capture と Trace によるプレイヤー入力の固定化、生成される乱数の固定化、 および画面描画を行わないビデオモードの実装によってバグの再現性の向上、 そしてテスト時間の短縮を実現することができた。また、テストログの出力により、 Task 間の同期問題のバグを修正することも出来た。 しかし、今回のテストでは Task Dandy の数ある状態遷移の一部をテストしかされて いない。さらに異なるバグを発見する為には、多種多様なゲームのプレイヤー入力を Capture、Trace する必要がある。しかし、これを人間によって行うには大きな労力 を伴う。このプレイヤー入力をある程度自動的に生成できる実装が必要となる。 %% 謝辞 \ack %\bibliographystyle{sieicej} %\bibliography{myrefs} \begin{thebibliography}{99}% 文献数が10未満の時 {9} \bibitem{kono} 河野 真治, PS3 上でのゲームプログラミング, 第51回プログラミング・シンポジウム, 2010. \bibitem{gongo} 宮國 渡, Cell 用の Fine-Grain Task Manager の実装, 琉球大学理工学研究科情報工学専攻 平成20年度学位論文, 2009. \bibitem{akira} 神里 晃, Cell を用いたゲームフレームワークの提案, 琉球大学理工学研究科情報工学専攻 平成19年度学位論文, 2008. \bibitem{yutaka} 金城 裕, Fine grain Task Manager Cerium のチューニング, 日本ソフトウェア科学会第27回大会論文集, 2010. \bibitem{gems1} Mark DeLoura, Game Programming Gems, Born Digital Inc, 東京, 2002. \bibitem{test} Kent Beck, テスト駆動開発入門, テクノロジックアート, 東京, 2008. \end{thebibliography} %% 付録 \appendix %% \section{} \if0 \begin{biography} \profile{}{}{} %\profile{会員種別}{名前}{紹介文}% 顔写真あり %\profile*{会員種別}{名前}{紹介文}% 顔写真なし \end{biography} \fi \end{document} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/sigss-presen.html Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,573 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> + +<html xmlns="http://www.w3.org/1999/xhtml"> + +<head> +<title>sig-ss_presentation</title> +<!-- metadata --> +<meta name="generator" content="S5" /> +<meta name="version" content="S5 1.1" /> +<meta name="presdate" content="20050728" /> +<meta name="author" content="Eric A. Meyer" /> +<meta name="company" content="Complex Spiral Consulting" /> +<!-- configuration parameters --> +<meta name="defaultView" content="slideshow" /> +<meta name="controlVis" content="hidden" /> +<!-- style sheet links --> +<link rel="stylesheet" href="ui/default/slides.css" type="text/css" media="projection" id="slideProj" /> +<link rel="stylesheet" href="ui/default/outline.css" type="text/css" media="screen" id="outlineStyle" /> +<link rel="stylesheet" href="ui/default/print.css" type="text/css" media="print" id="slidePrint" /> +<link rel="stylesheet" href="ui/default/opera.css" type="text/css" media="projection" id="operaFix" /> +<!-- S5 JS --> +<script src="ui/default/slides.js" type="text/javascript"></script> +</head> +<body> + +<div class="layout"> +<div id="controls"><!-- DO NOT EDIT --></div> +<div id="currentSlide"><!-- DO NOT EDIT --></div> +<div id="header"></div> +<div id="footer"> +<h1>[date:11/03/08]</h1> +<h2>Game Framework Cerium を用いたゲームプログラミングにおけるテスト手法の提案</h2> +</div> + +</div> + + +<div class="presentation"> + +<div class="slide"> +<h1>Game Framework Cerium を用いた<br> + ゲームプログラミングにおける<br> + テスト手法の提案</h1> +<h3>発表者:小林 佑亮</h3> +<h4>所属:琉球大学 理工学研究科 情報工学専攻 並列信頼研究室</h4> +<h4>指導教員:河野 真治</h4> +</div> + +<div class="slide"> +<h1>発表内容</h1> +<ol> +<li>序論</li> +<li>Cell BE と Cerium</li> +<li>ゲームプログラミングにおけるテスト</li> +<li>テスト対象のシューティングゲーム Super Dandy</li> +<li>構築したテスト環境</li> +<li>テスト環境によるデバッグと検証</li> +<li>まとめ</li> +</ol> +</div> + +<div class="slide"> +<h1>研究背景</h1> +<font size="4"><ul> +<li>我々は PlayStation3(以下 PS3) 上においてゲーム開発が行えるフレームワーク + Cerium を開発した。</li> +<li>Cerium ではプログラムを Task という単位に分けて管理し、これを PS3 の +アーキテクチャである Cell B.E に渡して並列処理を行う。</li> +<li>シーケンシャルなプログラムを Task に分割して並列実行させても、 +逐次実行させた時と同じ動作をするとは限らない。</li> +<li>オブジェクト同士のデータの同期や、処理の実行順序など、シーケンシャルな +プログラムに比べて、バグを発生させる要因は多い。</li> +<li>また、ゲームプログラムの特徴はプレイヤーの入力やプログラム内にある乱数 +などの非決定的な要素が多いことが挙げられる。</li> +<li>これによってバグの再現性が低下するため、ゲームプログラムのテストは + 一般的なソフトウェアのテストに比べて難しい</li> +</ul></font> +</div> + +<div class="slide"> +<h1>研究目的</h1> +<font size="4"><ul> +<li>本研究では Task に分割されたゲームプログラムがシーケンシャルなバージョン +と同じ動作である事を確認できるテスト環境の構築を目的とする。</li> +<li>プレイヤーの入力や乱数などの非決定的な要素を固定化し、バグの再現性を +低下させずにテストを行えるようにする。</li> +<li>動作の同一性を確かめるために必要なパラメータの書き出しを行う</li> +<li>高速なテストを行う為、テストに影響しない範囲で実行時間が大きい処理を +排除する。</li> +</ul></font> +</div> + +<div class="slide"> +<h1>Cell Broadband Engine</h1> +<center> +<img src="images/cell.png" width=350 height=150/> +</center> +<ul class="simple"> + <li>SCE と 東芝、IBM によって開発されたCPU</li> + <li>2 thread の PPE(PowerPC Processor Element) と 8 個の + SPE(Synergistic Processor Element)を持つ</li> + <li>各 CPU 間は高速リングバスであるEIB(Element Interface Bus)で + 繋がっている</li> +</ul> +</div> + +<div class="slide"> +<h1>Game Framework Cerium</h1> +<dl> + <b><dt>SceneGraph</dt></b> + <dd>オブジェクトのパラメータやポリゴン情報を tree 構造のノードで管理</dd> + <b><dt>Rendering Engine</dt></b> + <dd>3 種類の Task によって並列に描画処理を行う</dd> + <b><dt>TaskManager</dt></b> + <dd>Task を動的に SPE へ割り振るカーネルとして振舞う</dd> +</dl> +</div> + +<div class="slide"> +<h1>Task に設定できる項目</h1> +<ul class="simple"> + <li>Task 内で処理するデータ</li> + <li>処理したデータの出力先</li> + <li>Task を実行する CPU</li> + <li>Task 同士の依存関係</li> + <li>Task 終了時に実行する関数</li> +</ul> +</div> + +<!-- +<div class="slide"> +<h1>CppUnit</h1> +<ul class="simple"> + <li>xUnit と呼ばれる単体テストのためのフレームワークの内の 1 つ</li> + <li>単体テストとは関数やメソッドなどの比較的小さな単位で行うテストで、 + モジュールへの入力と出力を調べることでそのモジュールが要求された仕様を + 満たしているかをテストする手法</li> + <li>CppUnit は 1 つの事象に対して様々なテストケースを同時にテストできる</li> + <li>羅列したテストケースは一括で実行と結果表示が出来る</li> + <li>しかしこうした単体テストではゲームプログラムのバグを見つけるのは難しい</li> +</ul> +</div> + +<div class="slide"> +<h1>ゲームに対する単体テストの欠点</h1> +<ul> +<li>単体テストは瞬間的な値の正しさは調べられる</li> +<li>しかし常にオブジェクトのパラメータが変化するゲームには有効的ではない</li> +<li>ゲームのバグは他のオブジェクトのパラメータとの関係により発生するものが +多い</li> +<li>一般的な単体テストではゲームのバグの発見は難しい</li> +</ul> +</div> +--> + +<div class="slide"> +<h1>ゲームプログラムの特徴</h1> +<ul class="simple"> + <li>プレイヤーの入力がゲームに影響する</li> + <li>オブジェクトの生成、衝突などの遷移する状態が膨大</li> + <li>遷移する状態が仕様の範囲内に収まるかをチェックするテストは向かない</li> + <li>実際にプレイヤーがゲームをプレイするのが重要なテスト</li> +</ul> +</div> + +<div class="slide"> +<h1>プレイヤーの入力の不定性</h1> +<ul class="simple"> + <li>プレイヤーの入力は常に非決定的(毎回結果が異なる)</li> + <li>同じ人間が同じゲームの同じ場面をプレイしても全く同じ入力をする可能性 + は極めて低い</li> + <li>プレイヤーは制御不能なランダム要素</li> + <li>テストにおけるバグの再現性を低下させている</li> +</ul> +</div> + +<div class="slide"> +<h1>ゲームにおける乱数の役割</h1> +<ul class="simple"> + <li>オブジェクトの振る舞いに多様性を持たせる</li> + <li>ランダムな位置配置に使われる</li> + <li>乱数のランダム性はデバッグをする上でバグの再現を困難にする</li> + <li>対処法としては、乱数生成器を無効にするか、定数でシードする</li> +</ul> +</div> + +<div class="slide"> +<h1>シューティングゲーム SuperDandy</h1> +<table> + <tr> + <td><ul class="simple"> + <li>我々が PlayStation 上でのゲーム開発を行っていた 1998 年に開発</li> + <li>タイトルからゲーム本編中の敵機の登場、ステージクリア、エンディングと + ゲーム的な要素が多い</li> + <li>PlayStation, PlayStation2 Linux, OpenGL と伝統的に移植されてきた</li> + </ul></td> + <td> + <img src="images/dandy.png" width=300 height=250/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>Super Dandy 移植の利点</h1> +<ul class="simple"> + <li>全 5 ステージという、ある程度のボリュームのあるゲーム</li> + <li>衝突判定やオブジェクト判定、ステージクリアによるシーン切り替えと、基本的なゲームの要素が入っている</li> + <li>動作結果を過去の環境と比較することによる新たな環境のチューニングができる</li> +</ul> +</div> + +<!-- +<div class="slide"> +<h1>Super Dandy のデータ構造</h1> +<dl> + <b><dt>player</dt></b> + <dd>プレイヤーの操作する機体。xy 座標、残機数、無敵時間、 + コンテニュー回数などを持つ。</dd> + <b><dt>CHARACTER</dt></b> + <dd>敵機や敵の弾。xy 座標とその方向の速さ、体力、倒したときのスコア、 + オブジェクトの種類を表すキャラナンバーを持つ。</dd> + <b><dt>BULLET</dt></b> + <dd>プレイヤーが撃った弾。xy 座標をもつ。プレイヤーが射撃ボタンを押すと + 弾が配列に格納され、敵に当たるか画面外にいくと消滅する。</dd> +</dl> +</div> +--> + +<div class="slide"> +<h1>Task Dandy(Super Dandy Task version)</h1> +<table> + <tr> + <td><ul class="simple"> + <li>オブジェクトの Move や Collision を Task 化</li> + <li>オブジェクトの描画は SceneGraph tree の形成、Rendering Task の + 生成といった Cerium の描画処理を使用</li> + <li>Super Dandy のコードやデータ構造を流用</li> + </ul></td> + <td> + <img src="images/taskdandy.png" width=250 height=250/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>目標とするテスト環境</h1> +<ul class="simple"> + <li>逐次実行時と並列実行時による動作の違いが確認できる</li> + <li>プレイヤーの入力や乱数などの非決定的な要素の固定化</li> + <li>高速なテスト環境</li> +</ul> +</div> + +<div class="slide"> +<h1>並列処理によるバグ その1</h1> +<center> + <img src="images/parallel_bug1.png" width=300 height=150> +</center> +<font size="3"><ul class="simple"> + <li>逐次処理では弾の動く処理の後、敵オブジェクトが動く</li> + <li>敵オブジェクトが動く前に被弾したため、敵オブジェクトは削除される</li> + <li>並列処理では、敵オブジェクトの処理が弾の動く処理より先に行われる場合がある</li> + <li>逐次実行では削除されるはずの敵オブジェクトがそのまま生存する</li> +</ul></font> +</div> + +<div class="slide"> +<h1>並列処理によるバグ その2</h1> +<center> + <img src="images/parallel_bug2.png" width=300 height=150> +</center> +<font size="3"><ul class="simple"> + <li>敵オブジェクトと発射した弾の衝突判定が行われる</li> + <li>逐次実行では敵と弾が衝突したとき、逐次的に両方のオブジェクトの消滅処理が行われる</li> + <li>並列処理では敵と弾が衝突したとき、同時に別の敵オブジェクトの衝突判定も行われる</li> + <li>このオブジェクトは弾との衝突判定を行い、削除される</li> +</ul></font> +</div> + +<div class="slide"> +<h1>並列処理のバグを検出するタイミング</h1> +<font size="4"><ul class="simple"> + <li>ゲームの並列処理によるバグは主に衝突判定時に検出される</li> + <li>ゲームプログラムの状態が遷移する時、バグが検出される</li> + <li>ゲームの状態が遷移する時(オブジェクトの削除・生成)、テストログを書き出す</li> + <li>これにより並列処理のバグを洗い出す</li> +</ul></font> +</div> + +<div class="slide"> +<h1>出力されるテストログ</h1> +<center> +<font size="2"> +<div style="border :1px solid #000000"><pre> +F64: CREATE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -128.000000 + vx= 0.000000 vy= 4.000000 +F85: DELETE [NAME]enemy_greenclab_0 [COORD]x= 120.000000 y= -44.000000 + vx= 0.000000 vy= 4.000000 + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +</pre></div></font> +</center> +<font size="3"><dl class="simple"> + <b><dt>F64, F85</dt></b> + <dd>生成、被弾した時の経過フレーム</dd> + <b><dt>CREATE, DELETE</dt></b> + <dd>CREATE はオブジェクトの生成、DELETE はオブジェクトの被弾</dd> + <b><dt>NAME</dt></b> + <dd>オブジェクトの種類と ID</dd> + <b><dt>COORD</dt></b> + <dd>オブジェクトの xy 座標と速度</dd> + <b><dt>BULLET</dt></b> + <dd>その瞬間に画面内に存在した弾丸の数。</dd> +</dl></font> +</div> + +<div class="slide"> +<h1>Capture モードと Trace モード</h1> +<center> + <img src="images/cap_trace.png" width=300 height=150> +</center> +<font size="3"><ul class="simple"> + <li>プレイヤーからの入力を 1 フレーム毎に記録する</li> + <li>書き出したファイルを読み込むことで過去のプレイヤー入力を再現できる</li> + <li>旧バージョンの入力を記録し、新バージョンで読み出すことができる</li> + <li>入力が同じでも動作が違えばそこにバグが潜んでいると考えられる</li> +</ul></font> +</div> + +<div class="slide"> +<h1>SPE 内での予測可能な乱数の使用</h1> +<table> + <tr> + <td><font size="4"><ul class="simple"> + <li>シーケンシャルプログラムでは 1 つの乱数列から順番に乱数を取得</li> + <li>Cell における並列プログラムでは各 SPE 内で 独自の乱数列を生成</li> + <li>シーケンシャルと並列で異なる結果が出る</li> + </ul></font></td> + <td> + <img src="images/spe_random.png" width=350 height=250/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>SPE 内での予測可能な乱数の使用</h1> +<table> + <tr> + <td><ul class="simple"> + <li>あらかじめ PPE 内で乱数列を生成しておく</li> + <li>入力データとして Task に渡す</li> + <li>Task の生成タイミングは Super Dandy の Move や Collision と同じ</li> + <li>Super Dandy と同じ乱数が使用できる</li> + </ul></td> + <td> + <img src="images/spe_random.png" width=350 height=250/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>Cerium における画面の描画処理</h1> +<table> + <tr> + <td><ul class="simple"> + <li>ビデオモードの選択(SDL, OpenGL)</li> + <li>描画処理を行う画面バッファの領域の確保</li> + <li>ゲーム処理の実行</li> + <li>レンダリング Task による画面バッファへの描画</li> + </ul></td> + <td> + <img src="images/video.png" width=300 height=300/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>テスト環境における描画処理</h1> +<table> + <tr> + <td><ul class="simple"> + <li>プレイヤーの入力の自動化により、プログラムを実行するだけでテストが可能</li> + <li>描画処理が不要となる</li> + <li>描画用 Task の生成を行わない事により、テストの高速化ができる</li> + <li>また、画面バッファの確保も不要</li> + </ul></td> + <td> + <img src="images/video2.png" width=300 height=300/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>バグの検出実験</h1> +<ul class="simple"> + <li>OpenGL バージョンを Capture モードでプレイし、入力を記録</li> + <li>記録された入力を用いて Task Dandy を Trace モードで実行</li> + <li>各バージョンで得られたテストログを比較、考察</li> + <li>テストログの違いにより、バグの発生している箇所を特定</li> +</ul> +</div> + +<div class="slide"> +<h1>SuperDandy と TaskDandy の比較</h1> +<font size="4"><pre> +super dandy(OpenGL) >> +F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 + +<< task dandy +F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +F109: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= -24.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +</pre></font> +<ul class="simple"> + <li>OpenGL では別フレームで死んだ 2 つの敵オブジェクトが Task Dandy では + 同フレームで死亡</li> + <li>この時の弾丸の数が一致</li> + <li>片方が死んだ後、弾丸のオブジェクトの除去がされてない</li> + <li>弾丸データが取れていない</li> +</ul> +</div> + +<div class="slide"> +<h1>Collision Task 間でのデータの同期</h1> +<table> + <tr> + <td><ul class="simple"> + <li>Collision Task を同じ CPU に送る</li> + <li>予め衝突判定に必要なパラメータの領域を確保する</li> + <li>その領域のパラメータで衝突判定を行う</li> + <li>SPE 内で変更されたパラメータをメインメモリ側に反映させる</li> + </ul></td> + <td> + <img src="images/collision_reflect.png" width=300 height=300/> + </td> + </tr> +</table> +</div> + +<div class="slide"> +<h1>Collision Task の改良後の比較</h1> +<font size="4"><pre> +super dandy(OpenGL) >> +F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 + +<< task dandy +F109: DELETE [NAME]enemy_greenclab_1 [COORD]x= 56.000000 y= -24.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +F117: DELETE [NAME]enemy_greenclab_2 [COORD]x= 184.000000 y= 40.000000 ... + [BULLET]tlv1 = 2, tlv2 = 0 llv1 = 0 +</pre></font> +<ul class="simple"> + <li>2 つのバージョンのログがフレーム単位で同じ</li> + <li>Collision Task のデータ同期が有効に働いている</li> +</ul> +</div> + +<div class="slide"> +<h1>Task への乱数受け渡しの検証</h1> +<ul class="simple"> + <li>乱数によって初期配置が変わる隕石オブジェクトを用いて検証</li> + <li>多数の隕石オブジェクトが生成されるステージで全ての隕石オブジェクトが + 生成されるのを観察</li> + <li>隕石オブジェクト生成後のパラメータを出力</li> + <li>逐次実行させた場合と並列実行させた場合を比較</li> +</ul> +</div> + +<div class="slide"> +<h1>隕石オブジェクトの実装</h1> +<font size="4"><pre> + int sf; + + sf = random() % 4; + if((sf == 0) || (sf == 1)) + { + p->x = -35; + p->y = random() % (120 - 35); + p->vx = (random() % 4 + 1); + p->vy = random() % 3 + 1; + p->state = chara_state23; + } + if((sf == 2)) + { + ..... + } + if(sf == 3) + { + ..... +</pre></font> +</div> + +<div class="slide"> +<h1>実行結果</h1> +<font size="4"><pre> +demolog >> +[ID]0 [COORD]x= 320.000000 y= 66.000000 vx= -2.000000 vy= 0.000000 +[ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 +... +[ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 +... +[ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 +... + +<< tdandylog +[ID]6 [COORD]x= 220.000000 y= -30.000000 vx= 1.000000 vy= 4.000000 +[ID]11 [COORD]x= -35.000000 y= 57.000000 vx= 3.000000 vy= 3.000000 +[ID]1 [COORD]x= -35.000000 y= 20.000000 vx= 3.000000 vy= 1.000000 +... +</pre></font> +</div> + +<div class="slide"> +<h1>乱数受け渡しによる実行結果の検証</h1> +<ul class="simple"> + <li>生成された隕石オブジェクトのパラメータが両バージョンで一致している</li> + <li>Task への乱数受け渡しによるバグの再現性の低下防止は有効である</li> +</ul> +</div> + +<div class="slide"> +<h1>ビデオモードによる実行時間の比較</h1> +<ul class="simple"> + <li>実行時間の計測には unix の time コマンドを使用</li> + <li>オリジナルである OpenGL バージョン、Cerium による描画バージョン、描画無しバージョンで計測</li> +</ul> +</div> + +<div class="slide"> +<h1>実行結果</h1> +<center> +<table border="1" cellspacing="0"> + <tr><td></td><th>OpenGL</th><th>Task(no video)</th><th>Task</th></tr> + <tr><th>実行時間</th><td>336.09 sec</td><td>385.17 sec</td><td>6643.16 sec</td></tr> +</table> +</center> +<ul class="simple"> + <li>Task バージョンは劇的に処理時間が増加した</li> + <li>OpenGL は GPU を使用し、TaskDandy はソフトウェアレンダリングである</li> + <li>TaskDandy では Cerium における Task の処理が発生したため、実行時間が大きく増加したと考えられる</li> + <li>描画処理の Task に比べればゲームの Task は処理が小さい</li> +</ul> +</div> + +</ul> +</div> + +<div class="slide"> +<h1>結論</h1> +<h2>本研究では並列環境におけるゲームプログラムのテスト手法を提案した</h2> +<ul class="simple"> + <li>ゲームの状態遷移時におけるバグの検出を行った</li> + <li>ゲームにおけるランダム要素であるプレイヤー入力、乱数生成を固定化した</li> + <li></li> +</ul> +</div> + +</div> +</body> +</html>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/CVS/Entries Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,1 @@ +D/default////
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/CVS/Repository Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,1 @@ +member/koba/document/presentation/ui
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/CVS/Root Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,1 @@ +koba@firefly.cr.ie.u-ryukyu.ac.jp:/home/one/CVS_DB
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/CVS/Entries Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,12 @@ +/blank.gif/1.1/Fri Nov 21 07:36:57 2008// +/bodybg.gif/1.1/Fri Nov 21 07:36:57 2008// +/framing.css/1.1/Fri Nov 21 07:36:57 2008// +/iepngfix.htc/1.1/Fri Nov 21 07:36:57 2008// +/opera.css/1.1/Fri Nov 21 07:36:57 2008// +/outline.css/1.1/Fri Nov 21 07:36:57 2008// +/pretty.css/1.1/Fri Nov 21 07:36:57 2008// +/print.css/1.1/Fri Nov 21 07:36:57 2008// +/s5-core.css/1.1/Fri Nov 21 07:36:57 2008// +/slides.css/1.1/Fri Nov 21 07:36:57 2008// +/slides.js/1.1/Fri Nov 21 07:36:57 2008// +D
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/CVS/Repository Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,1 @@ +member/koba/document/presentation/ui/default
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/CVS/Root Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,1 @@ +koba@firefly.cr.ie.u-ryukyu.ac.jp:/home/one/CVS_DB
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/framing.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,23 @@ +/* The following styles size, place, and layer the slide components. + Edit these if you want to change the overall slide layout. + The commented lines can be uncommented (and modified, if necessary) + to help you with the rearrangement process. */ + +/* target = 1024x768 */ + +div#header, div#footer, .slide {width: 100%; top: 0; left: 0;} +div#header {top: 0; height: 3em; z-index: 1;} +div#footer {top: auto; bottom: 0; height: 2.5em; z-index: 5;} +.slide {top: 0; width: 92%; padding: 3.5em 4% 4%; z-index: 2; list-style: none;} +div#controls {left: 50%; bottom: 0; width: 50%; z-index: 100;} +div#controls form {position: absolute; bottom: 0; right: 0; width: 100%; + margin: 0;} +#currentSlide {position: absolute; width: 10%; left: 45%; bottom: 1em; z-index: 10;} +html>body #currentSlide {position: fixed;} + +/* +div#header {background: #FCC;} +div#footer {background: #CCF;} +div#controls {background: #BBD;} +div#currentSlide {background: #FFC;} +*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/iepngfix.htc Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,42 @@ +<public:component> +<public:attach event="onpropertychange" onevent="doFix()" /> + +<script> + +// IE5.5+ PNG Alpha Fix v1.0 by Angus Turnbull http://www.twinhelix.com +// Free usage permitted as long as this notice remains intact. + +// This must be a path to a blank image. That's all the configuration you need here. +var blankImg = 'ui/default/blank.gif'; + +var f = 'DXImageTransform.Microsoft.AlphaImageLoader'; + +function filt(s, m) { + if (filters[f]) { + filters[f].enabled = s ? true : false; + if (s) with (filters[f]) { src = s; sizingMethod = m } + } else if (s) style.filter = 'progid:'+f+'(src="'+s+'",sizingMethod="'+m+'")'; +} + +function doFix() { + if ((parseFloat(navigator.userAgent.match(/MSIE (\S+)/)[1]) < 5.5) || + (event && !/(background|src)/.test(event.propertyName))) return; + + if (tagName == 'IMG') { + if ((/\.png$/i).test(src)) { + filt(src, 'image'); // was 'scale' + src = blankImg; + } else if (src.indexOf(blankImg) < 0) filt(); + } else if (style.backgroundImage) { + if (style.backgroundImage.match(/^url[("']+(.*\.png)[)"']+$/i)) { + var s = RegExp.$1; + style.backgroundImage = ''; + filt(s, 'crop'); + } else filt(); + } +} + +doFix(); + +</script> +</public:component> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/opera.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,7 @@ +/* DO NOT CHANGE THESE unless you really want to break Opera Show */ +.slide { + visibility: visible !important; + position: static !important; + page-break-before: always; +} +#slide0 {page-break-before: avoid;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/outline.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,15 @@ +/* don't change this unless you want the layout stuff to show up in the outline view! */ + +.layout div, #footer *, #controlForm * {display: none;} +#footer, #controls, #controlForm, #navLinks, #toggle { + display: block; visibility: visible; margin: 0; padding: 0;} +#toggle {float: right; padding: 0.5em;} +html>body #toggle {position: fixed; top: 0; right: 0;} + +/* making the outline look pretty-ish */ + +#slide0 h1, #slide0 h2, #slide0 h3, #slide0 h4 {border: none; margin: 0;} +#slide0 h1 {padding-top: 1.5em;} +.slide h1 {margin: 1.5em 0 0; padding-top: 0.25em; + border-top: 1px solid #888; border-bottom: 1px solid #AAA;} +#toggle {border: 1px solid; border-width: 0 0 1px 1px; background: #FFF;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/pretty.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,86 @@ +/* Following are the presentation styles -- edit away! */ + +body {background: #FFF url(bodybg.gif) -16px 0 no-repeat; color: #000; font-size: 2em;} +:link, :visited {text-decoration: none; color: #00C;} +#controls :active {color: #88A !important;} +#controls :focus {outline: 1px dotted #227;} +h1, h2, h3, h4 {font-size: 100%; margin: 0; padding: 0; font-weight: inherit;} +ul, pre {margin: 0; line-height: 1em;} +html, body {margin: 0; padding: 0;} + +blockquote, q {font-style: italic;} +blockquote {padding: 0 2em 0.5em; margin: 0 1.5em 0.5em; text-align: center; font-size: 1em;} +blockquote p {margin: 0;} +blockquote i {font-style: normal;} +blockquote b {display: block; margin-top: 0.5em; font-weight: normal; font-size: smaller; font-style: normal;} +blockquote b i {font-style: italic;} + +kbd {font-weight: bold; font-size: 1em;} +sup {font-size: smaller; line-height: 1px;} + +.slide code {padding: 2px 0.25em; font-weight: bold; color: #533;} +.slide code.bad, code del {color: red;} +.slide code.old {color: silver;} +.slide pre {padding: 0; margin: 0.25em 0 0.5em 0.5em; color: #533; font-size: 90%;} +.slide pre code {display: block;} +.slide ul {margin-left: 5%; margin-right: 7%; list-style: disc;} +.slide li {margin-top: 0.75em; margin-right: 0;} +.slide ul ul {line-height: 1;} +.slide ul ul li {margin: .2em; font-size: 85%; list-style: square;} +.slide img.leader {display: block; margin: 0 auto;} + +div#header, div#footer {background: #005; color: #AAB; + font-family: Verdana, Helvetica, sans-serif;} +div#header {background: #005 url(bodybg.gif) -16px 0 no-repeat; + line-height: 1px;} +div#footer {font-size: 0.5em; font-weight: bold; padding: 1em 0;} +#footer h1, #footer h2 {display: block; padding: 0 1em;} +#footer h2 {font-style: italic;} + +div.long {font-size: 0.75em;} +.slide h1 {position: absolute; top: 0.7em; left: 87px; z-index: 1; + margin: 0; padding: 0.3em 0 0 50px; white-space: nowrap; + font: bold 150%/1em Helvetica, sans-serif; text-transform: capitalize; + color: #DDE; background: #005;} +.slide h3 {font-size: 130%;} +h1 abbr {font-variant: small-caps;} + +div#controls {position: absolute; left: 50%; bottom: 0; + width: 50%; + text-align: right; font: bold 0.9em Verdana, Helvetica, sans-serif;} +html>body div#controls {position: fixed; padding: 0 0 1em 0; + top: auto;} +div#controls form {position: absolute; bottom: 0; right: 0; width: 100%; + margin: 0; padding: 0;} +#controls #navLinks a {padding: 0; margin: 0 0.5em; + background: #005; border: none; color: #779; + cursor: pointer;} +#controls #navList {height: 1em;} +#controls #navList #jumplist {position: absolute; bottom: 0; right: 0; background: #DDD; color: #227;} + +#currentSlide {text-align: center; font-size: 0.5em; color: #449;} + +#slide0 {padding-top: 3.5em; font-size: 90%;} +#slide0 h1 {position: static; margin: 1em 0 0; padding: 0; + font: bold 2em Helvetica, sans-serif; white-space: normal; + color: #000; background: transparent;} +#slide0 h2 {font: bold italic 1em Helvetica, sans-serif; margin: 0.25em;} +#slide0 h3 {margin-top: 1.5em; font-size: 1.5em;} +#slide0 h4 {margin-top: 0; font-size: 1em;} + +ul.urls {list-style: none; display: inline; margin: 0;} +.urls li {display: inline; margin: 0;} +.note {display: none;} +.external {border-bottom: 1px dotted gray;} +html>body .external {border-bottom: none;} +.external:after {content: " \274F"; font-size: smaller; color: #77B;} + +.incremental, .incremental *, .incremental *:after {color: #DDE; visibility: visible;} +img.incremental {visibility: hidden;} +.slide .current {color: #B02;} + + +/* diagnostics + +li:after {content: " [" attr(class) "]"; color: #F88;} + */ \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/print.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,1 @@ +/* The following rule is necessary to have all slides appear in print! DO NOT REMOVE IT! */ .slide, ul {page-break-inside: avoid; visibility: visible !important;} h1 {page-break-after: avoid;} body {font-size: 12pt; background: white;} * {color: black;} #slide0 h1 {font-size: 200%; border: none; margin: 0.5em 0 0.25em;} #slide0 h3 {margin: 0; padding: 0;} #slide0 h4 {margin: 0 0 0.5em; padding: 0;} #slide0 {margin-bottom: 3em;} h1 {border-top: 2pt solid gray; border-bottom: 1px dotted silver;} .extra {background: transparent !important;} div.extra, pre.extra, .example {font-size: 10pt; color: #333;} ul.extra a {font-weight: bold;} p.example {display: none;} #header {display: none;} #footer h1 {margin: 0; border-bottom: 1px solid; color: gray; font-style: italic;} #footer h2, #controls {display: none;} /* The following rule keeps the layout stuff out of print. Remove at your own risk! */ .layout, .layout * {display: none !important;} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/s5-core.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,9 @@ +/* Do not edit or override these styles! The system will likely break if you do. */ + +div#header, div#footer, div#controls, .slide {position: absolute;} +html>body div#header, html>body div#footer, + html>body div#controls, html>body .slide {position: fixed;} +.handout {display: none;} +.layout {display: block;} +.slide, .hideme, .incremental {visibility: hidden;} +#slide0 {visibility: visible;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/slides.css Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,3 @@ +@import url(s5-core.css); /* required to make the slide show run at all */ +@import url(framing.css); /* sets basic placement and size of slide components */ +@import url(pretty.css); /* stuff that makes the slides look better than blah */ \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/slides.js Sun Mar 06 17:29:49 2011 +0900 @@ -0,0 +1,553 @@ +// S5 v1.1 slides.js -- released into the Public Domain +// +// Please see http://www.meyerweb.com/eric/tools/s5/credits.html for information +// about all the wonderful and talented contributors to this code! + +var undef; +var slideCSS = ''; +var snum = 0; +var smax = 1; +var incpos = 0; +var number = undef; +var s5mode = true; +var defaultView = 'slideshow'; +var controlVis = 'visible'; + +var isIE = navigator.appName == 'Microsoft Internet Explorer' && navigator.userAgent.indexOf('Opera') < 1 ? 1 : 0; +var isOp = navigator.userAgent.indexOf('Opera') > -1 ? 1 : 0; +var isGe = navigator.userAgent.indexOf('Gecko') > -1 && navigator.userAgent.indexOf('Safari') < 1 ? 1 : 0; + +function hasClass(object, className) { + if (!object.className) return false; + return (object.className.search('(^|\\s)' + className + '(\\s|$)') != -1); +} + +function hasValue(object, value) { + if (!object) return false; + return (object.search('(^|\\s)' + value + '(\\s|$)') != -1); +} + +function removeClass(object,className) { + if (!object) return; + object.className = object.className.replace(new RegExp('(^|\\s)'+className+'(\\s|$)'), RegExp.$1+RegExp.$2); +} + +function addClass(object,className) { + if (!object || hasClass(object, className)) return; + if (object.className) { + object.className += ' '+className; + } else { + object.className = className; + } +} + +function GetElementsWithClassName(elementName,className) { + var allElements = document.getElementsByTagName(elementName); + var elemColl = new Array(); + for (var i = 0; i< allElements.length; i++) { + if (hasClass(allElements[i], className)) { + elemColl[elemColl.length] = allElements[i]; + } + } + return elemColl; +} + +function isParentOrSelf(element, id) { + if (element == null || element.nodeName=='BODY') return false; + else if (element.id == id) return true; + else return isParentOrSelf(element.parentNode, id); +} + +function nodeValue(node) { + var result = ""; + if (node.nodeType == 1) { + var children = node.childNodes; + for (var i = 0; i < children.length; ++i) { + result += nodeValue(children[i]); + } + } + else if (node.nodeType == 3) { + result = node.nodeValue; + } + return(result); +} + +function slideLabel() { + var slideColl = GetElementsWithClassName('*','slide'); + var list = document.getElementById('jumplist'); + smax = slideColl.length; + for (var n = 0; n < smax; n++) { + var obj = slideColl[n]; + + var did = 'slide' + n.toString(); + obj.setAttribute('id',did); + if (isOp) continue; + + var otext = ''; + var menu = obj.firstChild; + if (!menu) continue; // to cope with empty slides + while (menu && menu.nodeType == 3) { + menu = menu.nextSibling; + } + if (!menu) continue; // to cope with slides with only text nodes + + var menunodes = menu.childNodes; + for (var o = 0; o < menunodes.length; o++) { + otext += nodeValue(menunodes[o]); + } + list.options[list.length] = new Option(n + ' : ' + otext, n); + } +} + +function currentSlide() { + var cs; + if (document.getElementById) { + cs = document.getElementById('currentSlide'); + } else { + cs = document.currentSlide; + } + cs.innerHTML = '<span id="csHere">' + snum + '<\/span> ' + + '<span id="csSep">\/<\/span> ' + + '<span id="csTotal">' + (smax-1) + '<\/span>'; + if (snum == 0) { + cs.style.visibility = 'hidden'; + } else { + cs.style.visibility = 'visible'; + } +} + +function go(step) { + if (document.getElementById('slideProj').disabled || step == 0) return; + var jl = document.getElementById('jumplist'); + var cid = 'slide' + snum; + var ce = document.getElementById(cid); + if (incrementals[snum].length > 0) { + for (var i = 0; i < incrementals[snum].length; i++) { + removeClass(incrementals[snum][i], 'current'); + removeClass(incrementals[snum][i], 'incremental'); + } + } + if (step != 'j') { + snum += step; + lmax = smax - 1; + if (snum > lmax) snum = lmax; + if (snum < 0) snum = 0; + } else + snum = parseInt(jl.value); + var nid = 'slide' + snum; + var ne = document.getElementById(nid); + if (!ne) { + ne = document.getElementById('slide0'); + snum = 0; + } + if (step < 0) {incpos = incrementals[snum].length} else {incpos = 0;} + if (incrementals[snum].length > 0 && incpos == 0) { + for (var i = 0; i < incrementals[snum].length; i++) { + if (hasClass(incrementals[snum][i], 'current')) + incpos = i + 1; + else + addClass(incrementals[snum][i], 'incremental'); + } + } + if (incrementals[snum].length > 0 && incpos > 0) + addClass(incrementals[snum][incpos - 1], 'current'); + ce.style.visibility = 'hidden'; + ne.style.visibility = 'visible'; + jl.selectedIndex = snum; + currentSlide(); + number = 0; +} + +function goTo(target) { + if (target >= smax || target == snum) return; + go(target - snum); +} + +function subgo(step) { + if (step > 0) { + removeClass(incrementals[snum][incpos - 1],'current'); + removeClass(incrementals[snum][incpos], 'incremental'); + addClass(incrementals[snum][incpos],'current'); + incpos++; + } else { + incpos--; + removeClass(incrementals[snum][incpos],'current'); + addClass(incrementals[snum][incpos], 'incremental'); + addClass(incrementals[snum][incpos - 1],'current'); + } +} + +function toggle() { + var slideColl = GetElementsWithClassName('*','slide'); + var slides = document.getElementById('slideProj'); + var outline = document.getElementById('outlineStyle'); + if (!slides.disabled) { + slides.disabled = true; + outline.disabled = false; + s5mode = false; + fontSize('1em'); + for (var n = 0; n < smax; n++) { + var slide = slideColl[n]; + slide.style.visibility = 'visible'; + } + } else { + slides.disabled = false; + outline.disabled = true; + s5mode = true; + fontScale(); + for (var n = 0; n < smax; n++) { + var slide = slideColl[n]; + slide.style.visibility = 'hidden'; + } + slideColl[snum].style.visibility = 'visible'; + } +} + +function showHide(action) { + var obj = GetElementsWithClassName('*','hideme')[0]; + switch (action) { + case 's': obj.style.visibility = 'visible'; break; + case 'h': obj.style.visibility = 'hidden'; break; + case 'k': + if (obj.style.visibility != 'visible') { + obj.style.visibility = 'visible'; + } else { + obj.style.visibility = 'hidden'; + } + break; + } +} + +// 'keys' code adapted from MozPoint (http://mozpoint.mozdev.org/) +function keys(key) { + if (!key) { + key = event; + key.which = key.keyCode; + } + if (key.which == 84) { + toggle(); + return; + } + if (s5mode) { + switch (key.which) { + case 10: // return + case 13: // enter + if (window.event && isParentOrSelf(window.event.srcElement, 'controls')) return; + if (key.target && isParentOrSelf(key.target, 'controls')) return; + if(number != undef) { + goTo(number); + break; + } + case 32: // spacebar + case 34: // page down + case 39: // rightkey + case 40: // downkey + if(number != undef) { + go(number); + } else if (!incrementals[snum] || incpos >= incrementals[snum].length) { + go(1); + } else { + subgo(1); + } + break; + case 33: // page up + case 37: // leftkey + case 38: // upkey + if(number != undef) { + go(-1 * number); + } else if (!incrementals[snum] || incpos <= 0) { + go(-1); + } else { + subgo(-1); + } + break; + case 36: // home + goTo(0); + break; + case 35: // end + goTo(smax-1); + break; + case 67: // c + showHide('k'); + break; + } + if (key.which < 48 || key.which > 57) { + number = undef; + } else { + if (window.event && isParentOrSelf(window.event.srcElement, 'controls')) return; + if (key.target && isParentOrSelf(key.target, 'controls')) return; + number = (((number != undef) ? number : 0) * 10) + (key.which - 48); + } + } + return false; +} + +function clicker(e) { + number = undef; + var target; + if (window.event) { + target = window.event.srcElement; + e = window.event; + } else target = e.target; + if (target.getAttribute('href') != null || hasValue(target.rel, 'external') || isParentOrSelf(target, 'controls') || isParentOrSelf(target,'embed') || isParentOrSelf(target,'object')) return true; + if (!e.which || e.which == 1) { + if (!incrementals[snum] || incpos >= incrementals[snum].length) { + go(1); + } else { + subgo(1); + } + } +} + +function findSlide(hash) { + var target = null; + var slides = GetElementsWithClassName('*','slide'); + for (var i = 0; i < slides.length; i++) { + var targetSlide = slides[i]; + if ( (targetSlide.name && targetSlide.name == hash) + || (targetSlide.id && targetSlide.id == hash) ) { + target = targetSlide; + break; + } + } + while(target != null && target.nodeName != 'BODY') { + if (hasClass(target, 'slide')) { + return parseInt(target.id.slice(5)); + } + target = target.parentNode; + } + return null; +} + +function slideJump() { + if (window.location.hash == null) return; + var sregex = /^#slide(\d+)$/; + var matches = sregex.exec(window.location.hash); + var dest = null; + if (matches != null) { + dest = parseInt(matches[1]); + } else { + dest = findSlide(window.location.hash.slice(1)); + } + if (dest != null) + go(dest - snum); +} + +function fixLinks() { + var thisUri = window.location.href; + thisUri = thisUri.slice(0, thisUri.length - window.location.hash.length); + var aelements = document.getElementsByTagName('A'); + for (var i = 0; i < aelements.length; i++) { + var a = aelements[i].href; + var slideID = a.match('\#slide[0-9]{1,2}'); + if ((slideID) && (slideID[0].slice(0,1) == '#')) { + var dest = findSlide(slideID[0].slice(1)); + if (dest != null) { + if (aelements[i].addEventListener) { + aelements[i].addEventListener("click", new Function("e", + "if (document.getElementById('slideProj').disabled) return;" + + "go("+dest+" - snum); " + + "if (e.preventDefault) e.preventDefault();"), true); + } else if (aelements[i].attachEvent) { + aelements[i].attachEvent("onclick", new Function("", + "if (document.getElementById('slideProj').disabled) return;" + + "go("+dest+" - snum); " + + "event.returnValue = false;")); + } + } + } + } +} + +function externalLinks() { + if (!document.getElementsByTagName) return; + var anchors = document.getElementsByTagName('a'); + for (var i=0; i<anchors.length; i++) { + var anchor = anchors[i]; + if (anchor.getAttribute('href') && hasValue(anchor.rel, 'external')) { + anchor.target = '_blank'; + addClass(anchor,'external'); + } + } +} + +function createControls() { + var controlsDiv = document.getElementById("controls"); + if (!controlsDiv) return; + var hider = ' onmouseover="showHide(\'s\');" onmouseout="showHide(\'h\');"'; + var hideDiv, hideList = ''; + if (controlVis == 'hidden') { + hideDiv = hider; + } else { + hideList = hider; + } + controlsDiv.innerHTML = '<form action="#" id="controlForm"' + hideDiv + '>' + + '<div id="navLinks">' + + '<a accesskey="t" id="toggle" href="javascript:toggle();">Ø<\/a>' + + '<a accesskey="z" id="prev" href="javascript:go(-1);">«<\/a>' + + '<a accesskey="x" id="next" href="javascript:go(1);">»<\/a>' + + '<div id="navList"' + hideList + '><select id="jumplist" onchange="go(\'j\');"><\/select><\/div>' + + '<\/div><\/form>'; + if (controlVis == 'hidden') { + var hidden = document.getElementById('navLinks'); + } else { + var hidden = document.getElementById('jumplist'); + } + addClass(hidden,'hideme'); +} + +function fontScale() { // causes layout problems in FireFox that get fixed if browser's Reload is used; same may be true of other Gecko-based browsers + if (!s5mode) return false; + var vScale = 22; // both yield 32 (after rounding) at 1024x768 + var hScale = 32; // perhaps should auto-calculate based on theme's declared value? + if (window.innerHeight) { + var vSize = window.innerHeight; + var hSize = window.innerWidth; + } else if (document.documentElement.clientHeight) { + var vSize = document.documentElement.clientHeight; + var hSize = document.documentElement.clientWidth; + } else if (document.body.clientHeight) { + var vSize = document.body.clientHeight; + var hSize = document.body.clientWidth; + } else { + var vSize = 700; // assuming 1024x768, minus chrome and such + var hSize = 1024; // these do not account for kiosk mode or Opera Show + } + var newSize = Math.min(Math.round(vSize/vScale),Math.round(hSize/hScale)); + fontSize(newSize + 'px'); + if (isGe) { // hack to counter incremental reflow bugs + var obj = document.getElementsByTagName('body')[0]; + obj.style.display = 'none'; + obj.style.display = 'block'; + } +} + +function fontSize(value) { + if (!(s5ss = document.getElementById('s5ss'))) { + if (!isIE) { + document.getElementsByTagName('head')[0].appendChild(s5ss = document.createElement('style')); + s5ss.setAttribute('media','screen, projection'); + s5ss.setAttribute('id','s5ss'); + } else { + document.createStyleSheet(); + document.s5ss = document.styleSheets[document.styleSheets.length - 1]; + } + } + if (!isIE) { + while (s5ss.lastChild) s5ss.removeChild(s5ss.lastChild); + s5ss.appendChild(document.createTextNode('body {font-size: ' + value + ' !important;}')); + } else { + document.s5ss.addRule('body','font-size: ' + value + ' !important;'); + } +} + +function notOperaFix() { + slideCSS = document.getElementById('slideProj').href; + var slides = document.getElementById('slideProj'); + var outline = document.getElementById('outlineStyle'); + slides.setAttribute('media','screen'); + outline.disabled = true; + if (isGe) { + slides.setAttribute('href','null'); // Gecko fix + slides.setAttribute('href',slideCSS); // Gecko fix + } + if (isIE && document.styleSheets && document.styleSheets[0]) { + document.styleSheets[0].addRule('img', 'behavior: url(ui/default/iepngfix.htc)'); + document.styleSheets[0].addRule('div', 'behavior: url(ui/default/iepngfix.htc)'); + document.styleSheets[0].addRule('.slide', 'behavior: url(ui/default/iepngfix.htc)'); + } +} + +function getIncrementals(obj) { + var incrementals = new Array(); + if (!obj) + return incrementals; + var children = obj.childNodes; + for (var i = 0; i < children.length; i++) { + var child = children[i]; + if (hasClass(child, 'incremental')) { + if (child.nodeName == 'OL' || child.nodeName == 'UL') { + removeClass(child, 'incremental'); + for (var j = 0; j < child.childNodes.length; j++) { + if (child.childNodes[j].nodeType == 1) { + addClass(child.childNodes[j], 'incremental'); + } + } + } else { + incrementals[incrementals.length] = child; + removeClass(child,'incremental'); + } + } + if (hasClass(child, 'show-first')) { + if (child.nodeName == 'OL' || child.nodeName == 'UL') { + removeClass(child, 'show-first'); + if (child.childNodes[isGe].nodeType == 1) { + removeClass(child.childNodes[isGe], 'incremental'); + } + } else { + incrementals[incrementals.length] = child; + } + } + incrementals = incrementals.concat(getIncrementals(child)); + } + return incrementals; +} + +function createIncrementals() { + var incrementals = new Array(); + for (var i = 0; i < smax; i++) { + incrementals[i] = getIncrementals(document.getElementById('slide'+i)); + } + return incrementals; +} + +function defaultCheck() { + var allMetas = document.getElementsByTagName('meta'); + for (var i = 0; i< allMetas.length; i++) { + if (allMetas[i].name == 'defaultView') { + defaultView = allMetas[i].content; + } + if (allMetas[i].name == 'controlVis') { + controlVis = allMetas[i].content; + } + } +} + +// Key trap fix, new function body for trap() +function trap(e) { + if (!e) { + e = event; + e.which = e.keyCode; + } + try { + modifierKey = e.ctrlKey || e.altKey || e.metaKey; + } + catch(e) { + modifierKey = false; + } + return modifierKey || e.which == 0; +} + +function startup() { + defaultCheck(); + if (!isOp) + createControls(); + slideLabel(); + fixLinks(); + externalLinks(); + fontScale(); + if (!isOp) { + notOperaFix(); + incrementals = createIncrementals(); + slideJump(); + if (defaultView == 'outline') { + toggle(); + } + document.onkeyup = keys; + document.onkeypress = trap; + document.onclick = clicker; + } +} + +window.onload = startup; +window.onresize = function(){setTimeout('fontScale()', 50);} \ No newline at end of file