前回は セグメント木をネタにゲーム を作りましたが、今回はフェニック木でゲームを作ります。クソゲー姉妹品 「セグ木が嫌ならFenwick木で殴ってやろうか？」です。ルールは前回と同じです。
Contents
フェニック木とは何か？
フェニック木 または Binary Indexed Tree (BIT) とは、部分和の計算と要素の更新の両方を効率的に行える木構造のことです。要素の更新と区間和の計算の両方が時間計算量 O(logN)で可能です。ピーター・フェニックにより提案されました。
セグメント木と比べると部分和の計算しかできない、部分和の計算も任意の区間ではなくA[0]からA[i]までという制限がありますが、セグ木よりも使用するノード数が少なく動作が軽いこと、任意の区間[a, b]の部分和であれば[0, b] – [0, a – 1]を計算すればよいことから使い勝手はよいと思われます。
以下はJavaScriptで書いたフェニック木のコードです。ノードを表すindexからその親と子のindexを求める処理が興味深いです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class FenwickTree { constructor(size){ this.A = []; for(let i = 0; i < size; i++) this.A.push(0); this.N = size + 1; this.Nodes = []; for(let i = 0; i < this.N; i++) this.Nodes.push(0); } // フェニック木は加算処理しかできないが、どれだけ値を増減すればいいかわかれば // 更新処理もまた加算処理として扱うことができる。 Update(idx, x){ if(0 <= idx && idx < this.N - 1){ const diff = x - this.A[idx]; this.Add(idx, diff); } else console.log('引数が不正'); } Add(idx, x) { if(0 <= idx && idx < this.N - 1){ this.A[idx] += x; for (let i = idx + 1; i < this.N; i += i & (-i)) this.Nodes[i] += x; } else console.log('引数が不正'); } GetSum(idx) { if(0 <= idx && idx < this.N - 1){ let ret = 0; for (let i = idx + 1; i > 0; i -= i&(-i)) ret += this.Nodes[i]; return ret; } else console.log('引数が不正'); } } const fenwick = new FenwickTree(8); for(let i=0; i<8; i++) fenwick.Update(i, i); console.log(fenwick.A); for(let i=0; i<8; i++) console.log(`[0, ${i}]の区間和は ${fenwick.GetSum(i)}`); // (8) [0, 1, 2, 3, 4, 5, 6, 7] // [0, 0]の区間和は 0 // [0, 1]の区間和は 1 // [0, 2]の区間和は 3 // [0, 3]の区間和は 6 // [0, 4]の区間和は 10 // [0, 5]の区間和は 15 // [0, 6]の区間和は 21 // [0, 7]の区間和は 28 |
HTML部分
ではさっそく作っていきましょう。最初にHTML部分を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>セグ木が嫌ならFenwick木で殴ってやろうか？</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <link rel="stylesheet" href="./style.css"> </head> <body> <div id = "container"> <div id = "field"> <div id = "field-header"> <h1><クソゲー姉妹品> セグ木が嫌ならFenwick木で殴ってやろうか？</h1> <div id = "score">Score 0</div><div id = "time"></div> </div> <table> <tr> <td colspan="8" id = "n8" class = "cell"></td> </tr> <tr> <td colspan="4" id = "n4" class = "cell"></td> <td colspan="4"></td> </tr> <tr> <td colspan="2" id = "n2" class = "cell"></td> <td colspan="2"></td> <td colspan="2" id = "n6" class = "cell"></td> <td colspan="2"></td> </tr> <tr> <td id = "n1" class = "cell"></td> <td></td> <td id = "n3" class = "cell"></td> <td></td> <td id = "n5" class = "cell"></td> <td></td> <td id = "n7" class = "cell"></td> <td></td> </tr> <tr> <td id = "a0" class = "cell"></td> <td id = "a1" class = "cell"></td> <td id = "a2" class = "cell"></td> <td id = "a3" class = "cell"></td> <td id = "a4" class = "cell"></td> <td id = "a5" class = "cell"></td> <td id = "a6" class = "cell"></td> <td id = "a7" class = "cell"></td> </tr> <tr> <td id = "update-0" class = "cell"><button>更新</button></td> <td id = "update-1" class = "cell"><button>更新</button></td> <td id = "update-2" class = "cell"><button>更新</button></td> <td id = "update-3" class = "cell"><button>更新</button></td> <td id = "update-4" class = "cell"><button>更新</button></td> <td id = "update-5" class = "cell"><button>更新</button></td> <td id = "update-6" class = "cell"><button>更新</button></td> <td id = "update-7" class = "cell"><button>更新</button></td> </tr> <tr> <td class = "idx">[0]</td> <td class = "idx">[1]</td> <td class = "idx">[2]</td> <td class = "idx">[3]</td> <td class = "idx">[4]</td> <td class = "idx">[5]</td> <td class = "idx">[6]</td> <td class = "idx">[7]</td> </tr> </table> <p id = "navi"></p> <p id = "interval-sums"></p> <p id = "q2">更新に使える数: <span id = "update-values"></span></p> <p><button id = "reset">やりなおす</button></p> <div id = "volume"></div> <div id = "start-buttons"> <p><label for="player-name">プレイヤー名：</label> <input id = "player-name" maxlength="32"></p> <p><button id = "start">START</button></p> <p><button id = "go-ranking" onclick="location.href = './ranking.html'">ランキング</button></p> </div> </div> </div> <script src="./index.js"></script> </body> </html> |
style.css
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
body { background-color: black; color: white; } #container { margin: 40px auto 40px auto; width: 360px; } #field-header { margin-bottom: 45px; } #field { width: 360px; height: 600px; margin-left: auto; margin-right: auto; position: relative; border: 0px #1DA1F2 solid; } #score { float: left; margin-left: 0px; } #time { float: right; margin-right: 0px; } h1 { color:aqua; font-size: large; } .cell { border: 1px solid white; width: 40px; text-align: center; height: 30px; } .idx { width: 40px; text-align: center; } #navi { margin-top: 30px; } .interval { width: 100px; } #update-values { margin-left: 50px; } #start-buttons { position: absolute; left: 0px; top: 130px; width: 100%; text-align: center; } #start, #go-ranking { font-weight: bold; text-align: center; font-size: 18px; width: 280px; border: none; font-size: 16px; background-color: #1DA1F2; padding: 10px 32px; border-radius: 100vh; color: white; cursor: pointer; } #reset { width: 160px; height: 40px; margin-left: 10px; } .red { color: magenta; font-weight: bold; } |
Gameクラスの定義
Gameクラスを定義します。最初にコンストラクタを示します。
index.js
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Game { constructor(){ this.IgnoreClick = true; this.Score = 0; this.Stage = 1; this.InitRemainingTime = 180 * 1000; // 制限時間は3分 this.RemainingTime = 0; // フェニック木の操作に関する変数 this.ArraySize = 8; this.A = []; for(let i = 0; i < this.ArraySize; i++) this.A.push(0); this.NodesCount = this.ArraySize + 1; this.Nodes = []; for(let i = 0; i < this.NodesCount; i++) this.Nodes.push(0); // お題に関する部分 this.SumOfIntervals = []; // 区間和 this.OrgValues = []; // 配列の初期値 this.OrgUpdateValues = []; // 更新に使える値 this.UpdateValues = []; // 更新されていない値 // 効果音 this.SoundSelect = new Audio('./sounds/select.mp3'); this.SoundOK = new Audio('./sounds/ok.mp3'); this.SoundNG = new Audio('./sounds/ng.mp3'); this.SoundUpdate = new Audio('./sounds/update.mp3'); this.SoundGameClear = new Audio('./sounds/game-clear.mp3'); this.SoundMiss = new Audio('./sounds/miss.mp3'); this.SoundGameover = new Audio('./sounds/gameover.mp3'); this.Sounds = [this.SoundSelect, this.SoundOK, this.SoundNG, this.SoundUpdate, this.SoundGameClear, this.SoundMiss, this.SoundGameover]; // 残り時間の表示と計測用の変数 this.$time = document.getElementById('time'); this.PrevUpdateTime = Date.now(); } } |
フェニック木の更新処理
フェニック木を更新するための処理を示します。以下は配列のidx番目がxに更新されたときにフェニック木を更新するとともに表示されている値を変更するためのものです。
|
1 2 3 4 5 6 7 8 9 10 11 |
class Game { UpdateFenwickTree(idx, x){ const diff = x - this.A[idx]; this.A[idx] += diff; document.getElementById('a' + idx).innerHTML = this.A[idx]; for (let i = idx + 1; i < this.NodesCount; i += i & (-i)){ this.Nodes[i] += diff; document.getElementById('n' + i).innerHTML = this.Nodes[i]; } } } |
以下は配列のidx番目がxに更新されたときにフェニック木と表示を更新するものですが、一気におこなわず、待機時間をいれながら どのノードが更新されたのかが視覚的にわかるようにしながら更新するためのものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class Game { async Sleep(ms){ await new Promise(resolve => setTimeout(resolve, ms)); } async UpdateFenwickTreeAsync(idx, x){ const ms = 400; const diff = x - this.A[idx]; this.A[idx] += diff; const $cell = document.getElementById('a' + idx); $cell.innerHTML = this.A[idx]; $cell.style.backgroundColor = '#0f0'; this.SoundUpdate.currentTime = 0; this.SoundUpdate.play(); await this.Sleep(ms); $cell.style.backgroundColor = '#000'; for (let i = idx + 1; i < this.NodesCount; i += i & (-i)){ this.Nodes[i] += diff; const $cell = document.getElementById('n' + i); $cell.innerHTML = this.Nodes[i]; $cell.style.backgroundColor = '#0f0'; this.SoundUpdate.currentTime = 0; this.SoundUpdate.play(); await this.Sleep(ms); $cell.style.backgroundColor = '#000'; } } } |
ユーザーが更新ボタンをクリックしたら更新すべき値でフェニック木と表示されている値を更新します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Game { async UpdateValue(idx){ if(this.IgnoreClick) // 処理をしているときは別の更新処理が開始されないようにする return; this.IgnoreClick = true; const v = this.UpdateValues.shift(); await this.UpdateFenwickTreeAsync(idx, v); if(this.UpdateValues.length > 0){ document.getElementById('navi').innerHTML = `どこを ${this.UpdateValues[0]} に更新しますか？`; document.getElementById('update-values').innerHTML = this.UpdateValues.join(', '); } else await this.Check(); this.IgnoreClick = false; } } |
お題を生成する処理
お題を生成する処理を示します。やっていることは お前もセグ木で殴ってやろうか？ とほぼ同じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Game { CreateQuestion(){ this.SumOfIntervals = []; this.OrgValues = []; this.OrgUpdateValues = []; this.UpdateValues = []; const indexes = []; for(let i = 0; i < this.ArraySize; i++){ this.OrgValues.push(Math.floor(Math.random() * 5) + 1); indexes.push(i); } this.SumOfIntervals.push({right: 7, sum: getSum(this.OrgValues, 7)}); this.SumOfIntervals.push({right: 5, sum: getSum(this.OrgValues, 5)}); const right = 4 - Math.floor(Math.random() * 3); this.SumOfIntervals.push({right: right, sum: getSum(this.OrgValues, right)}); function getSum(arr, r){ let ans = 0; for(let i = 0; i <= r; i++) ans += arr[i]; return ans; } let changeCount = this.Stage; if(this.Stage >= 4) changeCount = 4; const changed = []; for(let i = 0; i < changeCount; i++){ const idx = Math.floor(Math.random() * indexes.length); changed.push(indexes[idx]); console.log(indexes[idx]); indexes.splice(idx, 1); } changed.forEach(idx => { this.OrgUpdateValues.push(this.OrgValues[idx]); this.OrgValues[idx] += Math.floor(Math.random() * 4); this.OrgValues[idx] %= 5; this.OrgValues[idx]++; }); this.Reset(); // お題が生成されたのでフェニック木と表示を初期化する（後述） } } |
フェニック木と表示を初期化する処理
フェニック木と表示を初期化する処理を示します。お題を表す変数に格納されている値と現在の状態を示す値を同じにしているだけです。最後にこの値でフェニック木を初期化します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Game { Reset(){ this.UpdateValues = []; for(let i = 0; i < this.OrgUpdateValues.length; i++) this.UpdateValues.push(this.OrgUpdateValues[i]); let html = '区間和が以下の値になるようにFenwick木を更新せよ<br>'; for(let i = 0; i < this.SumOfIntervals.length; i++){ const obj = this.SumOfIntervals[i]; html += `<span style="margin-right: 20px;">[0, ${obj.right}] => ${obj.sum}</span>`; } document.getElementById('interval-sums').innerHTML = html; document.getElementById('navi').innerHTML = `どこを ${this.UpdateValues[0]} に更新しますか？`; document.getElementById('update-values').innerHTML = this.UpdateValues.join(', '); // フェニック木を初期化する for(let i = 0; i < this.ArraySize; i++) this.UpdateFenwickTree(i, this.OrgValues[i]); } } |
正誤判定
正誤判定をする部分を示します。
まず区間和を取得する処理を示します。ここでは区間を被覆しているノードを拾い集めてその和を計算するとともにそのノードに相当する部分を色を変えて表示することでフェニック木でどのような処理が行われているのかがわかるようにしています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Game { GetSum(idx) { let ret = 0; for (let i = idx + 1; i > 0; i -= i&(-i)) { const $cell = document.getElementById('n' + i); $cell.style.backgroundColor = '#0f0'; ret += this.Nodes[i]; } for (let i = 0; i <= idx; i++) { const $cell = document.getElementById('a' + i); $cell.style.backgroundColor = '#f00'; } return ret; } } |
Check関数はお題の区間和と実際の区間和がすべて一致するか調べ、合っていればステージクリアの処理を、合っていなければそのステージを最初からやり直させる処理をおこなっています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Game { async Check(){ document.getElementById('update-values').innerHTML = ''; document.getElementById('navi').innerHTML = `判定中`; await this.Sleep(1000); const ms = 700; let ok = true; for(let i = 0; i < this.SumOfIntervals.length; i++){ const sumOfInterval = this.SumOfIntervals[i]; if(this.GetSum(sumOfInterval.right) == sumOfInterval.sum){ this.SoundOK.currentTime = 0; this.SoundOK.play(); } else { this.SoundNG.currentTime = 0; this.SoundNG.play(); ok = false; } await this.Sleep(ms); for(let j = 1; j <= this.ArraySize; j++) document.getElementById('n' + j).style.backgroundColor = '#000'; for (let i = 0; i < this.ArraySize; i++) document.getElementById('a' + i).style.backgroundColor = '#000'; } if(ok){ document.getElementById('navi').innerHTML = `クリア!!`; this.SoundGameClear.play(); const add = Math.floor(this.RemainingTime / 100 + this.Stage * 5000); // 100000 -> 1000 document.getElementById('score').innerHTML = `<span class = "red">+ ${add.toLocaleString()}</span>`; await this.Sleep(2000); this.Score += add; document.getElementById('score').innerHTML = `Score ${this.Score.toLocaleString()}`; this.Stage++; this.CreateQuestion(); } else { document.getElementById('navi').innerHTML = `失敗!!`; this.SoundMiss.play(); await this.Sleep(2000); this.Reset(); } } } |
ゲームの開始とリセット
ゲーム開始時の処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Game { GameStart(){ this.Score = 0; this.Stage = 1; document.getElementById('score').innerHTML = `Score ${this.Score.toLocaleString()}`; this.CreateQuestion(); this.RemainingTime = this.InitRemainingTime; this.IgnoreClick = false; document.getElementById('start-buttons').style.display = 'none'; this.SoundSelect.play(); } } |
ステージの初期状態に戻す処理を示します。
|
1 2 3 4 5 6 7 8 9 |
class Game { OnClickReset(){ if(!this.IgnoreClick){ this.Reset(); this.SoundSelect.currentTime = 0; this.SoundSelect.play(); } } } |
更新処理
時間の経過とともに残り時間を減算する処理と時間切れになったらゲームオーバー処理をおこなう処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Game { Update(){ requestAnimationFrame(() => this.Update()); // 前回更新時刻との差を求め、プレイ中であればこれを残り時間から減算する const cur = Date.now(); const diff = cur - this.PrevUpdateTime; this.PrevUpdateTime = cur; if(!this.IgnoreClick){ this.RemainingTime -= diff; if(this.RemainingTime < 0) this.RemainingTime = 0; if(this.RemainingTime == 0) // 残り時間が 0 になったらゲームオーバー this.GameOver(); } const sec = (Math.floor(this.RemainingTime / 1000)).toString(); const ms = (this.RemainingTime % 1000).toString(); const text = `残り ${sec}.${ms.padStart(3, '0')}`; this.$time.innerHTML = text; //this.GetReminingTimeText(); } } |
ゲームオーバー時の処理
ゲームオーバー時の処理を示します。スコアランキングにスコアを登録します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Game { GameOver(){ if(this.IgnoreClick) return; this.IgnoreClick = true; const player_name = document.getElementById('player-name').value; const score = this.Score; this.SaveScore(player_name, score); this.SoundGameover.currentTime = 0; this.SoundGameover.play(); setTimeout(() => { document.getElementById('start-buttons').style.display = 'block'; }, 3000); } SaveScore(player_name, score){ if(player_name == '') player_name = '名無しのゴンベ'; // JSON形式でPOST fetch('./ranking.php', { method: 'POST', headers: { 'Content-Type': 'application/json' }, body: JSON.stringify({ name: player_name, score: score, }) }); } } |
サーバー側の処理とスコアランキングを表示させる処理はゲーム開始以降の処理 鳩でもわかるXORパズルをつくる（2）と同じなので省略します。
ページが読み込まれたときの処理
ページが読み込まれたときの処理を示します。Gameオブジェクトを生成してイベントリスナを追加してUpdate関数を呼び出しているだけです。レンジスライダーで効果音の音量をコントロールできるようにする処理はいつもと同じ処理です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
window.addEventListener('load', () => { const $playerName = document.getElementById('player-name'); const savedName = localStorage.getItem('hatodemowakaru-player-name'); if(savedName && $playerName != null) $playerName.value = savedName; $playerName?.addEventListener('change', () => { localStorage.setItem('hatodemowakaru-player-name', $playerName.value ); }); const game = new Game(); document.getElementById('start').addEventListener('click', () => game.GameStart()); document.getElementById('reset').addEventListener('click', () => game.OnClickReset()); for(let i = 0; i < 8; i++) document.getElementById('update-' + i).addEventListener('click', () => game.UpdateValue(i)); game.CreateQuestion(); game.Update(); initVolume('volume', game.Sounds); }); function initVolume(elementId, sounds){ let volume = 0.3; const savedVolume = localStorage.getItem('hatodemowakaru-volume'); if(savedVolume) volume = Number(savedVolume); const $element = document.getElementById(elementId); const $div = document.createElement('div'); const $span1 = document.createElement('span'); $span1.innerHTML = '音量'; $div.appendChild($span1); const $range = document.createElement('input'); $range.type = 'range'; $div.appendChild($range); const $span2 = document.createElement('span'); $div.appendChild($span2); $range.addEventListener('input', () => { const value = $range.value; $span2.innerText = value; volume = Number(value) / 100; setVolume(); }); $range.addEventListener('change', () => localStorage.setItem('hatodemowakaru-volume', volume.toString())); setVolume(); $span2.innerText = Math.round(volume * 100).toString(); $span2.style.marginLeft = '16px'; $range.value = Math.round(volume * 100).toString(); $range.style.width = '230px'; $range.style.verticalAlign = 'middle'; $element.appendChild($div); const $button = document.createElement('button'); $button.innerHTML = '音量テスト'; $button.style.width = '120px'; $button.style.height = '45px'; $button.style.marginTop = '12px'; $button.style.marginLeft = '32px'; $button.addEventListener('click', () => { sounds[0].currentTime = 0; sounds[0].play(); }); $element.appendChild($button); function setVolume(){ for(let i = 0; i < sounds.length; i++) sounds[i].volume = volume; } } |
