[알고리즘] A* 길찾기 알고리즘

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

---

A* 길찾기 알고리즘

본문내용넣기

 

---

A* 길찾기

 

점수 매기기

 F  = G + H(Heuristic)
최종 점수 = 이동 비용 + 목적지까지 거리  

F = 최종 점수 (작을수록 좋음, 경로에 따라 달라짐)
G = 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을수록 좋음, 경로에 따라 달라짐)
H = 목적지에서 얼마나 가까운지 (작을수록 좋음, 고정)

 

 

 

---

 

코드

 

void Player::AStar()
{
    Pos start = _pos;
    Pos dest = _board->GetExitPos();
 
    enum
    {
        DIR_COUNT = 8
    };
 
    Pos front[] =
    {
        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,  // UP_LEFT
        14,  // DOWN_LEFT
        14,  // DOWN_RIGHT
        14,  // UP_RIGHT
    };
 
    const int32 size = _board->GetSize(); // 맵의 사이즈
 
    // ClosedList
    // close[y][x] -> (y, x)에 방문을 했는지 여부
    vector<vector<bool>> closed(size, vector<bool>(size, false));
 
    // best[y][x] -> 지금까지 (y, x)에 대한 가장 좋은 비용 (작을수록 좋음)
    vector<vector<int32>> best(size, vector<int32>(size, INT32_MAX));
 
    // 부모 추적 용도
    map<Pos, Pos> parent;
 
    // OpenList
    priority_queue<PQNode, vector<PQNode>, greater<PQNode>> pq;
 
    // 1) 예약(발견) 시스템 구현
    //        - 이미 더 좋은 경로를 찾았다면 스킵
    // 2) 뒤는게 더 좋은 경로가 발견될 수 있음 -> 예외 처리 필수
    //     - openList에서 찾아서 제거하거나
    //     - pq에서 pop한 다음에 무시하거나
 
    // 초기값
    {
        int32 g = 0;
        int32 h = 10 * (abs(dest.y - start.y) + abs(dest.x - start.x));
        pq.push(PQNode{ g + h, g, start });
        best[start.y][start.x] = g + h;
        parent[start] = start;
 
    }
 
    while (pq.empty() == false)
    {
        // 제일 좋은 후보를 찾는다
        PQNode node = pq.top();
        pq.pop();
 
        // 동일한 좌표를 여러 경로를 찾아서, 
        // 더 빠른 경로로 인해서 이미 방문(closed)된 경우 스킵
 
        // [선택]
        if (closed[node.pos.y][node.pos.x])
            continue;
        if (best[node.pos.y][node.pos.x] < node.f)
            continue;
 
        // 방문
        closed[node.pos.y][node.pos.x] = true;
         
        // 목적지에 도착했으면 바로 종료
        if (node.pos == dest)
            break;
 
        for (int32 dir = 0; dir < DIR_COUNT; dir++)
        {
            Pos nextPos = node.pos + front[dir];
            // 갈 수 있는 지역은 맞는지 확인
            if (CanGo(nextPos) == false)
                continue;
            // [선택] 이미 방문한 곳이면 스킵
            if (closed[nextPos.y][nextPos.x])
                continue;
 
            // 비용 계산
            int32 g = node.g + cost[dir];
            int32 h = 10 * (abs(dest.y - nextPos.y) + abs(dest.x - nextPos.x));
            // 다른 경로에서 더 빠른 길을 찾았으면 스킵
            if (best[nextPos.y][nextPos.x] <= g + h)
                continue;
 
            // 예약 진행
            best[nextPos.y][nextPos.x] = g + h;
            pq.push(PQNode{ g + h, g, nextPos });
            parent[nextPos] = node.pos;
 
        }
    }
 
    // 거꾸로 거슬러 올라간다
    Pos pos = dest;
    
    _path.clear();
    _pathIndex = 0;
 
    while (true)
    {
        _path.push_back(pos);
 
        // 시작점은 자신이 곧 부모이다
        if (pos == parent[pos])
            break;
 
        pos = parent[pos]; // 부모 위치로 이동한다
    }
 
    std::reverse(_path.begin(), _path.end());
}

 

 

 

---

 

H3 중제목

본문내용넣기

 

 

 

 

 

---

 

마무리

마무리

 

 

 

A* 알고리즘 실행 (대각선 이동 가능)