https://itmining.tistory.com/66

• bfs 의 경우 도착점을 타겟팅으로 해서 진행하는 알고리즘이 아님. 다만, 진행중에 어 도착점이네 하면 멈추기만 함.

• 에이스타의 경우, 도착점을 타겟팅으로 해서 진행하는 알고리즘.
  추가적으로 최단 경로를 구하는데 , 휴리스틱을 이용함.

• 이 때 사용하는 휴리스틱은 타겟팅 정점과 시작점 까지의 거리 g
  타겟팅 정점과 도착점까지의 거리 h ,
  g 와 h의 합인 f

• 구한 f 와 정점 번호를 이용해서 도착점까지의 최단 경로를 구하는 알고리즘임.

• 여기서 다익스트라와 동일하게 매순간 최소비용의 정점을 찾음.
  -> priority_queue< f, vertexNum> 을 넣음.
  

• pq에서 최소비용의 f 즉, less? 로 삽입해서 진행하자.

• visited 는 필요 없음.
  다익스트라에서 배웠듯이 최소비용의 정점을 택한 순간, 어떻게 하더라도 인접 정점 순환하면서 최소비용으로의 정점으로 오더라도
  이미 구한 최소비용보다 작을 수 없음. (상식적인 것임.)

• 그래서 다익스트라와 동일하게 distTable 이 필요하고, distTable 을 이용해서 조건 처리를 할 것임.
  

• 그리고 게임에서는 추적 정점을 알기 위해서 map parent<Pos , Pos> 가 반드시 필요 함.

• 도착점에 도착할 경우, parent를 reverse 하기만 하면 됨.

주의할 점.

• 추가적으로, 다익스트라는 시작점으로부터 모든 정점을 구하는 것이지만, 에이스타의 경우의 도착점을 타겟으로 해서 최단 경로를 구하는 것임. 따라서 visited 와는 다르게, 현재 방문한 최소비용의 정점이 아닌 , 우회회서 가더라도 도착점에 최단경로로 도착할 수 있음.
  따라서 parent 값이 계속 변경될 수 있음.

에이스타 코드 1번.

void Player::AStar()
{
	// 점수 매기기
	// F = G + H
	// F = 최종 점수 (작을 수록 좋음, 경로에 따라 달라짐)
	// G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 (작을 수록 좋음, 경로에 따라 달라짐)
	// H = 목적지에서 얼마나 가까운지 (작을 수록 좋음, 고정)
	// H는 휴리스틱 
	Pos startPos = _pos;
	Pos destPos = _board->GetExitPos();

	enum
	{
		DIR_COUNT = 8
	};

	Pos Dir[] =
	{
		Pos { -1, 0},	// UP
		Pos { 0, -1},	// LEFT
		Pos { 1, 0},	// DOWN
		Pos { 0, 1},	// RIGHT
		Pos {-1, -1},	// UP_LEFT
		Pos {1, -1},	// DOWN_LEFT
		Pos {1, 1},		// DOWN_RIGHT
		Pos {-1, 1},	// UP_RIGHT
	};

	int32 cost[] =
	{
		10, // UP
		10, // LEFT
		10, // DOWN
		10, // RIGHT
		14,
		14,
		14,
		14
	};

	const int32 size = _board->GetSize();

	// 인접 정점 중에서 최소 비용의 정점을 get해서 타겟을 할 것임.
	// 따라서 최소비용을 저장할수 있는 distTable 필요 
	// distTable 의 값을 통해서 비교할 것이기 때문에 visited bool 변수 필요 없음. 

	//다익스트라에서는 간선의 차이간 비교를 했지만, 
	// 에이스타에서는 f값을 통해서 최소비용을 get하자. 

	// 여기서는 vertexNum 은 Pos로 대체하자. 
	priority_queue< PQNode> pq;
	
	// 일단 시작점부터 삽입하고 시작하자. 
	pq.push({ 0, startPos });

	// distTable 만들고, 초기값을 모두 1e9로 처리하자. 
	vector<vector<int>> distTable(size, vector<int>(size, 1e9));
	// 아래가 y값 + 임. 그리고 좌표축이 y, x 로 시작함. 링크하자.
	distTable[startPos.y][startPos.x] = 0;

	vector<vector<bool>> bVisited(size, vector<bool>(size, false));
	

	vector<Pos> parent;
	

	while (!pq.empty())
	{
		PQNode targetV = pq.top();
		pq.pop();
		parent.push_back(targetV.pos);
		bVisited[targetV.pos.y][targetV.pos.x] = true;

		if(targetV.pos == destPos)
			break;

		for (int i = 0; i < 8; ++i)
		{
			// 인접하는 8개의 정점을 확인하면서 
			// CanGo 함수 사용하자. 
			
			// g : 인접 정점에서 도착점까지
			// h : 인접 정점에서 시작점까지
			// f : g + h 

			Pos adjacentV = targetV.pos + Dir[i];
			if (CanGo(adjacentV) == false)
			{
				continue;
			}

			if (bVisited[adjacentV.y][adjacentV.x] == true)
				continue;
			
			// ghf 값 구해야지.
			// Pos 간의 차이 알아야 함. 
			int g = abs(startPos.x - adjacentV.x)
				+ abs(startPos.y - adjacentV.y);
			int h = abs(destPos.x - destPos.x)
				+ abs(destPos.y - destPos.y);
			int f = (g + h) * 10;

			if (distTable[adjacentV.y][adjacentV.x] < f)
			{
				continue;
			}

			pq.push({ f , adjacentV });
			// distTable 갱신해야지.
			distTable[adjacentV.y][adjacentV.x] = f;

		}

	}
	// 231022 이거 초기화해서 매번 변경되는 맵에 에이스타 적용됨.
	_pathIndex = 0;
	_path.clear();
	_path = parent;

}

위의 코드의 문제점에 대해서

• 매순간마다 parent를 push 하고, 확정해서 path로 사용하고 있는데, 문제점이 있음.
  -> 만약에 해당 길목에 장애물이 있따고 한다면 어떻게 처리할 것인가...
  --> 다익스트라와 동일하게 visited 를 처리하는 것은 맞음.
  --> but, 도착점까지 가는데 다른 정점을 통해서 가는게 효율적일 수 있음.

• 방문을 하지 않은 정점을 통해 도착점까지 가는데 더 효율적일 수 있음.

  이 때를 위해서 best[][] 값을 가지고 있자.
  그리고 parent 형식을 map < Pos , Pos> 로 관리하는 것이 효율적임.
  best[][] 는 매번 f 값이랑 비교를 해서 최소비용 갖는 것으로 처리하자.

변경한 코드 폴더

: H:_0ServerMake\AStar 길찾기 알고리즘_깡통코드_practice#1