[멋쟁이사자처럼 부트캠프 TIL] 유니티 게임 스쿨 3기 16일차

알고리즘

알고리즘은 프로그래밍에서 문제를 해결하기 위한 단계적인 절차나 방법을 의미한다.

 

알고리즘의 주요 특징

• 입력: 알고리즘은 하나 이상의 입력을 받는다.
• 출력: 알고리즘은 하나 이상의 결과를 생성한다.
• 명확성: 각 단계는 모호하지 않고 명확해야 한다.
• 유한성: 알고리즘은 유한한 수의 단계 후에 반드시 종료되어야 한다.
• 효율성: 알고리즘은 가능한 한 효율적으로 설계되어야 한다.

 

알고리즘의 중요성

프로그래밍에서 알고리즘은 매우 중요한 역할을 한다.

효율적인 알고리즘은 프로그램의 성능을 크게 향상시키고, 복잡한 문제를 해결하는 데 필수적이다. 

 

알고리즘의 종류

• 정렬 알고리즘: 버블 정렬, 퀵 정렬, 병합 정렬 등
• 검색 알고리즘: 선형 검색, 이진 검색 등
• 그래프 알고리즘: 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘 등
• 동적 프로그래밍: 최적화 문제를 해결하는 데 사용되는 기법
• 분할 정복 알고리즘: 문제를 작은 부분으로 나누어 해결하는 방식
• 그리디 알고리즘: 각 단계에서 최적의 선택을 하는 방식

 

 

---

 

정렬 알고리즘

버블 정렬(Bubble Sort)

인접한 두 원소를 비교하여 정렬하는 알고리즘

public void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                //swap
                (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
            }
        }
    }
}

시간복잡도는 $O(N^2)$이다.

 

퀵 정렬(Quick Sort)

대표적인 정렬 알고리즘이다.

최악의 경우 $O(N^2)$의 시간 복잡도를 갖지만, 이는 확률이 매우 낮다.

평균적으로 $O(NlogN)$의 시간 복잡도를 갖는다.

public void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

private int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }

    (arr[high], arr[i + 1]) = (arr[i + 1], arr[high]);

    return i + 1;
}

Partition함수는 pivot을 기준으로 작은 수와 큰 수를 구분하는 작업이다.

구분하는 작업이 끝나면 두 그룹으로 나눠 재귀적으로 정렬을 실행한다.

 

 

---

A*  알고리즘

A* 알고리즘은 최단 경로를 찾는 데 사용되는 그래프 탐색 알고리즘이다.

A* 알고리즘의 핵심은 휴리스틱 함수를 사용하여 최적의 경로를 찾는 것이다.

휴리스틱이란 '경험에 기반한 추측'을 의미하며, A* 알고리즘에서는 다음과 같은 휴리스틱 함수를 사용한다.

f(n) = g(n) + h(n)

• g(n): 시작 노드에서 현재 노드까지의 실제 비용
• h(n): 현재 노드에서 목표 노드까지의 추정 비용 (휴리스틱)
• f(n): 총 예상 비용

 

일반적으로 사용되는 휴리스틱 함수들

• 맨해튼 거리(Manhattan Distance): 격자 기반 맵에서 수평과 수직 이동만 가능할 때 사용 $h(n) = |x1 - x2| + |y1 - y2|$
• 유클리드 거리(Euclidean Distance): 모든 방향으로 이동이 가능할 때 사용 $h(n) = \sqrt{(x1 - x2)² + (y1 - y2)²}$
• 대각선 거리(Diagonal Distance): 8방향 이동이 가능한 격자 맵에서 사용 $h(n) = max(|x1 - x2|, |y1 - y2|)$

 

휴리스틱 함수 선택 시 고려사항

• 허용성(Admissible): 실제 비용을 절대 과대 추정하지 않아야 함
• 일관성(Consistent): 인접한 노드 간의 추정 비용 차이가 실제 이동 비용보다 크지 않아야 함
• 계산 효율성: 빠르게 계산될 수 있어야 함

적절한 휴리스틱 함수를 선택하면 A* 알고리즘의 성능을 크게 향상시킬 수 있다.

휴리스틱 값이 0이면 다익스트라 알고리즘과 동일하게 작동하며, 값이 커질수록 목표 지점을 향한 탐색이 더 직접적이 된다.

 

A*를 이용한 길 찾기

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

public class Player : MonoBehaviour
{
    private Tile targetTile;
    private Tile currentTile;

    [SerializeField] private Vector2Int gridSize = new Vector2Int(10, 10);
    [SerializeField] private float nodeSize = 1f;
    [SerializeField] private bool allowDiagonalMovement = true;
    [Header("Grid Visualization")]
    [SerializeField] private List<Color> gridColors = new List<Color>();
    [SerializeField] private Tile TilePrefab;

    private List<Tile> currentPath;

    private List<int> dy = new List<int>{ -1, 0, 1, 0, -1, 1, 1, -1 };
    private List<int> dx = new List<int>{ 0, 1, 0, -1, 1, 1, -1, -1 };
    
    private Tile[,] grid;

    // 직선 이동과 대각선 이동의 비용
    private const int MOVE_STRAIGHT_COST = 10;
    private const int MOVE_DIAGONAL_COST = 14;
    bool bMoveEnd;

    private void Awake()
    {
        CreateGrid();
    }

    private void CreateGrid()
    {
        grid = new Tile[gridSize.x, gridSize.y];
        for (int y = 0; y < gridSize.x; y++)
        {
            for (int x = 0; x < gridSize.y; x++)
            {
                Vector3 worldPosition = new Vector3(x * nodeSize + nodeSize * 0.5f, 0, y * nodeSize + nodeSize * 0.5f);
                grid[y, x] = Instantiate(TilePrefab, worldPosition, TilePrefab.transform.rotation);

                int colorIdx = (y % 2 + x % 2) % 2;
                grid[y, x].SetOriginColor(gridColors[colorIdx]);
                grid[y, x].gridY = y;
                grid[y, x].gridX = x;
            }
        }

        currentTile = grid[0, 0];
        transform.position = grid[0, 0].transform.position;
    }

    void Update()
    {
        if (Input.GetMouseButtonDown(1))
        {
            StopAllCoroutines();
            transform.position = currentTile.transform.position;
            foreach (var tile in grid)
            {
                tile.ResetColor();
            }

            var underMouseTile = GetTileUnderMouse();
            FindPath(underMouseTile);
        }
        else if (Input.GetMouseButtonDown(0))
        {
            //Create Obstacle
            var underMouseTile = GetTileUnderMouse();
            if (underMouseTile != null)
            {
                underMouseTile.Disable();
                currentPath = null;
            }
            
            FindPath(targetTile);
        }
    }

    Tile GetTileUnderMouse()
    {
        var ray = Camera.main.ScreenPointToRay(Input.mousePosition);                    
        RaycastHit RayHit;
            
        if (Physics.Raycast(ray, out RayHit))
        {
            if (RayHit.transform.gameObject.GetComponent<Tile>())
            {
                return RayHit.transform.gameObject.GetComponent<Tile>();
            }
        }

        return null;
    }

    private void ResetAllTile()
    {
        foreach (var tile in grid)
        {
            tile.ResetColor();
        }
    }

    private void FindPath(Tile target)
    {
        if (target == null) return;
        
        //Set Target Tile
        targetTile = target;
        ResetAllTile();
        targetTile.SetColor(Color.red);
        
        //Find Tiles
        var path = FindRoute();
        if (path == null)
        {
            targetTile.ResetColor();
            Debug.Log("Can not Reach");
            return;
        }

        currentPath = path;
        
        foreach (var tile in path)
        {
            if(tile == targetTile) continue;
            tile.SetColor(Color.green);
        }

        StartCoroutine(Move());
    }
    
    private List<Tile> FindRoute()
    {
        foreach (var tile in grid)
        {
            tile.parent = null;
            tile.gCost = gridSize.y * gridSize.x * MOVE_DIAGONAL_COST;
            tile.hCost = gridSize.y * gridSize.x * MOVE_DIAGONAL_COST;
        }

        currentTile.gCost = 0;
        currentTile.hCost = 0;

        if (currentTile == targetTile) return null;
        if (currentTile == null || targetTile == null) return null;

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

        SortedSet<Tile> openSet = new SortedSet<Tile>(new TileComparer());
        openSet.Add(currentTile);
        
        while (openSet.Count > 0)
        {
            Tile tile = openSet.First();
            openSet.Remove(tile);
            closedSet.Add(tile);

            if (tile == targetTile)
            {
                return Retrace(tile);
            }

            foreach (Tile neighbor in GetNeighbors(tile))
            {
                if (closedSet.Contains(neighbor)) continue;
                if (!neighbor.bCanWalk) continue;

                int newMovementCostToNeighbor = tile.gCost + GetDistance(tile, neighbor);
                if (newMovementCostToNeighbor < neighbor.gCost && !openSet.Contains(neighbor))
                {
                    neighbor.gCost = newMovementCostToNeighbor;
                    neighbor.hCost = GetDistance(neighbor, targetTile);
                    neighbor.parent = tile;

                    openSet.Add(neighbor);
                }
            }
        }

        return null;
    }

    private List<Tile> Retrace(Tile tile)
    {
        var result = new List<Tile>();

        while (tile.parent != null)
        {
            result.Add(tile);
            tile = tile.parent;
        }

        result.Reverse();
        return result;
    }

    private int GetDistance(Tile tileA, Tile tileB)
    {
        int distX = Mathf.Abs(tileA.gridX - tileB.gridX);
        int distY = Mathf.Abs(tileA.gridY - tileB.gridY);

        if (!allowDiagonalMovement)
        {
            return MOVE_STRAIGHT_COST * (distX + distY);
        }

        int diagonal = Mathf.Min(distX, distY);
        int straight = Mathf.Abs(distX - distY);
        return MOVE_DIAGONAL_COST * diagonal + MOVE_STRAIGHT_COST * straight;

    }

    private List<Tile> GetNeighbors(Tile tile)
    {
        var neighbors = new List<Tile>();
        int loop = allowDiagonalMovement ? 8 : 4;

        for (int i = 0; i < loop; i++)
        {
            int newY = tile.gridY + dy[i];
            int newX = tile.gridX + dx[i];

            if (newY < 0 || newY >= gridSize.y || newX < 0 || newX >= gridSize.x) continue;
            neighbors.Add(grid[newY, newX]);
        }

        return neighbors;
    }
    
    private IEnumerator Move()
    {
        if(currentPath == null) yield break;

        foreach (var tile in currentPath)
        {
            StartCoroutine(MoveToTile(tile));
            yield return new WaitUntil(() =>
            {
                return bMoveEnd;
            });
        }

        foreach (var tile in currentPath)
        {
            tile.ResetColor();
        }

        currentPath = null;
    }

    private IEnumerator MoveToTile(Tile tile)
    {
        bMoveEnd = false;
        currentTile = tile;

        float time = 0f;
        float duration = 0.5f;
        while (time <= duration)
        {
            transform.position = Vector3.Lerp(transform.position, tile.transform.position, time/duration);

            time += Time.deltaTime;
            yield return null;
        }

        bMoveEnd = true;
        transform.position = tile.transform.position;
    }

}


public class TileComparer : IComparer<Tile>
{
    public int Compare(Tile x, Tile y)
    {
        if (x == null || y == null) throw new ArgumentNullException();

        // fCost 비교
        int fCostComparison = x.fCost.CompareTo(y.fCost);
        if (fCostComparison != 0) return fCostComparison;

        // hCost 비교
        int hCostComparison = x.hCost.CompareTo(y.hCost);
        if (hCostComparison != 0) return hCostComparison;

        // ID 비교 (마지막 우선순위)
        return x.GetInstanceID().CompareTo(y.GetInstanceID());
    }
}

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

public class Tile : MonoBehaviour
{
    private Material mat;
    public int gridX;
    public int gridY;
    public int gCost;
    public int hCost;
    public int fCost => gCost + hCost;
    public Tile parent;
    public bool bCanWalk = true;
    private Color originColor;
    [SerializeField] private Color obstacleColor = new Color(0f, 0f, 0f, 0.8f);

    private void Awake()
    {
        mat = gameObject.GetComponent<Renderer>().material;
    }

    public void SetOriginColor(Color newColor)
    {
        originColor = newColor;
        SetColor(originColor);
    }
    
    public void SetColor(Color newColor)
    {
        mat.SetColor("_Color", newColor);
    }

    public void ResetColor()
    {
        if(!bCanWalk) SetColor(obstacleColor);
        else SetColor(originColor);
    }

    public void Disable()
    {
        bCanWalk = false;
        ResetColor();
    }
}