Grid System (3) - A* Pathfinding

2020/05/22 - [Unity & C#] - Grid System (2) - 미로 만들기 (Maze Algorithm)

지난 번 만든 미로에서 길을 찾는 A* 알고리즘을 구현해보자.

 

 

A* 알고리즘

시작점에서 끝점까지 최단 경로를 찾는 알고리즘이다.

끝점까지 도달하는데 각 노드의 세 값 F, G, H를 계산하여 다음 경로를 정한다.

G = 시작점에서 현재 노드까지 도달하는데 발생한 비용

H = 현재 노드에서 끝점까지 필요한 비용

F = G + H

G, F, H

 

2차원 Grid 형식의 맵에서 G, H, F 값을 계산할 때 수직, 수평 이동은 1.0의 비용이 발생하고,

대각선 이동은 1.4의 비용이 발생한다. (피타고라스의 정리에 의해 sqrt(2)값이 아닌가 싶다)

지난 번 생성한 미로에서는 대각선 이동이 없으므로, 노드 간 이동에 발생하는 비용은 모두 1로 계산한다.

 

 

 

 

구현할 알고리즘을 간단히 정리해보자.

1) 현재 노드에서 현재 갈 수 있는 모든 노드에 현재 노드를 이전 노드로 기록하고, open list에 담는다.

2) oepn list에서 가장 F값이 낮은 노드로 이동한다.

3) 1), 2)를 반복하다 현재 노드가 끝점이 될 경우 탐색을 중지하고, 경로를 반환하면 A*의 최적해가 된다.

 

 

 

 

우선 미로에서 Start Node와 End Node를 정하고, Start Node를 current node로 잡는다.

current node를 open list에 담아는다.

private void Start()
{
	...
	
	_startNode = _tiles[0, 3];
	_endNode = _tiles[0, 0];
	_openNodes.Add(_startNode);
}

 

 

 

 

 

current node는 open list에서 제거하고, closed list에 추가한다.

current node에서 갈 수 있는 모든 node를 찾아 current node를 각 노드의 previous node로 저장하고, open list에 담는다.

가장 낮은 F값이 있는 node로 이동하고, 그 node를 current node로 잡고 반복한다.

private void FindPath()
{   
    var currentNode = GetLowestFCostNode();
    
    // 탐색 중지
    if (currentNode == _endNode)
    {
        ShowPath();
        return;
    }

    // open list에서 제거하고, closed list에 추가한다.
    _openNodes.Remove(currentNode);
    _visitedNodes.Add(currentNode);
        
    // 방문 가능한 주변 노드를 open list에 다는다.
    foreach (var next in GetNeighbours(currentNode))
    {
        GetCost(currentNode, next);
        
        // 이전 노드를 기록한다.
        next.previousNode = currentNode;
        _openNodes.Add(next);
    }
}


// F값이 가장 낮은 노드를 반환
private Tile GetLowestFCostNode()
{
    var lowestNode = _openNodes.First();

    foreach (var node in _openNodes)
    {
        if (lowestNode.f > node.f)
        {
            lowestNode = node;
        }
    }

    return lowestNode;
}

private void Update()
{
    if (Input.GetKeyDown(KeyCode.F))
    {
        FindPath();
    }
}

 

 

 

 

 

끝점을 찾았으면 탐색을 중지하고, 저장해뒀던 previous node를 타고 start node까지 돌아간다.

private void ShowPath()
{
    var currentNode = _endNode;
    
    // startNode로 돌아올 때까지 반복한다.
    while (currentNode != _startNode)
    {
    	// 기록했던 이전 노드를 타고 돌아간다.
        var previousNode = currentNode.previousNode;
        previousNode.FillColor(1);

        currentNode = previousNode;
    }
}

 

A* Path Finding

 

 

 

*주의할 점

- 가장 낮은 F값을 찾을 때 현재 노드에서 이동 가능한 노드 중에서 찾는 것이 아니라, 이전 노드들에서 추가했고 아직 방문하지 않은 모든 open list의 노드 중에서 찾아야한다. 

- end node에 도착했을 때 backtracking을 하기 위해 previous node를 기록해야 한다.

 

 

 

<참고>

code monkey - youtu.be/alU04hvz6L4