🍀 한 줄 평 :

공부시간 : 0h 0min

응원해주는 사람들의 얼굴과 말들을 떠올려

진인사대천명

1. 오전

A* 알고리즘 코드 복습 및 이해. : **코드를 옆에 두고 같이 따라 읽어가면 이해하기 좋음. ★ 대략적인 알고리즘 개괄 ★
타일을 순회하며 인접 타일의 비용을 계산 후, 정렬, → OpenList에 저장. (계산 된 타일은 CloseList에 저장.)
비용이 가장 작은 타일부터 하나씩 재귀적으로 인접 타일 비용 계산.
계산 해가며 새 인접타일을 계산할 때. 타일의 iParentIndex 에 이전 타일 저장.
적은 비용대로 인접타일 계산하다보면 목표타일을 만나게 됨.
Best List에 목표타일의 iParentIndex 부터 역으로 경로를 찾아서 저장.**
1. [Player.cpp :: Update()] Player에서 마우스 클릭시 Using_Astar 함수 시작과 동시에 vStart(Player의 위치)와 vGoal(마우스 포인터 위치)를 넘겨준다.
2. [AstarMgr :: Using_Astar()] Close, Open, Best LIst 를 모두 Clear해준다.
3. [AstarMgr :: Using_Astar()] Get_Terrain()을 통해 Terrain Obj 를 가져오고, Get_Tile을 통해 Tile의 정보가 담겨있는 Vector를 가져온다.
4. [AstarMgr :: Using_Astar()] Get_TileIndex()를 통해 vStart와 vGoal 의 (x,y)좌표에 해당하는 타일 Index번호를 가져온다.
  1. [Get_TileIndex()] vecTile을 순회하면서, 매개변수로 주어진 좌표에 해당하는 타일의 번호(Index)를 가져오는 함수.
  2. [Get_TileIndex()]
  3. Terrain class 와 vecTile을 가져옴.
  4. vecTile을 순회하면서 Picking(vPos, iIndex) 함수를 순회
    1. [Picking()] 벡터의 내적을 이용하여 특정 좌표(vPos)가 특정타일(Index)에 들어가 있는지를 확인하는 함수.
    - 매개변수 : vPos, iIndex(현재 순회중인 Tile의 Index.
    1. [Picking()]
      1. Terrain class 와 vecTile을 가져옴.
      2. 현재 Index에 해당하는 타일의 네 꼭짓점을 vPoint[4]에 저장.
      3. vPoint를 통해 시계방향으로 향하는 네 방향 벡터를 구해서 vDir[4]에 저장
      4. vDir[i]의 각 법선 벡터를 구함. 2차원에서 (x, y)에 대한 법선 벡터는 (-y, x) 이다. vNormal[4]에 저장.
      5. 각 vPoint에서 마우스 클릭 포인트 vPos 로 향하는 벡터를 구해서 vMouseDir[4]에 저장
      6. vMouseDir[i] 과 vNormal[i] 정규화 한 뒤, 내적함.
        
        피킹 포인트가 마름모 안쪽.
        
        vMouseDir[i] 과 vNormal[i]이 **둔각(θ > 90)**을 이룬다. ⇒ θ > 90 이므로, 정규화한 벡터를 내적하여 나오는 cosθ 의 값이 음수이다. (그림참조)
        
        피킹 포인트가 마름모 바깥쪽.
        
        vMouseDir[i] 과 vNormal[i]이 **예각(θ < 90)**을 이룬다. ⇒ θ < 90 이므로, 정규화한 벡터를 내적하여 나오는 cosθ 의 값이 양수이다.
      7. 내적값이 하나라도 양수일 경우, 타일의 바깥쪽이라 판단하여 false를 반환.
    2. [Picking()] vPos가 현재 순회중인 Index의 타일의 안쪽일 경우 → true를 반환
  5. [Get_TileIndex()] Picking()→true일 경우. 현재 Index를 반환. 아닐경우, -1 반환.
5. [AstarMgr :: Using_Astar()] vStart와 vGoal 의 에 해당하는 타일의 Index를 m_iStartIdx와 m_GoalIdx 에 저장.
6. [AstarMgr :: Using_Astar()] 예외 조건. m_iStartIdx와 m_GoalIdx 가 i. 전체 타일의 Index번호보다 크거나, ii. 0보다 작거나, (Picking 실패해서 -1값을 가진 경우) iii. m_iStartIdx==m_GoalIdx 이거나, iv. m_GoalIdx 의 byOption 이 0이 아닐 경우(장애물 타일 인 경우), 함수 retrun.
7. 그 이외에는 Make_Route(m_iStartIdx, m_GoalIdx) 함수 실행.
8. [AstarMgr :: Make_Route(m_iStartIdx, m_GoalIdx)] - 재귀적인 함수 (완전한 최단 경로를 찾지 않고 최단 경로의 근사값을 찾아내는 것을 목표)
  1. 사실상 A* 알고리즘 구현 된 부분.
  2. CTerrain class, vecTile, vecAdj 를 가져옴.
    - vector<list<TILE*>> m_vecAdjacency : 각각의 타일마다 인접한 타일의 정보를 저장한 vector. : 장애물인지 or 최외각 타일인지 의 여부에 따라 인접 타일을 저장.
- 주석으로 정리함.
```
bool CAstarMgr::Make_Route(int iCurIdx, int iGoalIdx)
{
	// 타일 관련 정보 가져오는 것.
	CObj* pTerrain = CObjMgr::Get_Instance()->Get_Terrain();
	if (nullptr == pTerrain)
		goto Jump;

	vector<TILE*>& vecTile = dynamic_cast<CTerrain*>(pTerrain)->Get_VecTile();
	if (vecTile.empty())
		goto Jump;

	vector<list<TILE*>>& vecAdj = dynamic_cast<CTerrain*>(pTerrain)->Get_Adj();
	if (vecAdj.empty())
		goto Jump;
	/*=======================================================*/

	// 두번 째 이후의 Make_Route 함수 실행 상태 인 경우.
	// 현재 iCurIdx가 m_OpenList.front() 이므로, m_OpenList.pop_front() 해줌.
	if (!m_OpenList.empty())
		m_OpenList.pop_front();

	// 현재 iCurIdx을 탐색 완료된 타일로 push_back 해줌.
	m_CloseList.push_back(iCurIdx);

	// 현재 Index에 해당하는 벡터의 인접 타일들을 순회.
	for (auto& AdjTile : vecAdj[iCurIdx])
	{
		// 현재 순회중인 인접 타일이 목표 타일일 경우 
		// -> 현재 순회중인 인접 타일(목표타일)의 iParentIndex에 iCurIdx 기입.
		// -> 탐색 종료.
		if (iGoalIdx == AdjTile->iIndex)
		{
			AdjTile->iParentIndex = iCurIdx;
			return true;
		}

		// 목표 타일이 아니었다,
		// 현재 순회중인 인접 타일이 Opon, Close 리스트에 있는지 조사
		if (false == Check_Close(AdjTile->iIndex) &&
			false == Check_Open(AdjTile->iIndex))
		{
			// 현재 순회중인 인접 타일의 iParentIndex에 iCurIdx 기입.
			// 최단 비용 계산을 위해 OpenList에 현재 순회중인 인접 타일 저장. x 4.
			AdjTile->iParentIndex = iCurIdx;
			m_OpenList.push_back(AdjTile->iIndex);
		}
	}

	// 더 이상 찾을 길이 없을 경우
	if (m_OpenList.empty())
		goto Jump;

	int	iStart = m_iStartIdx;

	// 이동가능한 인접 타일들의 h(), g() (이동 비용 (가중치) ) 를 계산하여 
	// Open List 에서 정렬함 --> 가장 비용이 작은 Front부터 쓸 예정.
	//												list 원소 순회.
	m_OpenList.sort([&vecTile, &iStart, &iGoalIdx](int Temp, int Sour)->bool
		{
			// cost = PCost + GCost

			// 시작점 타일에서 현재 타일까지의 이동가능한 인접 타일까지의 거리 비용.
			D3DXVECTOR3	vPCost1 = vecTile[iStart]->vPos - vecTile[Temp]->vPos;
			D3DXVECTOR3	vPCost2 = vecTile[iStart]->vPos - vecTile[Sour]->vPos;

			// 이동가능한 인접 타일로부터 목표 타일까지의 거리 비용
			D3DXVECTOR3	vGCost1 = vecTile[Temp]->vPos - vecTile[iGoalIdx]->vPos;
			D3DXVECTOR3	vGCost2 = vecTile[Sour]->vPos - vecTile[iGoalIdx]->vPos;

			float	fDist1 = D3DXVec3Length(&vPCost1) + D3DXVec3Length(&vGCost1);
			float	fDist2 = D3DXVec3Length(&vPCost2) + D3DXVec3Length(&vGCost2);

			// 오름차순 정렬.
			return fDist1 < fDist2;
		});

	// 이동비용이 가장 작은 타일을 시작점으로 다시 Make_Route실행.
	return Make_Route(m_OpenList.front(), iGoalIdx);

Jump:
	return false;
}
```
용책 복습하기. : 11:40 ~ 13:00 : 페이지 : ㅇ ~ ㅇ 1.