Mercurial > hg > Papers > 2017 > kazuma-thesis

<!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 16:56:02 +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="section-1">インピーダンスミスマッチ</h1>

<p>プログラム中ではListやネスト構造によりデータを扱うことができる。
しかしデータベースにはそのような概念はない。</p>

<p>そこにプログラムとデータベースの間にギャップが生じる。
これをインピーダンスミスマッチという。</p>

<p>RDBではネスト構造を許さない第一正規形とは相容れない。</p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="nosql">NoSQLのトランザクション</h1>

<p>CassandraやほとんどのNoSQLではACIDなトランザクションがない。
トランザクション中の処理は外部からは閲覧出来ない。
しかし、複数行を1回で書き換える機能を持っていないため、
データを書き込んでいる途中の状態が見えてしまう場合がある。</p>


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

<p>前章までRDBではプログラムとのミスマッチや分散構造に向いていない問題、NoSQLではトランザクションでの問題点について触れた。
これらの問題を解決するため、当研究室で開発しているデータベースJungleを提案する。</p>

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

<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-2">ゲームのデータ構造</h1>

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

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

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


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

<p>JungleはもともとJavaとHaskellで書かれていた。
今回はJava版をベースにC#で再実装する。</p>

<p>エラーをチェックするEitherの部分だけはHaskellの要素を取ってくる。</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="list">Listの実装</h1>

<p>木やリストをたどる時にJavaではIteratorを用いる。
Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
C#では木やリストを辿りながらyeildで次の値を返す。
Javaでは以下のように実装されている。</p>

<pre lang="Java"><code>
public Iterator&lt;T&gt; iterator() {
  return new Iterator&lt;T&gt;() {
    Node&lt;T&gt; currentNode = head.getNext();

    @Override
    public boolean hasNext() {
      return currentNode.getAttribute()
                                    != null;
    }

    @Override
    public T next() {
      T attribute
            = currentNode.getAttribute();
      currentNode
            = currentNode.getNext();
      return attribute;
    }
  };
}

</code></pre>


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

<p>C#ではそもそも匿名クラスの中でメソッドを定義できない。
この場合はIEnuratorを使って書き直すことができた。</p>

<pre lang="C"><code class="language-\#">
// C\#
public IEnumerator&lt;T&gt; iterator() {
  Node&lt;T&gt; currentNode = head.getNext();
  while (currentNode.getAttribute() != null) {
    yield return (T)currentNode.getAttribute();
    currentNode = currentNode.getNext ();
  }
}

</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-3">例題のゲーム</h1>

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-7">データのデータ設計</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="600" />
</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="800" />
</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-8">データを取り出す</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="section-9">まとめ</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>現在C#版のJungleにはデータを永続化させる仕組みは備わっていない。
実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。</p>
<!-- === end markdown block === -->
</div>


</div><!-- presentation -->
</body>
</html>
author	Kazuma Takeda
date	Wed, 15 Feb 2017 17:20:12 +0900
parents	207fa0b0c3a2
children	b2f7835ac00e