ブラウザゲームにおける囲まれた空間の効率的な検出
2025-02-07
ブラウザゲームにおいて、プレイヤーは敵を妨害するために障害物を配置します。プレイヤーが自分自身や敵を囲い込むことでチートをするのを防ぐために、著者は囲まれた空間を効率的に検出するアルゴリズムを設計しました。初期の総当たり法（各セルのフラッドフィル）は遅すぎることが判明しました。著者は、「開いている」セル（障害物に囲まれていないセル）のキャッシュを利用して、フラッドフィルの探索空間を削減する改良アルゴリズムを考案しました。障害物が追加または削除されると、アルゴリズムは開いているセルのセットを更新し、合法的な配置場所を再計算します。最悪の場合の時間計算量は総当たり法と同じですが、実際にはこのアルゴリズムは遅延を大幅に削減します。著者は、反復的な更新や複数の障害物に隣接するセルのみのチェックなど、他の最適化テクニックについても説明しています。最後に、著者は別の可能な解決策として、サイクル検出に基づくアルゴリズムについて述べています。
続きを読む
ゲーム
囲まれた空間の検出
