11
|
1 <!DOCTYPE html>
|
|
2 <html>
|
|
3 <head>
|
|
4 <meta http-equiv="content-type" content="text/html;charset=utf-8">
|
|
5 <title>ゲームエンジンにおけるJungleDatabaseの提案</title>
|
|
6
|
|
7 <meta name="generator" content="Slide Show (S9) 2.2.0 on Ruby 2.3.3 (2016-11-21) [x86_64-darwin16]">
|
|
8 <meta name="author" content="Kazuma Takeda" >
|
|
9
|
|
10 <!-- style sheet links -->
|
|
11 <link rel="stylesheet" href="s6/themes/screen.css" media="screen">
|
|
12 <link rel="stylesheet" href="s6/themes/print.css" media="print">
|
|
13 <link rel="stylesheet" href="s6/themes/blank.css" media="screen,projection">
|
|
14
|
|
15 <!-- JS -->
|
|
16 <script src="s6/js/jquery-1.11.3.min.js"></script>
|
|
17 <script src="s6/js/jquery.slideshow.js"></script>
|
|
18 <script src="s6/js/jquery.slideshow.counter.js"></script>
|
|
19 <script src="s6/js/jquery.slideshow.controls.js"></script>
|
|
20 <script src="s6/js/jquery.slideshow.footer.js"></script>
|
|
21 <script src="s6/js/jquery.slideshow.autoplay.js"></script>
|
|
22
|
|
23 <!-- prettify -->
|
|
24 <link rel="stylesheet" href="scripts/prettify.css">
|
|
25 <script src="scripts/prettify.js"></script>
|
|
26
|
|
27 <style>
|
|
28 .slide {page-break-after: always;}
|
|
29 </style>
|
|
30
|
|
31
|
|
32
|
|
33
|
|
34 </head>
|
|
35 <body>
|
|
36
|
|
37 <div class="layout">
|
|
38 <div id="header"></div>
|
|
39 <div id="footer">
|
|
40 <div align="right">
|
|
41 <img src="s6/images/logo.svg" width="200px">
|
|
42 </div>
|
|
43 </div>
|
|
44 </div>
|
|
45
|
|
46 <div class="presentation">
|
|
47
|
|
48 <div class='slide cover'>
|
|
49 <table width="90%" height="90%" border="0" align="center">
|
|
50 <tr>
|
|
51 <td>
|
|
52 <div align="center">
|
|
53 <h1><font color="#808db5">ゲームエンジンにおけるJungleDatabaseの提案</font></h1>
|
|
54 </div>
|
|
55 </td>
|
|
56 </tr>
|
|
57 <tr>
|
|
58 <td>
|
|
59 <div align="left">
|
|
60 Kazuma Takeda
|
|
61
|
|
62 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
|
|
63 </div>
|
|
64 </td>
|
|
65 </tr>
|
|
66 </table>
|
|
67 </div>
|
|
68
|
|
69 <div class='slide '>
|
|
70 <!-- === begin markdown block ===
|
|
71
|
|
72 generated by markdown/1.2.0 on Ruby 2.3.3 (2016-11-21) [x86_64-darwin16]
|
13
|
73 on 2017-02-15 16:56:02 +0900 with Markdown engine kramdown (1.13.1)
|
11
|
74 using options {}
|
|
75 -->
|
|
76
|
|
77 <!-- _S9SLIDE_ -->
|
|
78 <h1 id="section">この発表のセクション</h1>
|
|
79
|
|
80 <ul>
|
|
81 <li>RDBとNoSQL</li>
|
|
82 <li>Jungle Databseの提案</li>
|
|
83 <li>Jungleの仕様</li>
|
|
84 <li>ゲームのデータ構造</li>
|
|
85 <li>Jungle-Sharpの実装</li>
|
|
86 <li>例題ゲームの実装</li>
|
|
87 <li>Jungle-Sharpの改良点</li>
|
|
88 </ul>
|
|
89
|
|
90
|
|
91 </div>
|
|
92 <div class='slide '>
|
|
93 <!-- _S9SLIDE_ -->
|
|
94 <h1 id="rdbnosql">RDBとNoSQL</h1>
|
|
95
|
|
96 <p>Relational Databseと呼ばれるRDBは行と列からなる2次元のテーブルにより実装されているデータベース。
|
|
97 データ型として文字列や数値、日付、Bool型がある。</p>
|
|
98
|
|
99 <p>データの一貫性を重視しているRDBでは分散システムには向いていない。</p>
|
|
100
|
|
101 <p>NoSQL(Not Only SQL) Databaseと呼ばれる非リレーショナル型のデータベース。
|
|
102 スキームを持たないため、扱うデータの型を気にしなくてもよい。</p>
|
|
103
|
|
104 <p>一貫性を一部犠牲にしているNoSQLでは分散させることが可能である。
|
|
105 CassandraやMongoDBなどが例に挙げられる。</p>
|
|
106
|
|
107
|
|
108 </div>
|
|
109 <div class='slide '>
|
|
110 <!-- _S9SLIDE_ -->
|
|
111 <h1 id="section-1">インピーダンスミスマッチ</h1>
|
|
112
|
|
113 <p>プログラム中ではListやネスト構造によりデータを扱うことができる。
|
|
114 しかしデータベースにはそのような概念はない。</p>
|
|
115
|
|
116 <p>そこにプログラムとデータベースの間にギャップが生じる。
|
|
117 これをインピーダンスミスマッチという。</p>
|
|
118
|
|
119 <p>RDBではネスト構造を許さない第一正規形とは相容れない。</p>
|
|
120
|
|
121
|
|
122 </div>
|
|
123 <div class='slide '>
|
|
124 <!-- _S9SLIDE_ -->
|
|
125 <h1 id="nosql">NoSQLのトランザクション</h1>
|
|
126
|
|
127 <p>CassandraやほとんどのNoSQLではACIDなトランザクションがない。
|
|
128 トランザクション中の処理は外部からは閲覧出来ない。
|
|
129 しかし、複数行を1回で書き換える機能を持っていないため、
|
|
130 データを書き込んでいる途中の状態が見えてしまう場合がある。</p>
|
|
131
|
|
132
|
|
133 </div>
|
|
134 <div class='slide '>
|
|
135 <!-- _S9SLIDE_ -->
|
|
136 <h1 id="jungle-database">Jungle Databaseの提案</h1>
|
|
137
|
|
138 <p>前章までRDBではプログラムとのミスマッチや分散構造に向いていない問題、NoSQLではトランザクションでの問題点について触れた。
|
|
139 これらの問題を解決するため、当研究室で開発しているデータベースJungleを提案する。</p>
|
|
140
|
|
141 <p>Jungleは過去の変更データを保存しつつ新しい木を構築してく木構造(非破壊構造)の手法をとる。
|
|
142 非破壊にすることにより、データを読み出す側と書き込む側のデータを安全に扱うことができる。</p>
|
|
143
|
|
144 <p>Jungleは名前で管理された木のあつまりからなる。
|
|
145 木は複数のノードの集合からなる。</p>
|
|
146
|
|
147 <p>ノード自身にはKey-Valueのデータを格納することができる。
|
|
148 これはデータベースのレコードに相当する。</p>
|
|
149
|
|
150 <p>Jungleのトランザクションはルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。
|
|
151 最後にルートをアトミックに入れ替えてコミットする。
|
|
152 コミットが失敗した場合は最初からやり直す。
|
|
153 これにより、原子性を実現する。</p>
|
|
154
|
|
155 <p>Jungleはcommit logを持ち、それを他のノードやディスクに転送することにより、
|
|
156 分散構成と永続性を実現する。</p>
|
|
157
|
|
158
|
|
159 </div>
|
|
160 <div class='slide '>
|
|
161 <!-- _S9SLIDE_ -->
|
13
|
162 <h1 id="jungledatabase">JungleのDatabase</h1>
|
11
|
163
|
13
|
164 <p>Jungleの構造としては以下の図のようになっている。</p>
|
11
|
165
|
|
166 <div style="text-align: center;">
|
13
|
167 <img src="./images/transaction.pdf" alt="message" width="700" />
|
11
|
168 </div>
|
|
169
|
|
170
|
|
171 </div>
|
|
172 <div class='slide '>
|
|
173 <!-- _S9SLIDE_ -->
|
13
|
174 <h1 id="section-2">ゲームのデータ構造</h1>
|
11
|
175
|
|
176 <p>Jungleはもともと認証管理システムやWeb向けに作られたものである。
|
|
177 これらはすべて木構造をベースとしている。</p>
|
|
178
|
|
179 <p>ゲームでも同じことが考えられる。
|
|
180 そこでゲームエンジンUnity向けにJungleの再実装を行い、ゲーム向けのデータベースとしての提案を行う。</p>
|
|
181
|
|
182 <p>Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC#で制御する。
|
|
183 Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
|
|
184 これをシーングラフと言う。
|
|
185 シーングラフをそのままJungleに格納するという手法が考えられる。</p>
|
|
186
|
|
187
|
|
188 </div>
|
|
189 <div class='slide '>
|
|
190 <!-- _S9SLIDE_ -->
|
|
191 <h1 id="jungle-sharp">Jungle-Sharpの実装</h1>
|
|
192
|
|
193 <p>JungleはもともとJavaとHaskellで書かれていた。
|
|
194 今回はJava版をベースにC#で再実装する。</p>
|
|
195
|
|
196 <p>エラーをチェックするEitherの部分だけはHaskellの要素を取ってくる。</p>
|
|
197
|
|
198
|
|
199 </div>
|
|
200 <div class='slide '>
|
|
201 <!-- _S9SLIDE_ -->
|
|
202 <h1 id="atomic-refarence">Atomic Refarenceの実装</h1>
|
|
203
|
|
204 <p>Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。
|
|
205 競合している書き込み中に自分の書き込みが成功した場合に関数commit()が成功する。
|
|
206 失敗した場合ははじめからもう一度行う。</p>
|
|
207
|
|
208 <p>JavaのモジュールにはAtomicRefarenceが存在した。
|
|
209 C#では自分で作る必要があった。</p>
|
|
210
|
|
211 <pre lang="C"><code class="language-\#">
|
|
212 // C\#
|
|
213 public bool CompareAndSet(T newValue, T prevValue) {
|
|
214 T oldValue = value;
|
|
215 return (oldValue
|
|
216 != Interlocked.CompareExchange
|
|
217 (ref value, newValue, prevValue));
|
|
218 }
|
|
219
|
|
220 </code></pre>
|
|
221
|
|
222
|
|
223 </div>
|
|
224 <div class='slide '>
|
|
225 <!-- _S9SLIDE_ -->
|
|
226 <h1 id="list">Listの実装</h1>
|
|
227
|
|
228 <p>木やリストをたどる時にJavaではIteratorを用いる。
|
|
229 Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
|
|
230 C#では木やリストを辿りながらyeildで次の値を返す。
|
|
231 Javaでは以下のように実装されている。</p>
|
|
232
|
|
233 <pre lang="Java"><code>
|
|
234 public Iterator<T> iterator() {
|
|
235 return new Iterator<T>() {
|
|
236 Node<T> currentNode = head.getNext();
|
|
237
|
|
238 @Override
|
|
239 public boolean hasNext() {
|
|
240 return currentNode.getAttribute()
|
|
241 != null;
|
|
242 }
|
|
243
|
|
244 @Override
|
|
245 public T next() {
|
|
246 T attribute
|
|
247 = currentNode.getAttribute();
|
|
248 currentNode
|
|
249 = currentNode.getNext();
|
|
250 return attribute;
|
|
251 }
|
|
252 };
|
|
253 }
|
|
254
|
|
255 </code></pre>
|
|
256
|
|
257
|
|
258 </div>
|
|
259 <div class='slide '>
|
|
260 <!-- _S9SLIDE_ -->
|
|
261 <h1 id="list-1">Listの実装</h1>
|
|
262
|
|
263 <p>C#ではそもそも匿名クラスの中でメソッドを定義できない。
|
|
264 この場合はIEnuratorを使って書き直すことができた。</p>
|
|
265
|
|
266 <pre lang="C"><code class="language-\#">
|
|
267 // C\#
|
|
268 public IEnumerator<T> iterator() {
|
|
269 Node<T> currentNode = head.getNext();
|
|
270 while (currentNode.getAttribute() != null) {
|
|
271 yield return (T)currentNode.getAttribute();
|
|
272 currentNode = currentNode.getNext ();
|
|
273 }
|
|
274 }
|
|
275
|
|
276 </code></pre>
|
|
277
|
|
278
|
|
279 </div>
|
|
280 <div class='slide '>
|
|
281 <!-- _S9SLIDE_ -->
|
13
|
282 <h1 id="either">Eitherのチェック</h1>
|
11
|
283
|
|
284 <p>Haskellでは例外処理はモナド内部で行う設計になっている。
|
|
285 Eitherもその一つである。</p>
|
|
286
|
|
287 <p>Jungleではある処理に対してエラーであればA、
|
|
288 なければBをEitherに包んで返す。</p>
|
|
289
|
|
290 <p>JavaのJungleでは分岐を使ってチェックする必要があった。</p>
|
|
291
|
|
292 <pre lang="Java"><code>
|
|
293 // Java
|
|
294 Either<Error,TreeNode> either = children.at(2);
|
|
295 if (either.isA())
|
|
296 return either.a();
|
|
297 TreeNode child = either.b();
|
|
298
|
|
299 </code></pre>
|
|
300
|
|
301
|
|
302 </div>
|
|
303 <div class='slide '>
|
|
304 <!-- _S9SLIDE_ -->
|
|
305 <h1 id="bind">bindの実装</h1>
|
|
306
|
|
307 <p>Eitherクラスに実装したbindは自身のEitherをチェックした後、
|
|
308 エラーがなければ関数fを実行し評価する仕組みである。</p>
|
|
309
|
|
310 <pre lang="C"><code class="language-\#">
|
|
311 public Either<A, B> bind (System.Func<B, Either<A, B>> f) {
|
|
312 if (this.isA ()) {
|
|
313 return this;
|
|
314 }
|
|
315 return f (this.b ());
|
|
316 }
|
|
317
|
|
318 </code></pre>
|
|
319
|
|
320 <p>ユーザー側でのエラーのチェックは不要になるが、関数fのLambda式を自分で定義する必要がある。
|
|
321 次のページにその例を示す。</p>
|
|
322
|
|
323
|
|
324 </div>
|
|
325 <div class='slide '>
|
|
326 <!-- _S9SLIDE_ -->
|
|
327 <h1 id="bind-1">bindの引数に渡すラムダ式の例</h1>
|
|
328
|
|
329 <pre lang="C"><code class="language-\#">
|
|
330 Either<Error, JungleTreeEditor> either = DefaultEither<Error, JungleTreeEditor>.newB(editor);
|
|
331 Item apple = new Item("Apple");
|
|
332
|
|
333 either = either.bind ((JungleTreeEditor arg) => {
|
|
334 return arg.putAttribute (rootNode, item.name, item);
|
|
335 });
|
|
336
|
|
337 </code></pre>
|
|
338
|
|
339
|
|
340 </div>
|
|
341 <div class='slide '>
|
|
342 <!-- _S9SLIDE_ -->
|
13
|
343 <h1 id="section-3">例題のゲーム</h1>
|
11
|
344
|
|
345 <p>前章ではJungle-Sharpのどのように実装したかを述べた。</p>
|
|
346
|
|
347 <p>この章では実際にゲームを構築し、そのデータベースとしてJungleを導入する。</p>
|
|
348
|
|
349 <p>今回作ったゲームはMinecraftの簡易版である。</p>
|
|
350
|
|
351 <div style="text-align: center;">
|
|
352 <img src="./images/craft.png" alt="message" width="400" />
|
|
353 </div>
|
|
354
|
|
355 <p>プレイヤーは自由にマップを移動し、ステージの破壊や、生成を行うことができる。</p>
|
|
356
|
|
357 <p>破壊や生成のオペレーションに合わせてJungleのノードにも同期する。</p>
|
|
358
|
|
359
|
|
360 </div>
|
|
361 <div class='slide '>
|
|
362 <!-- _S9SLIDE_ -->
|
13
|
363 <h1 id="section-4">ゲームデータの種類</h1>
|
11
|
364
|
|
365 <p>ゲームのデータにはいくつかの種類が考えられる。</p>
|
|
366
|
13
|
367 <h2 id="section-5">オブジェクトが単体で持つデータ</h2>
|
11
|
368
|
|
369 <p>シーン内に存在するオブジェクトが持つパラメータ。</p>
|
|
370
|
|
371 <p>例えば、プレイヤーのHPや経験値、位置座標などを示す。</p>
|
|
372
|
13
|
373 <h2 id="section-6">オブジェクト1つで複数持つデータ</h2>
|
11
|
374
|
|
375 <p>プレイヤーが持つアイテムデータなどを示す。</p>
|
|
376
|
|
377 <h2 id="readonly">マスタデータ(ReadOnly)</h2>
|
|
378
|
|
379 <p>アイテムの名前や敵の出現確率などを示す。</p>
|
|
380
|
|
381 <p>ゲーム開発者のみが更新できる。</p>
|
|
382
|
|
383
|
|
384 </div>
|
|
385 <div class='slide '>
|
|
386 <!-- _S9SLIDE_ -->
|
13
|
387 <h1 id="section-7">データのデータ設計</h1>
|
11
|
388
|
|
389 <p>Jungleには複数の木を持つことができる。</p>
|
|
390
|
|
391 <p>ゲームのシーンを構成するGameTreeとアイテムを管理するItemTreeをJungle内に作る。</p>
|
|
392
|
|
393
|
|
394 </div>
|
|
395 <div class='slide '>
|
|
396 <!-- _S9SLIDE_ -->
|
|
397 <h1 id="gametree">GameTree</h1>
|
|
398
|
|
399 <p>GameTreeではシーン内にあるPlayerやStageを構成するCubeなどを格納している。
|
|
400 Jungleではオブジェクトが単体で持つデータと、オブジェクト一つで複数持つデータを同時に表現できる。
|
|
401 以下にその例を示す。</p>
|
|
402
|
|
403 <div style="text-align: center;">
|
|
404 <img src="./images/Tree.pdf" alt="message" width="600" />
|
|
405 </div>
|
|
406
|
|
407
|
|
408 </div>
|
|
409 <div class='slide '>
|
|
410 <!-- _S9SLIDE_ -->
|
|
411 <h1 id="itemtree">ItemTree</h1>
|
|
412
|
|
413 <p>ItemTreeではItemデータを格納している。
|
|
414 データの種類ではマスターデータにあたいする。
|
|
415 以下にその例を示す。</p>
|
|
416
|
|
417 <div style="text-align: center;">
|
|
418 <img src="./images/ItemTree.pdf" alt="message" width="800" />
|
|
419 </div>
|
|
420
|
|
421
|
|
422 </div>
|
|
423 <div class='slide '>
|
|
424 <!-- _S9SLIDE_ -->
|
13
|
425 <h1 id="jungle">Jungleの改良</h1>
|
11
|
426
|
|
427 <p>前章では例題となるゲームを作成した。
|
|
428 その上でJungleではデータ型について問題となった。</p>
|
|
429
|
|
430 <p>C#の再実装を行った際にJavaのJungleに沿ってデータの型、つまりByteArrayで設計を行っていた。</p>
|
|
431
|
|
432 <p>データの格納を行うたびにByte Arrayへのキャストを行う必要がある。
|
|
433 しかし、キャストの処理は軽くはない。</p>
|
|
434
|
|
435 <p>そこで、シーンを構成するObjectをそのまま格納するに仕様を変更した。
|
|
436 C#ではObjectクラスのエイリアスとしてobject型が使える。</p>
|
|
437
|
|
438 <pre lang="C"><code class="language-\#">
|
|
439 Player player = new Player ();
|
|
440 either = either.bind ((JungleTreeEditor arg) => {
|
|
441 return arg.putAttribute ("Player", player);
|
|
442 });
|
|
443
|
|
444 Enemy enemy = new Enemy ();
|
|
445 either = either.bind ((JungleTreeEditor arg) => {
|
|
446 return arg.putAttribute ("Enemy", enemy);
|
|
447 });
|
|
448
|
|
449 </code></pre>
|
|
450
|
|
451
|
|
452 </div>
|
|
453 <div class='slide '>
|
|
454 <!-- _S9SLIDE_ -->
|
13
|
455 <h1 id="section-8">データを取り出す</h1>
|
11
|
456
|
|
457 <p>データを取り出すにはGenericで型を指定する、もしくはas演算子を用いてキャストを行う。
|
|
458 以下に取り出す例を記述する。</p>
|
|
459
|
|
460 <pre lang="C"><code class="language-\#">Player player = attr.get<Player> ("Player");
|
|
461 Enemy enemy = attr.get ("Enemy") as Enemy;
|
|
462 </code></pre>
|
|
463
|
|
464 <p>データの型の再設計を行ったことによりシーン内のオブジェクトをそのまま格納が可能になった。
|
|
465 格納の際にByte Arrayに変換する必要がない。</p>
|
|
466
|
|
467 <p>分散構造や、ネットワークで必要な時だけ変換する。</p>
|
|
468
|
|
469
|
|
470 </div>
|
|
471 <div class='slide '>
|
|
472 <!-- _S9SLIDE_ -->
|
13
|
473 <h1 id="section-9">まとめ</h1>
|
11
|
474
|
|
475 <p>本研究の流れは</p>
|
|
476
|
|
477 <ul>
|
|
478 <li>Jungle-Sharpの実装</li>
|
|
479 <li>UnityでのApplicationの実装</li>
|
|
480 <li>問題点の改良</li>
|
|
481 </ul>
|
|
482
|
13
|
483 <p>である。</p>
|
11
|
484
|
13
|
485 <p>Jungle-Sharpの実装ではJavaと比較的似ている言語であるため、移行する方法を確立した。
|
11
|
486 C#版のJungleではJavaに劣らない、もしくはそれ以上のパフォーマンスを出すことが出来た。</p>
|
|
487
|
|
488 <p>実際のゲームに合わせたJungleの拡張を行った。</p>
|
|
489
|
|
490 <p>データの格納の際にByteBufferであったものをObject型に変更した。
|
|
491 これにより、シーンを構成するObjectデータを手間なく格納することを可能にした。</p>
|
|
492
|
|
493 <p>Jungleは非破壊であるため、過去の変更を持っている。</p>
|
|
494
|
|
495 <p>ゲームにおいて過去の木を持ち続けることはパフォーマンスの低下につながる。
|
|
496 そのため、過去の木をどこまで必要かを検討しなければならない。</p>
|
|
497
|
|
498 <p>現在C#版のJungleにはデータを永続化させる仕組みは備わっていない。
|
|
499 実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。</p>
|
|
500 <!-- === end markdown block === -->
|
|
501 </div>
|
|
502
|
|
503
|
|
504 </div><!-- presentation -->
|
|
505 </body>
|
|
506 </html>
|