Mercurial > hg > Papers > 2017 > kazuma-thesis

view presen/slide.html @ 17:9a433c2a0ef6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add files
author Kazuma Takeda
date Wed, 15 Feb 2017 19:37:42 +0900
parents b2f7835ac00e
children 071398fb07fd
line wrap: on
line source

<!DOCTYPE html>
<html>
<head>
   <meta http-equiv="content-type" content="text/html;charset=utf-8">
   <title>ゲームエンジンにおけるJungleDatabaseの提案</title>

<meta name="generator" content="Slide Show (S9) 2.2.0 on Ruby 2.3.3 (2016-11-21) [x86_64-darwin16]">
<meta name="author"    content="Kazuma Takeda" >

<!-- style sheet links -->
<link rel="stylesheet" href="s6/themes/projection.css"   media="screen,projection">
<link rel="stylesheet" href="s6/themes/screen.css"       media="screen">
<link rel="stylesheet" href="s6/themes/print.css"        media="print">
<link rel="stylesheet" href="s6/themes/blank.css"        media="screen,projection">

<!-- JS -->
<script src="s6/js/jquery-1.11.3.min.js"></script>
<script src="s6/js/jquery.slideshow.js"></script>
<script src="s6/js/jquery.slideshow.counter.js"></script>
<script src="s6/js/jquery.slideshow.controls.js"></script>
<script src="s6/js/jquery.slideshow.footer.js"></script>
<script src="s6/js/jquery.slideshow.autoplay.js"></script>

<!-- prettify -->
<link rel="stylesheet" href="scripts/prettify.css">
<script src="scripts/prettify.js"></script>

<script>
  $(document).ready( function() {
    Slideshow.init();

    $('code').each(function(_, el) {
      if (!el.classList.contains('noprettyprint')) {
        el.classList.add('prettyprint');
      }
    });
    prettyPrint();
  } );

  
</script>

<!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
<!--[if IE]>
<script src="s6/js/jquery.microsoft.js"></script>
<![endif]-->



</head>
<body>

<div class="layout">
  <div id="header"></div>
  <div id="footer">
    <div align="right">
      <img src="s6/images/logo.svg" width="200px">
    </div>
  </div>
</div>

<div class="presentation">

  <div class='slide cover'>
    <table width="90%" height="90%" border="0" align="center">
      <tr>
        <td>
          <div align="center">
            <h1><font color="#808db5">ゲームエンジンにおけるJungleDatabaseの提案</font></h1>
          </div>
        </td>
      </tr>
      <tr>
        <td>
          <div align="left">
            Kazuma Takeda
            
            <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
          </div>
        </td>
      </tr>
    </table>
  </div>

<div class='slide '>
<!-- === begin markdown block ===

      generated by markdown/1.2.0 on Ruby 2.3.3 (2016-11-21) [x86_64-darwin16]
                on 2017-02-15 19:03:56 +0900 with Markdown engine kramdown (1.13.1)
                  using options {}
  -->

<!-- _S9SLIDE_ -->
<h1 id="section">この発表では</h1>

<ul>
  <li>RDBとNoSQL</li>
  <li>Jungle Databseの提案</li>
  <li>Jungleの仕様</li>
  <li>ゲームのデータ構造</li>
  <li>Jungle-Sharpの実装</li>
  <li>例題ゲームの実装</li>
  <li>Jungle-Sharpの改良点</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="rdbnosql">RDBとNoSQL</h1>

<p>Relational Databseと呼ばれるRDBは行と列からなる2次元のテーブルにより実装されているデータベース。
データ型として文字列や数値、日付、Bool型がある。</p>

<p>データの一貫性を重視しているRDBでは分散システムには向いていない。</p>

<p>NoSQL(Not Only SQL) Databaseと呼ばれる非リレーショナル型のデータベース。
スキームを持たないため、扱うデータの型を気にしなくてもよい。</p>

<p>一貫性を一部犠牲にしているNoSQLでは分散させることが可能である。
CassandraやMongoDBなどが例に挙げられる。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="jungle-database">Jungle Databaseの提案</h1>

<p>Jungleは過去の変更データを保存しつつ新しい木を構築してく木構造(非破壊構造)の手法をとる。
非破壊にすることにより、データを読み出す側と書き込む側のデータを安全に扱うことができる。</p>

<p>ノード自身にはKey-Valueのデータを格納することができる。
これはデータベースのレコードに相当する。</p>

<p>Jungleのトランザクションはルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。
最後にルートをアトミックに入れ替えてコミットする。
コミットが失敗した場合は最初からやり直す。
これにより、原子性を実現する。</p>

<p>Jungleはcommit logを持ち、それを他のノードやディスクに転送することにより、
分散構成と永続性を実現する。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="jungledatabase">JungleのDatabase</h1>

<p>Jungleの構造としては以下の図のようになっている。</p>

<div style="text-align: center;">
　<img src="./images/transaction.pdf" alt="message" width="700" />
</div>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-1">ゲームのデータ構造</h1>

<p>Jungleはもともと認証管理システムやWeb向けに作られたものである。
これらはすべて木構造をベースとしている。</p>

<p>ゲームでも同じことが考えられる。
そこでゲームエンジンUnity向けにJungleの再実装を行い、ゲーム向けのデータベースとしての提案を行う。</p>

<p>Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC#で制御する。
Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
これをシーングラフと言う。
シーングラフをそのままJungleに格納するという手法が考えられる。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="atomic-refarence">Atomic Refarenceの実装</h1>

<p>Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。
競合している書き込み中に自分の書き込みが成功した場合に関数commit()が成功する。
失敗した場合ははじめからもう一度行う。</p>

<p>JavaのモジュールにはAtomicRefarenceが存在した。
C#では自分で作る必要があった。</p>

<pre lang="C"><code class="language-\#">
// C\#  
public bool CompareAndSet(T newValue, T prevValue) {
    T oldValue = value;
    return (oldValue 
        != Interlocked.CompareExchange 
                  (ref value, newValue, prevValue));
}

</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="either">Eitherのチェック</h1>

<p>Haskellでは例外処理はモナド内部で行う設計になっている。
Eitherもその一つである。</p>

<p>Jungleではある処理に対してエラーであればA、
なければBをEitherに包んで返す。</p>

<p>JavaのJungleでは分岐を使ってチェックする必要があった。</p>

<pre lang="Java"><code>
// Java
Either&lt;Error,TreeNode&gt; either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();

</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="bind">bindの実装</h1>

<p>Eitherクラスに実装したbindは自身のEitherをチェックした後、
エラーがなければ関数fを実行し評価する仕組みである。</p>

<pre lang="C"><code class="language-\#">
public Either&lt;A, B&gt; bind (System.Func&lt;B, Either&lt;A, B&gt;&gt; f) {
    if (this.isA ()) {
      return this;
    }
    return f (this.b ());
}

</code></pre>

<p>ユーザー側でのエラーのチェックは不要になるが、関数fのLambda式を自分で定義する必要がある。
次のページにその例を示す。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="bind-1">bindの引数に渡すラムダ式の例</h1>

<pre lang="C"><code class="language-\#">
Either&lt;Error, JungleTreeEditor&gt; either = DefaultEither&lt;Error, JungleTreeEditor&gt;.newB(editor);
Item　apple = new Item("Apple");

either = either.bind ((JungleTreeEditor arg) =&gt; {
	return arg.putAttribute (rootNode, item.name, item);
});

</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-2">例題のゲーム</h1>

<p>前章ではJungle-Sharpのどのように実装したかを述べた。</p>

<p>この章では実際にゲームを構築し、そのデータベースとしてJungleを導入する。</p>

<p>今回作ったゲームはMinecraftの簡易版である。</p>

<div style="text-align: center;">
　<img src="./images/craft.png" alt="message" width="500px" />
</div>

<p>プレイヤーは自由にマップを移動し、ステージの破壊や、生成を行うことができる。</p>

<p>破壊や生成のオペレーションに合わせてJungleのノードにも同期する。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-3">ゲームデータの種類</h1>

<p>ゲームのデータにはいくつかの種類が考えられる。</p>

<h2 id="section-4">オブジェクトが単体で持つデータ</h2>

<p>シーン内に存在するオブジェクトが持つパラメータ。</p>

<p>例えば、プレイヤーのHPや経験値、位置座標などを示す。</p>

<h2 id="section-5">オブジェクト1つで複数持つデータ</h2>

<p>プレイヤーが持つアイテムデータなどを示す。</p>

<h2 id="readonly">マスタデータ(ReadOnly)</h2>

<p>アイテムの名前や敵の出現確率などを示す。</p>

<p>ゲーム開発者のみが更新できる。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-6">データのデータ設計</h1>

<p>Jungleには複数の木を持つことができる。</p>

<p>ゲームのシーンを構成するGameTreeとアイテムを管理するItemTreeをJungle内に作る。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="gametree">GameTree</h1>

<p>GameTreeではシーン内にあるPlayerやStageを構成するCubeなどを格納している。
Jungleではオブジェクトが単体で持つデータと、オブジェクト一つで複数持つデータを同時に表現できる。
以下にその例を示す。</p>

<div style="text-align: center;">
　<img src="./images/tree.pdf" alt="message" width="600px" />
</div>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="itemtree">ItemTree</h1>

<p>ItemTreeではItemデータを格納している。
データの種類ではマスターデータにあたいする。
以下にその例を示す。</p>

<div style="text-align: center;">
　<img src="./images/itemtree.pdf" alt="message" width="800px" />
</div>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="jungle">Jungleの改良</h1>

<p>前章では例題となるゲームを作成した。
その上でJungleではデータ型について問題となった。</p>

<p>C#の再実装を行った際にJavaのJungleに沿ってデータの型、つまりByteArrayで設計を行っていた。</p>

<p>データの格納を行うたびにByte Arrayへのキャストを行う必要がある。
しかし、キャストの処理は軽くはない。</p>

<p>そこで、シーンを構成するObjectをそのまま格納するに仕様を変更した。
C#ではObjectクラスのエイリアスとしてobject型が使える。</p>

<pre lang="C"><code class="language-\#">
Player player = new Player ();
either = either.bind ((JungleTreeEditor arg) =&gt; {
  return arg.putAttribute ("Player", player);
});

Enemy enemy = new Enemy ();
either = either.bind ((JungleTreeEditor arg) =&gt; {
  return arg.putAttribute ("Enemy", enemy);
});

</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-7">データを取り出す</h1>

<p>データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。
以下に取り出す例を記述する。</p>

<pre lang="C"><code class="language-\#">Player player = attr.get&lt;Player&gt; ("Player");
Enemy enemy = attr.get ("Enemy") as Enemy;
</code></pre>

<p>データの型の再設計を行ったことによりシーン内のオブジェクトをそのまま格納が可能になった。
格納の際にByte Arrayに変換する必要がない。</p>

<p>分散構造や、ネットワークで必要な時だけ変換する。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="jungle-sharp">Jungle-Sharpの評価</h1>

<div style="text-align: center;">
  <img src="./images/benchmark.pdf" alt="message" width="700px" />
</div>

<p>以下の図より、Unityで実行した結果ではO(n)のグラフを示している。
Unityではレンダリングの機能も兼ねている。
そのためプログラムを実行している間もレンダリングを行っているため、
純粋なPutAttributeの計算時間ではないと考えられる。</p>

<p>そこで、純粋な速度を測定するためXamarinで動かし測定した。
C#で再実装したJungleはJava版とほぼ同じ計算量を示している。
これにより、本来のJavaと同じ、もしくはそれ以上のパフォーマンスを引き出すことができる。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-8">まとめ</h1>

<p>本研究の流れは</p>

<ul>
  <li>Jungle-Sharpの実装</li>
  <li>UnityでのApplicationの実装</li>
  <li>問題点の改良</li>
</ul>

<p>である。</p>

<p>Jungle-Sharpの実装ではJavaと比較的似ている言語であるため、移行する方法を確立した。
C#版のJungleではJavaに劣らない、もしくはそれ以上のパフォーマンスを出すことが出来た。</p>

<p>実際のゲームに合わせたJungleの拡張を行った。</p>

<p>データの格納の際にByteBufferであったものをObject型に変更した。
これにより、シーンを構成するObjectデータを手間なく格納することを可能にした。</p>

<p>Jungleは非破壊であるため、過去の変更を持っている。</p>

<p>ゲームにおいて過去の木を持ち続けることはパフォーマンスの低下につながる。
そのため、過去の木をどこまで必要かを検討しなければならない。</p>

<p>実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。</p>
<!-- === end markdown block === -->
</div>


</div><!-- presentation -->
</body>
</html>