[C#] 비선형 자료구조 - Graph와 길찾기 실습하기(수정필요)

[확인문제]

 

1. Graph가 무엇인지 알고 있나요?

Graph는 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 구성된 자료구조이다.

그래프는 여러 형태로 나타날 수 있으며, 노드와 간선의 개수, 방향성, 가중치 여부 등에 따라 분류된다.

 

2. Tree는 Graph인가요? Graph는 Tree인가요?

Tree는 Graph의 일종으로, 트리는 사이클이 없는 연결된 그래프이다.

반대로 모든 Graph가 Tree인 것은 아니다. Graph는 사이클이 있을 수도 있고, 연결되지 않을 수도 있다.

 

3. NavMesh가 길찾기를 위해 사용하는 알고리즘은 무엇인가요?

NavMesh는 일반적으로 A* (A-star) 알고리즘을 사용합니다. A* 알고리즘은 휴리스틱을 사용하여 최단 경로를 효율적으로 찾을 수 있는 알고리즘이다.

 

 

 

[설명문제]

 

1. 길찾기 알고리즘에 대해 알고 있는 것이 있나요?

• BFS (Breadth-First Search)
• DFS (Depth-First Search)
• Dijkstra's Algorithm(다익스트라자 알고리즘)
• A* (A-star) 알고리즘

 

2. 각 길찾기 알고리즘의 차이점은 무엇인가요?

 

• BFS: 너비 우선 탐색으로, 최단 경로를 보장하지만, 모든 경로를 탐색해야 하므로 시간이 오래 걸릴 수 있다.
• DFS: 깊이 우선 탐색으로, 특정 경로를 깊게 탐색하지만, 최단 경로를 보장하지 않는다.
• Dijkstra's Algorithm: 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로, 모든 노드를 방문하여 최단 경로를 찾는다.
• A*: Dijkstra's 알고리즘의 확장으로, 휴리스틱을 사용하여 최단 경로를 더 효율적으로 찾는다.

 

 

3. A* 알고리즘에 대해 설명해주세요.

 

경로 탐색 알고리즘으로, 시작 노드에서 목표 노드까지의 최단 경로를 찾기 위해 휴리스틱 함수를 사용한다. 휴리스틱 함수는 현재 노드에서 목표 노드까지의 추정 비용을 계산한다.

 

* 휴리스틱 함수

휴리스틱 함수는 주어진 문제를 해결하는 데 있어 최적의 해결책을 찾기 위한 지침을 제공하는 경험적 함수로 이 함수는 목표 상태에 도달하기 위해 남은 비용을 추정하는 데 사용된다. 휴리스틱 함수는 문제 해결의 효율성을 높이기 위해 설계된 것으로, 일반적으로 복잡한 문제를 해결할 때 단순한 규칙이나 경험을 기반으로 한다.

 

A* 알고리즘은 G와 H 값을 사용한다:

 - G: 시작 노드에서 현재 노드까지의 실제 비용

 - H: 현재 노드에서 목표 노드까지의 추정 비용 (휴리스틱)

 - F: G와 H의 합으로, F 값이 가장 낮은 노드를 우선적으로 탐색

 

4. 해당 알고리즘들을 프로젝트에 적용해본 경험이 있나요?

이전 프로젝트에서 NavMesh를사용하여 몬스터의 경로 탐색을 구현한 경험이 있다. 미로 문제를 해결하거나, NPC가 장애물을 피해 목표 지점까지 이동하는 기능을 구현할 때 A* 알고리즘을 사용했다.

 

[실습문제]

 

💡 [A* 알고리즘 직접 구현해보기]

 

A* 알고리즘을 이용하여 플레이어가 현재 위치에서 목표 위치까지의 최단 경로를 찾고 출력하는 코드를 작성하세요.

구현사항

• PathFinding 메서드: A* 알고리즘 구현.
• 입력 매개 변수:
  • Board board - 맵 객체
  • Block start - 시작 블록
  • Block dest - 목표 블록
• 반환값: Block - 시작 블록을 반환하여 경로를 나타냄. 경로를 찾지 못하면 null을 반환.
• 초기 조건 확인 및 변수 초기화:
  • 맵에서 시작 블록과 목표 블록의 존재 여부를 확인합니다.
  • 모든 블록의 상태를 초기화합니다.
  • 대기 목록과 검사 완료 목록을 초기화합니다.
  • 현재 블록을 시작 블록으로 설정합니다.
• 경로 탐색 루프:
  • 현재 블록의 주변 블록을 가져옵니다.
  • 주변 블록을 대기 목록에 추가합니다.
  • 현재 블록을 검사 완료 목록에 추가하고, 대기 목록에서 제거합니다.
  • 만약 주변에 이동 가능한 블록이 없다면 경로 탐색을 중단합니다.
  • 주변 블록들의 G, H 값을 계산합니다.
  • 다음 검사할 블록을 선택합니다.
  • 만약 다음 검사할 블록이 없다면, 대기 목록에서 F 값이 가장 낮은 블록을 선택합니다.
  • 목표 블록에 도착한 경우 탐색을 종료합니다.
• 경로 역추적:
  • 탐색이 끝나면 목표 블록에서 시작 블록으로 경로를 역추적합니다.
  • 경로를 설정하여 반환합니다.

주요 클래스와 메서드

• AStar 클래스:
  • GetPriorityBlock
    • 대기 목록에 있는 블록들 중에서 F 값(총 비용)이 가장 낮은 블록을 선택하여 반환합니다.
    • F 값이 낮을수록 해당 블록이 목적지에 가까운 경로에 위치해 있음을 의미합니다.
  • GetNextBlock
    • 현재 블록의 주변 블록들 중에서 검사되지 않은 블록 중 H 값이 가장 낮은 블록을 선택하여 반환합니다.
  • CalcRating
    • 주변 블록들의 G, H, F 값을 계산하고 설정합니다. G 값은 시작점부터 현재 블록까지의 비용을 나타내며, H 값은 현재 블록에서 목표 블록까지의 휴리스틱 비용을 나타냅니다. F 값은 G와 H의 합으로, 경로 탐색의 우선순위를 결정하는 데 사용됩니다.
• Board 클래스:
  • CheckClear 메서드: 블록 상태 초기화.
  • Exists 메서드: 블록 존재 여부 확인.
  • GetNode 메서드: 특정 좌표의 블록 반환.
  • GetAroundBlocks 메서드: 주변 블록 반환.
• Block 클래스:
  • SetPrice 메서드: G와 H 값 설정.
  • Clear 메서드: 블록 상태 초기화.
  • Equals 메서드: 블록 좌표 비교.

public class Program
{
    static void Main(string[] args)
    {
        char[,] map = {
            {'□', '□', '□', '□', '□'},
            {'□', '■', '■', '□', '□'},
            {'□', '□', '□', '□', '□'},
            {'□', '□', '■', '■', '□'},
            {'□', '□', '□', '□', '□'}
        };

        for (int i = 0; i < map.GetLength(0); i++)
        {
            for (int j = 0; j < map.GetLength(1); j++)
                Console.Write(map[i, j]);
            Console.WriteLine();
        }

        Console.WriteLine("현재 플레이어 위치를 입력하세요 (a, b):");
        int a = int.Parse(Console.ReadLine());
        int b = int.Parse(Console.ReadLine());

        Console.WriteLine("목표 위치를 입력하세요 (x, y):");
        int x = int.Parse(Console.ReadLine());
        int y = int.Parse(Console.ReadLine());

        Board board = new Board(map);
        Block start = board.GetNode(a, b);
        Block dest = board.GetNode(x, y);

        Block path = AStar.PathFinding(board, start, dest);

        if (path != null)
        {
            Console.WriteLine("최단 경로:");
            while (path != null)
            {
                Console.Write($"({path.x}, {path.y}) ");
                path = path.next;
            }
        }
        else
        {
            Console.WriteLine("경로를 찾을 수 없습니다.");
        }
    }
}

public static class AStar
{
    public static Block PathFinding(Board board, Block start, Block dest)
    {
        // TODO : A* 알고리즘 직접 구현
        
    }

    private static Block GetPriorityBlock(List<Block> waittingBlocks)
    {
        Block block = null;
        var enumerator = waittingBlocks.GetEnumerator();
        while (enumerator.MoveNext())
        {
            var current = enumerator.Current;
            if (block == null || block.F > current.F)
            {
                block = current;
            }
        }

        return block;
    }

    private static Block GetNextBlock(List<Block> arounds, Block current)
    {
        Block minValueBlock = null;
        for (int i = 0; i < arounds.Count; i++)
        {
            Block next = arounds[i];
            if (!next.check)
            {
                if (minValueBlock == null)
                {
                    minValueBlock = next;
                }
                else if (minValueBlock.H > next.H)
                {
                    minValueBlock = next;
                }
            }
        }
        return minValueBlock;
    }

    private static void CalcRating(List<Block> arounds, Block start, Block current, Block dest)
    {
        if (arounds != null)
        {
            for (int i = 0; i < arounds.Count; i++)
            {
                var block = arounds[i];
                bool isDiagonalBlock = Math.Abs(block.x - current.x) == 1 && Math.Abs(block.y - current.y) == 1;
                int priceFromDest = (Math.Abs(dest.x - block.x) + Math.Abs(dest.y - block.y)) * 10;
                if (block.prev == null)
                    block.prev = current;
                block.SetPrice(current.G + (isDiagonalBlock ? 14 : 10), priceFromDest);
            }
        }
    }
}

public class Board
{
    public Block[,] blocks;

    public Board(char[,] map)
    {
        int width = map.GetLength(0);
        int height = map.GetLength(1);
        blocks = new Block[width, height];
        for (int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                blocks[i, j] = new Block(i, j, map[i, j] == '■');
            }
        }
    }

    public void CheckClear()
    {
        foreach (Block block in blocks)
        {
            block.Clear();
        }
    }

    public bool Exists(Block block)
    {
        return Exists(block.x, block.y);
    }

    public bool Exists(int x, int y)
    {
        return x >= 0 && x < blocks.GetLength(0) && y >= 0 && y < blocks.GetLength(1);
    }

    public Block GetNode(int x, int y)
    {
        return blocks[x, y];
    }

    public List<Block> GetAroundBlocks(Block target)
    {
        List<Block> arounds = new List<Block>();
        if (Exists(target.x - 1, target.y - 1))
        {
            Block block = blocks[target.x - 1, target.y - 1];
            arounds.Add(block);
        }
        if (Exists(target.x, target.y - 1))
        {
            Block block = blocks[target.x, target.y - 1];
            arounds.Add(block);
        }
        if (Exists(target.x + 1, target.y - 1))
        {
            Block block = blocks[target.x + 1, target.y - 1];
            arounds.Add(block);
        }

        if (Exists(target.x - 1, target.y))
        {
            Block block = blocks[target.x - 1, target.y];
            arounds.Add(block);
        }
        if (Exists(target.x + 1, target.y))
        {
            Block block = blocks[target.x + 1, target.y];
            arounds.Add(block);
        }

        if (Exists(target.x - 1, target.y + 1))
        {
            Block block = blocks[target.x - 1, target.y + 1];
            arounds.Add(block);
        }
        if (Exists(target.x, target.y + 1))
        {
            Block block = blocks[target.x, target.y + 1];
            arounds.Add(block);
        }
        if (Exists(target.x + 1, target.y + 1))
        {
            Block block = blocks[target.x + 1, target.y + 1];
            arounds.Add(block);
        }

        for (int i = arounds.Count - 1; i >= 0; i--)
        {
            Block block = arounds[i];
            bool isDiagonalBlock = Math.Abs(block.x - target.x) == 1 && Math.Abs(block.y - target.y) == 1;
            if (isDiagonalBlock)
            {
                Block blockX = arounds.Find(b => b.x == block.x && b.y == target.y);
                if (blockX != null && blockX.wall)
                    arounds.Remove(block);

                Block blockY = arounds.Find(b => b.x == target.x && b.y == block.y);
                if (blockY != null && blockY.wall)
                    arounds.Remove(block);
            }
        }

        arounds.RemoveAll(b => b.wall);

        return arounds;
    }
}

public class Block
{
    public int x, y;
    public bool wall;

    public int F => G + H;
    public int G { get; private set; } = 0;
    public int H { get; private set; } = 0;
    public bool check = false;
    public Block prev = null;
    public Block next = null;

    public Block(int x, int y, bool wall = false)
    {
        this.x = x;
        this.y = y;
        this.wall = wall;
    }

    public void SetPrice(int g, int h)
    {
        this.G = g;
        this.H = h;
    }

    public void Clear()
    {
        check = false;
        G = 0;
        H = 0;
        prev = null;
        next = null;
    }

    public override bool Equals(object obj)
    {
        if (obj is Block other)
        {
            return x == other.x && y == other.y;
        }
        return false;
    }
}