A*で作るSRPGの最短ルート探索｜迷わないパスファインディング実装

A*アルゴリズムは、最短経路を効率的に求められます。

SRPGの経路探索に最適です。

この記事では、実装方法を詳しく解説します。

✨ この記事でわかること

A*アルゴリズムの基本概念
ノード構造の設計
ヒューリスティック関数の実装
コスト設計と地形対応
実装例とコード

ゲーム開発講師

A*アルゴリズムは、BFSより効率的です。ただし、実装は少し複雑になります。まずは基本構造を理解しましょう。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

ゲームを「遊ぶ側」から「作る側」へ

あなたのオリジナルゲーム、今年こそ完成させませんか？

RPG・アクション・ホラー…Unityで本格ゲームを作りたい人のための学習サイトです。

Unity入門の森｜永久会員チケット

全講座ラインナップを見てみる

実際に完成するゲームを題材に、
ソースコード・素材・プロジェクト一式をすべて公開。
仕事や学校の合間の1〜2時間でも、
「写経→改造」で自分のゲームまで作りきれる環境です。

A*アルゴリズムの基本概念
1. BFSとの違い
ノード構造の設計
1. ノードクラスの実装
ヒューリスティック関数の実装
1. マンハッタン距離（推奨）
2. ユークリッド距離
A*アルゴリズムの実装
地形コストへの対応
1. 地形コストの設定
2. コストを考慮した経路探索
障害物への対応
1. 障害物チェック
2. 動的障害物の対応
実装例：完全なA*パスファインディング
よくある質問（FAQ）
まとめ

A*アルゴリズムの基本概念

A*アルゴリズムは、最短経路を効率的に求めます。

基本概念を理解しましょう。

f(n) = g(n) + h(n)：評価関数
g(n)：スタートから現在ノードまでの実コスト
h(n)：現在ノードからゴールまでの推定コスト（ヒューリスティック）

f(n)が最小のノードを優先的に探索します。

これにより、効率的に最短経路を見つけられます。

BFSとの違い

✅ A*とBFSの違い

BFS：すべてのノードを均等に探索（無駄が多い）
A*：ゴールに向かって優先的に探索（効率的）
計算量：A*の方が一般的に速い

地形コストがある場合、A*が特に有効です。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

ノード構造の設計

ノード構造は、A*の基礎です。

実装方法を紹介します。

ノードクラスの実装

using UnityEngine;

public class PathNode
{
    public int x;
    public int y;
    public int gCost;  // スタートからの実コスト
    public int hCost;  // ゴールまでの推定コスト
    public int fCost;  // gCost + hCost
    public PathNode parent;  // 親ノード（経路再構築用）
    
    public PathNode(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    
    public void CalculateFCost()
    {
        fCost = gCost + hCost;
    }
}

using UnityEngine;

public class PathNode

{

public int x;

public int y;

public int gCost; // スタートからの実コスト

public int hCost; // ゴールまでの推定コスト

public int fCost; // gCost + hCost

public PathNode parent; // 親ノード（経路再構築用）

public PathNode(int x, int y)

{

this.x = x;

this.y = y;

}

public void CalculateFCost()

{

fCost = gCost + hCost;

}

このノード構造で、経路探索に必要な情報を管理できます。

fCostは、gCostとhCostの合計です。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

ヒューリスティック関数の実装

ヒューリスティック関数は、ゴールまでの距離を推定します。

実装方法を紹介します。

マンハッタン距離（推奨）

public int HeuristicManhattan(PathNode node, PathNode goal)
{
    return Mathf.Abs(node.x - goal.x) + Mathf.Abs(node.y - goal.y);
}

public int HeuristicManhattan(PathNode node, PathNode goal)

{

return Mathf.Abs(node.x - goal.x) + Mathf.Abs(node.y - goal.y);

}

マンハッタン距離は、SRPGに最適です。

斜め移動がない場合、正確な距離を返します。

ユークリッド距離

public float HeuristicEuclidean(PathNode node, PathNode goal)
{
    float dx = node.x - goal.x;
    float dy = node.y - goal.y;
    return Mathf.Sqrt(dx * dx + dy * dy);
}

public float HeuristicEuclidean(PathNode node, PathNode goal)

{

float dx = node.x - goal.x;

float dy = node.y - goal.y;

return Mathf.Sqrt(dx * dx + dy * dy);

}

ユークリッド距離は、斜め移動がある場合に有効です。

ただし、計算コストが高いです。

マンハッタン距離：SRPG推奨、計算が速い
ユークリッド距離：斜め移動あり、計算が遅い
チェビシェフ距離：8方向移動、計算が速い

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

A*アルゴリズムの実装

A*アルゴリズムの完全な実装を紹介します。

using UnityEngine;
using System.Collections.Generic;
using System.Linq;

public class AStarPathfinder : MonoBehaviour
{
    public List<PathNode> FindPath(PathNode start, PathNode goal, GridMap gridMap)
    {
        List<PathNode> openSet = new List<PathNode>();
        HashSet<PathNode> closedSet = new HashSet<PathNode>();
        
        start.gCost = 0;
        start.hCost = HeuristicManhattan(start, goal);
        start.CalculateFCost();
        
        openSet.Add(start);
        
        Vector2Int[] directions = new Vector2Int[]
        {
            new Vector2Int(1, 0),
            new Vector2Int(-1, 0),
            new Vector2Int(0, 1),
            new Vector2Int(0, -1)
        };
        
        while (openSet.Count > 0)
        {
            // fCostが最小のノードを選択
            PathNode current = openSet.OrderBy(n => n.fCost).First();
            
            if (current.x == goal.x && current.y == goal.y)
            {
                // 経路を再構築
                return ReconstructPath(current);
            }
            
            openSet.Remove(current);
            closedSet.Add(current);
            
            foreach (var direction in directions)
            {
                int newX = current.x + direction.x;
                int newY = current.y + direction.y;
                
                if (!gridMap.IsValidPosition(newX, newY))
                    continue;
                
                PathNode neighbor = new PathNode(newX, newY);
                
                if (closedSet.Contains(neighbor))
                    continue;
                
                if (gridMap.HasObstacle(newX, newY))
                    continue;
                
                int tentativeGCost = current.gCost + gridMap.GetMoveCost(newX, newY);
                
                if (!openSet.Contains(neighbor))
                {
                    openSet.Add(neighbor);
                }
                else if (tentativeGCost >= neighbor.gCost)
                {
                    continue;
                }
                
                neighbor.parent = current;
                neighbor.gCost = tentativeGCost;
                neighbor.hCost = HeuristicManhattan(neighbor, goal);
                neighbor.CalculateFCost();
            }
        }
        
        // 経路が見つからなかった
        return new List<PathNode>();
    }
    
    int HeuristicManhattan(PathNode node, PathNode goal)
    {
        return Mathf.Abs(node.x - goal.x) + Mathf.Abs(node.y - goal.y);
    }
    
    List<PathNode> ReconstructPath(PathNode node)
    {
        List<PathNode> path = new List<PathNode>();
        PathNode current = node;
        
        while (current != null)
        {
            path.Add(current);
            current = current.parent;
        }
        
        path.Reverse();
        return path;
    }
}

using UnityEngine;

using System.Collections.Generic;

using System.Linq;

public class AStarPathfinder : MonoBehaviour

{

public List<PathNode> FindPath(PathNode start, PathNode goal, GridMap gridMap)

{

List<PathNode> openSet = new List<PathNode>();

HashSet<PathNode> closedSet = new HashSet<PathNode>();

start.gCost = 0;

start.hCost = HeuristicManhattan(start, goal);

start.CalculateFCost();

openSet.Add(start);

Vector2Int[] directions = new Vector2Int[]

{

new Vector2Int(1, 0),

new Vector2Int(-1, 0),

new Vector2Int(0, 1),

new Vector2Int(0, -1)

};

while (openSet.Count > 0)

{

// fCostが最小のノードを選択

PathNode current = openSet.OrderBy(n => n.fCost).First();

if (current.x == goal.x && current.y == goal.y)

{

// 経路を再構築

return ReconstructPath(current);

}

openSet.Remove(current);

closedSet.Add(current);

foreach (var direction in directions)

{

int newX = current.x + direction.x;

int newY = current.y + direction.y;

if (!gridMap.IsValidPosition(newX, newY))

continue;

PathNode neighbor = new PathNode(newX, newY);

if (closedSet.Contains(neighbor))

continue;

if (gridMap.HasObstacle(newX, newY))

continue;

int tentativeGCost = current.gCost + gridMap.GetMoveCost(newX, newY);

if (!openSet.Contains(neighbor))

{

openSet.Add(neighbor);

}

else if (tentativeGCost >= neighbor.gCost)

{

continue;

}

neighbor.parent = current;

neighbor.gCost = tentativeGCost;

neighbor.hCost = HeuristicManhattan(neighbor, goal);

neighbor.CalculateFCost();

}

// 経路が見つからなかった

return new List<PathNode>();

}

int HeuristicManhattan(PathNode node, PathNode goal)

{

return Mathf.Abs(node.x - goal.x) + Mathf.Abs(node.y - goal.y);

}

List<PathNode> ReconstructPath(PathNode node)

{

List<PathNode> path = new List<PathNode>();

PathNode current = node;

while (current != null)

{

path.Add(current);

current = current.parent;

}

path.Reverse();

return path;

}

このコードで、A*アルゴリズムが実装できます。

最短経路が自動で求められます。

ゲーム開発講師

A*アルゴリズムは、最初は複雑に見えますが、一度理解すれば応用が効きます。まずは基本構造を覚えましょう。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

地形コストへの対応

地形によって移動コストが変わる場合、A*が特に有効です。

実装方法を紹介します。

地形コストの設定

public class GridMap : MonoBehaviour
{
    public enum TerrainType
    {
        Plain,      // 平地（コスト1）
        Forest,     // 森（コスト2）
        Mountain,   // 山（コスト3）
        Water       // 水（移動不可）
    }
    
    private TerrainType[,] terrainMap;
    
    public int GetMoveCost(int x, int y)
    {
        TerrainType terrain = terrainMap[x, y];
        
        switch (terrain)
        {
            case TerrainType.Plain:
                return 1;
            case TerrainType.Forest:
                return 2;
            case TerrainType.Mountain:
                return 3;
            case TerrainType.Water:
                return 999; // 移動不可
            default:
                return 1;
        }
    }
    
    public bool HasObstacle(int x, int y)
    {
        return terrainMap[x, y] == TerrainType.Water;
    }
}

public class GridMap : MonoBehaviour

{

public enum TerrainType

{

Plain, // 平地（コスト1）

Forest, // 森（コスト2）

Mountain, // 山（コスト3）

Water // 水（移動不可）

}

private TerrainType[,] terrainMap;

public int GetMoveCost(int x, int y)

{

TerrainType terrain = terrainMap[x, y];

switch (terrain)

{

case TerrainType.Plain:

return 1;

case TerrainType.Forest:

return 2;

case TerrainType.Mountain:

return 3;

case TerrainType.Water:

return 999; // 移動不可

default:

return 1;

}

public bool HasObstacle(int x, int y)

{

return terrainMap[x, y] == TerrainType.Water;

}

地形ごとに移動コストを設定します。

A*アルゴリズムが、コストを考慮して最短経路を求めます。

コストを考慮した経路探索

A*アルゴリズムの実装では、tentativeGCostの計算で地形コストを考慮します。

これにより、コストが最小の経路が選ばれます。

✅ 地形コストの例

平地：コスト1（標準）
森：コスト2（移動しにくい）
山：コスト3（さらに移動しにくい）
水：移動不可

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

障害物への対応

障害物がある場合、経路から除外します。

実装方法を紹介します。

障害物チェック

public class GridMap : MonoBehaviour
{
    private bool[,] obstacleMap;
    private List<Unit> units = new List<Unit>();
    
    public bool HasObstacle(int x, int y)
    {
        // 地形による障害物
        if (terrainMap[x, y] == TerrainType.Water)
            return true;
        
        // ユニットによる障害物
        foreach (var unit in units)
        {
            if (unit.gridX == x && unit.gridY == y)
            {
                return true;
            }
        }
        
        return false;
    }
    
    public bool IsValidPosition(int x, int y)
    {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
}

public class GridMap : MonoBehaviour

{

private bool[,] obstacleMap;

private List<Unit> units = new List<Unit>();

public bool HasObstacle(int x, int y)

{

// 地形による障害物

if (terrainMap[x, y] == TerrainType.Water)

return true;

// ユニットによる障害物

foreach (var unit in units)

{

if (unit.gridX == x && unit.gridY == y)

{

return true;

}

return false;

}

public bool IsValidPosition(int x, int y)

{

return x >= 0 && x < width && y >= 0 && y < height;

}

地形とユニットの両方をチェックします。

障害物があるマスは、経路から除外されます。

動的障害物の対応

ユニットが移動する場合、障害物マップを更新します。

経路探索のたびに、最新の状態をチェックしましょう。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

実装例：完全なA*パスファインディング

実際に使える、完全なA*パスファインディングの実装例を紹介します。

using UnityEngine;
using System.Collections.Generic;
using System.Linq;

public class CompleteAStarPathfinder : MonoBehaviour
{
    public List<Vector2Int> FindPath(Vector2Int start, Vector2Int end, GridMap gridMap)
    {
        PathNode startNode = new PathNode(start.x, start.y);
        PathNode endNode = new PathNode(end.x, end.y);
        
        List<PathNode> openSet = new List<PathNode>();
        HashSet<string> closedSet = new HashSet<string>();
        
        Dictionary<string, PathNode> allNodes = new Dictionary<string, PathNode>();
        allNodes[GetNodeKey(startNode)] = startNode;
        
        startNode.gCost = 0;
        startNode.hCost = HeuristicManhattan(startNode, endNode);
        startNode.CalculateFCost();
        
        openSet.Add(startNode);
        
        Vector2Int[] directions = new Vector2Int[]
        {
            new Vector2Int(1, 0),
            new Vector2Int(-1, 0),
            new Vector2Int(0, 1),
            new Vector2Int(0, -1)
        };
        
        while (openSet.Count > 0)
        {
            PathNode current = openSet.OrderBy(n => n.fCost).ThenBy(n => n.hCost).First();
            
            if (current.x == endNode.x && current.y == endNode.y)
            {
                return ReconstructPath(current);
            }
            
            openSet.Remove(current);
            closedSet.Add(GetNodeKey(current));
            
            foreach (var direction in directions)
            {
                int newX = current.x + direction.x;
                int newY = current.y + direction.y;
                
                if (!gridMap.IsValidPosition(newX, newY))
                    continue;
                
                string nodeKey = $"{newX},{newY}";
                
                if (closedSet.Contains(nodeKey))
                    continue;
                
                if (gridMap.HasObstacle(newX, newY))
                    continue;
                
                PathNode neighbor;
                if (!allNodes.ContainsKey(nodeKey))
                {
                    neighbor = new PathNode(newX, newY);
                    allNodes[nodeKey] = neighbor;
                }
                else
                {
                    neighbor = allNodes[nodeKey];
                }
                
                int moveCost = gridMap.GetMoveCost(newX, newY);
                int tentativeGCost = current.gCost + moveCost;
                
                if (!openSet.Contains(neighbor))
                {
                    openSet.Add(neighbor);
                }
                else if (tentativeGCost >= neighbor.gCost)
                {
                    continue;
                }
                
                neighbor.parent = current;
                neighbor.gCost = tentativeGCost;
                neighbor.hCost = HeuristicManhattan(neighbor, endNode);
                neighbor.CalculateFCost();
            }
        }
        
        return new List<Vector2Int>();
    }
    
    int HeuristicManhattan(PathNode node, PathNode goal)
    {
        return Mathf.Abs(node.x - goal.x) + Mathf.Abs(node.y - goal.y);
    }
    
    List<Vector2Int> ReconstructPath(PathNode node)
    {
        List<Vector2Int> path = new List<Vector2Int>();
        PathNode current = node;
        
        while (current != null)
        {
            path.Add(new Vector2Int(current.x, current.y));
            current = current.parent;
        }
        
        path.Reverse();
        path.RemoveAt(0); // スタート地点を除外
        return path;
    }
    
    string GetNodeKey(PathNode node)
    {
        return $"{node.x},{node.y}";
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

using UnityEngine;

using System.Collections.Generic;

using System.Linq;

public class CompleteAStarPathfinder : MonoBehaviour

{

public List<Vector2Int> FindPath(Vector2Int start, Vector2Int end, GridMap gridMap)

{

PathNode startNode = new PathNode(start.x, start.y);

PathNode endNode = new PathNode(end.x, end.y);

List<PathNode> openSet = new List<PathNode>();

HashSet<string> closedSet = new HashSet<string>();

Dictionary<string, PathNode> allNodes = new Dictionary<string, PathNode>();

allNodes[GetNodeKey(startNode)] = startNode;

startNode.gCost = 0;

startNode.hCost = HeuristicManhattan(startNode, endNode);

startNode.CalculateFCost();

openSet.Add(startNode);

Vector2Int[] directions = new Vector2Int[]

{

new Vector2Int(1, 0),

new Vector2Int(-1, 0),

new Vector2Int(0, 1),

new Vector2Int(0, -1)

};

while (openSet.Count > 0)

{

PathNode current = openSet.OrderBy(n => n.fCost).ThenBy(n => n.hCost).First();

if (current.x == endNode.x && current.y == endNode.y)

{

return ReconstructPath(current);

}

openSet.Remove(current);

closedSet.Add(GetNodeKey(current));

foreach (var direction in directions)

{

int newX = current.x + direction.x;

int newY = current.y + direction.y;

if (!gridMap.IsValidPosition(newX, newY))

continue;

string nodeKey = $"{newX},{newY}";

if (closedSet.Contains(nodeKey))

continue;

if (gridMap.HasObstacle(newX, newY))

continue;

PathNode neighbor;

if (!allNodes.ContainsKey(nodeKey))

{

neighbor = new PathNode(newX, newY);

allNodes[nodeKey] = neighbor;

}

else

{

neighbor = allNodes[nodeKey];

}

int moveCost = gridMap.GetMoveCost(newX, newY);

int tentativeGCost = current.gCost + moveCost;

if (!openSet.Contains(neighbor))

{

openSet.Add(neighbor);

}

else if (tentativeGCost >= neighbor.gCost)

{

continue;

}

neighbor.parent = current;

neighbor.gCost = tentativeGCost;

neighbor.hCost = HeuristicManhattan(neighbor, endNode);

neighbor.CalculateFCost();

}

return new List<Vector2Int>();

}

int HeuristicManhattan(PathNode node, PathNode goal)

{

return Mathf.Abs(node.x - goal.x) + Mathf.Abs(node.y - goal.y);

}

List<Vector2Int> ReconstructPath(PathNode node)

{

List<Vector2Int> path = new List<Vector2Int>();

PathNode current = node;

while (current != null)

{

path.Add(new Vector2Int(current.x, current.y));

current = current.parent;

}

path.Reverse();

path.RemoveAt(0); // スタート地点を除外

return path;

}

string GetNodeKey(PathNode node)

{

return $"{node.x},{node.y}";

}

このコードで、完全なA*パスファインディングが実装できます。

地形コストと障害物の両方に対応しています。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

よくある質問（FAQ）

Q: A*とBFS、どちらを使えばいいですか？
A: 移動コストがすべて同じならBFS、地形によってコストが変わるならA*です。SRPGでは、地形コストがあることが多いため、A*がおすすめです。

Q: A*の計算が重いです。どう最適化すればいいですか？
A: ノードの比較を最適化しましょう。Dictionaryを使うことで、ノードの検索が速くなります。また、探索範囲を制限することも有効です。

Q: ヒューリスティック関数はどう選べばいいですか？
A: SRPGなら、マンハッタン距離がおすすめです。斜め移動がない場合、正確な距離を返します。計算も速いです。

Q: 障害物が動く場合、どう対応すればいいですか？
A: 経路探索のたびに、最新の障害物マップをチェックします。ユニットが移動したら、障害物マップを更新しましょう。

Q: 経路が見つからない場合、どう処理すればいいですか？
A: 空のリストを返し、UIで「移動不可」と表示します。また、移動範囲の計算時に、到達不可能なマスを除外することも有効です。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる

ゲームを「遊ぶ側」から「作る側」へ

あなたのオリジナルゲーム、今年こそ完成させませんか？

RPG・アクション・ホラー…Unityで本格ゲームを作りたい人のための学習サイトです。

Unity入門の森｜永久会員チケット

全講座ラインナップを見てみる

まとめ

A*アルゴリズムは、最短経路を効率的に求められます。

地形コストがある場合、特に有効です。

✅ 今日から始める3ステップ

ステップ1：ノード構造を実装する（所要1時間）
ステップ2：ヒューリスティック関数を実装する（所要1時間）
ステップ3：A*アルゴリズムを実装する（所要3時間）

本格的にUnityを学びたい方は、Unity入門の森で実践的なスキルを身につけましょう。

あなたのペースで、少しずつ進めていけば大丈夫です。

＼ゲーム制作をゼロから学びたいあなたへ／
Unity入門の森を見る初心者歓迎！動画×プロジェクト一式で本格ゲーム制作を学べる