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のAPI

前章ではJungleの概要を記述した。
本章ではJungleの主なAPIについて紹介する。


# Jungleの木

Jungleは複数の木を名前を利用して管理しており、名前により作成・編集を行う。

``` Java
// Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す
JungleTree  createNewTree(string treeName)

// JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す
JungleTree  getTreeByName(string treeName)

```

以下のコードは、Jungleの木を"TreeName"で生成し取得する。

``` Java
JungleTree tree = jungle.createNewTree("GameTree");
```

# TreeNode

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

``` Java
// ノードの子供を扱うChildrenオブジェクトを返す
Children getChildren()

// ノードが保持しているデータを扱うAttribteオブジェクトを返す
Attribute getAttribute()
```

# ChildrenとAttribute

Childrenクラスを利用し、ノードの子どもにアクセスする。

``` Java
// ノードが持っている子どもの個数を返す
int size()

// ノードが持つ子どもの中から、 変数numで指定された位置にある子ノードを返す
Either<Error, TreeNode> at(int num)
```

Attributeクラスを利用し、ノードの保持する値にアクセスする。

``` Java
// ノードからKeyで管理されるValueをobject型で返す
object get(string key)

// ノードからKeyで管理されるValueをstring型で返す
string getString(string key)
```

# Eitherクラス

Jungleでは例外がある場合、Eitherクラスを用いて行う。

- 失敗時はA
- 成功時はB

を包んで返す。
失敗した場合ははじめからやり直す。
以下に例を記述する。

``` C\#
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();

```

# Jungleのサンプルコード

Jungleの例を記載する。

以下のコードは、ルートノードの2番目の子どもから、属性名"name"とペアになっている属性値を取得する。

``` C\#
JungleTree tree = jungle.getTreeByName("GameTree");
TreeNode root = tree.getRootNode();
Children children = root.getChildren();
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    return either.a();
TreeNode child = either.b();
Attribute attribute = child.getAttribute();
string value = attribute.getstring("name");

```

# Jungleの木の編集

Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。

JungleTreeEditorクラスには編集を行うために、定義されているAPIを記述する。

また、ノードを指定して編集を行う際にNodePathクラスを用いる。

# NodePath

Jungleでは、木のノードの位置をNodePathクラスを使って表す。

NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。

また、ルートノードは例外として-1と表記される。

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

# ノードの追加

``` C\#
// 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置子ノードを追加
Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)
// 変数pathで指定した場所にあるノードに、属性名 変数key 属性値 変数valueのペアで値を挿入
Either<Error, JungleTreeEditor> putAttribute( NodePath path, string key, object value)

// 変数pathで指定した場所にあるノードが持つ、属性名 変数keyとペアで保存されているデータを削除
Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, string key)

```

# コミット

編集の最後にTreeに対してコミットを行う。

``` C\#
// 木へ行った変更をコミット。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗
Either<Error, JungleTreeEditor> commit()
```

# ゲームのデータ構造

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にはデータを永続化させる仕組みは備わっていない。
実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。