Unityタワーディフェンスの経路計算の作り方：BFSと封鎖判定

壁を置くと敵の道が変わる防衛ゲームでは、敵ごとに毎回道を探さなくて済みます。 Codexで作った「最後の灯台」は、灯台から全床への距離を一度計算し、敵がその数字をたどる方式にしました。配置前には同じ盤面で、両方の侵入口から灯台へ届くかも調べます。

ここで作り方を説明するのは、7列×9行の盤面での経路計算と封鎖判定です。完成した画面や音までこのZIPで再現するものではありません。まず実際のゲームを遊ぶと、配置によって水色の進路が曲がる様子を確認できます。

配布Coreと公開ゲームは2026年10月1日のv1.6です。 v1.3で入口A→B→両入口への展開と波終了時の冷却、v1.4で敗北の振り返り、v1.5で増援前からの再挑戦を追加しました。v1.5.1では必要資材を個数と誤読させない表示へ修正。v1.6は勝利後に全3波の戦績を比較できます。敵数・費用・防衛の数値は維持しています。配置・射程・第2波の掲載画面はv1.3、振り返りはv1.4、再挑戦はv1.5、勝利結果はv1.6です。

C#サンプルで配置ごとの結果を確認する

.NET 10 SDKを入れ、経路計算と配置探索のサンプルZIPを展開します。LighthouseSample.csprojのある場所で実行してください。Unityは不要で、追加NuGetパッケージも使いません。

dotnet run --project LighthouseSample.csproj -c Release

empty health=0 kills=0 leaks=5 ticks=731
two-cannon wins=362/1223
wall rescues=188

emptyは何も置かず5隻が灯台へ到達して敗北した結果です。362/1223は、初期資材10で合法に置ける砲台2基の組を列挙し、第1波10隻の後に灯台が残った数。順番を入れ替えただけの同じ組は一つと数えています。wall rescues=188は全組ではなく、敗北した組のうち撃退数が多い上位90組に障壁を追加し、敗北から生存に変わった配置数です。成功率と読まないため、母集団を分けました。

灯台からBFSを広げ、敵は小さい数字へ進む

灯台を距離0として、上下左右の通れる床へ1、2、3と広げます。岩礁と建設物は通れません。幅優先探索（BFS）なので、各床を訪れるのは一度。今回の盤面は最大63マスで、接続は上下左右だけです。Defense.csのRebuildDistancesが共有の距離場を作ります。

distance[BeaconX, BeaconY] = 0;
queue[tail++] = BeaconY * Width + BeaconX;
while (head < tail)
{
    int cell = queue[head++], x = cell % Width, y = cell / Width;
    Visit(x + 1, y, distance[x, y] + 1, ref tail);
    Visit(x - 1, y, distance[x, y] + 1, ref tail);
    Visit(x, y + 1, distance[x, y] + 1, ref tail);
    Visit(x, y - 1, distance[x, y] + 1, ref tail);
}

これは実際のメソッドから抜き出した断片です。Visitは盤外・岩礁・建設物・訪問済みの床を除き、距離とキューを更新します。全体をコンパイルするにはZIPのDefense.csを使ってください。

敵は進むたびに現在位置の上下左右を見て、距離が最小の床を選びます。同じ距離なら「上、左、右、下」の順に決めました。この固定順がないと、同じ配置でも見た目の進路とテストの結果が揺れます。画面の進路線も敵と同じ距離場・同じ順で引き、表示と実際の移動を一致させています。

封鎖する壁は資材を使う前に拒否する

プレイヤーには二つの侵入口があります。候補マスを一時的に通行不可として灯台からBFSを行い、どちらか一方でも到達できなくなれば拒否します。岩礁、侵入口、灯台、使用済みの床、資材不足も別々の理由として返します。拒否した操作は盤面も資材も変えません。画面のホバー表示はこのCheckPlacementを使うので、押せそうな色と実際の判定が食い違わないようにしました。

public bool TryPlace(int x, int y, Building building, out PlacementError error)
{
    error = CheckPlacement(x, y, building);
    if (error != PlacementError.None) return false;
    buildings[x, y] = building;
    RebuildDistances();
    Material -= Cost(building);
    return true;
}

合法な設置では、候補の到達性を確認するBFSと、設置後の距離場を確定するBFSを実行します。敵の数だけBFSをやり直すわけではありません。戦闘中の建設を禁止しているため、進行中の敵が新しい壁の中へ取り残されるケースも生じません。戦闘中に建てられるゲームへ拡張するなら、そのケースの処理を別途設計する必要があります。

射程と次の襲撃を、実際の判定に合わせて見せる

v1.1ではPCのホバーだけで射程内の床を色づけていました。タッチでは置く前に確かめられないため、v1.2は床を押している間に射程を表示し、同じ床で離すと設置する操作へ変更。外で離せばキャンセルし、既存砲台のタップは確認だけで資材を消費しません。輪郭はDefense.CannonRangeの2.9マス、床の中心の色づけと敵への攻撃はInCannonRangeを使います。床の色は中心の目安で、移動中の敵は小数座標で判定します。砲台の旋回も、攻撃側と同じFindTargetを参照するよう修正しました。

予告用の敵リストを別に手書きすると、出現処理を直したときにずれます。そこでKindForSpawnとEntryForSpawnを実出現と予告集計で共有し、seed19・20の全3波を実際に進めて照合しました。第1・第2波はどちらも小艇8・装甲2で、装甲の出現が7/10隻目から3/7隻目へ早まります。v1.3では第1波Aから10隻、第2波Bから10隻。第3波は小艇8・装甲4、両入口から各6隻です。

第2波は敵数を増やさず、守る入口を変えた

旧版でも、第1波を生存した砲台2基362組を増援なしで進めると、第2波の生存は0組でした。難しさはありましたが、入口Aへの対処が続きます。v1.3では第2波を入口Bへ切り替え、最終波で両側の守りを組み合わせる構成にしました。待機側の経路を薄くし、上部の予告と盤面の侵入口を同じCoreから表示します。

比較は固定seed19、初期砲台(1,0)/(2,1)・障壁(3,1)、座標は左上(0,0)です。各波間に砲台を1基ずつ追加する合法配置を列挙しました。初期配置・資材・敵数・速度・射程を共通にして、入口の変更だけを比べています。

勝てる配置の数を減らすことが目的ではありません。 同じ増援位置が通用しない例と、方向を読み直せば全編を守れる例を両方残しました。機械列挙はこの初期配置だけで、全戦略を調べた数字でも人の勝率でもありません。

旧版の波間は、熱を次波開始時に消していたため、建設中だけ前波の赤い「冷却中」が止まって見えました。v1.3は波終了時に熱・発射待ち・過熱停止をまとめて解除し、画面も冷却完了を知らせます。累積の発射数と過熱回数は消しません。戦闘中の過熱ルールは同じです。

初期配置を変えても勝てるか、合法な列を調べた

v1.6の監査では、砲台2基から始め、各波の間に砲台を1基ずつ増やす列を調べました。障壁なし・合法な初期1,223組のうち第1波を生存するのは362組。第2波を生存した増援列1,462から、第3波を開始できる合法な配置列68,109を列挙しました。最終波の入口順を変えて両方を実行しています。

両方で勝てる初期197組は同じでした。単一の正解配置だけを探すゲームではありません。 一方、資材のある分だけ「盤面の行順」「灯台の近く」「現在の入口の近く」「中央の近く」に砲台を置く4方針は、どちらの入口順でも第1・2波で敗北しました。単純方針の失敗と、有効な選択の幅を分けて確認しています。

dotnet run --project CampaignProbe.csproj -c Release -- 19 campaign-19.json
dotnet run --project CampaignProbe.csproj -c Release -- 20 campaign-20.json
dotnet run --project StrategyProbe.csproj -c Release -- campaign-19.json timing.json

この検査も配布ZIPに含めました。初期砲台1基・複数障壁・一括増援は探索していません。 勝利列を人の勝率や全戦略の数と呼ばないため、探索した資材配分を明記しています。seedは最終波の入口順の偶奇だけに作用し、多数のseedを独立した条件と扱いません。

障壁は早く置くほど得か、同じ予定で時点を変えた

成功した初期配置を重心の西/中央/東と前/中/入口側の9区画に分け、各区画の代表1組と既存の障壁攻略、計10組を選びました。各組で障壁なしと、1個を第1・2・3波前に置く2,780ケースを比較。成功に偏った代表で、無作為標本ではありません。 選び方の評価式と、設置拒否・未到達の扱いはZIPのREADMEと検査コードに残しています。

初期砲台(3,5)/(4,5)、第2波(4,2)、第3波(5,4)へ増援する予定を固定し、障壁(3,6)を置く時点だけ変えました。左上が(0,0)です。

公開ゲームでもPC/375pxで、早置きと後置きの各波がCoreの記録と一致しました。早置きでは第3波の増援へ進めません。壁は進路を曲げますが、今の入口に対して砲台の前を長く通るかで結果が変わります。資材を余らせず使い切ることが常に最善ではありません。

敗北した波の漏れと熱停止を、配置の見直しへ使う

結果を全波累積だけで表示すると、第2波で守れなかった方向が分かりません。v1.4では敵の出現時にEntryXを保存し、灯台へ到達したときにその入口の漏れ数を増やしました。二つの進路が合流した後も、敵が右側にいるからBと決めることはありません。撃退と砲台別の熱停止も、その波の実イベントで数えます。

波の開始時に波記録を消し、敗北時には保持。「配置を見る」で盤面を再表示し、砲台にその波の熱停止回数、入口に漏れ数を重ねます。閲覧中は建設と進行を止め、結果へ戻るか再挑戦できます。振り返りの数字を、GUIの描画回数から数えないことも決めました。

この例の停止回数は、砲台(1,0)が1回、(2,1)が1回、追加した(3,3)が3回でした。回数だけで過熱を敗因とは断定できません。 射程の外を進んだ時間、攻撃対象、他の砲台との位置関係も影響します。ゲームではB側を見直す提案を示し、盤面で経路と砲台を照らし合わせられるようにしました。

無砲台の第1波ではA漏れ5・B漏れ0・熱停止0。その場合も架空の過熱原因を表示しません。seed19/20の全3波では、実際に消えた敵と停止へ変わった砲台を独立に観察して集計と比較。全編再開時に波記録が0へ戻ることも検査しました。

この2例は同じ配布ZIPのReviewProbe.csprojでも再現できます。メインの配置探索とは別に、展開した場所で実行してください。

dotnet run --project ReviewProbe.csproj -c Release

JSONのwaveLeaksA/waveLeaksBが当該波の漏れ、waveOverheatsが当該波の停止、stopMapが各砲台の座標と停止回数です。leaks/overheatsは全波累積。画面を含むサンプルではありませんが、表示した数字の根拠を同じCoreで追えます。

再挑戦は、失敗した増援を置く前へ戻す

敗北を振り返れても、第2波で失敗するたびに第1波からやり直すのは手間でした。v1.5では、 「この波をやり直す」で、その波の増援前の建設へ戻ります。 前の波までの施設は残り、失敗した波で追加した施設は消えます。「最初から」なら第1波の配置も変更できます。

保存対象は施設と距離場、耐久・資材、波番号、時刻・出現seed、撃退・漏れ・発射・過熱の累積値と波記録。保存用の配列は別にコピーし、再挑戦では保存値を代入します。資材や耐久を毎回加算しないため、繰り返しても増殖しません。敵と熱は消し、画面側の選択・射撃演出も戻します。

dotnet run --project RetryProbe.csproj -c Release

配布ZIPのこの検査はseed19/20で同じ第2波の敗北を3回ずつ繰り返し、復元後に増援を置き直します。JSONのbeforeが増援前、failuresが3回の敗北、winが置き直し後の最終結果です。

Unityでは第1〜3波それぞれ、seed19/20で3回ずつ敗北と復元を繰り返し、配置・経路・時刻・記録が保存時と一致することを確認しました。同じ配置なら同じ敗北になります。復元は敗北後だけ受け付け、建設中・戦闘中・勝利後からは使えません。

全3波の確定記録を勝利後にも残す

v1.6では、次の波へ進む前に戦績を確定して保存します。 勝利画面には撃退・入口A/B別の漏れ・施設数・熱停止を波ごとに並べました。波の集計は次波でリセットされるため、最後の値だけを読むと第1・2波の結果が消えます。OutcomeAt(wave)から確定済みの値を読み、未終了の波は記録済みと扱いません。

これは上の配置で勝利した実記録です。熱停止が最多の第3波でも漏れは0でした。停止回数だけを敗因と決めつけず、漏れた入口や配置と見比べます。 再挑戦では失敗した波の記録を取り消し、前波の記録を残します。配布ZIPのRetryProbe.csprojでもoutcomesに同じ記録が出ます。

何を検査し、何をまだ測っていないか

UnityのEditMode 26件では封鎖、資材、固定入力での再現、波終了時の冷却と3波の勝利、旧攻略の第2波敗北、射程の境界、seed19/20の実出現と予告、対象選択に加え、入口別の漏れと砲台別の停止を実状態の変化から照合しました。波の確定記録と累積の合計、再挑戦時の失敗記録の取り消しも検査。PlayMode 1件では素材、配置、距離場、進行/停止、予告/冷却、振り返り、再挑戦と置き直し後の勝利、記録リセットを確認。WebGLでもPCと375px幅で全3波と敗北からの見直しを操作しました。公開ビルドのサイズと起動時間はゲーム紹介ページに現行値を載せます。

人の初見難度とスマホ実機の処理速度は未評価です。 ここでの375px検査はPCのブラウザにタッチ幅を再現したものです。機械的に勝てる配置があっても、進路の読みやすさや試行錯誤の気持ちよさを保証しません。次の改良では、その手触りを実際の操作で確かめます。