유니티 A* 길찾기 알고리즘 구현

 

 

유니티 A* 알고리즘

 

 

 

A* 알고리즘(A star algorithm) grid map 개념 및 구현

 

위 글을 바탕으로 구현되었으며 다른 점으로 장애물(벽)이 추가되었습니다.

 

장애물로 인하여 다음 조건이 추가되었습니다.

 

1. 장애물은 지나갈 수 없습니다.

2. 대각선으로 이동 시, 이동하고자 하는 노드 방향의 사이드에 장애물이 있다면 지나갈 수 없습니다.

 

대각 이동 시 장애물에 의해 이동불가 그림 및 잘못된 예

 

 

코드 전체

using System;
using System.Collections;
using System.Collections.Generic;
using TMPro;
using UnityEditor.Experimental.GraphView;
using UnityEngine;
using UnityEngine.UI;
using Random = UnityEngine.Random;


public class Node
{
    public bool isObstacle;
    public int x;
    public int y;
    public int f;
    public int g;
    public int h;

    public Node parent;

    public Node(int x, int y, int f, int g, int h)
	{
		this.x = x; 
        this.y = y;
		this.f = f;
		this.g = g;
		this.h = h;
	}
}

public class UI_Node
{
    public int x;
    public int y;
    public Image image;
    public TextMeshProUGUI f;
    public TextMeshProUGUI g;
    public TextMeshProUGUI h;
    public RectTransform arrow;
}

public class AStar : MonoBehaviour
{
    public int mapSizeX;
    public int mapSizeY;
    public int _startX;
    public int _startY;
    public int _destX;
    public int _destY;

    public GameObject nodeObj;
    public Transform dNodeParent;

    UI_Node[,] uiNodes;
    List<GameObject> uiClones = new List<GameObject>();

    Node[,] map;

    // Start is called before the first frame update
    void Start()
    {
        StartCoroutine(GO());
    }

    IEnumerator GO()
    {
        while (true)
        {
            DestoryClone();
			SetSizeAndPoint();
			SetMap();
			SetUI();
			yield return new WaitForSeconds(0.1f);

			yield return StartCoroutine(Navigate());
			yield return new WaitForSeconds(1f);
        }
    }

    void DestoryClone()
    {
        for (int i = 0; i < uiClones.Count; ++i)
        {
            Destroy(uiClones[i]);
            uiClones[i] = null;
        }
        uiClones.Clear();
    }

    void SetSizeAndPoint()
    {
        mapSizeX = Random.Range(8, 16);
		mapSizeY = Random.Range(8, 16);
        _startX = Random.Range(0, mapSizeX);
        _startY = Random.Range(0, mapSizeY);
        int iter = 0;
        while (iter < 100)
        {
            int seed = Random.Range(int.MinValue, int.MaxValue);
			Random.InitState(seed);
			int randX = Random.Range(0, mapSizeX);
			int randY = Random.Range(0, mapSizeY);
			if (randX == _startX && randY == _startY)
				continue;

			_destX = randX;
			_destY = randY;

            if (_destX - _startX < 3 || _destY - _startY < 3)
            {
                iter++;
                continue;
            }

            break;
        }
    }

    void SetMap()
    {
		map = new Node[mapSizeX, mapSizeY];
		uiNodes = new UI_Node[mapSizeX, mapSizeY];

		for (int i = 0; i < map.GetLength(0); i++)
		{
			for (int j = 0; j < map.GetLength(1); j++)
			{
				map[i, j] = new Node(i, j, 0, 0, 0);

				if (i == _startX && j == _startY || i == _destX && j == _destY)
					continue;

				int rand = Random.Range(0, 6);
				if (rand == 1)
				{
					map[i, j].isObstacle = true;
				}
			}
		}
	}

    void SetUI()
    {
        for (int i = 0; i < map.GetLength(0);i++)
        {
            for (int j = 0;j < map.GetLength(1);j++)
            {
                var g = Instantiate(nodeObj, dNodeParent);
                var a = g.GetComponent<RectTransform>();
                a.anchoredPosition3D = new Vector3(i * 100, j * 100, 0);

                uiNodes[i, j] = new UI_Node();
                uiNodes[i, j].x = i; 
                uiNodes[i, j].y = j;
                uiNodes[i, j].image = a.GetComponent<Image>();
                uiNodes[i, j].f = a.GetChild(0).GetComponent<TextMeshProUGUI>();
                uiNodes[i, j].g = a.GetChild(1).GetComponent<TextMeshProUGUI>();
                uiNodes[i, j].h = a.GetChild(2).GetComponent<TextMeshProUGUI>();
                uiNodes[i, j].arrow = a.GetChild(3).GetComponent<RectTransform>();
                uiNodes[i, j].arrow.gameObject.SetActive(false);

				if (map[i, j].isObstacle)
                {
                    uiNodes[i, j].image.color = Color.black;
                }

                uiClones.Add(g);

			}
        }

		uiNodes[_startX, _startY].image.color = Color.green;
		uiNodes[_destX, _destY].image.color = Color.blue;
	}

    enum Dir
    {
        Left, Right, Up, Down,
        LeftUp, RightUp, LeftDown, RightDown
    }

    IEnumerator Navigate()
    {
        List<Node> open = new List<Node>();
        List<Node> close = new List<Node>();

        Node parentNode = null;

        // 주변 탐색 순서
        Dir[] dir = new Dir[] { Dir.Left, Dir.Up, Dir.Right, Dir.Right, Dir.Down, Dir.Down, Dir.Left, Dir.Left };

        // 출발지로부터 인점한 노드 가져오기
        int startX = _startX;
        int startY = _startY;
        int destX = _destX;
        int destY = _destY;
        int x = startX;
        int y = startY;

        // 출발 및 부모노드 설정
        parentNode = map[startX, startY];
		parentNode.h = (Mathf.Abs(x - destX) + Mathf.Abs(y - destY)) * 10;
		parentNode.f = parentNode.g + parentNode.h;
		// UI 그리기
		uiNodes[x, y].f.text = parentNode.f.ToString();
		uiNodes[x, y].g.text = parentNode.g.ToString();
		uiNodes[x, y].h.text = parentNode.h.ToString();
		close.Add(parentNode);

        bool isDest = false;
        while (!isDest)
        {
            for (int i = 0; i < dir.Length; i++)
            {
                switch (dir[i])
                {
                    case Dir.Left:
                        x--;
                        break;
                    case Dir.Right:
                        x++;
                        break;
                    case Dir.Up:
                        y++;
                        break;
                    case Dir.Down:
                        y--;
                        break;
                }

                // 존재하지 않는 좌표인 경우 스킵
                if (!ExistMap(x, y))
                    continue;

				var node = map[x, y];

				// 장애물이 있다면 스킵
				if (map[x, y].isObstacle)
                    continue;

				// 대각방향일 때 장애물이 진행방향의 사방으로 존재한다면 스킵
				// 현재 노드가 부모로부터 어느쪽 대각선에 위치해있다면
				// 현재 노드에서 오른쪽, 아래를 확인해서 한 군데이상 장애물이 있다면 이동 불가
				Dir d = GetDir(node, parentNode);
                switch (d)
                {
                    case Dir.LeftUp:
                        if (ExistMap(parentNode.x, parentNode.y - 1))
                            if (map[parentNode.x, parentNode.y - 1].isObstacle)
                                continue;

                        if (ExistMap(parentNode.x + 1, parentNode.y))
                            if (map[parentNode.x + 1, parentNode.y].isObstacle)
                                continue;
                        break;
                    case Dir.RightUp:
                        if (ExistMap(parentNode.x - 1, parentNode.y))
                            if (map[parentNode.x - 1, parentNode.y].isObstacle)
                                continue;
                        if (ExistMap(parentNode.x, parentNode.y - 1))
                            if (map[parentNode.x, parentNode.y - 1].isObstacle)
                                continue;
                        break;
                    case Dir.LeftDown:
                        if (ExistMap(parentNode.x + 1, parentNode.y))
                            if (map[parentNode.x + 1, parentNode.y].isObstacle)
                                continue;
                        if (ExistMap(parentNode.x, parentNode.y + 1))
                            if (map[parentNode.x, parentNode.y + 1].isObstacle)
                                continue;
                        break;
                    case Dir.RightDown:
                        if (ExistMap(parentNode.x - 1, parentNode.y))
                            if (map[parentNode.x - 1, parentNode.y].isObstacle)
                                continue;
                        if (ExistMap(parentNode.x, parentNode.y + 1))
                            if (map[parentNode.x, parentNode.y + 1].isObstacle)
                                continue;
                        break;
                }

                // 닫힌 목록에 있다면 스킵
                var isClose = close.Find((n) => n.x == x && n.y == y);
                if (isClose != null)
                    continue;

                // 이미 열린 목록에 있다면 스킵
                var isOpen = open.Find((n) => n.x == x && n.y == y);
                if (isOpen != null)
                    continue;

                // 인접 노드들의 부모를 지정해주고 열린 목록에 추가
                node.parent = parentNode;
                open.Add(node);

                DrawArrow(node, parentNode);

                // f = g + h
                // g 출발노드에서 현재노드까지 거리 (대각 14, 가세 10)
                // h 현재노드에서 목표노드까지 거리 (가세 10만 판단)
                int dist = Mathf.Abs(x - startX) + Mathf.Abs(y - startY);
                if (dist == 2) // 대각선 이동이 가능한 경우
                {
                    //Debug.Log($"({x}, {y}) 대각선, 가로세로 이동 가능");
                    node.g = parentNode.g + 14;

                }
                else // 가로세로만 이동이 가능한 경우
                {
                    //Debug.Log($"({x}, {y}) 가로세로 이동 가능");
                    node.g = parentNode.g + 10;
                }

                node.h = (Mathf.Abs(x - destX) + Mathf.Abs(y - destY)) * 10;
                node.f = node.g + node.h;

                // UI 그리기
                uiNodes[x, y].f.text = node.f.ToString();
                uiNodes[x, y].g.text = node.g.ToString();
                uiNodes[x, y].h.text = node.h.ToString();

				// 목적지이므로
				if (node.h == 0)
				{
					isDest = true;
					yield return DrawFastPath(node);
					yield break;// return;
				}
			}

            // 목표까지 가장 빠르게 이동할 수 있는 노드 찾기
            int fast = int.MaxValue;
            int x1 = -1;
            int y1 = -1;
            for (int i = 0; i < open.Count; i++)
            {
                if (open[i].f < fast)
                {
                    fast = open[i].f;
                    x1 = open[i].x;
                    y1 = open[i].y;
                }
            }

            // 해당 노드를 부모노드로 지정하고 열린목록에서 제거하고 닫힌 목록에 추가
            var fastNode = open.Find((n) => n.x == x1 && n.y == y1);
            if (open.Count == 0)
            {
                // 벽으로 완전히 둘러싸인 경우 목적지에 도달할 수 없음
                Debug.Log("벽에 막혀 도착지에 도달할 수 없음");
                yield return new WaitForSeconds(3f);
                yield break;
            }
            parentNode = fastNode;
            close.Add(parentNode);
            open.RemoveAll((n) => n.x == x1 && n.y == y1);

            //Debug.Log($"현재 부모 노드 : {parentNode.x}, {parentNode.y}");

            x = x1;
            y = y1;

            uiNodes[x1, y1].image.color = Color.yellow;

            yield return new WaitForSeconds(0.1f);
        }
    }

    bool ExistMap(int x, int y)
    {
		if (x < 0 || x >= map.GetLength(0) || y < 0 || y >= map.GetLength(1))
		{
            return false;
		}
        return true;
	}

	Dir GetDir(Node node, Node parent)
    {
		int x = parent.x - node.x;
		int y = parent.y - node.y;

        if (x == -1 && y == 0) // 왼쪽
            return Dir.Left;
        else if (x == -1 && y == 1) // 왼쪽위대각
            return Dir.LeftUp;
        else if (x == 0 && y == 1) // 위
            return Dir.Up;
        else if (x == 1 && y == 1) // 오른쪽위대각
			return Dir.RightUp;
		else if (x == 1 && y == 0) // 오른쪽
			return Dir.Right;
		else if (x == 1 && y == -1) // 오른쪽아래대각
			return Dir.RightDown;
		else if (x == 0 && y == -1) // 아래
			return Dir.Down;
		else if (x == -1 && y == -1) // 왼쪽아래대각
			return Dir.LeftDown;

        return Dir.Left;
	}

    void DrawArrow(Node node, Node parent)
    {
        switch (GetDir(node, parent))
        {
            case Dir.Left:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -270f);
				break;
            case Dir.Right:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -90f);
				break;
            case Dir.Up:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, 0f);
				break;
            case Dir.Down:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -180f);
				break;
            case Dir.LeftUp:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -315f);
				break;
            case Dir.RightUp:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -45f);
				break;
            case Dir.LeftDown:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -225f);
				break;
            case Dir.RightDown:
				uiNodes[node.x, node.y].arrow.localRotation = Quaternion.Euler(0, 0, -135f);
				break;
        }

        uiNodes[node.x, node.y].arrow.gameObject.SetActive(true);
	}

    IEnumerator DrawFastPath(Node node)
    {
        if (node.parent == null) yield break;
        if (node.parent.x == _startX && node.parent.y == _startY) yield break;

        int x = node.parent.x;
        int y = node.parent.y;

        uiNodes[x, y].image.color = Color.red;

        yield return new WaitForSeconds(0.1f);

        yield return DrawFastPath(node.parent);
    }
}

 

 

씬 구성

씬

 

맵 사이즈 및 시작점과 도착점은 코드 내에서 랜덤값으로 변경됨.

 

Node UI 구성

화면은 UI Canvas를 이용하여 구현 됨.