Mercurial > hg > Papers > 2017 > kazuma-thesis
diff 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 diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/slide.pdf.html Tue Feb 14 18:59:03 2017 +0900 @@ -0,0 +1,667 @@ +<!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>