\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{Proposal of tree structured database Jungle in Game Engine.}
\icon{
    \includegraphics[width=80mm,bb=0 0 595 642]{fig/ryukyu.pdf} %%元は 642じゃなくて842
}
\year{平成29年度 卒業論文}
\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{ゲームエンジンにおけるデータベース}

この章ではデータベースの種類であるRelational DatabaseとNoSQLについて述べる。
次に分散システムにおいて重要なCAP定理に触れる。

\section{Relational Database}

Relational Database(RDB)は、列と行からなる２次元のテーブルにより実装されるデータベースである。
データ型として文字列、数値、日付、Bool型がある。
RDBはスキーマの決まったデータを扱うことを長所としている。

RDBは主として使われているデータベースであるが、苦手としている事がある。

それは、スキーマレスなデータの扱いやマシン台数を増やし処理速度を上げることである。

テーブルを水平分割や垂直分割によりデータを分割できるが構造としては複雑化していく。

プログラムとデータベースとの間にミスマッチが発生する。
これをインピーダンスミスマッチという。

プログラムではリストやネスト構造によりデータを持つことができる。
しかし、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。

ORMapperではデータベースのレコードをプログラム中のオブジェクトにマッピングし扱うことができる。
オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。
しかしレコードをプログラム中のオブジェクトを対応させるORMapperの技術でインピーダンスミスマッチの本質的な部分を解決することはできない。


\section{ACIDトランザクション}

ACID(Atomicity,Consistency,Isolation,Durability) は
データベースのトランザクションの処理が確実に実行されることを保証するものである\cite{amazonacid}。

ほとんどのRDBではACIDトランザクションを保証している。

\begin{itemize}
\item Atomicity(原子性)

トランザクションを実行する際に、すべて成功するか、すべて失敗するか。

\item Consistency(一貫性)

トランザクション開始時と終了時にデータが一貫していなければならない。

\item Isolation(独立性)

他のトランザクションによる干渉を受けない。

\item Durability(永続性)

コミットしたトランザクションのデータは保存される。

\end{itemize}

\section{NoSQL}

NoSQLはNot Only SQLの略である。

通常NoSQLデータベースは非リレーショナル型であり、スキームの定義がない\cite{nosql}。
そのため、扱うデータの型が決まっていなくても気軽に扱える。

\section{CAP定理}

分散システムにおいて、次の3つを同時に保証することは出来ない。

\begin{itemize}
\item Consistency(一貫性)

すべてのノードはクエリが同じならば同じデータを返す。

\item Availability(可用性)

あるノードに障害が発生しても、機能しているノードにより常にデータの読み書きが行える。

\item Partition-tolerance(分断耐性)

ネットワーク障害によりノードの接続が切れてもデータベースは機能し続けることができる。

\end{itemize}

これはCAP定理\cite{cap}と呼ばれる。
データベースを利用する場合はCAP定理を意識しながら選択する。

一貫性と可用性を重視したデータベースがRDBである。
分断耐性を必要とする場合はNoSQLデータベースとなる。

NoSQLデータベースでは一貫性を取るか、可用性を取るかによって選択するデータベースが変わる。
以下にその2つの例を示す。

\section{MongoDB}

MongoDBは2009年に公開されたNoSQLのデータベースである。
ドキュメント指向型とされ、事前にテーブルの構造を決めておく必要がない。
これをスキーマレスという。

MongoDBはマスター/スレーブ方式のReplicationを採用している。
保存したデータ(マスター)を複数のサーバー(スレーブ)に複製を取る。

スレーブをReadさせることによって負荷分散も可能になる。

また、一台のサーバーにすべてのデータを持たず、複数のサーバーに分割して保持する。
これをShardingという。

MongoDBはReplocationとShardingにより、分断耐性と一貫性を持つ。

\section{Cassandra}

Cassandra\cite{cassandra}は2008年にFacebookによって公開されたKey-Value型のデータベースである。
AmazonのDynamo\cite{amazonacid}とGoogleのBigTable\cite{bigtable}を合わせた特徴を持っている。
Key-Valueであるため、スキーマレスなNoSQLとなる。

Bigtableから採用した、カラムファミリーと呼ばれる構造を基本としている。

カラムファミリーの行の部分はHashMapや連想配列のようにKey-Valueで複数格納している。

1つのKey-Valueの組をカラムと呼ぶ。
RDBとは異なり、カラム名を事前に定義する必要がない。

Cassandraではサーバーノードの配置にConsistent hasingアルゴリズムを用いる。
また、これによりサーバー同士が理論上リング構造になっている。

Consistency Hashingによるリングの形成を図\ref{cassandra_ring}に示す.

   \begin{figure}[h]
     \begin{center}
       \includegraphics[width=10cm]{images/cassandra_ring.pdf}
       \caption{Consisteyncy hashingによるring型トポロジーの形成}
       \label{cassandra_ring}
     \end{center}
   \end{figure} 

   Cassandraはデータを最大どれだけ配置するかを示すReplication factorと, データの読み書きをいくつのノードから行うのかを決めるConsistency Levelの設定が行える。
   Consistency Levelには主に ONE, QUORAM, ALL がある。

   Replication factorの数値をNとした場合, ONE は1つのノード, QUORUMは N/2 + 1 のノード, ALLはNのノードへと読み書きを行う。
   Replication factorとConsistentcy Levelの設定により, Cassandraは最新のデータを取得したいときと
   そうでないときで読み込みと書き込みの速度をあげることができる。
   一貫性が重要なデータに関してはQUORUMにより書き込み読み込みを行うことで常に最新のデータを取得することができる。
   多少データが古くてもよい場合はONEなどを使用することでレスポンスを早くすることができる。
   Consistency Level QUORUMの時のデータ書き込みと読み込みについて図\ref{quorum_write}と図\ref{quorum_read}に示す。
   Consistencyハッシング, Replication factorとConsistency Levelの設定により Cassandra は高い可用性と分断耐性を持つ。

   \begin{figure}[h]
      \begin{center}
        \includegraphics[width=10cm]{images/cassandra_quorum_write.pdf}
        \caption{Consisteyncy Level QUORUMによる書き込み}
        \label{quorum_write}
      \end{center}
    \end{figure}

    \begin{figure}[h]
      \begin{center}
        \includegraphics[width=10cm]{images/cassandra_quorum_read.pdf}
        \caption{Consisteyncy Level QUORUMによる読み込み}
        \label{quorum_read}
      \end{center}
    \end{figure}

\section{Jungleの提案}

この章の前半ではRDBとNoSQLの利点と問題点を取り上げた。

非破壊的木構造データベースのJungleを提案している\cite{jungle}。
Jungleはスケーラビリティのあるデータベースとして開発している。

ウェブサイトの構造は大体が木構造であるため、データ構造として木構造を採用している。
しかし、ウェブサイトだけでなくゲームにおいてもデータ構造が木構造になっている。

そこで、本研究ではJungleの木構造である特性を活かし、ゲームエンジンUnityで作成したゲームで使用する方法を提案する。

データベースとしてJungle Databaseを採用する。

JungleはJavaとHaskellによりそれぞれの言語で開発されている。
本研究で扱うのはJava版をC\#で再実装したものである。

\chapter{Jungle Database の概念}

本章ではまずはJungle Databaseの概念と構造について記述する。

\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を持ち、それを他のノードやディスクに転送することにより、分散構成と持続性を実現する。

\chapter{JungleDatabaseのAPI}

本章ではJungleDatabaseのAPIを記述する。

\section{Jungleの木}

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

\begin{table}[htb]
\begin{center}
\caption{Jungleに実装されているAPI}
\begin{tabular}{|p{14em}|p{14em}|}        \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}

\section{TreeNode}

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

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

\section{Either}

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

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

\begin{itembox}[l]{SaveData.cs}
\scriptsize{
\begin{verbatim}
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();
\end{verbatim}
}
\end{itembox}

\section{ChildrenとAttribute}

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

\begin{table}[htb]
\begin{center}
\caption{Childrenに実装されているAPI}
\begin{tabular}{|p{14em}|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{14em}|p{14em}|} \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}

\section{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}

\section{木の編集}

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

\begin{table}[htb]
\begin{center}
\caption{Editorに実装されているAPI}
\begin{tabular}{|p{14em}|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,　object 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を使うといいかも箇条書きっぽいかきかた。
\begin{itemize}
\item オブジェクトが単体で持つデータ

シーン内に存在するオブジェクトが持つパラメータ
例えばプレイヤーのHPや経験値、位置座標などを示す。

\item オブジェクト1つで複数持つデータ

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

\item マスタデータ(ReadOnly)\cite{gamedata}\cite{gamedata2}

アイテムの名前や敵の出現確率などを示す。
ゲーム開発者のみが更新できる。

\end{itemize}

\section{ゲームデータとデータベース}

ゲームのデータベースとして使われているのがRDBである。

1章で述べたようにRDBとプログラム間ではインピーダンスミスマッチという問題がある。

ここではゲームでのインピーダンスミスマッチの例を紹介する。

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

\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化することができる。

\chapter{Jungle-Sharpの実装}

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

\section{AtomicRefarenceの実装}

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

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

\begin{itembox}[l]{AtomicRefarence.cs}
\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}

bindでのEitherをチェックしつつデータを格納する例を以下に記述する。

\begin{itembox}[l]{DataSaveTest.cs}
\scriptsize{
\begin{verbatim}
  Item　apple = new Item("Apple");

  either = either.bind ((JungleTreeEditor arg) => {
    return arg.addNewChildAt (rootPath, 0);
  });

  either = either.bind ((JungleTreeEditor arg) => {
    return arg.putAttribute (apple);
  });

\end{verbatim}
}
\end{itembox}

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


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

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

\section{例題のゲーム}

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

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{images/craft.png}
\caption{craft}
\label{craft}
\end{center}
\end{figure}

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

\section{ゲームを構成する要素}

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

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

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

\begin{table}[htb]
\begin{center}
\caption{ItemBoxクラスが持つパラメータ}
\begin{tabular}{|p{14em}|p{14em}|}        \hline
int {\tt Broken }&
Itemの耐久力、0になると自身のItemBoxのオブジェクトを破壊\\ \hline
Color {\tt ColorCode}      &
自身のブロックの色 \\ \hline
\end{tabular}
\label{itemboxes}
\end{center}
\end{table}

ステージ上に回復アイテムをランダムに配置する。
回復アイテムにはコンポーネントとして、ItemFoodクラスを紐付ける。
ItemFoodが持つ変数を表\ref{itemfood}に示す。

\begin{table}[htb]
\begin{center}
\caption{ItemFoodクラスが持つパラメータ}
\begin{tabular}{|p{14em}|p{14em}|}        \hline
string {\tt Name}      &
食べ物の名前 \\ \hline
int {\tt Recovery}&
アイテムを取得時に回復する数\\ \hline
\end{tabular}
\label{itemfood}
\end{center}
\end{table}

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

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

\section{データの設計}

Unityにおけるゲームの構成はObjectの親子関係、つまり木構造である。
同じくJungle Databaseは木構造である。
% Unityでシーンを構成する際にデータの設計を気にしなくてもいい。

Jungleでは複数の木を持つことができる。
ゲームのシーンを構成するGameTreeとアイテムを管理するItemTreeをJungle内に作る。

ItemTreeは第4章で述べたマスターデータとして扱う。

GameTreeではシーン内にあるPlayerやStageを構成するCubeなどを格納している。
図\ref{GameTree}ではJungleに格納する構造を示したものである。


\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{images/Tree.pdf}
\caption{GameTree}
\label{GameTree}
\end{center}
\end{figure}

Jungleではオブジェクトが単体で持つデータとオブジェクトが複数持つデータを同時に表現できる。

ノード1つのAttributeに対してデータを格納する。
図\ref{GameTree}のようにPlayerが持つアイテムを表現したい場合はPlayerノードの子としてHaveItemノードを作る。
HaveItemノードの子として持っているアイテムを子ノードとすればよい。

ItemTreeではItemの情報が格納されている。
図\ref{ItemTree}ではJungleに格納しているItemの構造を示したものである。

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{images/ItemTree.pdf}
\caption{ItemTree}
\label{ItemTree}
\end{center}
\end{figure}

ItemTreeではRootノードはItemのTypeが書かれた子ノードを持っている。
子ノードはStageを構成するBox Type、回復アイテムとするFood Typeの２種類である。

\section{ゲームエンジンに特化したデータベース}

C\#の再実装を行った際にJavaのJungleに沿ってデータの型、つまりByteArrayで設計を行っていた。

データの格納を行うたびにByte Arrayへのキャストを行う必要がある。
しかし、キャストの処理は軽くはない。

そこで、シーンを構成するObjectをそのまま格納するに仕様を変更した。
C\#ではObjectクラスのエイリアスとしてobject型が使える。

object型を使うことによってユーザーが定義した任意の変数を代入することができる。
以下にその使用例を記述する。

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

% as演算子はbyte arrayにするよりも早いのでOK?か？
データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。
以下に取り出す例を記述する。

\begin{itembox}[l]{SaveData.cs}
\scriptsize{
\begin{verbatim}
Player player = attr.get<Player> ("Player");
Enemy enemy = attr.get ("Enemy") as Enemy;
\end{verbatim}
}
\end{itembox}

データの型の再設計を行ったことによりシーン内のオブジェクトをそのまま格納が可能になった。
格納の際にByte Arrayに変換する必要がない。

分散構造や、ネットワークで必要な時だけ変換する。

\chapter{Jungle-Sharpの評価}

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

\section{Javaとの比較}

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

% 単一のベンチマーク
\begin{itembox}[l]{BenchMarkmark.cs}
\scriptsize{
\begin{verbatim}
for (int i = 0; i < trial; i++) {
  Either<Error, JungleTreeEditor> either = edt.addNewChildAt (path, i);
  either = either.bind ((JungleTreeEditor arg) => {
    return arg.putAttribute ("name", "Kazuma");
  });
}
\end{verbatim}
}
\end{itembox}

計測に使用したマシンの環境を記述する。

\begin{table}[htb]
\begin{center}
\caption{計測環境}
\begin{tabular}{|p{14em}|p{14em}|}        \hline
OS          & 
Mac OS Sierra 10.12.3 \\ \hline
Memory      &
8 GB 2133 MHz LPDDR3  \\ \hline
CPU         &
2.9 GHz Intel Core i5 \\ \hline
Java        &
1.8.0111              \\ \hline
.NET Runtimes (MonoDevelop-Unity) &
Mono 4.0.5            \\ \hline
.NET Runtimes (Xamarin) &
Mono 4.6.2            \\ \hline
\end{tabular}
\label{itembox}
\end{center}
\end{table}

%% データの図を入れる

計測結果を図\ref{BenchMark}に示す。

\begin{figure}[h]
\begin{center}
\includegraphics[width = 10cm]{images/benchmark.pdf}
\caption{BenchMark}
\label{BenchMark}
\end{center}
\end{figure}

Jungleでは木構造を変更する計算量として、O(1)からO(n)が期待される。

図\ref{BenchMark}より、Unityで実行した結果ではO(n)のグラフを示している。
Unityではレンダリングの機能も兼ねている。
そのためプログラムを実行している間もレンダリングを行っているため、
純粋なPutAttributeの計算時間ではないと考えられる。

XamarinはC\#の性能を確認するために実行した。
C\#で再実装したJungleはJava版とほぼ同じ計算量を示している。


% なんでか？みたいなお話
% プリミティブ型？データ型？
% Javaは純粋オブジェクト指向言語ではないから？
% if文が遅い？
% Lambda式だから早い？ - いや遅い気がする

\section{SQLite3とPlayerPrefsとの比較}

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

以下にJungle、SQLite3、PlayerPrefsでのデータ挿入を行うサンプルコードを記述する。

% 単一のベンチマーク
\begin{itembox}[l]{BenchMarkmark.cs}
\scriptsize{
\begin{verbatim}

// Jungle
for (int i = 0; i < TrialCount; i++) {
    either.bind ((JungleTreeEditor arg) => {
      return arg.putAttribute (rootPath ,"Player_" + i, HP);
    });
}

either.bind ((JungleTreeEditor arg) => {
    return arg.commit();
});

// SQLite3
for (int i = 0; i < TrialCount; i++) {
    sql.ExecuteNonQuery ("insert into player values("+ i + "," + HP + " )");
}

// PlayerPrefs
for (int i = 0; i < TrialCount; i++) {
    PlayerPrefs.SetInt ("Player_" + i, HP);
}
PlayerPrefs.Save ();
\end{verbatim}
}
\end{itembox}

Jungleは挿入後、\tt{commit()}を行うまでを挿入とする。

PlayerPrefsは\tt{Save()}を行うとバイナリに書き出される。
そこまでを挿入とする。

計測結果を以下に記述する。

\begin{table}[htb]
\begin{center}
\caption{実行結果}
\begin{tabular}{|p{14em}|p{14em}|} \hline
Jungle       & 
12.217ms     \\ \hline
SQLite3      &
126.265ms    \\ \hline
PlayerPrefs  &
985.131ms    \\ \hline
\end{tabular}
\label{itembox}
\end{center}
\end{table}

Jungleはデータを直接プログラム内部、つまりオンメモリに持っている。
そのため通信を行わずにデータのやり取りができる。

SQLite3ではデータを挿入のSQLを実行するたびデータベースとの通信を行うため遅くなっている。

PlayerPrefsはデータをまとめてセットすることができる。
しかし、バイナリ形式で保存されるため、書き出す時間がかかってしまう。

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

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

性能としてもJava版に劣らない、もしくはそれ以上のパフォーマンスを出せる。

Eitherでのbindの実装で、より関数型プログラミングを意識しながら記述することができる。
これはJava版にはない実装である。

Jungle DatabaseはもともとWeb向けに作られたデータベースである。

Webではリニアにデータが書き換わることは多くない。
しかしゲームでは扱うデータが多くリニアに書き換わる。

そのため、Jungleの構成は保ちつつ、ゲームに合わせたJungleの拡張を行った。

データの格納の際にByteBufferであったものをObject型に変更した。
これにより、シーンを構成するObjectを手間なく格納することを可能にした。

Jungleは非破壊であるため、過去の変更を持っている。

ゲームにおいて過去の木を持ち続けることはパフォーマンスの低下につながる。
そのため、過去の木をどこまで必要かを検討しなければならない。

現在C\#版のJungleにはデータを永続化させる仕組みは備わっていない。
実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。

%\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}