A* 알고리즘

 

 

A Star 알고리즘으로 만든 길찾기

'

[System.Serializable]
public struct Tile
{
    // 타일의 위치 정보
    public Vector3Int Position;
    // 타일 위 오브젝트
    public GameObject UnitObject;
    public GameObject TileObject;

    // 장애물
    public bool Obstacle
    {
        get
        {
            // 타일이 없거나 유닛이 있으면 true
            return TileObject != null ? UnitObject != null ? true : false : true;
        }
    }
}

public class TileManager : MonoBehaviour
{
    public static TileManager instance;

    public GameObject TilePrefab;

    public Tile[,] Tiles;

    int MapSize_X = 15;
    int MapSize_Z = 15;

    private void Awake()
    {
        instance = this;

        Tiles = new Tile[MapSize_X, MapSize_Z];

        for (int x = 0; x < MapSize_X; x++)
        {
            for (int z = 0; z < MapSize_Z; z++)
            {
                Tiles[x, z].Position = new Vector3Int(x, 0, z);
                Tiles[x, z].TileObject = Instantiate(TilePrefab, new Vector3(x, 0, z), Quaternion.identity, transform);
            }
        }
    }

    public List<Tile> AStar(Vector3 start, Vector3 end)
    {
        // Vector3 를 Vector3Int 로 변환
        Vector3Int istart = Support.Vector.GetRoundVector(start);
        Vector3Int iend = Support.Vector.GetRoundVector(end);

        // 범위 검사
        if (istart.x < 0 || istart.x >= MapSize_X || istart.z < 0 || istart.z >= MapSize_Z ||
            iend.x < 0 || iend.x >= MapSize_X || iend.z < 0 || iend.z >= MapSize_Z)
        {
            Debug.LogError("시작 또는 종료 위치가 범위를 벗어났습니다.");
            return new List<Tile>();  // 빈 경로 반환
        }

        Tile startTile = Tiles[istart.x, istart.z];
        Tile endTile = Tiles[iend.x, iend.z];

        if (endTile.Obstacle)
        {
            List<Tile> possibleGoals = GetNeighbors(endTile).Where(t => !t.Obstacle).ToList();
            if (possibleGoals.Count == 0)
            {
                Debug.LogError("접근이 가능한 타일이 없습니다.");
                return new List<Tile>();
            }
            // 가능한 목적지 중 하나를 선택 (예: 가장 가까운 타일)
            endTile = possibleGoals.OrderBy(t => Heuristic(startTile, t)).First();
        }

        List<Tile> openSet = new List<Tile>();
        HashSet<Tile> closedSet = new HashSet<Tile>();
        Dictionary<Tile, Tile> cameFrom = new Dictionary<Tile, Tile>();

        Dictionary<Tile, float> gScore = new Dictionary<Tile, float>();
        Dictionary<Tile, float> fScore = new Dictionary<Tile, float>();

        // 모든 타일에 대한 초기 점수 설정
        foreach (Tile tile in Tiles)
        {
            gScore[tile] = float.MaxValue;
            fScore[tile] = float.MaxValue;
        }

        gScore[startTile] = 0;
        fScore[startTile] = Heuristic(startTile, endTile);

        openSet.Add(startTile);

        while (openSet.Count > 0)
        {
            Tile current = openSet.OrderBy(tile => fScore[tile]).First();

            if (current.Equals(endTile))
            {
                return ReconstructPath(cameFrom, current);
            }

            openSet.Remove(current);
            closedSet.Add(current);

            foreach (Tile neighbor in GetNeighbors(current))
            {
                if (closedSet.Contains(neighbor) || neighbor.Obstacle)
                {
                    continue;
                }

                float tentativeGScore = gScore[current] + 1; // 가정: 모든 이동 비용은 1

                if (!openSet.Contains(neighbor))
                {
                    openSet.Add(neighbor);
                }
                else if (tentativeGScore >= gScore[neighbor])
                {
                    continue;
                }

                cameFrom[neighbor] = current;
                gScore[neighbor] = tentativeGScore;
                fScore[neighbor] = gScore[neighbor] + Heuristic(neighbor, endTile);
            }
        }

        return new List<Tile>(); // 경로를 찾을 수 없는 경우
    }

    private List<Tile> ReconstructPath(Dictionary<Tile, Tile> cameFrom, Tile current)
    {
        List<Tile> totalPath = new List<Tile>();
        while (cameFrom.ContainsKey(current))
        {
            totalPath.Add(current);
            current = cameFrom[current];
        }
        totalPath.Reverse();
        return totalPath;
    }

    private IEnumerable<Tile> GetNeighbors(Tile tile)
    {
        List<Tile> neighbors = new List<Tile>();

        int x = tile.Position.x;
        int z = tile.Position.z;

        // 8방향 위치 설정
        int[] dx = { -1, 0, 1, -1, 1, -1, 0, 1 };
        int[] dz = { 1, 1, 1, 0, 0, -1, -1, -1 };

        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int nz = z + dz[i];

            // 맵 범위를 벗어나지 않는지 검사
            if (nx >= 0 && nx < MapSize_X && nz >= 0 && nz < MapSize_Z)
            {
                Tile neighbor = Tiles[nx, nz];
                // 장애물이 아닌 경우에만 이웃으로 추가
                if (!neighbor.Obstacle)
                {
                    neighbors.Add(neighbor);
                }
            }
        }

        return neighbors;
    }

    private float Heuristic(Tile a, Tile b)
    {
        return Mathf.Abs(a.Position.x - b.Position.x) + Mathf.Abs(a.Position.z - b.Position.z);
    }

    public bool ChangeUnitObject(Vector3 vector, GameObject unit)
    {
        Vector3Int ivector = Support.Vector.GetRoundVector(vector);

        if (ivector.x < 0 || ivector.x >= MapSize_X || ivector.z < 0 || ivector.z >= MapSize_Z)
            return false;

        Tiles[ivector.x, ivector.z].UnitObject = unit;
        return true;
    }
}

 

start -> end 까지 경로를 List에 저장홰서 반환