「マンハッタン距離vsチェビシェフ距離」Unityエンジニアが語る最適な移動アルゴリズムとは？
「マンハッタン距離vsチェビシェフ距離」Unityエンジニアが語る最適な移動アルゴリズムとは？
ゲーム開発において、キャラクターの移動や敵の追跡アルゴリズムはプロジェクトの完成度を左右する重要な要素です。特にタイルベースの2Dゲームや3D空間を扱う作品で、AIの移動ルートを決める際には「距離」をどのように定義するかが非常に大きな影響を与えます。本記事では、代表的な2つの距離計算手法であるマンハッタン距離とチェビシェフ距離の違いを中心に、ゲームAIの文脈でどのように使い分けるかを解説し、Unity*C#における実装のヒントを紹介します。ゲームAIエンジニアが直面しがちな悩みにフォーカスしながら、読者がスムーズに導入できるように丁寧に説明していきます。
なぜ距離計算が重要なのか？
ゲーム開発では、キャラクターの移動に関連するさまざまなロジックが存在します。たとえば、以下のようなケースがあります。
- 敵や味方キャラクターの最短ルート探索
- ノンプレイヤーキャラクター（NPC）の追従や到達地点の判定
- 探索ゲームでのアイテムやイベントポイントへの誘導
これらのシステムを考えるうえで、AIが「どれだけ離れているか」を算出する手段として距離計算を用います。しかし、同じ「距離」という言葉でも、その計算式によってルート選定の結果や処理負荷が大きく変化する点が見逃せません。
マンハッタン距離とは
マンハッタン距離（Manhattan Distance）は、碁盤目状のマップで上下左右（垂直・水平方向）にしか移動しない場合の最短距離を表すのに使われる手法です。2点 ((x_1, y_1)) と ((x_2, y_2)) のマンハッタン距離は次式で示されます:
-
用途の例
- タイルベースの2Dゲーム（ローグライクやシミュレーションRPGなど）
- 街路（グリッド）を想定した都市マップ上のルート探索
マンハッタン距離の利点は、実際の道路構造や縦横移動を想定したゲームマップにマッチしやすいことです。一方、斜め移動を行わないため、移動方向が制限されるケースでは非常に直感的ですが、「最短ルート」を求めるときに余計な回り道が増える可能性がある点も考慮が必要です。
チェビシェフ距離とは
チェビシェフ距離（Chebyshev Distance）は、斜め移動を含めたあらゆる方向へ1ステップで移動可能な状況を想定した距離計算です。2点 ((x_1, y_1)) と ((x_2, y_2)) のチェビシェフ距離は次式で示されます:
この計算式は、チェスの“キング”の移動に例えられることが多く、1手で8方向すべてに1マス移動できる状況をイメージすると分かりやすいです。たとえば、より斜め移動を多用するアクションゲームや、8方向に自由なパス探索を行うAIで用いられます。
詳しい解説は以下のリンク先でも確認できます。
この方法の利点は移動ステップが少なく済みやすい点ですが、マップの構造によっては障害物を回避するロジックを別途用意しないと、AIがジグザグに動きすぎるなどの問題も起こりがちです。
両者を比較する際のポイント
マンハッタン距離とチェビシェフ距離は、ゲームの要件や想定移動方向によって使い分けます。
-
マンハッタン距離を選ぶ理由
- 縦横移動のみが許される格子状マップ
- 都市マップやローグライク系ゲームとの親和性が高い
- 実装がシンプルで処理も軽量になりやすい
-
チェビシェフ距離を選ぶ理由
- 斜め移動をフルに活用したいゲームシステム
- グリッドの8方向移動が標準となるシミュレーション系やストラテジー系
- より柔軟かつスムーズな移動が求められる
また、ユークリッド距離（(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2})）を含めた多様な定義を紹介しているページもあります。 ゲームの種類や世界観によって、どれを採用すると操作感や動きが自然に感じられるかを見極めましょう。
Unity*C#での実装例
簡単な疑似コード
以下は、Unityで2Dグリッド上の移動を想定した疑似コード例です。マンハッタン距離とチェビシェフ距離を切り替えて使うイメージを示します。
public static class DistanceCalculator
{
// マンハッタン距離
public static float GetManhattanDistance(Vector2Int posA, Vector2Int posB)
{
return Mathf.Abs(posB.x - posA.x) + Mathf.Abs(posB.y - posA.y);
}
// チェビシェフ距離
public static float GetChebyshevDistance(Vector2Int posA, Vector2Int posB)
{
return Mathf.Max(Mathf.Abs(posB.x - posA.x), Mathf.Abs(posB.y - posA.y));
}
}
あらかじめタイル座標を Vector2Int で管理しておき、AIの移動ルート探索部分で呼び出せば、目的に応じて適切な移動コストを算出できます。
障害物の考慮とA*アルゴリズム
実際のゲーム制作では、単純に距離だけを求めるだけでなく、障害物や移動コストの差異（例：草地は1.5倍、砂地は2倍など）を考慮するケースが多々あります。そんなときはA*アルゴリズムを用いて、ヒューリスティックにマンハッタン距離やチェビシェフ距離を導入します。
ヒント: 「A*アルゴリズム＋チェビシェフ距離」を使うと、8方向移動時の最短経路が短時間で算出できる一方、壁を回り込むケースが増えるマップではマンハッタン距離のほうが計算負荷が小さい場合もあります。
ゲーム設計者・AIエンジニアが押さえておくべきポイント
- 適用範囲を最初に明確化する
- 「移動方向は4方向か、8方向か？」
- 「余計なジグザグ移動が発生してもいいのか？」
- 処理負荷と精度のバランス
- ゲームのジャンルやステージ規模によってアルゴリズムの負荷は変わる
- 数百、数千単位のNPCがいる大規模マップでは単純さが武器になることも
- 見た目や操作感への影響
- プレイヤーの直感に合った動きを実装できているか
- 斜め移動が可能な場合でもわざと使用制限をかけるケースもある
また、以下のページにはマンハッタン距離とチェビシェフ距離の図解が掲載されています。移動範囲のイメージをつかむ上で役立つでしょう。
まとめと次のステップ
ゲームAIにおいて「距離」をどう定義するかは、NPCの動きやプレイヤーが感じる操作性を左右する重要な要素です。マンハッタン距離はグリッドマップ上の縦横移動に最適であり、実装コストも低め。一方のチェビシェフ距離は斜め移動を考慮することで、より少ない移動ステップ数を実現しやすく、リアルな挙動を提供できます。
使い分けのポイントとしては、「ゲームジャンル」「移動方向の自由度」「パフォーマンス要件」などが挙げられます。特にUnityC#での実装では、Aアルゴリズムや独自のヒューリスティック設計との組み合わせ次第で多彩な動きを表現できるでしょう。
最適なアルゴリズムを見極めるには、実際に動かしてみるのがいちばん効果的です。あなたのゲームの世界観や操作性にしっくりくる設定を探る過程は、クリエイターとしての醍醐味でもあります。ぜひ、記事中のリンクも活用しながら、自分だけの最適解を見つけてください。
この記事を読んでもっと実践したいと感じたあなたへ
Unity開発を効率よく進めるためには、実践的なスキルと仲間との交流が欠かせません。
そんな方におすすめのステップが、下記の3つです。
1. 有料教材「どこでもUnity教室」でゲーム制作を短期マスター
- 5日でシンプルなFPS完成：初心者向けに要点を押さえたカリキュラム
- C#や最新のInputSystem、FPS実装まで網羅：つまずきやすいポイントを先回りで解説
- 購入特典：Discord招待＋サンプルプロジェクトDLで、疑問や実装例を即確認
Unity初心者でも最短5日で3D FPSが完成！今すぐ始める入門チュートリアルはこちら
2. 無料コミュニティで、疑問をすぐに解消＆モチベーションUP
- 初心者～中級者までOK：学習進度に合わせて質問や情報共有
- 質問サポートが充実：わからないことを仲間や講師に即相談
- 学習仲間と切磋琢磨：一緒に学ぶから続けやすい
Discordサーバー参加はこちら
3. 実績豊富な“ゲーム開発所RYURYU”があなたをトータルサポート
- コナラ総販売200件超：さまざまなUnity開発の依頼を対応
- VR/AR/AIなど最新技術にも精通：幅広いノウハウを活かして開発支援
- ゲームクリエイター甲子園や東京ゲームショウなど出展実績多数
ご相談・お問い合わせはこちら
Discussion