Mercurial > hg > Papers > 2011 > koba-sigss

<!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>
  <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>
<table>
  <tr>
    <td><ul class="simple">
	<li>プレイヤー入力によるゲーム内容への影響</li>
	<li>オブジェクトの生成、衝突などにより状態が遷移</li>
	<li>プレイヤー入力、乱数などのランダム要素</li>
	<br>
	<li>テストプログラムとして我々が開発したシューティングゲーム
	  SuperDandy を用意</li>
	<li>全 5 ステージという、ある程度のボリュームのあるゲーム</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 の形成、描画用 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>並列処理によるバグ</h1>
<table>
  <tr>
    <td><ul class="simple">
	<li>逐次処理と異なり、並列処理では、敵オブジェクトの処理が弾の動く処理より先に行われる場合がある</li>
	<li>逐次実行では削除されるはずの敵オブジェクトがそのまま生存する</li>
    </ul></td>
    <td>
      <center>
	<img src="images/parallel_bug1.png" width=300 height=150>
      </center>
    </td>
  </tr>
  <tr>
      <td><ul class="simple">
	<li>並列処理では敵と弾が衝突したとき、同時に別の敵オブジェクトの衝突判定も行われる</li>
	<li>逐次実行では生存するはずの敵オブジェクトが削除される</li>
    </ul></td>
    <td>
      <center>
	<img src="images/parallel_bug2.png" width=300 height=150>
      </center>
    </td>
  </tr>

</table>

<!--
<font size="3"><ul class="simple">

  <li>逐次処理では弾の動く処理の後、敵オブジェクトが動く</li>
  <li>敵オブジェクトが動く前に被弾したため、敵オブジェクトは削除される</li>
  <li>逐次処理と異なり、並列処理では、敵オブジェクトの処理が弾の動く処理より先に行われる場合がある</li>
  <li>逐次実行では削除されるはずの敵オブジェクトがそのまま生存する</li>
</ul></font>
</div>

<div class="slide">
<h1>並列処理によるバグ その2</h1>
<center>
</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>
</ul></font>
<br>
<center>
  <font size="3">
    <div style="border :2px 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>
</div>

<!--
<div class="slide">
<h1>出力されるテストログ</h1>
<center>
  <font size="4">
    <div style="border :2px 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>プレイヤー入力の固定の実装</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>テスト環境における描画処理</h1>
<table>
  <tr>
    <td><ul class="simple">
	<li>Cerium を用いたゲームでは画面バッファの確保、描画用の Task の生成により画面を描画する</li>
	<li>プレイヤーの入力の固定化とテストログ出力により画面描画を行わずにテストができる</li>
	<li>描画用 Task や画面バッファの生成処理を行わない事により、テストの高速化ができる</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>SuperDandy でプレイヤー入力を記録</li>
  <li>記録された入力を用いて TaskDandy を実行</li>
  <li>各バージョンで得られたテストログを比較</li>
  <li>テストログの違いにより、バグの発生している箇所を特定</li>
</ul>
</div>

<div class="slide">
<h1>SuperDandy と TaskDandy の比較</h1>
<font size="3"><div style="border :2px solid #000000"><pre>
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
</pre></div></font>
<ul class="simple">
  <li>SuperDandy では別フレームで死んだ 2 つの敵オブジェクトが TaskDandy では
  同フレームで死亡</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="3"><div style="border :2px solid #000000"><pre>
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
</pre></div></font>
<ul class="simple">
  <li>2 つのバージョンのログがフレーム単位で同じ</li>
  <li>Collision Task のデータ同期によるバグの除去</li>
</ul>
</div>

<div class="slide">
<h1>隕石オブジェクトによる乱数の検証</h1>
<div style="border :2px solid #000000"><font size="2"><pre>
  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;
      p->state = chara_state23;
    }
  if((sf == 2))
    {
      .....
    }
  if(sf == 3)
    {
      .....
</pre></font></div>
<ul class="simple">
  <li>乱数によって初期配置が変わる隕石オブジェクトを用いて検証</li>
  <li>乱数によって決定される条件式を持つ</li>
  <li>また、乱数によって配置される座標が変化する</li>
  <li>逐次実行させた場合と並列実行させた場合を比較</li>
</ul>
</div>

<div class="slide">
<h1>実行結果</h1>
<div style="border :2px solid #000000"><font size="3"><pre>
demolog >>
[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>
<ul class="simple">
  <li>同一の ID を持つオブジェクト同士では、パラメータが一致している</li>
  <li>Task への乱数受け渡しによる固定化が行われている</li>
</ul>
</div>

<!--
<div class="slide">
<h1>乱数受け渡しによる実行結果の検証</h1>
<ul class="simple">
  <li>生成された隕石オブジェクトのパラメータが両バージョンで一致している</li>
  <li>Task への乱数受け渡しによるバグの再現性の低下防止は有効である</li>
</ul>
</div>
-->

<div class="slide">
<h1>ビデオモードによる実行時間の比較</h1>
<p>SuperDandy と TaskDandy の描画の有無による実行時間を観測</p>
<center>
<table border="1" cellspacing="0">
  <tr><td></td><!--<th>SuperDandy</th>--><th>TaskDandy</th><th>TaskDandy(no video)</th></tr>
  <tr><th>実行時間</th><!--<td>336.09 sec</td>--><td>6643.16 sec</td><td>385.17 sec</td></tr>
</table>
</center>
<ul class="simple">
  <li>描画を行わないことにより、処理時間が大幅に減少した</li>
  <li>描画処理 Task の処理時間が非常に大きい</li>
  <li>Cerium のチューニングにより実行時間は減少する</li>
</ul>
</div>

</ul>
</div>

<div class="slide">
<h1>まとめ</h1>
<!--<h2>本研究では並列環境におけるゲームプログラムのテスト手法を提案した</h2>-->
<ul class="simple">
  <li>ゲームの状態遷移時におけるバグの検出を行った</li>
  <li>ゲームにおけるランダム要素であるプレイヤー入力、乱数生成を固定化した</li>
  <li>描画の除去によるテストの高速化を行った</li>
  <br>
  <li>ゲームの状態遷移数を数えることにより、ゲーム内の全ての事象をテストできる</li>
  <li>並列環境上における、ゲームプログラムのテストを自動化する事が可能</li>
  <li>今後はゲームの状態遷移数の数え上げを行う</li>
</ul>
</div>

</div>
</body>
</html>
author	koba <koba@cr.ie.u-ryukyu.ac.jp>
date	Sun, 06 Mar 2011 19:47:14 +0900
parents	7b20f8b4d697
children	7e707cabd73a