\documentclass[a4j,12pt]{jreport}
\usepackage[dvipdfmx]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{ascmac} 
\usepackage{here}
\usepackage{url}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{listings, jlisting}
%% \input{dummy} %% font

\lstset{
    language=java, 
    tabsize=2, 
    frame=single, 
    basicstyle={\ttfamily\footnotesize},% 
    identifierstyle={\footnotesize},% 
    commentstyle={\footnotesize\itshape},% 
    keywordstyle={\footnotesize\bfseries},% 
    ndkeywordstyle={\footnotesize},% 
    stringstyle={\footnotesize\ttfamily}, 
    breaklines=true, 
    captionpos=b, 
    columns=[l]{fullflexible},% 
    xrightmargin=0zw,% 
    xleftmargin=1zw,% 
    aboveskip=1zw, 
    numberstyle={\scriptsize},% 
    stepnumber=1, 
    numbersep=0.5zw,% 
    lineskip=-0.5ex, 
    numbers=left 
}
\renewcommand{\lstlistingname}{Code}

\setlength{\itemsep}{-1zh}

\title{ゲームエンジンにおける木構造データベースJungleの提案}
%\title{Supporting NAT in Screen Sharing System TreeVNC}
\icon{
    \includegraphics[width=80mm,bb=0 0 595 642]{fig/ryukyu.pdf} %%元は 642じゃなくて842
}
\year{平成28年度 卒業論文}
\belongto{琉球大学工学部情報工学科}
\author{135768K 武田 和馬 \\ 指導教員 {河野 真治} }

%% TreeVNC のNATへの対応
%% マルチスクリーン TreeVNC
%% プリアンブルに記述
%% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要
%%
\makeatletter
\newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}
\makeatother
\setlength\abovecaptionskip{0pt}

\begin{document}

% タイトル
\maketitle
\baselineskip 17pt plus 1pt minus 1pt

\pagenumbering{roman}
\setcounter{page}{0}

\tableofcontents	% 目次
\listoffigures		% 図目次
\listoftables		% 表目次

%以下のように、章ごとに個別の tex ファイルを作成して、
% main.tex をコンパイルして確認する。
%章分けは個人で違うので下のフォーマットを参考にして下さい。

% はじめに

% １章では研究目的を書かない(もったいない)
\chapter{ゲームエンジンにおけるデータベース}

この章ではデータベースのあり方と問題点を提議し、解決方法を提案する。

\section{インピーダンスミスマッチ}

プログラムからデータを分離して扱うデータベースには、
プログラム中のデータ構造とRDBの表構造のズレによりインピーダンスミスマッチという問題がある。

例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。
プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、第一正規形を要求するRDBではネスト構造を許さない。

ORMapperではデータベースのレコードをプログラム中のオブジェクトにマッピングし扱うことができる。
オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。

しかしレコードをプログラム中のオブジェクトを対応させるORMapperの技術でインピーダンスミスマッチの本質的な部分を解決することはできない。

\section{NoSQL}

NoSQLはSQLを必要としない非リレーショナル型のデータベースである。

JsonやXMLを扱えるデータベースでは通常スキームを必要としないため、特に設計を行わずデータを格納することができる。

しかし、不定形の構造の変更をトランザクションとして、Jsonの一括変更という形で処理されてしまっており、並列アプリケーションには向いていない。

\section{Jungleの提案}
当研究室ではデータの変更の際に過去の木構造を保存するデータベースのJungleを提案している\cite{1}。

本研究ではJungleをUnityを用いたゲームで使用する方法を提案する。
データベースとしてJungle DatabaseをC\#で再実装を行い、Unity向けに組み込みを行う。

\chapter{Jungle Database の概念}

本章ではJungle Databaseの構造とAPIについて記述する。

\section{木構造データベースJungle}

当研究室で開発しているJungleは過去の木を保存しつつ、新しい木を構成する手法を採用している。
これを非破壊的木構造という。
非破壊的木構造により、データベースを参照する側と更新する側のデータを安全に扱うことができる。

JungleDatabaseは木の集合からなり、名前で管理される。
木はノードの集合から出来ている。
ノードにはKeyとValueの組からなるデータを持つことができる。
これはデータベースのレコードに相当する。

通常のデータベースと違う点として子のノードを持つことである。

Jungleは、データの変更を一度生成した木を上書きせず、ルートから編集を行うノードまでのコピーを行い、新しく木構造を構築し、そのルートをアトミックに入れ替える{図\ref{nonDestractTreeEdit}}。
これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安全に読み出せるという大きな特徴がある。
しかし、書き込みの手間は大きくなる。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 3cm , bb=0 0 511 188]{images/nonDestractTreeEdit.pdf}
\caption{非破壊的木構造の木の編集}
\label{nonDestractTreeEdit}
\end{center}
\end{figure}

\section{Jungle Database の構造}

非破壊木構造を採用しているJungleでは、木の変更の手間はO(1)からO(n)となり得る。
つまりアプリケーションに合わせて木を設計しない限り充分な性能を出すことは出来ない。
逆に木の設計を行えば高速な処理が可能である。

Jungleはオンメモリで使用することを考えており、一度木のルートを取得すれば、その上で木構造として自由にアクセスしてもよい。

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

\section{JungleDatabaseのAPI}

\subsection{Jungleの木}

Jungleは複数の木の名前を利用し、管理しており、名前により生成、編集を行う。
以下にJungleクラスが提供している木の生成、管理を行うAPI(表\ref{jungleTree})に記述する。

\begin{table}[htb]
\begin{center}
\caption{Jungleに実装されているAPI}
\begin{tabular*}{\textwidth}{|l|l|}        \hline
{\tt JungleTree  createNewTree(string treeName) } & Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
{\tt JungleTree getTreeByName(string treeName)}   & JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
\end{tabular*}
\label{jungleTree}
\end{center}
\end{table}

\subsection{TreeNode}

Jungleが保有する木は、複数のノードの集合で出来ている。
ノードは、自身の子のList、属性名と属性値の組のデータを持つ。
ノードに対するアクセスは表\ref{treeNodeAPI}に記述されているAPIを用いて行う。

\begin{table}[htb]
\begin{center}
\caption{TreeNodeに実装されているAPI}
\begin{tabular}{|p{8em}|p{14em}|}                                  \hline
{\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
{\tt Attribute getAttribute()} &ノードが保持しているデータを扱うAttribteオブジェクトを返す。    \\ \hline
\end{tabular}
\label{treeNodeAPI}
\end{center}
\end{table}

\subsection{Either}

jungleでは例外処理を投げる時にEitherクラスを用いて行う。返って来たEitherのオブジェクトに対して、{\tt isA() }で{\tt Error}かどうかをチェックする。
{\tt Error}でない場合は{\tt b()}で対象のオブジェクトを取り出す事ができる。

以下にルートノードの2番目の子どもを取ってくるのEitherのサンプルコードを記述する。

\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();
\end{lstlisting}


\subsection{ChildrenとAttribute}

Childrenクラスへのアクセスは表\ref{Children}に記述されているAPIを、Attributeクラスへアクセスは表\ref{Attribute}に記述されているAPIを用いて行う。

\begin{table}[htb]
\begin{center}
\caption{Childrenに実装されているAPI}
\begin{tabular}{|p{8em}|p{14em}|}                                  \hline
{\tt int size()}  &  子供の数を返す。\\ \hline
{\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。   \\ \hline
\end{tabular}
\label{Children}
\end{center}
\end{table}

\begin{table}[htb]
\begin{center}
\caption{Attributeに実装されているAPI}
\begin{tabular}{|p{10em}|p{12em}|} \hline
{\tt T get<T>(string key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt Generic}型で返す。 \\ \hline
{\tt string getString(string key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt string}型で返す。 \\ \hline
\end{tabular}
\label{Attribute}
\end{center}
\end{table}

\subsection{NodePath}

Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。
{\tt NodePath}クラスが{\tt < -1,1,2,3>} を表している際の例を図\ref{NodePath}に記す。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 6cm , bb=0 0 568 455]{images/nodePath.pdf}
\caption{NodePath}
\label{NodePath}
\end{center}
\end{figure}

\subsection{木の編集}

Jungleの木の編集は{\tt JungleTreeEditor}クラスを用いて行われる。
{\tt JungleTreeEditor}クラスには編集を行うために、表\ref{editor}に記述されているAPIを用いて行う。

\begin{table}[htb]
\begin{center}
\caption{Editorに実装されているAPI}
\begin{tabular}{|p{8em}|p{14em}|}        \hline
{\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)} &
変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置子ノードを追加する\\ \hline
{\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path, int pos)}      &
変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
{\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path, string key,　byte[] value)} &
変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
{\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, string key)}&
変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されているデータを削除する。\\ \hline
{\tt Either<Error, JungleTreeEditor> commit()}  &
木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
\end{tabular}
\label{editor}
\end{center}
\end{table}

編集を行った後は、関数{\tt editor.commit()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt commit()}は{\tt Error}を返す。
その場合は、木の編集を最初からやり直す必要がある。



\label{chap:introduction}
\pagenumbering{arabic}

%序論の目安としては1枚半ぐらい．
%英語発表者は，最終予稿の「はじめに」の英訳などを載せてもいいかも．

\chapter{Unityでのデータベースの取扱い}
\label{chap:concept}

この章ではゲームにおけるデータについて述べ、その後Jungleとの関係性や実装を記述する。

\section{ゲームのデータ}
ゲーム中のデータには幾つか考えられる。

%% Attonさんの論文に書いてたitemizeを使うといいかも箇条書きっぽいかきかた。
シーンのオブジェクトが持つパラメータ
ゲームのセーブデータ
ネットワーク上で使用するデータ

\section{UnityとJungleの関係}

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

\section{Unityにおけるデータベース}

Unityでのデータベースとして考えられるものとしてはSQLite3、PlayerPrefsが挙げられる。

PlayerPrefsとは、Unityに特化したバイナリ形式でKeyとValueのみで保存されるものである。
セーブ機能に特化していてメモリ上にDBを展開するものではない。

SQLite3ではC\#で利用できるORMapperが提供されている。
プログラム中からデータのインサートやデリートを行う。

%% 思いついたこと入れた　UnityでのJsonのお話
Unity5.3以降のバージョンでは標準でJsonが扱えるようになった。
これにより、インスタンスをJson化することができる。
しかし、変数名をKeyとしてValueを取り出すといったことは出来ない。


\chapter{Jungle-Sharpの実装}

JavaとC\#はよく似た言語であり、移行はそれほど難しくない。
Jungleの中心部分である木構造とIndexを構成する赤黒木のコードはほぼ変更なく移行できた。
C\#ではインナークラスが使えないので明示的なクラスに変換する必要があった。

\section{AtomicRefarenceの実装}

Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。競合している書き込み中に自分の書き込みが成功した場合に関数\verb+success()+が成功する。

JavaではAtomicRefarenceが標準であるがC\#にはなかったためAtomicRefarenceのClassを新たにつくった。

\begin{itembox}[l]{AtomicReplace}
\scriptsize{
\begin{verbatim}
// C#  
public bool CompareAndSet(T newValue, T prevValue) {
    T oldValue = value;
    return (oldValue 
        != Interlocked.CompareExchange 
                  (ref value, newValue, prevValue));
}

// Java
AtomicRefarence<T> atomic = new AtomicRefarence<T>();
atomic.compareAndSet(prevValue, newValue);

\end{verbatim}
}
\end{itembox}


\section{Listの実装}

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

\begin{itembox}[l]{List.java}
\scriptsize{
\begin{verbatim}
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;
    }
  };
}
\end{verbatim}
}
\end{itembox}

C\#ではIEnumeratorがあるのでそれを利用した。
ListのforeachではIteratorを呼び出すために、一つずつ要素を返す必要がある。
yield returnステートメントを利用することで位置が保持され、次に呼ばれた際に続きから値の取り出しが可能になる。
以下にその実装例を示す。

\begin{itembox}[l]{List.cs}
\scriptsize{
\begin{verbatim}
public IEnumerator<T> iterator() {
  Node<T> currentNode = head.getNext();
  while (currentNode.getAttribute() != null) {
    yield return (T)currentNode.getAttribute();
    currentNode = currentNode.getNext ();
  }
}
\end{verbatim}
}
\end{itembox}

\section{bindの実装}

Jungleではデータの編集を行った後、Eitherを用いてエラーのチェックを行う。
エラーがあればエラーが包まれたEitherが返される。
エラーがない場合は指定した型のオブジェクトがEitherに包まれて返される。

これは関数型プログラミング言語、Haskellから採用したものである。

編集を行うたび、Eitherのチェックbindで行うことにより、より関数型プログラミングに特化した書き方が可能になる。
C\#で実装したbindは以下に記述する。

\begin{itembox}[l]{DefaultEither.cs}
\scriptsize{
\begin{verbatim}
public Either<A, B> bind (System.Func<B, Either<A, B>> f) {
    if (this.isA ()) {
      return this;
    }

    return f (this.b ());
}
\end{verbatim}
}
\end{itembox}

Eitherをチェックしつつデータを格納する例を以下に記述する。
\begin{itembox}[l]{DataSaveTest.cs}
\scriptsize{
\begin{verbatim}
System.Collection.Generic.List<BoxItemInfo> infoList = new System.Collection.Generic.List<BoxItemInfo> ();
    infoList.Add (new BoxItemInfo (1, 2, "Grass", "#019540FF"));
    infoList.Add (new BoxItemInfo (2, 4, "Wood", "#7F3C01FF"));
    infoList.Add (new BoxItemInfo (3, 1, "Sand", "#D4500EFF"));
    infoList.Add (new BoxItemInfo (4, 5, "Water", "#2432ADFF"));

    foreach (var info in infoList.Select((v, i) => new {v, i})) {
      either = either.bind ((JungleTreeEditor arg) => {
        return arg.addNewChildAt (path, info.i);
      });

      either = either.bind ((JungleTreeEditor arg) => {
        return arg.putAttribute (info.v);
      });
    }
\end{verbatim}
}
\end{itembox}

bindの実装により、ユーザ側がErrorのチェックする必要がなくなる。


\chapter{Unityで実装したアプリケーション}

本章ではUnityで実際に作成したアプリケーションを示し、どのようにデータの設計を行ったかを述べる。

\section{例題ゲーム}

本論文ではC\#で再実装を行ったJungleをUnityで作られたゲームの上に構築する。
例題のゲームとしては図\ref{craft}に記載した、マインクラフトの簡易版を作成する。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 6cm , bb=0 0 568 455]{images/craft.png}
\caption{craft}
\label{craft}
\end{center}
\end{figure}

プレイヤーは自由にマップを移動し、ステージの破壊や、生成を行うことができる。
破壊や生成のオペレーションに合わせてJungleのノードにも同期する。
この同期も非破壊で行われる。

\section{ゲームの要素}

例題ゲームを構成するゲームの要素を記述する。

Unityではオブジェクトに対してコンポーネントが紐付けられる。
クラスも同様にコンポーネントして扱える。
%% ただし、MonoBehaviourを継承している場合インスタンスを生成することができない。

ステージを構成するブロックのコンポーネントして、ItemBoxクラスを紐付ける。
ItemBoxの持つ変数を表\ref{itembox}に示す。

\begin{table}[htb]
\begin{center}
\caption{ItemBoxクラスが持つAttribute}
\begin{tabular}{|p{8em}|p{14em}|}        \hline
{\tt Broken }&
Itemの体力、0になると自身のItemBoxのオブジェクトを破壊\\ \hline
{\tt ColorCode}      &
自身のブロックの色 \\ \hline
\end{tabular}
\label{itembox}
\end{center}
\end{table}

プレーヤーにはコンポーネントとしてPlayerクラスを紐付ける。
Playerクラスの持つ変数を表\ref{player}に示す。

\begin{table}[htb]
\begin{center}
\caption{Playerクラスが持つAttribute}
\begin{tabular}{|p{8em}|p{14em}|}        \hline
{\tt HP }&
プレイヤーの体力、0になるとゲームオーバー\\ \hline
{\tt ItemList}      &
プレイヤーが持つアイテムのリスト \\ \hline
\end{tabular}
\label{player}
\end{center}
\end{table}

\section{データ設計}

Unityにおけるゲームの構成はObjectの親子関係、つまり木構造である。
Jungle Databaseは木構造型のデータベースであるので、そのまま格納するという手法が考えられる。
%% Unityでシーンを構成する際にデータの設計を気にしなくてもいい。

図\ref{GameTree}ではJungleに格納する構造を示したものである。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 6cm , bb=0 0 568 455]{images/GameTree.pdf}
\caption{GameTree}
\label{GameTree}
\end{center}
\end{figure}


\section{Attributeの格納するデータの型}

UnityではGameObjectクラスがシーンを構成する。


\chapter{ベンチマーク}

本章ではC\#とJavaのJungleとの比較、Jungle-SharpとUnity上で使われるSQLite3、PlayerPrefsとの比較を行う。

\section{Javaとの比較}

本論文ではJavaで書かれたJungle DatabaseをC\#で再実装した。
同じオペレーションでJavaとC\#で計測する。オペレーションは以下に記述する。
なお、1回目の処理はキャッシュを作り処理が遅くなるため、計測は行わず、2回目以降から行う。

\begin{itembox}[l]{Benchmark.cs}
\scriptsize{
\begin{verbatim}
public JungleTreeEditor createTree(JungleTreeEditor editor, int _curY, int _maxHeight, NodePath path) {

    if (_curY == _maxHeight) {
      return editor;
    }

    for (int i = 0; i < 3; i++) {
      Either<Error, JungleTreeEditor> either = editor.addNewChildAt (path, _curY);
      DebugCommon.Assert (either.isA (), "Error");
      editor = either.b ();
      string value = path.add (_curY).ToString ();
      either = editor.putAttribute (path.add (_curY), key, System.Text.Encoding.ASCII.GetBytes (value));
      DebugCommon.Assert (either.isA (), "Error");
      editor = either.b ();
      string value2 = value + "+ index";
      either = editor.putAttribute (path.add (_curY), indexKey, System.Text.Encoding.ASCII.GetBytes (value2));
      DebugCommon.Assert (either.isA (), "Error");
      editor = either.b ();
      editor = createTree (editor, _curY + 1, _maxHeight, path);
    }
    return editor;
  }
\end{verbatim}
}
\end{itembox}

%% データの図を入れる


\section{SQLite3とPlayerPrefsとの比較}

Unityで使われているデータ保存としてSQLite3とPlayerPrefsがある。
それぞれに対し、データの格納を行い、計測する。

%% データの図を入れる/

\chapter{結論}
\section{まとめ}

本論文ではJungleDatabaseをC\#で再実装を行った。
JavaとC\#は比較的似ている言語であるため移行は難しくはなかった。

Jungleはオンメモリで動作する。
その為SQLite3やPlayerPrefsよりも速く動作する。

%\section{Alice での実装}

% 参考文献
\def\line{−\hspace*{-.7zw}−}
\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}


\chapter*{謝辞}
\thispagestyle{empty}

%基本的な内容は以下の通り．参考にしてみて下さい．
%厳密な決まりは無いので，個々人の文体でも構わない．
%GISゼミや英語ゼミに参加した人はその分も入れておく．
%順番は重要なので気を付けるように．(提出前に周りの人に確認してもらう．)

\hspace{1zw}本研究の遂行，また本論文の作成にあたり、御多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治准教授に深く感謝致します。

数々の貴重な御助言と細かな御配慮を戴いた金川 竜己さん、比嘉健太さん、伊波立樹さん、並びに並列信頼研究室の皆様に深く感謝致します。

最後に、有意義な時間を共に過ごした情報工学科の学友、並びに物心両面で支えてくれた両親に深く感謝致します。

\begin{flushright}
    2017年 3月 \\ 武田和馬
\end{flushright}

% 付録

\end{document}