[A* 알고리즘] 05_가중치 주가

jh Seo·2023년 8월 25일

A* 알고리즘

목록 보기

5/8

개요

https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
위의 재생목록 링크를 통해 유니티에서 A* 알고리즘을 공부하며 정리하는 글이다.

6번째 영상인 Weight를 읽고 정리한 글이다.
이제 노드에 가중치인 movePenalty가 붙고, 레이어에 movePenalty를 줘서
각 노드 생성시에 Raycast로 자신의 노드가 어떤 레이어인지에 따라 가중치를 둔다.

Node클래스 추가

public class Node:IHeapItem<Node>
{
    public int movePenalty;

    public Node(bool tmpWalkable, Vector3 tmpWorldPosition,int tmpGridX, int tmpGridY, int tmpMovePenalty)
    {
        walkable = tmpWalkable;
        worldPosition = tmpWorldPosition;
        gridX = tmpGridX;
        gridY = tmpGridY;
        movePenalty = tmpMovePenalty;
    }
}

위 코드들이 추가되었다.
movePenalty가 추가되면서, 노드 클래스 생성자 인자로 movePenalty를 받는다.

PathFinding클래스 추가

A* 알고리즘으로 현재 curnode 주위 neighbour을 순회하는 부분이 수정되었다.
새로운 노드의 GCost를 계산할 때, 현재 노드의 Gcost+ 현재노드에서 새로운 노드까지 거리에 movepenalty까지 더해진다.

int newGCost = curNode.gCost + GetDistance(elem, curNode)+elem.movePenalty;

Agrid클래스 추가

추가된 부분들이다.

public class Agrid : MonoBehaviour
{
   public TerrainType[] walkableRegions;
   private LayerMask walkableMask;
   private Dictionary<int, int> walkableRegionsDictionary = new Dictionary<int, int>();
   private void Init()
   {
       foreach(TerrainType terrain in walkableRegions)
       {
           walkableMask |= terrain.terrainMask.value;
           walkableRegionsDictionary.Add((int)Mathf.Log(terrain.terrainMask.value,2)
           ,terrain.terrainPenalty);
       }
       CreateGrid();
   }

   private void CreateGrid()
   {
       grid = new Node[gridXCnt, gridYCnt];
       //현재 포지션에서 x축으로 gridWorldSize의 x값/2 만큼 빼고 z축으로 gridWorldSize.y/2만큼 빼야함.
       worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward * gridWorldSize.y / 2;

       for (int i = 0; i < gridXCnt; i++)
       {
           for (int j = 0; j < gridYCnt; j++)
           {
               Vector3 worldPoint = worldBottomLeft + (i * nodeDiameter + nodeRadius) * Vector3.right + (j * nodeDiameter + nodeRadius) * Vector3.forward;
               bool walkable = !Physics.CheckSphere(worldPoint, nodeRadius, UnWalkableLayer);

               int movePenalty = 0;

               Ray ray = new Ray(worldPoint + Vector3.up * 50, Vector3.down);
               RaycastHit hit;
               if(Physics.Raycast(ray, out hit, 100, walkableMask))
               {
                   walkableRegionsDictionary.TryGetValue(hit.collider.gameObject.layer
                   , out movePenalty);
                   grid[i, j] = new Node(walkable, worldPoint,i,j,movePenalty);
               }
           }
       }
   }

   [System.Serializable]
   public class TerrainType
   {
       public LayerMask terrainMask;
       public int terrainPenalty;
   }
}

추가된 멤버변수과 클래스.

LayerMask와 terrainPenalty를 변수로 가진 클래스 TerrainType이다.

[System.Serializable]
public class TerrainType
{
    public LayerMask terrainMask;
	public int terrainPenalty;
}

walkableRegions는 TerrainType배열로 인스펙터창에서 레이어와 movePenalty를 설정해준다.
walkableMask는 걸을 수 있는 오브젝트의 레이어마스크로
비트 or 연산을 통해 TerrainType배열의 모든 레이어들을 넣어준다.
walkableRegionsDictionary는 레이어의 번호와 movePenalty를 매핑한다.

 public TerrainType[] walkableRegions;
 private LayerMask walkableMask;
 private Dictionary<int, int> walkableRegionsDictionary = new Dictionary<int, int>();

init함수 수정된 부분

foreach(TerrainType terrain in walkableRegions)
{
   	walkableMask |= terrain.terrainMask.value;
    
    walkableRegionsDictionary.Add
    (
    	(int)Mathf.Log(terrain.terrainMask.value,2),
    	terrain.terrainPenalty
    );
}

walkableMask에 walkableRegions의 모든 레이어들을 bit or 연산으로 넣어준다.
layermask.value가 2의 배수이므로 밑이 2인 로그함수를 취해서
레이어 번호를 알아낸다.
해당 레이어번호와 movePenalty를 walkableRegionsDictionary에 매핑해준다

CreateGrid 함수

for (int i = 0; i < gridXCnt; i++)
{
	for (int j = 0; j < gridYCnt; j++)
    {
    Vector3 worldPoint = worldBottomLeft + (i * nodeDiameter + nodeRadius) * Vector3.right + (j * nodeDiameter + nodeRadius) * Vector3.forward;
    bool walkable = !Physics.CheckSphere(worldPoint, nodeRadius, UnWalkableLayer);

    int movePenalty = 0;

    Ray ray = new Ray(worldPoint + Vector3.up * 50, Vector3.down);
    RaycastHit hit;
    if(Physics.Raycast(ray, out hit, 100, walkableMask))
    {
    	walkableRegionsDictionary.TryGetValue
        (
        	hit.collider.gameObject.layer,
		    out movePenalty
        );
		grid[i, j] = new Node(walkable, worldPoint,i,j,movePenalty);
        }
	}