[Toy/Unity] 타일맵 길찾기 (A*) - 대각선 포함

결과물. 저번 글과 크게 달라진 것은 없다.

대각선으로 가로질러 갈수 있게 하되,
가로지르는 경로에 장애물이 존재할 경우 이동하지 못하도록 했다.
아직 실제로 이동을 구현해보지는 않았지만 타일맵이기 때문에
장애물을 가로지르는 경로는 이상해 보일 것 같았다.
(충돌 문제도 있고..)

🔽 작성한 코드

public class Node : IComparable<Node>
{
    public int x, y;
    public int G, H;
    public int F => G + H;
    public Node parent;
    public bool isObstacle;

    public Node(bool _isObstacle, int _x, int _y) { isObstacle = _isObstacle; x = _x; y = _y; }

    public int CompareTo(Node other)
    {
        if (F == other.F)
            return H.CompareTo(other.H);
        return F.CompareTo(other.F);
    }
}

...

private void PathFinding()
{
    List<(int, int)> dir = new List<(int, int)> { (0, -1), (0, 1), (1, 0), (-1, 0),
                                                    (1, 1), (-1, 1), (-1, -1), (1, -1)};

    Node currNode;
    Node startNode = mapData[startPos.x - bottomLeft.x, startPos.y - bottomLeft.y];
    Node endNode = mapData[endPos.x - bottomLeft.x, endPos.y - bottomLeft.y];

    List<Node> waitingNodes = new List<Node>() { startNode };
    HashSet<Node> visitedNodes = new HashSet<Node>();

    while (waitingNodes.Count > 0)
    {
        waitingNodes.Sort();

        currNode = waitingNodes.First();
        waitingNodes.Remove(currNode);
        visitedNodes.Add(currNode);

        if (currNode == endNode)
        {
            // *** Gizmo 그리기 용 리스트 저장
            // Node node = endNode;
            // while (node != startNode)
            // {
            //     finalPaths.Add(node);
            //     node = node.parent;
            // }
            // finalPaths.Add(startNode);
            // finalPaths.Reverse();

            return;
        }

        for (int i = 0; i < dir.Count; ++i)
        {
            int nextX = currNode.x + dir[i].Item1;
            int nextY = currNode.y + dir[i].Item2;

            if (nextX < bottomLeft.x || nextX > topRight.x || nextY > topRight.y || nextY < bottomLeft.y) continue;
            [⭐]if (mapData[currNode.x - bottomLeft.x, nextY - bottomLeft.y].isObstacle
                || mapData[nextX - bottomLeft.x, currNode.y - bottomLeft.y].isObstacle)   continue;	
            if (mapData[nextX - bottomLeft.x, nextY - bottomLeft.y].isObstacle)     continue;
            if (visitedNodes.Contains(mapData[nextX - bottomLeft.x, nextY - bottomLeft.y])) continue;

            Node nextNode = mapData[nextX - bottomLeft.x, nextY - bottomLeft.y];
            int cost = (currNode.x - nextX == 0 || currNode.y - nextY == 0) ? 10 : 14;
            int moveCost = currNode.G + cost;

            if (moveCost < nextNode.G || waitingNodes.Contains(nextNode) == false)
            {
                nextNode.G = moveCost;
                nextNode.H = (Mathf.Abs(nextNode.x - endNode.x) + Mathf.Abs(nextNode.y - endNode.y)) * 10;
                nextNode.parent = currNode;

                waitingNodes.Add(nextNode);
            }
        }
    }
}

고라니님의 코드와 크게 다른것은 없고, 자료형이나 정렬 방식만 조금 수정했다.
⭐ 부분이 장애물 여부를 검사하는 부분이다.

---

🔽 여러 테스트 사진





당연하겠지만 못가는 경우는 그려지지 않는다.

📝 다음에 할 일

• 대각선 이동 구현
• 실제 캐릭터 이동
• 맵 정보 저장 개선