|
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
|
|
|
70 # JungleのAPI
|
|
|
71
|
|
|
72 前章ではJungleの概要を記述した。
|
|
|
73 本章ではJungleの主なAPIについて紹介する。
|
|
|
74
|
|
|
75
|
|
|
76 # Jungleの木
|
|
|
77
|
|
|
78 Jungleは複数の木を名前を利用して管理しており、名前により作成・編集を行う。
|
|
|
79
|
|
|
80 ``` Java
|
|
|
81 // Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す
|
|
|
82 JungleTree createNewTree(string treeName)
|
|
|
83
|
|
|
84 // JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す
|
|
|
85 JungleTree getTreeByName(string treeName)
|
|
|
86
|
|
|
87 ```
|
|
|
88
|
|
|
89 以下のコードは、Jungleの木を"TreeName"で生成し取得する。
|
|
|
90
|
|
|
91 ``` Java
|
|
|
92 JungleTree tree = jungle.createNewTree("GameTree");
|
|
|
93 ```
|
|
|
94
|
|
|
95 # TreeNode
|
|
|
96
|
|
|
97 Jungleが保持している木は、複数のノードの集合で出来ている。
|
|
|
98 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
|
|
|
99 ノードに対するアクセスは、TreeNodeクラスに記述されているAPIを用いて行われる。
|
|
|
100
|
|
|
101 ``` Java
|
|
|
102 // ノードの子供を扱うChildrenオブジェクトを返す
|
|
|
103 Children getChildren()
|
|
|
104
|
|
|
105 // ノードが保持しているデータを扱うAttribteオブジェクトを返す
|
|
|
106 Attribute getAttribute()
|
|
|
107 ```
|
|
|
108
|
|
|
109 # ChildrenとAttribute
|
|
|
110
|
|
|
111 Childrenクラスを利用し、ノードの子どもにアクセスする。
|
|
|
112
|
|
|
113 ``` Java
|
|
|
114 // ノードが持っている子どもの個数を返す
|
|
|
115 int size()
|
|
|
116
|
|
|
117 // ノードが持つ子どもの中から、 変数numで指定された位置にある子ノードを返す
|
|
|
118 Either<Error, TreeNode> at(int num)
|
|
|
119 ```
|
|
|
120
|
|
|
121 Attributeクラスを利用し、ノードの保持する値にアクセスする。
|
|
0
|
122
|
|
10
|
123 ``` Java
|
|
|
124 // ノードからKeyで管理されるValueをobject型で返す
|
|
|
125 object get(string key)
|
|
|
126
|
|
|
127 // ノードからKeyで管理されるValueをstring型で返す
|
|
|
128 string getString(string key)
|
|
|
129 ```
|
|
|
130
|
|
|
131 # Eitherクラス
|
|
|
132
|
|
|
133 Jungleでは例外がある場合、Eitherクラスを用いて行う。
|
|
|
134
|
|
|
135 - 失敗時はA
|
|
|
136 - 成功時はB
|
|
|
137
|
|
|
138 を包んで返す。
|
|
|
139 失敗した場合ははじめからやり直す。
|
|
|
140 以下に例を記述する。
|
|
|
141
|
|
|
142 ``` C\#
|
|
|
143 Either<Error,TreeNode> either = children.at(2);
|
|
|
144 if (either.isA())
|
|
|
145 return either.a();
|
|
|
146 TreeNode child = either.b();
|
|
|
147
|
|
|
148 ```
|
|
|
149
|
|
|
150 # Jungleのサンプルコード
|
|
|
151
|
|
|
152 Jungleの例を記載する。
|
|
|
153
|
|
|
154 以下のコードは、ルートノードの2番目の子どもから、属性名"name"とペアになっている属性値を取得する。
|
|
|
155
|
|
|
156 ``` C\#
|
|
|
157 JungleTree tree = jungle.getTreeByName("GameTree");
|
|
|
158 TreeNode root = tree.getRootNode();
|
|
|
159 Children children = root.getChildren();
|
|
|
160 Either<Error,TreeNode> either = children.at(2);
|
|
|
161 if (either.isA())
|
|
|
162 return either.a();
|
|
|
163 TreeNode child = either.b();
|
|
|
164 Attribute attribute = child.getAttribute();
|
|
|
165 string value = attribute.getstring("name");
|
|
|
166
|
|
|
167 ```
|
|
|
168
|
|
|
169 # Jungleの木の編集
|
|
|
170
|
|
|
171 Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。
|
|
|
172
|
|
|
173 JungleTreeEditorクラスには編集を行うために、定義されているAPIを記述する。
|
|
|
174
|
|
|
175 また、ノードを指定して編集を行う際にNodePathクラスを用いる。
|
|
|
176
|
|
|
177 # NodePath
|
|
|
178
|
|
|
179 Jungleでは、木のノードの位置をNodePathクラスを使って表す。
|
|
|
180
|
|
|
181 NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。
|
|
|
182
|
|
|
183 また、ルートノードは例外として-1と表記される。
|
|
|
184
|
|
|
185 <div style="text-align: center;">
|
|
|
186 <img src="./images/NodePath.pdf" alt="message" width="400">
|
|
|
187 </div>
|
|
|
188
|
|
|
189 # ノードの追加
|
|
|
190
|
|
|
191 ``` C\#
|
|
|
192 // 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置子ノードを追加
|
|
|
193 Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)
|
|
|
194 // 変数pathで指定した場所にあるノードに、属性名 変数key 属性値 変数valueのペアで値を挿入
|
|
|
195 Either<Error, JungleTreeEditor> putAttribute( NodePath path, string key, object value)
|
|
|
196
|
|
|
197 // 変数pathで指定した場所にあるノードが持つ、属性名 変数keyとペアで保存されているデータを削除
|
|
|
198 Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, string key)
|
|
|
199
|
|
|
200 ```
|
|
|
201
|
|
|
202 # コミット
|
|
|
203
|
|
|
204 編集の最後にTreeに対してコミットを行う。
|
|
|
205
|
|
|
206 ``` C\#
|
|
|
207 // 木へ行った変更をコミット。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗
|
|
|
208 Either<Error, JungleTreeEditor> commit()
|
|
|
209 ```
|
|
|
210
|
|
|
211 # ゲームのデータ構造
|
|
|
212
|
|
|
213 Jungleはもともと認証管理システムやWeb向けに作られたものである。
|
|
|
214 これらはすべて木構造をベースとしている。
|
|
|
215
|
|
|
216 ゲームでも同じことが考えられる。
|
|
|
217 そこでゲームエンジンUnity向けにJungleの再実装を行い、ゲーム向けのデータベースとしての提案を行う。
|
|
|
218
|
|
|
219 Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC\#で制御する。
|
|
|
220 Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
|
|
|
221 これをシーングラフと言う。
|
|
|
222 シーングラフをそのままJungleに格納するという手法が考えられる。
|
|
|
223
|
|
|
224 # Jungle-Sharpの実装
|
|
|
225
|
|
|
226 JungleはもともとJavaとHaskellで書かれていた。
|
|
|
227 今回はJava版をベースにC\#で再実装する。
|
|
|
228
|
|
|
229 エラーをチェックするEitherの部分だけはHaskellの要素を取ってくる。
|
|
|
230
|
|
|
231 # Atomic Refarenceの実装
|
|
|
232
|
|
|
233 Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。
|
|
|
234 競合している書き込み中に自分の書き込みが成功した場合に関数commit()が成功する。
|
|
|
235 失敗した場合ははじめからもう一度行う。
|
|
|
236
|
|
|
237 JavaのモジュールにはAtomicRefarenceが存在した。
|
|
|
238 C\#では自分で作る必要があった。
|
|
|
239
|
|
|
240 ``` C\#
|
|
0
|
241
|
|
10
|
242 // C\#
|
|
|
243 public bool CompareAndSet(T newValue, T prevValue) {
|
|
|
244 T oldValue = value;
|
|
|
245 return (oldValue
|
|
|
246 != Interlocked.CompareExchange
|
|
|
247 (ref value, newValue, prevValue));
|
|
|
248 }
|
|
|
249
|
|
|
250 ```
|
|
|
251
|
|
|
252 # Listの実装
|
|
|
253
|
|
|
254 木やリストをたどる時にJavaではIteratorを用いる。
|
|
|
255 Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
|
|
|
256 C\#では木やリストを辿りながらyeildで次の値を返す。
|
|
|
257 Javaでは以下のように実装されている。
|
|
|
258
|
|
|
259 ``` Java
|
|
|
260
|
|
|
261 public Iterator<T> iterator() {
|
|
|
262 return new Iterator<T>() {
|
|
|
263 Node<T> currentNode = head.getNext();
|
|
|
264
|
|
|
265 @Override
|
|
|
266 public boolean hasNext() {
|
|
|
267 return currentNode.getAttribute()
|
|
|
268 != null;
|
|
|
269 }
|
|
|
270
|
|
|
271 @Override
|
|
|
272 public T next() {
|
|
|
273 T attribute
|
|
|
274 = currentNode.getAttribute();
|
|
|
275 currentNode
|
|
|
276 = currentNode.getNext();
|
|
|
277 return attribute;
|
|
|
278 }
|
|
|
279 };
|
|
|
280 }
|
|
|
281
|
|
|
282 ```
|
|
|
283
|
|
|
284 # Listの実装
|
|
|
285
|
|
|
286 C\#ではそもそも匿名クラスの中でメソッドを定義できない。
|
|
|
287 この場合はIEnuratorを使って書き直すことができた。
|
|
|
288
|
|
|
289 ``` C\#
|
|
|
290
|
|
|
291 // C\#
|
|
|
292 public IEnumerator<T> iterator() {
|
|
|
293 Node<T> currentNode = head.getNext();
|
|
|
294 while (currentNode.getAttribute() != null) {
|
|
|
295 yield return (T)currentNode.getAttribute();
|
|
|
296 currentNode = currentNode.getNext ();
|
|
|
297 }
|
|
|
298 }
|
|
|
299
|
|
|
300 ```
|
|
|
301
|
|
|
302 # Eitherのチェック
|
|
|
303
|
|
|
304 Haskellでは例外処理はモナド内部で行う設計になっている。
|
|
|
305 Eitherもその一つである。
|
|
|
306
|
|
|
307 Jungleではある処理に対してエラーであればA、
|
|
|
308 なければBをEitherに包んで返す。
|
|
|
309
|
|
|
310 JavaのJungleでは分岐を使ってチェックする必要があった。
|
|
|
311
|
|
|
312 ``` Java
|
|
|
313
|
|
|
314 // Java
|
|
|
315 Either<Error,TreeNode> either = children.at(2);
|
|
|
316 if (either.isA())
|
|
|
317 return either.a();
|
|
|
318 TreeNode child = either.b();
|
|
|
319
|
|
|
320 ```
|
|
|
321
|
|
|
322 # bindの実装
|
|
|
323
|
|
|
324 Eitherクラスに実装したbindは自身のEitherをチェックした後、
|
|
|
325 エラーがなければ関数fを実行し評価する仕組みである。
|
|
|
326
|
|
|
327 ```C\#
|
|
|
328
|
|
|
329 public Either<A, B> bind (System.Func<B, Either<A, B>> f) {
|
|
|
330 if (this.isA ()) {
|
|
|
331 return this;
|
|
|
332 }
|
|
|
333 return f (this.b ());
|
|
|
334 }
|
|
|
335
|
|
|
336 ```
|
|
|
337
|
|
|
338 ユーザー側でのエラーのチェックは不要になるが、関数fのLambda式を自分で定義する必要がある。
|
|
|
339 次のページにその例を示す。
|
|
|
340
|
|
|
341 # bindの引数に渡すラムダ式の例
|
|
|
342
|
|
|
343 ``` C\#
|
|
|
344
|
|
|
345 Either<Error, JungleTreeEditor> either = DefaultEither<Error, JungleTreeEditor>.newB(editor);
|
|
|
346 Item apple = new Item("Apple");
|
|
|
347
|
|
|
348 either = either.bind ((JungleTreeEditor arg) => {
|
|
|
349 return arg.putAttribute (rootNode, item.name, item);
|
|
|
350 });
|
|
|
351
|
|
|
352 ```
|
|
|
353
|
|
|
354 # 例題のゲーム
|
|
|
355
|
|
|
356 前章ではJungle-Sharpのどのように実装したかを述べた。
|
|
|
357
|
|
|
358 この章では実際にゲームを構築し、そのデータベースとしてJungleを導入する。
|
|
|
359
|
|
|
360 今回作ったゲームはMinecraftの簡易版である。
|
|
0
|
361
|
|
10
|
362 <div style="text-align: center;">
|
|
|
363 <img src="./images/craft.png" alt="message" width="400">
|
|
|
364 </div>
|
|
|
365
|
|
|
366 プレイヤーは自由にマップを移動し、ステージの破壊や、生成を行うことができる。
|
|
|
367
|
|
|
368 破壊や生成のオペレーションに合わせてJungleのノードにも同期する。
|
|
|
369
|
|
|
370
|
|
|
371 # ゲームデータの種類
|
|
|
372
|
|
|
373 ゲームのデータにはいくつかの種類が考えられる。
|
|
|
374
|
|
|
375 ## オブジェクトが単体で持つデータ
|
|
|
376
|
|
|
377 シーン内に存在するオブジェクトが持つパラメータ。
|
|
|
378
|
|
|
379 例えば、プレイヤーのHPや経験値、位置座標などを示す。
|
|
|
380
|
|
|
381 ## オブジェクト1つで複数持つデータ
|
|
|
382
|
|
|
383 プレイヤーが持つアイテムデータなどを示す。
|
|
|
384
|
|
|
385 ## マスタデータ(ReadOnly)
|
|
|
386
|
|
|
387 アイテムの名前や敵の出現確率などを示す。
|
|
|
388
|
|
|
389 ゲーム開発者のみが更新できる。
|
|
|
390
|
|
|
391 # データのデータ設計
|
|
|
392
|
|
|
393 Jungleには複数の木を持つことができる。
|
|
|
394
|
|
|
395 ゲームのシーンを構成するGameTreeとアイテムを管理するItemTreeをJungle内に作る。
|
|
|
396
|
|
|
397 # GameTree
|
|
|
398
|
|
|
399 GameTreeではシーン内にあるPlayerやStageを構成するCubeなどを格納している。
|
|
|
400 Jungleではオブジェクトが単体で持つデータと、オブジェクト一つで複数持つデータを同時に表現できる。
|
|
|
401 以下にその例を示す。
|
|
|
402
|
|
|
403 <div style="text-align: center;">
|
|
|
404 <img src="./images/Tree.pdf" alt="message" width="600">
|
|
|
405 </div>
|
|
|
406
|
|
|
407 # ItemTree
|
|
|
408
|
|
|
409 ItemTreeではItemデータを格納している。
|
|
|
410 データの種類ではマスターデータにあたいする。
|
|
|
411 以下にその例を示す。
|
|
|
412
|
|
|
413 <div style="text-align: center;">
|
|
|
414 <img src="./images/ItemTree.pdf" alt="message" width="800">
|
|
|
415 </div>
|
|
|
416
|
|
|
417 # Jungleの改良
|
|
|
418
|
|
|
419 前章では例題となるゲームを作成した。
|
|
|
420 その上でJungleではデータ型について問題となった。
|
|
0
|
421
|
|
10
|
422 C\#の再実装を行った際にJavaのJungleに沿ってデータの型、つまりByteArrayで設計を行っていた。
|
|
|
423
|
|
|
424 データの格納を行うたびにByte Arrayへのキャストを行う必要がある。
|
|
|
425 しかし、キャストの処理は軽くはない。
|
|
|
426
|
|
|
427 そこで、シーンを構成するObjectをそのまま格納するに仕様を変更した。
|
|
|
428 C\#ではObjectクラスのエイリアスとしてobject型が使える。
|
|
|
429
|
|
|
430 ``` C\#
|
|
|
431
|
|
|
432 Player player = new Player ();
|
|
|
433 either = either.bind ((JungleTreeEditor arg) => {
|
|
|
434 return arg.putAttribute ("Player", player);
|
|
|
435 });
|
|
|
436
|
|
|
437 Enemy enemy = new Enemy ();
|
|
|
438 either = either.bind ((JungleTreeEditor arg) => {
|
|
|
439 return arg.putAttribute ("Enemy", enemy);
|
|
|
440 });
|
|
|
441
|
|
|
442 ```
|
|
|
443
|
|
|
444 # データを取り出す
|
|
|
445
|
|
|
446 データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。
|
|
|
447 以下に取り出す例を記述する。
|
|
|
448
|
|
|
449 ``` C\#
|
|
|
450 Player player = attr.get<Player> ("Player");
|
|
|
451 Enemy enemy = attr.get ("Enemy") as Enemy;
|
|
|
452 ```
|
|
|
453
|
|
|
454 データの型の再設計を行ったことによりシーン内のオブジェクトをそのまま格納が可能になった。
|
|
|
455 格納の際にByte Arrayに変換する必要がない。
|
|
|
456
|
|
|
457 分散構造や、ネットワークで必要な時だけ変換する。
|
|
|
458
|
|
|
459 # まとめ
|
|
|
460
|
|
|
461 本研究の流れは
|
|
|
462
|
|
|
463 - Jungle-Sharpの実装
|
|
|
464 - UnityでのApplicationの実装
|
|
|
465 - 問題点の改良
|
|
|
466
|
|
|
467 である。
|
|
|
468
|
|
12
|
469 Jungle-Sharpの実装ではJavaと比較的似ている言語であるため、移行する方法を確立した。
|
|
10
|
470 C\#版のJungleではJavaに劣らない、もしくはそれ以上のパフォーマンスを出すことが出来た。
|
|
|
471
|
|
|
472 実際のゲームに合わせたJungleの拡張を行った。
|
|
|
473
|
|
|
474 データの格納の際にByteBufferであったものをObject型に変更した。
|
|
|
475 これにより、シーンを構成するObjectデータを手間なく格納することを可能にした。
|
|
|
476
|
|
|
477 Jungleは非破壊であるため、過去の変更を持っている。
|
|
|
478
|
|
|
479 ゲームにおいて過去の木を持ち続けることはパフォーマンスの低下につながる。
|
|
|
480 そのため、過去の木をどこまで必要かを検討しなければならない。
|
|
|
481
|
|
|
482 現在C\#版のJungleにはデータを永続化させる仕組みは備わっていない。
|
|
|
483 実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。
|
