データ構造とアルゴリズムの設計

設計と分析の全体像

1. 計算したい課題を定義する

まず「経路探索をする」ではなく、何を受け取り、何を返す処理なのかを決めます。VEINの戦闘では、クリーチャーが通れる盤面と探索者の位置を基に、探索者へ近づく次のマスを選びます。

この段階で、結果の正しさと入力規模を明らかにします。ここが曖昧なままでは、どのデータ構造やアルゴリズムが適切か比較できません。

2. データの表し方を決める

VEINの盤面では、一つひとつのマスが上下左右のマスとつながっています。この「要素と、要素同士のつながり」を表す考え方がGraph（グラフ）です。ここでは各マスがGraphの頂点、移動できる隣接マスとのつながりが辺に当たります。Graphという名前のクラスを作るという意味ではありません。

探索を始めたら、見つけた隣接マスを「これから調べるマス」として順番に待たせます。この待ち行列がQueue（キュー）です。先に追加したマスから取り出すため、探索者に近いマスから順に距離を確定できます。

「有名だからMapを使う」のではなく、探索者の位置から対応する距離の表を繰り返し取り出すという操作に合わせて選びます。順序、重複、更新頻度、追加メモリも選択条件です。

3. 処理手順を設計する

VEINは、探索者まで何歩かを各マスに記録した「距離の表」を作ります。このように、各地点へ値を割り当てたものを距離場と呼び、コードではDistanceFieldと表しています。

この距離の表は、探索者のマスを0として、近いマスから順番に1、2、3と数字を付けて作ります。VEINのdistanceField()は、この処理に幅優先探索（BFS）を使います。

Kotlin — PassageNavigation.ktから抜粋

// 各マスまでの距離。-1はまだ訪問していないことを表す
val distances = IntArray(cellCount) { -1 }

// 調べるマスを、追加された順番に取り出すQueue
val queue = IntArray(cellCount)
var readIndex = 0
var writeIndex = 0

while (readIndex < writeIndex) {
    // Queueの先頭から、次に調べるマスを取り出す
    val index = queue[readIndex++]
    val nextDistance = distances[index] + 1

    fun visit(nextIndex: Int) {
        // 通れないマスと、すでに距離を求めたマスは調べない
        if (!passable[nextIndex] || distances[nextIndex] >= 0) return

        // 距離を記録し、隣接マスを後で調べるためQueueへ追加する
        distances[nextIndex] = nextDistance
        queue[writeIndex++] = nextIndex
    }
}

Queueから先に入れたマスを先に調べるため、距離の小さい順序を保てます。訪問済みのマスを再び追加しないことで、探索は必ず終了します。

4. 正しさと使用資源を分析する

正しさは「Queueから取り出したマスには最短距離が入っている」「通れないマスと訪問済みのマスは追加しない」という条件から確認できます。各マスと隣接関係を高々一度ずつ調べるため、時間計算量はGraphの頂点数をV、辺数をEとしてO(V + E)、距離とQueueにO(V)のメモリを使います。

さらにVEINでは、探索者の位置ごとに距離の表を一度作り、Mapへ保存します。クリーチャーごとに同じ探索を繰り返す時間を減らす代わりに、距離の表を保持するメモリを使う設計です。

Kotlin — AssaultBattle.ktから抜粋

val targetDistances = explorers
    // 同じ位置にいる探索者の距離の表を重複して作らない
    .map(ExplorerCombatant::position)
    .distinct()

    // 探索者の位置をキーにして、計算した距離の表を保存する
    .associateWith { target ->
        navigation.distanceField(listOf(target))
    }

設計は一度で終わらない

最初は正しく動く単純な方法を作り、入力規模や呼び出し頻度を測りながら見直します。Big Oは入力が増えたときの傾向を比較する道具です。Android上の実際の速さは、端末、メモリ割り当て、GC、実行頻度も含めて測定します。