Mercurial > hg > Papers > 2017 > kazuma-thesis

view presen/slide.html @ 22:45181a72dedc default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
image add.
author Kazuma Takeda
date Thu, 16 Feb 2017 10:56:58 +0900
parents 458ff581cdc8
children
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-16 10:54:05 +0900 with Markdown engine kramdown (1.13.1)
                  using options {}
  -->

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

<ul>
  <li>RDBとNoSQL</li>
  <li>Jungle Databaseの提案</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>

<h2 id="relational-database">Relational Database</h2>

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

<h2 id="nosqlnot-only-sql-database">NoSQL(Not Only SQL) Database</h2>

<p>非リレーショナル型のデータベース。
スキームを持たないため、扱うデータの型を気にしなくてもよい。</p>


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

<ul>
  <li>Jungleは過去の変更データを保存しつつ新しい木を構築していく木構造(非破壊構造)の手法をとる。</li>
</ul>

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

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

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

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

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


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="jungleunity">JungleとゲームエンジンUnity</h1>

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

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

<h2 id="unity">Unity</h2>

<p>3Dゲームエンジン
ゲームを構成する要素(Object)をC#で制御する。</p>

<p>Javaと似た言語である。</p>

<h2 id="section-1">シーングラフ</h2>

<p>Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
これをシーングラフと言う。</p>

<p>シーングラフをそのままJungleに格納するという手法が考えられる。</p>


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

<p>Jungleを構成する上で必要な部分で問題や大幅な変更なく、移行出来た部分を以下にリストアップする。</p>

<ul>
  <li>Jungleのデータを構成するTreeMap</li>
  <li>ノードを指定するNodePath</li>
  <li>Jungleや木、ノードを構成する部分</li>
</ul>

<p>しかし、トランザクションを実装する部分では自分で実装する必要があった。</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

Item apple = new Item("Apple");
Item painapple = new Item ("Painapple");

Either&lt;Error,TreeNode&gt; either = edt.putAttribute("Apple", apple);
if (either.isA()) 
    return either.a();
JungleTreeEditor edt = either.b();

either = edt.putAttribute("Painapple", painapple);
if (either.isA()) 
    return either.a();
edt = 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");
Item painapple = new Item("painapple");

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

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>

<p>次にJungleに格納するTreeを紹介します。</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-1">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-6">データを取り出す</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-1">Jungle-Sharpの評価</h1>

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

<p>以下の図より、Unityで実行した結果ではO(n)のグラフを示している。</p>

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


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-7">まとめ</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>
<!-- === end markdown block === -->
</div>


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