Mercurial > hg > Papers > 2017 > kazuma-thesis
view presen/slide.pdf.html @ 11:4d06f18af177
add prepaper.
author | Kazuma Takeda |
---|---|
date | Tue, 14 Feb 2017 18:59:03 +0900 |
parents | |
children | 7b39f43e4088 |
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/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> <style> .slide {page-break-after: always;} </style> </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-13 20:40:38 +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="jungleapi">JungleのAPI</h1> <p>前章ではJungleの概要を記述した。 本章ではJungleの主なAPIについて紹介する。</p> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="jungle">Jungleの木</h1> <p>Jungleは複数の木を名前を利用して管理しており、名前により作成・編集を行う。</p> <pre lang="Java"><code>// Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す JungleTree createNewTree(string treeName) // JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す JungleTree getTreeByName(string treeName) </code></pre> <p>以下のコードは、Jungleの木を”TreeName”で生成し取得する。</p> <pre lang="Java"><code>JungleTree tree = jungle.createNewTree("GameTree"); </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="treenode">TreeNode</h1> <p>Jungleが保持している木は、複数のノードの集合で出来ている。 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。 ノードに対するアクセスは、TreeNodeクラスに記述されているAPIを用いて行われる。</p> <pre lang="Java"><code>// ノードの子供を扱うChildrenオブジェクトを返す Children getChildren() // ノードが保持しているデータを扱うAttribteオブジェクトを返す Attribute getAttribute() </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="childrenattribute">ChildrenとAttribute</h1> <p>Childrenクラスを利用し、ノードの子どもにアクセスする。</p> <pre lang="Java"><code>// ノードが持っている子どもの個数を返す int size() // ノードが持つ子どもの中から、 変数numで指定された位置にある子ノードを返す Either<Error, TreeNode> at(int num) </code></pre> <p>Attributeクラスを利用し、ノードの保持する値にアクセスする。</p> <pre lang="Java"><code>// ノードからKeyで管理されるValueをobject型で返す object get(string key) // ノードからKeyで管理されるValueをstring型で返す string getString(string key) </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="either">Eitherクラス</h1> <p>Jungleでは例外がある場合、Eitherクラスを用いて行う。</p> <ul> <li>失敗時はA</li> <li>成功時はB</li> </ul> <p>を包んで返す。 失敗した場合ははじめからやり直す。 以下に例を記述する。</p> <pre lang="C"><code class="language-\#">Either<Error,TreeNode> either = children.at(2); if (either.isA()) return either.a(); TreeNode child = either.b(); </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="jungle-1">Jungleのサンプルコード</h1> <p>Jungleの例を記載する。</p> <p>以下のコードは、ルートノードの2番目の子どもから、属性名”name”とペアになっている属性値を取得する。</p> <pre lang="C"><code class="language-\#">JungleTree tree = jungle.getTreeByName("GameTree"); TreeNode root = tree.getRootNode(); Children children = root.getChildren(); Either<Error,TreeNode> either = children.at(2); if (either.isA()) return either.a(); TreeNode child = either.b(); Attribute attribute = child.getAttribute(); string value = attribute.getstring("name"); </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="jungle-2">Jungleの木の編集</h1> <p>Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。</p> <p>JungleTreeEditorクラスには編集を行うために、定義されているAPIを記述する。</p> <p>また、ノードを指定して編集を行う際にNodePathクラスを用いる。</p> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="nodepath">NodePath</h1> <p>Jungleでは、木のノードの位置をNodePathクラスを使って表す。</p> <p>NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。</p> <p>また、ルートノードは例外として-1と表記される。</p> <div style="text-align: center;"> <img src="./images/NodePath.pdf" alt="message" width="400" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-2">ノードの追加</h1> <pre lang="C"><code class="language-\#">// 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置子ノードを追加 Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos) // 変数pathで指定した場所にあるノードに、属性名 変数key 属性値 変数valueのペアで値を挿入 Either<Error, JungleTreeEditor> putAttribute( NodePath path, string key, object value) // 変数pathで指定した場所にあるノードが持つ、属性名 変数keyとペアで保存されているデータを削除 Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, string key) </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-3">コミット</h1> <p>編集の最後にTreeに対してコミットを行う。</p> <pre lang="C"><code class="language-\#">// 木へ行った変更をコミット。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗 Either<Error, JungleTreeEditor> commit() </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-4">ゲームのデータ構造</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<T> iterator() { return new Iterator<T>() { Node<T> 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<T> iterator() { Node<T> 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-1">Eitherのチェック</h1> <p>Haskellでは例外処理はモナド内部で行う設計になっている。 Eitherもその一つである。</p> <p>Jungleではある処理に対してエラーであればA、 なければBをEitherに包んで返す。</p> <p>JavaのJungleでは分岐を使ってチェックする必要があった。</p> <pre lang="Java"><code> // Java Either<Error,TreeNode> 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<A, B> bind (System.Func<B, Either<A, B>> 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<Error, JungleTreeEditor> either = DefaultEither<Error, JungleTreeEditor>.newB(editor); Item apple = new Item("Apple"); either = either.bind ((JungleTreeEditor arg) => { return arg.putAttribute (rootNode, item.name, item); }); </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-5">例題のゲーム</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-6">ゲームデータの種類</h1> <p>ゲームのデータにはいくつかの種類が考えられる。</p> <h2 id="section-7">オブジェクトが単体で持つデータ</h2> <p>シーン内に存在するオブジェクトが持つパラメータ。</p> <p>例えば、プレイヤーのHPや経験値、位置座標などを示す。</p> <h2 id="section-8">オブジェクト1つで複数持つデータ</h2> <p>プレイヤーが持つアイテムデータなどを示す。</p> <h2 id="readonly">マスタデータ(ReadOnly)</h2> <p>アイテムの名前や敵の出現確率などを示す。</p> <p>ゲーム開発者のみが更新できる。</p> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-9">データのデータ設計</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-3">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) => { return arg.putAttribute ("Player", player); }); Enemy enemy = new Enemy (); either = either.bind ((JungleTreeEditor arg) => { return arg.putAttribute ("Enemy", enemy); }); </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-10">データを取り出す</h1> <p>データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。 以下に取り出す例を記述する。</p> <pre lang="C"><code class="language-\#">Player player = attr.get<Player> ("Player"); Enemy enemy = attr.get ("Enemy") as Enemy; </code></pre> <p>データの型の再設計を行ったことによりシーン内のオブジェクトをそのまま格納が可能になった。 格納の際にByte Arrayに変換する必要がない。</p> <p>分散構造や、ネットワークで必要な時だけ変換する。</p> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h1 id="section-11">まとめ</h1> <p>本研究の流れは</p> <ul> <li>Jungle-Sharpの実装</li> <li>UnityでのApplicationの実装</li> <li>問題点の改良</li> </ul> <p>となった。</p> <p>Jungle-Sharpの実装ではそれほど難しくはなかった。 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>