Rubberbanding & Smoothing

Rubberbanding

• 그리드 기반에서 불필요한 중간 노드를 지우는 과정
• 세 그리드 또는 지점 사이가 통과 가능한 공간인지를 확인
  • 통과 가능하면 중간 점은 리스트에서 제거

bool AStarPather::rubberbanding(
    const GridPos& first, 
    const GridPos& second,
    const GridPos& third)
{
    // 세 점이 이루는 전 영역을 대상
    int left = std::min(first.row, std::min(second.row, third.row)),
        right = std::max(first.row, std::max(second.row, third.row)),
        top = std::max(first.col, std::max(second.col, third.col)),
        bot = std::min(first.col, std::min(second.col, third.col));

    for (int i = left; i <= right; i++) {
        for (int j = bot; j <= top; j++) {

            // 해당 영역이 이동가능한지 확인
            GridPos p{i, j};
            if (terrain->is_valid_grid_position(p)
                && terrain->is_wall(p))
                return false;
        }
    }

    // otherwise,
    return true;
}

Smoothing

• Waypoint들을 추가하여 에이전트가 각 지점을 경유하면서 자연스러운 곡선을 그리며 이동하도록 하는 Post-processing

곡선

• 두 점 A, B 사이의 점 P를 위와 같이 표현
• t에 대한 방정식
  • 1차 베지에 곡선
  • 점 P의 집합, 즉 A와 B를 잇는 선분

• 각 점을 잇는 선분 또는 곡선 위의 점들에 대하여, 이들을 다시 서로 잇는다
• n차 베지에 곡선은 n개의 점들에 대해 밀도 t를 조절해가며 곡선을 생성할 수 있다

연속성

• 여러 곡선을 자연스럽게 잇는 방법
• C0: 전체 곡선이 연속한다
• C1: 곡선이 연속하고, 각 곡선이 만나는 곳의 접선 벡터가 같다
  • 0차, 1차 도함수가 연속이다
• C2: 곡선이 연속하고, 각 곡선이 만나는 곳의 접선 벡터가 같고, 곡률도 같다
  • 0차, 1차, 2차 도함수가 연속이다

Spline Points

• 보간 스플라인의 한 종류
• 4게 제어점이 주어질 때 이들 모두를 곡선을 그리며 통과하는 선을 그린다
  • 네 개 점에서 곡선은 중간 점 2개 사이에 정의된다

캣멀롬 스플라인

• s는 밀도
• 4개 점을 대상으로 곡선을 이루는 점들을 구하는 방법

오류

• 그리드 간 World Distance를 1로 잡았을 때, Rubberbanding 후의 각 점 사이의 거리가 1.5배 이상이면 Smoothing 시 오류가 발생한다

• 이 경우 back points를 새로 삽입해준다
  • 기존에 있던 point 들의 중간 지점을 몇 개 더 배치한다
• 그 다음 스무싱을 해준다

출처

• https://tsyang.tistory.com/57
• https://ko.wikipedia.org/wiki/%EC%BA%A3%EB%A9%80%EB%A1%AC_%EC%8A%A4%ED%94%8C%EB%9D%BC%EC%9D%B8