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などが例に挙げられる。

# インピーダンスミスマッチ

プログラム中ではListやネスト構造によりデータを扱うことができる。
しかしデータベースにはそのような概念はない。

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

RDBではネスト構造を許さない第一正規形とは相容れない。


# NoSQLのトランザクション

CassandraやほとんどのNoSQLではACIDなトランザクションがない。
トランザクション中の処理は外部からは閲覧出来ない。
しかし、複数行を1回で書き換える機能を持っていないため、
データを書き込んでいる途中の状態が見えてしまう場合がある。

# Jungle Databaseの提案

前章までRDBではプログラムとのミスマッチや分散構造に向いていない問題、NoSQLではトランザクションでの問題点について触れた。
これらの問題を解決するため、当研究室で開発しているデータベースJungleを提案する。

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

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に格納するという手法が考えられる。

# Jungle-Sharpの実装

JungleはもともとJavaとHaskellで書かれていた。
今回はJava版をベースにC\#で再実装する。

エラーをチェックするEitherの部分だけはHaskellの要素を取ってくる。

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

```

# Listの実装

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

``` Java

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

```

# Listの実装

C\#ではそもそも匿名クラスの中でメソッドを定義できない。
この場合はIEnuratorを使って書き直すことができた。

``` C\#

// C\#
public IEnumerator<T> iterator() {
  Node<T> currentNode = head.getNext();
  while (currentNode.getAttribute() != null) {
    yield return (T)currentNode.getAttribute();
    currentNode = currentNode.getNext ();
  }
}

```

# 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="400">
</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="600">
</div>

# ItemTree

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

<div style="text-align: center;">
　<img src="./images/ItemTree.pdf" alt="message" width="800">
</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の実装
- UnityでのApplicationの実装
- 問題点の改良

である。

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

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

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

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

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

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