\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\usepackage{ascmac} 
\usepackage{abstract}
\usepackage{url}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\input{dummy.tex}
\renewcommand{\abstractname}{Abstract}
\begin{document}
\title{ゲームエンジンにおける木構造データベースJungleの提案}
%\title{Supporting NAT in Screen Sharing System TreeVNC}
\author{135768K 氏名 {武田}{和馬} 指導教員 : 河野 真治}
\date{}
\twocolumn [
\maketitle
\begin{onecolabstract}
There are some problems to Relational Database and NoSQL.
One of them as Impedance mismatch. This problem is cased by a difference between the first normal form of database and the programs.
There is a problem that NoSQL is unfit for parallel processing.

Laboratory proposes the database Jungle that solves those problems.
Jungle does not destroy the tree structure.
Jungle develops as a scalable database.

The structure of the game like the structure of the web.
This paper suggests a method to use as a database of game engine Unity.
% way to use? how to use?

Jungle rewrite C\# programming language by written Java.  

% まだかけてない...
\end{onecolabstract}]
\thispagestyle{fancy} 

\section{ゲームエンジンにおけるデータベース}

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

RDBではプログラムとデータベースとの間にミスマッチが発生する。
プログラムではリストやネスト構造によりデータを持つことができる。
しかし、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。
これをインピーダンスミスマッチという。

この例として、ゲーム中のユーザが持つアイテムという単純なものでは
RDBではユーザとアイテムの組をキーとする巨大な表として管理する。

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

NoSQLはNot Only SQLの略である。

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

しかし、トランザクションとしてJsonの一括といった形で処理されている。
そのため並列処理を必要とするアプリケーションには向かない。

\section{Jungle Databaseの提案}

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

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

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

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

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

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

\section{Jungle-Sharpの再実装}

JungleはもともとJavaとHaskellで書かれていた。
今回はJava版をベースにC\#で再実装する。
エラーをチェックするEitherの部分だけはHaskellの要素を取ってくる。

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チェックを行う必要がなくなる。

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

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

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

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

\section{データの設計}

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

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

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

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

ItemTreeではItemの情報が格納されている。
ItemTreeはマスターデータとしている\cite{gamedata}\cite{gamedata2}。
マスターデータとは、アイテムの名前や敵の出現確率などを示す。
ゲーム開発者のみが更新できる。

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

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

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

データを取り出すには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に変換する必要がない。

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

\section{Jungle-Sharpの評価}

本論文では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{7em}|p{7em}|}        \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 = 8cm]{images/benchmark.pdf}
\caption{BenchMark}
\label{BenchMark}
\end{center}
\end{figure}

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

そこで、純粋な速度を測定するためXamarinで動かし測定した。
C\#で再実装したJungleはJava版とほぼ同じ計算量を示している。
これにより、本来のJavaと同じ、もしくはそれ以上のパフォーマンスを引き出すことができる。

\section{まとめ}

本研究ではJungleDatabaseをC\#で再実装を行った。
JavaとC\#は比較的似ている言語であるため移行する方法を確立した。

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

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

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

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

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

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

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

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

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

\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}
\end{document}