title: ゲームエンジンにおけるJungleDatabaseの提案
author: Kazuma Takeda
profile:
lang: Japanese
code-engine: coderay

# この発表では

- RDBとNoSQL
- Jungle Databseの提案
- Jungleの仕様
- ゲームのデータ構造
- Jungle-Sharpの実装
- 例題ゲームの実装
- Jungle-Sharpの改良点

# RDBとNoSQL

Relational Databseと呼ばれるRDBは行と列からなる2次元のテーブルにより実装されているデータベース。
データ型として文字列や数値、日付、Bool型がある。

データの一貫性を重視しているRDBでは分散システムには向いていない。

NoSQL(Not Only SQL) Databaseと呼ばれる非リレーショナル型のデータベース。
スキームを持たないため、扱うデータの型を気にしなくてもよい。

一貫性を一部犠牲にしているNoSQLでは分散させることが可能である。
CassandraやMongoDBなどが例に挙げられる。

# Jungle Databaseの提案

Jungleは過去の変更データを保存しつつ新しい木を構築してく木構造(非破壊構造)の手法をとる。
非破壊にすることにより、データを読み出す側と書き込む側のデータを安全に扱うことができる。

ノード自身にはKey-Valueのデータを格納することができる。
これはデータベースのレコードに相当する。

Jungleのトランザクションはルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。
最後にルートをアトミックに入れ替えてコミットする。
コミットが失敗した場合は最初からやり直す。
これにより、原子性を実現する。

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

# JungleのDatabase

Jungleの構造としては以下の図のようになっている。

<div style="text-align: center;">
　<img src="./images/transaction.pdf" alt="message" width="700">
</div>

# ゲームのデータ構造

Jungleはもともと認証管理システムやWeb向けに作られたものである。
これらはすべて木構造をベースとしている。

ゲームでも同じことが考えられる。
そこでゲームエンジンUnity向けにJungleの再実装を行い、ゲーム向けのデータベースとしての提案を行う。

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

# Atomic Refarenceの実装

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

JavaのモジュールにはAtomicRefarenceが存在した。
C\#では自分で作る必要があった。

``` C\#

// C\#  
public bool CompareAndSet(T newValue, T prevValue) {
    T oldValue = value;
    return (oldValue 
        != Interlocked.CompareExchange 
                  (ref value, newValue, prevValue));
}

```

# Eitherのチェック

Haskellでは例外処理はモナド内部で行う設計になっている。
Eitherもその一つである。

Jungleではある処理に対してエラーであればA、
なければBをEitherに包んで返す。

JavaのJungleでは分岐を使ってチェックする必要があった。

``` Java

// Java
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();

```

# bindの実装

Eitherクラスに実装したbindは自身のEitherをチェックした後、
エラーがなければ関数fを実行し評価する仕組みである。

```C\#

public Either<A, B> bind (System.Func<B, Either<A, B>> f) {
    if (this.isA ()) {
      return this;
    }
    return f (this.b ());
}

```

ユーザー側でのエラーのチェックは不要になるが、関数fのLambda式を自分で定義する必要がある。
次のページにその例を示す。

# bindの引数に渡すラムダ式の例

``` C\#

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);
});

```

# 例題のゲーム

前章ではJungle-Sharpのどのように実装したかを述べた。

この章では実際にゲームを構築し、そのデータベースとしてJungleを導入する。

今回作ったゲームはMinecraftの簡易版である。

<div style="text-align: center;">
　<img src="./images/craft.png" alt="message" width="500px">
</div>

プレイヤーは自由にマップを移動し、ステージの破壊や、生成を行うことができる。

破壊や生成のオペレーションに合わせてJungleのノードにも同期する。


# ゲームデータの種類

ゲームのデータにはいくつかの種類が考えられる。

## オブジェクトが単体で持つデータ

シーン内に存在するオブジェクトが持つパラメータ。

例えば、プレイヤーのHPや経験値、位置座標などを示す。

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

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

## マスタデータ(ReadOnly)

アイテムの名前や敵の出現確率などを示す。

ゲーム開発者のみが更新できる。

# データのデータ設計

Jungleには複数の木を持つことができる。

ゲームのシーンを構成するGameTreeとアイテムを管理するItemTreeをJungle内に作る。

# GameTree

GameTreeではシーン内にあるPlayerやStageを構成するCubeなどを格納している。
Jungleではオブジェクトが単体で持つデータと、オブジェクト一つで複数持つデータを同時に表現できる。
以下にその例を示す。

<div style="text-align: center;">
　<img src="./images/tree.pdf" alt="message" width="600px">
</div>

# ItemTree

ItemTreeではItemデータを格納している。
データの種類ではマスターデータにあたいする。
以下にその例を示す。

<div style="text-align: center;">
　<img src="./images/itemtree.pdf" alt="message" width="800px">
</div>

# Jungleの改良

前章では例題となるゲームを作成した。
その上でJungleではデータ型について問題となった。

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

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

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

``` C\#

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);
});

```

# データを取り出す

データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。
以下に取り出す例を記述する。

``` C\#
Player player = attr.get<Player> ("Player");
Enemy enemy = attr.get ("Enemy") as Enemy;
```

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

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

# Jungle-Sharpの評価

<div style="text-align: center;">
  <img src="./images/benchmark.pdf" alt="message" width="700px">
</div>

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

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


# まとめ

本研究の流れは

- Jungle-Sharpの実装
- UnityでのApplicationの実装
- 問題点の改良

である。

Jungle-Sharpの実装ではJavaと比較的似ている言語であるため、移行する方法を確立した。
C\#版のJungleではJavaに劣らない、もしくはそれ以上のパフォーマンスを出すことが出来た。

実際のゲームに合わせたJungleの拡張を行った。

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

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

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

実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。