ゲームの敵AIの作り方｜迷路で相手を追いかける3つの動きと、捕まえた割合の実測

ゲームの敵が、壁のある迷路で相手を追いかけるときは、最短経路を探す「幅優先探索」を使うと、確実に追えます。相手のほうへ近づくだけの動きにすると、壁の前で止まって、ほとんど捕まえられませんでした。この記事のコードは、迷路を作り、3つの追い方を何百回も戦わせて、捕まえた割合を数えます。

コードはNodeで実行しました。数字は、乱数のシードを固定して、このコードを実行して数えた値です。

ターン制の対戦ゲームのAIは、AIと対戦するゲームの作り方とオセロAIの作り方で扱っています。ここでは、敵が相手を追いかける、動きのあるゲームの敵です。

この記事の目次

1. 01追い方は3つ
2. 02コード全体
3. 03追い方ごとの結果
   1. 最短経路の計算にかかる時間
4. 04迷路づくりの落とし穴
5. 05確かめられていないこと
6. 06うまくいかないとき
7. 07よくある疑問
8. 08この記事のまとめ

追い方は3つ

敵が1ターンに1歩ずつ進んで、相手を追います。相手は、敵から道のりで最も遠くなる隣のマスへ逃げます。追い方は、次の3つを比べました。

• まっすぐ近づく：相手との距離が縮まる隣へ進む。縮まらなければ動かない
• 最短経路（幅優先探索）：迷路全体を調べて、相手までの最短の道の最初の1歩を選ぶ
• でたらめに歩く：通れる隣のマスを、でたらめに選ぶ

左の図は、相手が動かないときの、同じ迷路での歩き方です。まっすぐ近づく追い方は、16歩で壁の前に着いて、そこから動けなくなりました。最短経路の追い方は、遠回りしても、68歩で相手に着きました。

コード全体

次のコードを、chase.jsという名前で保存して、「node chase.js」で実行します。迷路は穴掘り法で作ります。ブラウザでの実行は、確かめていません。

// 壁のある迷路で、敵が逃げる相手を追う。追い方の違いを、何度も戦わせて数える
// 実行: node chase.js

// 同じ乱数の並びを再現できるシード付きの乱数
function makeRng(seed) { let a = seed >>> 0; return () => { a = (a + 0x6D2B79F5) >>> 0; let t = a; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }

const N = 21; // 迷路の大きさ（奇数）。1が壁、0が通路
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];

// 穴掘り法で、必ずつながった迷路を作る。さらに壁を少し壊して、回り道ができるようにする
function makeMaze(rnd, safe = true) {
  const g = Array.from({ length: N }, () => Array(N).fill(1));
  const stack = [[1, 1]]; g[1][1] = 0;
  while (stack.length) {
    const [x, y] = stack[stack.length - 1];
    const next = DIRS.map(([dx, dy]) => [x + dx * 2, y + dy * 2, dx, dy]).filter(([nx, ny]) => nx > 0 && ny > 0 && nx < N - 1 && ny < N - 1 && g[ny][nx] === 1);
    if (!next.length) { stack.pop(); continue; }
    const [nx, ny, dx, dy] = next[Math.floor(rnd() * next.length)];
    g[y + dy][x + dx] = 0; g[ny][nx] = 0; stack.push([nx, ny]);
  }
  for (let i = 0; i < 25; i++) { // 壁を25か所壊して、回り道を作る
    const x = 1 + Math.floor(rnd() * (N - 2)), y = 1 + Math.floor(rnd() * (N - 2));
    // 通路どうしの間にある壁（x+yが奇数の位置）だけを壊す。それ以外を壊すと、孤立した穴ができる
    if (g[y][x] === 1 && (!safe || (x + y) % 2 === 1)) g[y][x] = 0; // safe=falseは、比較用（どの壁でも壊す）
  }
  return g;
}
// 追う側が、1歩進む方向を決める
function stepGreedy(g, from, to) { // 相手に向かって、まっすぐ近づく（壁があれば動けない）
  const opts = DIRS.map(([dx, dy]) => [from[0] + dx, from[1] + dy]).filter(([x, y]) => g[y][x] === 0);
  if (!opts.length) return from;
  const d = (p) => Math.abs(p[0] - to[0]) + Math.abs(p[1] - to[1]);
  opts.sort((a, b) => d(a) - d(b));
  return d(opts[0]) < d(from) ? opts[0] : from; // 近づけないなら、動かない
}
function stepBfs(g, from, to) { // 幅優先探索で、最短経路の最初の1歩を選ぶ
  const prev = new Map([[from.join(), null]]);
  const q = [from];
  while (q.length) {
    const p = q.shift();
    if (p[0] === to[0] && p[1] === to[1]) break;
    for (const [dx, dy] of DIRS) {
      const n = [p[0] + dx, p[1] + dy];
      if (g[n[1]][n[0]] === 0 && !prev.has(n.join())) { prev.set(n.join(), p); q.push(n); }
    }
  }
  let cur = to;
  if (!prev.has(cur.join())) return from;
  while (prev.get(cur.join()) && prev.get(cur.join()).join() !== from.join()) cur = prev.get(cur.join());
  return prev.get(cur.join()) ? cur : from;
}
function stepRandom(g, from, to, rnd) {
  const opts = DIRS.map(([dx, dy]) => [from[0] + dx, from[1] + dy]).filter(([x, y]) => g[y][x] === 0);
  return opts[Math.floor(rnd() * opts.length)];
}

// 逃げる側: 敵から最も遠くなる隣へ動く（壁に追い詰められないよう、距離は迷路の道のりで測る）
function bfsDist(g, from) {
  const d = Array.from({ length: N }, () => Array(N).fill(Infinity)); d[from[1]][from[0]] = 0;
  const q = [from];
  while (q.length) { const [x, y] = q.shift(); for (const [dx, dy] of DIRS) { const nx = x + dx, ny = y + dy; if (g[ny][nx] === 0 && d[ny][nx] === Infinity) { d[ny][nx] = d[y][x] + 1; q.push([nx, ny]); } } }
  return d;
}
function stepRun(g, from, enemy) {
  const d = bfsDist(g, enemy);
  const opts = [from, ...DIRS.map(([dx, dy]) => [from[0] + dx, from[1] + dy]).filter(([x, y]) => g[y][x] === 0)];
  opts.sort((a, b) => d[b[1]][b[0]] - d[a[1]][a[0]]);
  return opts[0];
}

// 1回の追いかけ。maxTurns以内に捕まえたら、かかったターン数。逃げ切られたらnull
// enemySpeed: 敵が1ターンに進む歩数（1か2）。逃げる側は1歩
function chase(g, stepFn, enemySpeed, rnd, maxTurns = 200) {
  const free = []; for (let y = 0; y < N; y++) for (let x = 0; x < N; x++) if (g[y][x] === 0) free.push([x, y]);
  let enemy = free[Math.floor(rnd() * free.length)], me = free[Math.floor(rnd() * free.length)];
  for (let t = 1; t <= maxTurns; t++) {
    me = stepRun(g, me, enemy);
    for (let s = 0; s < enemySpeed; s++) { enemy = stepFn(g, enemy, me, rnd); if (enemy[0] === me[0] && enemy[1] === me[1]) return t; }
  }
  return null;
}

if (typeof module !== 'undefined') module.exports = { makeRng, makeMaze, stepGreedy, stepBfs, stepRandom, chase, bfsDist, N };

if (typeof require !== 'undefined' && require.main === module) {
  const rnd = makeRng(2026);
  // 迷路が必ずつながっているかの確認（通路が孤立していないか）
  const isConnected = (g) => { const d = bfsDist(g, [1, 1]); for (let y = 0; y < N; y++) for (let x = 0; x < N; x++) if (g[y][x] === 0 && d[y][x] === Infinity) return false; return true; };
  for (const [name, mk] of [['どの壁でも壊す作り方', (r) => makeMaze(r, false)], ['通路の間の壁だけ壊す作り方', makeMaze]]) {
    let ok = 0; for (let i = 0; i < 1000; i++) if (isConnected(mk(rnd))) ok++;
    console.log(name, '：迷路1000個のうち、通路がすべてつながっていた数', ok);
  }

  console.log('追い方ごとの結果（迷路300個×1回。200ターン以内に捕まえた割合・平均ターン）');
  for (const speed of [1, 2]) {
    for (const [name, fn] of [['まっすぐ近づく', stepGreedy], ['最短経路（幅優先）', stepBfs], ['でたらめに歩く', stepRandom]]) {
      const r = makeRng(7); let caught = 0, total = 0;
      for (let i = 0; i < 300; i++) { const g = makeMaze(r); const t = chase(g, fn, speed, r); if (t !== null) { caught++; total += t; } }
      console.log('敵の速さ', speed + '歩', name, '捕まえた', (caught / 3).toFixed(1) + '%', '平均', caught ? (total / caught).toFixed(1) : '―', 'ターン');
    }
  }
  // 計算時間: 幅優先は、1歩ごとに迷路全体を調べる
  const g = makeMaze(makeRng(1)); const t0 = performance.now(); for (let i = 0; i < 1000; i++) stepBfs(g, [1, 1], [N - 2, N - 2]); console.log('幅優先1回あたりの時間', ((performance.now() - t0) / 1000).toFixed(3) + 'ms（21×21の迷路）');
}

追い方ごとの結果

迷路を300個作って、1個につき1回、敵と相手を、でたらめな位置に置いて追いかけさせました。200ターン以内に捕まえたら成功です。敵の速さは、1ターンに1歩の場合と、2歩の場合で比べました。相手は、どちらも1歩です。

最短経路の追い方は、敵が2歩のとき100.0%（平均21.7ターン）で、300回すべて捕まえました。敵が1歩のときは70.7%（平均47.6ターン）で、約3割の逃げ切りを許しました。この迷路は、壁を25か所壊して回り道があるので、同じ速さでは、相手が輪になった道をぐるぐる回って逃げられるためと考えられます。この理由は、確かめていません。

まっすぐ近づく追い方は、1歩でも2歩でも、捕まえた割合が1.3%と3.0%でした。でたらめに歩く追い方も、1.3%と3.3%です。この迷路では、近づくだけの追い方は、でたらめに歩くのとほとんど変わりませんでした。

最短経路の計算にかかる時間

最短経路の計算は、敵が1歩進むたびに、迷路全体を調べます。21×21の迷路で、1回あたり約0.09ミリ秒（1,000回の平均）でした。1画面に敵が数十体いても、1フレームに収まる範囲です。もっと大きな迷路や、多くの敵では、確かめていません。

迷路づくりの落とし穴

回り道を作るために、迷路の壁を25か所、でたらめに壊しました。最初は、壊す壁を選ばずに壊しました。この作り方で迷路を1,000個作ると、通路がすべてつながっていたのは、975個でした。25個の迷路には、壁の中に孤立した穴ができていました。

穴掘り法の迷路では、通路のマスが奇数番目の行と列に並びます。その間の壁が、x＋yが奇数の位置です。偶数番目の行と列が交わる位置の壁（柱）は、四方が壁なので、壊すと、まわりが壁の孤立した穴になります。x＋yが奇数の壁だけを壊すようにすると、1,000個すべてがつながりました。コードのmakeMazeの第2引数が、この切り替えです。

孤立した穴に、敵や相手が置かれると、どんな追い方でも追いつけません。追いつけない原因が、AIの動きではなく、迷路のほうにある例です。結果が悪いときは、AIの動きより先に、使っているデータ（迷路）を確かめます。

確かめられていないこと

• 実際のゲームでの遊び心地ここでの捕まえた割合は、1ターンごとに動くコードでの数字です。リアルタイムで動くゲームでの遊び心地は、確かめていません。
• 同じ速さのとき、逃げ切られる理由（回り道のある迷路で輪になった道を回るためと考えられますが、確かめていません）
• 相手が、人の操作で動く場合
• A*探索との比較（この記事は幅優先探索だけです）
• 大きな迷路や、敵が多い場合の処理の速さ
• ブラウザでの実行

確かめていないものは、動かして確かめてから、別の記事で扱います。

うまくいかないとき

症状	確認すること
敵が壁の前で止まる	近づくだけの動きになっていないかを確かめます。最短経路を探す動きに替えます
どうしても追いつけない敵がいる	迷路が、孤立した穴を作っていないかを確かめます。通路がすべてつながっているかを、幅優先探索で数えられます
敵が速すぎて、遊べない	敵の速さを下げます。同じ速さでも、この記事の迷路では約3割が逃げ切りました
動きが止まる	最短経路の計算で、相手の位置が壁になっていないかを確かめます

関連記事AIと対戦するゲームの作り方｜負けないまるばつAI（ミニマックス法）と弱くする方法

よくある疑問

この記事のまとめ