|
5
|
1 title: ゲームエンジンにおけるJungleDatabaseの提案
|
|
|
2 author: Kazuma Takeda
|
|
0
|
3 profile:
|
|
|
4 lang: Japanese
|
|
|
5 code-engine: coderay
|
|
|
6
|
|
10
|
7 # この発表のセクション
|
|
|
8
|
|
|
9 - RDBとNoSQL
|
|
|
10 - Jungle Databseの提案
|
|
|
11 - Jungleの仕様
|
|
|
12 - ゲームのデータ構造
|
|
|
13 - Jungle-Sharpの実装
|
|
|
14 - 例題ゲームの実装
|
|
|
15 - Jungle-Sharpの改良点
|
|
|
16
|
|
|
17 # RDBとNoSQL
|
|
|
18
|
|
|
19 Relational Databseと呼ばれるRDBは行と列からなる2次元のテーブルにより実装されているデータベース。
|
|
|
20 データ型として文字列や数値、日付、Bool型がある。
|
|
|
21
|
|
|
22 データの一貫性を重視しているRDBでは分散システムには向いていない。
|
|
|
23
|
|
|
24 NoSQL(Not Only SQL) Databaseと呼ばれる非リレーショナル型のデータベース。
|
|
|
25 スキームを持たないため、扱うデータの型を気にしなくてもよい。
|
|
|
26
|
|
|
27 一貫性を一部犠牲にしているNoSQLでは分散させることが可能である。
|
|
|
28 CassandraやMongoDBなどが例に挙げられる。
|
|
|
29
|
|
|
30 # インピーダンスミスマッチ
|
|
|
31
|
|
|
32 プログラム中ではListやネスト構造によりデータを扱うことができる。
|
|
|
33 しかしデータベースにはそのような概念はない。
|
|
|
34
|
|
|
35 そこにプログラムとデータベースの間にギャップが生じる。
|
|
|
36 これをインピーダンスミスマッチという。
|
|
|
37
|
|
|
38 RDBではネスト構造を許さない第一正規形とは相容れない。
|
|
|
39
|
|
|
40
|
|
|
41 # NoSQLのトランザクション
|
|
|
42
|
|
|
43 CassandraやほとんどのNoSQLではACIDなトランザクションがない。
|
|
|
44 トランザクション中の処理は外部からは閲覧出来ない。
|
|
|
45 しかし、複数行を1回で書き換える機能を持っていないため、
|
|
|
46 データを書き込んでいる途中の状態が見えてしまう場合がある。
|
|
|
47
|
|
|
48 # Jungle Databaseの提案
|
|
|
49
|
|
|
50 前章までRDBではプログラムとのミスマッチや分散構造に向いていない問題、NoSQLではトランザクションでの問題点について触れた。
|
|
|
51 これらの問題を解決するため、当研究室で開発しているデータベースJungleを提案する。
|
|
|
52
|
|
|
53 Jungleは過去の変更データを保存しつつ新しい木を構築してく木構造(非破壊構造)の手法をとる。
|
|
|
54 非破壊にすることにより、データを読み出す側と書き込む側のデータを安全に扱うことができる。
|
|
|
55
|
|
|
56 Jungleは名前で管理された木のあつまりからなる。
|
|
|
57 木は複数のノードの集合からなる。
|
|
|
58
|
|
|
59 ノード自身にはKey-Valueのデータを格納することができる。
|
|
|
60 これはデータベースのレコードに相当する。
|
|
|
61
|
|
|
62 Jungleのトランザクションはルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。
|
|
|
63 最後にルートをアトミックに入れ替えてコミットする。
|
|
|
64 コミットが失敗した場合は最初からやり直す。
|
|
|
65 これにより、原子性を実現する。
|
|
|
66
|
|
|
67 Jungleはcommit logを持ち、それを他のノードやディスクに転送することにより、
|
|
|
68 分散構成と永続性を実現する。
|
|
|
69
|
|
13
|
70 # JungleのDatabase
|
|
10
|
71
|
|
13
|
72 Jungleの構造としては以下の図のようになっている。
|
|
10
|
73
|
|
|
74 <div style="text-align: center;">
|
|
13
|
75 <img src="./images/transaction.pdf" alt="message" width="700">
|
|
10
|
76 </div>
|
|
|
77
|
|
|
78 # ゲームのデータ構造
|
|
|
79
|
|
|
80 Jungleはもともと認証管理システムやWeb向けに作られたものである。
|
|
|
81 これらはすべて木構造をベースとしている。
|
|
|
82
|
|
|
83 ゲームでも同じことが考えられる。
|
|
|
84 そこでゲームエンジンUnity向けにJungleの再実装を行い、ゲーム向けのデータベースとしての提案を行う。
|
|
|
85
|
|
|
86 Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC\#で制御する。
|
|
|
87 Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
|
|
|
88 これをシーングラフと言う。
|
|
|
89 シーングラフをそのままJungleに格納するという手法が考えられる。
|
|
|
90
|
|
|
91 # Jungle-Sharpの実装
|
|
|
92
|
|
|
93 JungleはもともとJavaとHaskellで書かれていた。
|
|
|
94 今回はJava版をベースにC\#で再実装する。
|
|
|
95
|
|
|
96 エラーをチェックするEitherの部分だけはHaskellの要素を取ってくる。
|
|
|
97
|
|
|
98 # Atomic Refarenceの実装
|
|
|
99
|
|
|
100 Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。
|
|
|
101 競合している書き込み中に自分の書き込みが成功した場合に関数commit()が成功する。
|
|
|
102 失敗した場合ははじめからもう一度行う。
|
|
|
103
|
|
|
104 JavaのモジュールにはAtomicRefarenceが存在した。
|
|
|
105 C\#では自分で作る必要があった。
|
|
|
106
|
|
|
107 ``` C\#
|
|
0
|
108
|
|
10
|
109 // C\#
|
|
|
110 public bool CompareAndSet(T newValue, T prevValue) {
|
|
|
111 T oldValue = value;
|
|
|
112 return (oldValue
|
|
|
113 != Interlocked.CompareExchange
|
|
|
114 (ref value, newValue, prevValue));
|
|
|
115 }
|
|
|
116
|
|
|
117 ```
|
|
|
118
|
|
|
119 # Listの実装
|
|
|
120
|
|
|
121 木やリストをたどる時にJavaではIteratorを用いる。
|
|
|
122 Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
|
|
|
123 C\#では木やリストを辿りながらyeildで次の値を返す。
|
|
|
124 Javaでは以下のように実装されている。
|
|
|
125
|
|
|
126 ``` Java
|
|
|
127
|
|
|
128 public Iterator<T> iterator() {
|
|
|
129 return new Iterator<T>() {
|
|
|
130 Node<T> currentNode = head.getNext();
|
|
|
131
|
|
|
132 @Override
|
|
|
133 public boolean hasNext() {
|
|
|
134 return currentNode.getAttribute()
|
|
|
135 != null;
|
|
|
136 }
|
|
|
137
|
|
|
138 @Override
|
|
|
139 public T next() {
|
|
|
140 T attribute
|
|
|
141 = currentNode.getAttribute();
|
|
|
142 currentNode
|
|
|
143 = currentNode.getNext();
|
|
|
144 return attribute;
|
|
|
145 }
|
|
|
146 };
|
|
|
147 }
|
|
|
148
|
|
|
149 ```
|
|
|
150
|
|
|
151 # Listの実装
|
|
|
152
|
|
|
153 C\#ではそもそも匿名クラスの中でメソッドを定義できない。
|
|
|
154 この場合はIEnuratorを使って書き直すことができた。
|
|
|
155
|
|
|
156 ``` C\#
|
|
|
157
|
|
|
158 // C\#
|
|
|
159 public IEnumerator<T> iterator() {
|
|
|
160 Node<T> currentNode = head.getNext();
|
|
|
161 while (currentNode.getAttribute() != null) {
|
|
|
162 yield return (T)currentNode.getAttribute();
|
|
|
163 currentNode = currentNode.getNext ();
|
|
|
164 }
|
|
|
165 }
|
|
|
166
|
|
|
167 ```
|
|
|
168
|
|
|
169 # Eitherのチェック
|
|
|
170
|
|
|
171 Haskellでは例外処理はモナド内部で行う設計になっている。
|
|
|
172 Eitherもその一つである。
|
|
|
173
|
|
|
174 Jungleではある処理に対してエラーであればA、
|
|
|
175 なければBをEitherに包んで返す。
|
|
|
176
|
|
|
177 JavaのJungleでは分岐を使ってチェックする必要があった。
|
|
|
178
|
|
|
179 ``` Java
|
|
|
180
|
|
|
181 // Java
|
|
|
182 Either<Error,TreeNode> either = children.at(2);
|
|
|
183 if (either.isA())
|
|
|
184 return either.a();
|
|
|
185 TreeNode child = either.b();
|
|
|
186
|
|
|
187 ```
|
|
|
188
|
|
|
189 # bindの実装
|
|
|
190
|
|
|
191 Eitherクラスに実装したbindは自身のEitherをチェックした後、
|
|
|
192 エラーがなければ関数fを実行し評価する仕組みである。
|
|
|
193
|
|
|
194 ```C\#
|
|
|
195
|
|
|
196 public Either<A, B> bind (System.Func<B, Either<A, B>> f) {
|
|
|
197 if (this.isA ()) {
|
|
|
198 return this;
|
|
|
199 }
|
|
|
200 return f (this.b ());
|
|
|
201 }
|
|
|
202
|
|
|
203 ```
|
|
|
204
|
|
|
205 ユーザー側でのエラーのチェックは不要になるが、関数fのLambda式を自分で定義する必要がある。
|
|
|
206 次のページにその例を示す。
|
|
|
207
|
|
|
208 # bindの引数に渡すラムダ式の例
|
|
|
209
|
|
|
210 ``` C\#
|
|
|
211
|
|
|
212 Either<Error, JungleTreeEditor> either = DefaultEither<Error, JungleTreeEditor>.newB(editor);
|
|
|
213 Item apple = new Item("Apple");
|
|
|
214
|
|
|
215 either = either.bind ((JungleTreeEditor arg) => {
|
|
|
216 return arg.putAttribute (rootNode, item.name, item);
|
|
|
217 });
|
|
|
218
|
|
|
219 ```
|
|
|
220
|
|
|
221 # 例題のゲーム
|
|
|
222
|
|
|
223 前章ではJungle-Sharpのどのように実装したかを述べた。
|
|
|
224
|
|
|
225 この章では実際にゲームを構築し、そのデータベースとしてJungleを導入する。
|
|
|
226
|
|
|
227 今回作ったゲームはMinecraftの簡易版である。
|
|
0
|
228
|
|
10
|
229 <div style="text-align: center;">
|
|
|
230 <img src="./images/craft.png" alt="message" width="400">
|
|
|
231 </div>
|
|
|
232
|
|
|
233 プレイヤーは自由にマップを移動し、ステージの破壊や、生成を行うことができる。
|
|
|
234
|
|
|
235 破壊や生成のオペレーションに合わせてJungleのノードにも同期する。
|
|
|
236
|
|
|
237
|
|
|
238 # ゲームデータの種類
|
|
|
239
|
|
|
240 ゲームのデータにはいくつかの種類が考えられる。
|
|
|
241
|
|
|
242 ## オブジェクトが単体で持つデータ
|
|
|
243
|
|
|
244 シーン内に存在するオブジェクトが持つパラメータ。
|
|
|
245
|
|
|
246 例えば、プレイヤーのHPや経験値、位置座標などを示す。
|
|
|
247
|
|
|
248 ## オブジェクト1つで複数持つデータ
|
|
|
249
|
|
|
250 プレイヤーが持つアイテムデータなどを示す。
|
|
|
251
|
|
|
252 ## マスタデータ(ReadOnly)
|
|
|
253
|
|
|
254 アイテムの名前や敵の出現確率などを示す。
|
|
|
255
|
|
|
256 ゲーム開発者のみが更新できる。
|
|
|
257
|
|
|
258 # データのデータ設計
|
|
|
259
|
|
|
260 Jungleには複数の木を持つことができる。
|
|
|
261
|
|
|
262 ゲームのシーンを構成するGameTreeとアイテムを管理するItemTreeをJungle内に作る。
|
|
|
263
|
|
|
264 # GameTree
|
|
|
265
|
|
|
266 GameTreeではシーン内にあるPlayerやStageを構成するCubeなどを格納している。
|
|
|
267 Jungleではオブジェクトが単体で持つデータと、オブジェクト一つで複数持つデータを同時に表現できる。
|
|
|
268 以下にその例を示す。
|
|
|
269
|
|
|
270 <div style="text-align: center;">
|
|
|
271 <img src="./images/Tree.pdf" alt="message" width="600">
|
|
|
272 </div>
|
|
|
273
|
|
|
274 # ItemTree
|
|
|
275
|
|
|
276 ItemTreeではItemデータを格納している。
|
|
|
277 データの種類ではマスターデータにあたいする。
|
|
|
278 以下にその例を示す。
|
|
|
279
|
|
|
280 <div style="text-align: center;">
|
|
|
281 <img src="./images/ItemTree.pdf" alt="message" width="800">
|
|
|
282 </div>
|
|
|
283
|
|
|
284 # Jungleの改良
|
|
|
285
|
|
|
286 前章では例題となるゲームを作成した。
|
|
|
287 その上でJungleではデータ型について問題となった。
|
|
0
|
288
|
|
10
|
289 C\#の再実装を行った際にJavaのJungleに沿ってデータの型、つまりByteArrayで設計を行っていた。
|
|
|
290
|
|
|
291 データの格納を行うたびにByte Arrayへのキャストを行う必要がある。
|
|
|
292 しかし、キャストの処理は軽くはない。
|
|
|
293
|
|
|
294 そこで、シーンを構成するObjectをそのまま格納するに仕様を変更した。
|
|
|
295 C\#ではObjectクラスのエイリアスとしてobject型が使える。
|
|
|
296
|
|
|
297 ``` C\#
|
|
|
298
|
|
|
299 Player player = new Player ();
|
|
|
300 either = either.bind ((JungleTreeEditor arg) => {
|
|
|
301 return arg.putAttribute ("Player", player);
|
|
|
302 });
|
|
|
303
|
|
|
304 Enemy enemy = new Enemy ();
|
|
|
305 either = either.bind ((JungleTreeEditor arg) => {
|
|
|
306 return arg.putAttribute ("Enemy", enemy);
|
|
|
307 });
|
|
|
308
|
|
|
309 ```
|
|
|
310
|
|
|
311 # データを取り出す
|
|
|
312
|
|
|
313 データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。
|
|
|
314 以下に取り出す例を記述する。
|
|
|
315
|
|
|
316 ``` C\#
|
|
|
317 Player player = attr.get<Player> ("Player");
|
|
|
318 Enemy enemy = attr.get ("Enemy") as Enemy;
|
|
|
319 ```
|
|
|
320
|
|
|
321 データの型の再設計を行ったことによりシーン内のオブジェクトをそのまま格納が可能になった。
|
|
|
322 格納の際にByte Arrayに変換する必要がない。
|
|
|
323
|
|
|
324 分散構造や、ネットワークで必要な時だけ変換する。
|
|
|
325
|
|
|
326 # まとめ
|
|
|
327
|
|
|
328 本研究の流れは
|
|
|
329
|
|
|
330 - Jungle-Sharpの実装
|
|
|
331 - UnityでのApplicationの実装
|
|
|
332 - 問題点の改良
|
|
|
333
|
|
|
334 である。
|
|
|
335
|
|
12
|
336 Jungle-Sharpの実装ではJavaと比較的似ている言語であるため、移行する方法を確立した。
|
|
10
|
337 C\#版のJungleではJavaに劣らない、もしくはそれ以上のパフォーマンスを出すことが出来た。
|
|
|
338
|
|
|
339 実際のゲームに合わせたJungleの拡張を行った。
|
|
|
340
|
|
|
341 データの格納の際にByteBufferであったものをObject型に変更した。
|
|
|
342 これにより、シーンを構成するObjectデータを手間なく格納することを可能にした。
|
|
|
343
|
|
|
344 Jungleは非破壊であるため、過去の変更を持っている。
|
|
|
345
|
|
|
346 ゲームにおいて過去の木を持ち続けることはパフォーマンスの低下につながる。
|
|
|
347 そのため、過去の木をどこまで必要かを検討しなければならない。
|
|
|
348
|
|
|
349 現在C\#版のJungleにはデータを永続化させる仕組みは備わっていない。
|
|
|
350 実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。
|
