학원 수업 ) 길 찾기 알고리즘

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

[System.Serializable]
public class Node
{
    public bool isWall;
    public Node parentNode;
    public int x, y;
    public int g, h;
    
    public int f { get { return h + g; } }
	
    public Node(bool _isWall, int _x, int _y)
    {
        isWall = _isWall;
        x = _x;
        y = _y;
    }
}

public class GameManager : MonoBehaviour
{
    public GameObject startPos_ob, EndPos_ob, bottomLeft_ob, topRight_ob;

    [SerializeField]
    Vector2Int bottomLeft, topRight, startPos, endPos;

    public bool allowDiagonal = true;
    public bool dontCrossCorner = true;

    int sizeX, sizeY;
    public Node[,] nodeArray = new Node[0, 0];
    Node startNode, endNode, curNode;

    [SerializeField]
    List<Node> finalList;
    SimplePriorityQueue<Node> openList;
    HashSet<Node> closedList;

    void OnValidate()
    {
        SetPosition();
    }

    void SetPosition()
    {
        startPos = Vector2Int.FloorToInt(startPos_ob.transform.position);
        bottomLeft = Vector2Int.FloorToInt(bottomLeft_ob.transform.position);
        topRight = Vector2Int.FloorToInt(topRight_ob.transform.position);
        endPos = Vector2Int.FloorToInt(EndPos_ob.transform.position);
    }

    public void PathFinding()
    {
        SetPosition();
        sizeX = topRight.x - bottomLeft.x + 1;
        sizeY = topRight.y - bottomLeft.y + 1;

        nodeArray = new Node[sizeX, sizeY];

        for (int c = 0; c < sizeX; c++)
        {
            for (int r = 0; r < sizeY; r++)
            {
                RaycastHit2D hit = Physics2D.Raycast(new Vector3(c + bottomLeft.x, r + bottomLeft.y, 0), Vector3.zero, Mathf.Infinity, 1 << LayerMask.NameToLayer("Wall"));
                nodeArray[c, r] = new Node(hit.collider != null, c + bottomLeft.x, r + bottomLeft.y);
            }
        }

        startNode = nodeArray[startPos.x - bottomLeft.x, startPos.y - bottomLeft.y];
        endNode = nodeArray[endPos.x - bottomLeft.x, endPos.y - bottomLeft.y];

        openList = new SimplePriorityQueue<Node>();
        closedList = new HashSet<Node>();
        finalList = new List<Node>();

        openList.Enqueue(startNode, startNode.f);

        while (openList.Count > 0)
        {
            curNode = openList.Dequeue();
            closedList.Add(curNode);

            if (curNode == endNode)
            {
                BuildFinalPath();
                StartCoroutine(AiMove_co());
                return;
            }

            EvaluateNeighbours(curNode);
        }
    }

    void BuildFinalPath()
    {
        Node target = endNode;
        while (target != startNode)
        {
            finalList.Add(target);
            target = target.parentNode;
        }
        finalList.Add(startNode);
        finalList.Reverse();
    }

    void EvaluateNeighbours(Node currentNode)
    {
        int[] dx = { 1, -1, 0, 0, 1, -1, 1, -1 };
        int[] dy = { 0, 0, 1, -1, 1, 1, -1, -1 };

        for (int i = 0; i < (allowDiagonal ? 8 : 4); i++)
        {
            int newX = currentNode.x + dx[i];
            int newY = currentNode.y + dy[i];
            OpenList_Add(newX, newY, currentNode);
        }
    }

    void OpenList_Add(int x, int y, Node currentNode)
    {
        if (IsValidNode(x, y))
        {
            Node neighbourNode = nodeArray[x - bottomLeft.x, y - bottomLeft.y];
            int moveCost = currentNode.g + ((currentNode.x == x || currentNode.y == y) ? 10 : 14);

            if (moveCost < neighbourNode.g || !openList.Contains(neighbourNode))
            {
                neighbourNode.g = moveCost;
                neighbourNode.h = (Mathf.Abs(neighbourNode.x - endNode.x) + Mathf.Abs(neighbourNode.y - endNode.y)) * 10;
                neighbourNode.parentNode = currentNode;

                if (!openList.Contains(neighbourNode))
                {
                    openList.Enqueue(neighbourNode, neighbourNode.f);
                }
            }
        }
    }

    bool IsValidNode(int x, int y)
    {
        if (x < bottomLeft.x || x > topRight.x || y < bottomLeft.y || y > topRight.y)
            return false;

        Node node = nodeArray[x - bottomLeft.x, y - bottomLeft.y];
        if (node.isWall || closedList.Contains(node))
            return false;

        if (allowDiagonal && dontCrossCorner)
        {
            if (nodeArray[curNode.x - bottomLeft.x, y - bottomLeft.y].isWall &&
                nodeArray[x - bottomLeft.x, curNode.y - bottomLeft.y].isWall)
            {
                return false;
            }
        }
        else if (dontCrossCorner)
        {
            if (nodeArray[curNode.x - bottomLeft.x, y - bottomLeft.y].isWall ||
                nodeArray[x - bottomLeft.x, curNode.y - bottomLeft.y].isWall)
            {
                return false;
            }
        }

        return true;
    }

    private void OnDrawGizmos()
    {
        if (finalList != null)
        {
            Gizmos.color = Color.red;
            for (int i = 0; i < finalList.Count - 1; i++)
            {
                Gizmos.DrawLine(new Vector2(finalList[i].x, finalList[i].y), new Vector2(finalList[i + 1].x, finalList[i + 1].y));
            }
        }
    }

    [SerializeField]
    float speed = 1;

    IEnumerator AiMove_co()
    {
        Transform player = GameObject.Find("Player").transform;
        foreach (var node in finalList)
        {
            player.position = new Vector3(node.x, node.y, 0);
            yield return new WaitForSecondsRealtime(speed);
        }
    }
}

 

 

1. Priority_Queue 라이브러리 설치
Priority_Queue는 C#의 우선순위 큐 라이브러리입니다. 이를 Unity 프로젝트에 추가하려면 다음 단계를 따르세요:

NuGet Package: 가장 간단한 방법은 NuGet 패키지를 사용하는 것입니다. 하지만 Unity는 기본적으로 NuGet을 지원하지 않으므로, 다른 방법을 사용해야 합니다.
수동 설치: GitHub에서 소스 코드를 직접 다운로드하여 Unity 프로젝트에 추가할 수 있습니다.
수동 설치 방법
Priority_Queue GitHub 저장소에 접속합니다.
Priority Queue 소스 코드를 다운로드합니다.
다운로드한 파일에서 Priority_Queue 폴더를 찾아 복사합니다.
Unity 프로젝트의 Assets 폴더 안에 Plugins 폴더를 생성하고, 그 안에 Priority_Queue 폴더를 붙여 넣습니다.

 

 

 

 

가장 기본적인 길찾기를 위해

유니티의 타일맵을 사용하여 맵을 만든다.

 

벽이 없는 타일맵을 만들어둔다.

 

왼쪽 아래의 좌표가 0, 0 이 될 것이다.

오른쪽 위의 좌표가 타일 맵의 끝이며 노드 이차원 배열의 크기 (+1) 가 될 것이다.

 

중요한 것은 벽이 될  타일 맵의 설정이다.

 

 

 

 

이 위에 지나갈 수 없는 타일맵을 겹쳐둔다.

 

 

 

여기에 Tilemap Collider 2D 컴포넌트를 추가하면

 

Collider가 추가되어 Raycast2D 로 검출할 수 있게 된다.

 

 

추가적으로 태그나 레이어 설정을 하면 벽 타일을 검출하는 데 도움이 될 것이다.

 

 

 

---

코드 해부

// 나중에...

 

 

 

---

 

1. 데이터 구조 개선
효율적인 데이터 구조를 사용하기 위해 openList의 경우, 최소 힙(Min-Heap) 또는 우선순위 큐를 사용하여 성능을 크게 향상시킬 수 있습니다.

2. 코드 중복 제거
OpenList_Add 함수 내부에서 여러 번 사용되는 연산과 조건문을 함수로 분리하여 중복 코드를 제거할 수 있습니다.

3. 함수 분리 및 구조 개선
큰 함수들을 작게 나누어 코드의 가독성을 높이고, 유지보수가 용이하도록 합니다.

 

 

 

 

 

 

참고자료

 

2D 타일맵을 위한 A* 길찾기 알고리즘 (youtube.com)

 

 

 

 

그 밖의 길찾기 알고리즘

 

DFS (깊이 우선 탐색 알고리즘)

BFS (범위 우선 탐색 알고리즘)

JPS (점프 포인트 탐색 알고리즘)

Dijkstra (최단 경로 탐색 알고리즘)

...