Grassfire Algorithm

Grassfire Algorithm은 시작점에서 불이 일정한 속도로 사방으로 퍼져 나간다고 가정하여, 각 위치까지의 최단 거리를 계산하는 최단 경로 탐색 알고리즘이다. 불은 한 번에 인접한 셀로만 이동하며, 모든 방향으로 동일한 속도로 확산된다. 따라서 어떤 셀에 불이 처음 도달한 순간의 이동 횟수가 바로 시작점으로부터 그 셀까지의 최단 거리가 된다.

알고리즘은 먼저 시작점 \(S\)에 거리값 0을 부여한 후, 인접한 셀에는 1, 그 다음 단계의 셀에는 2와 같이 거리값을 차례대로 증가시키며 전체 공간으로 확산시킨다. 이 과정에서 장애물은 불이 통과할 수 없는 영역으로 처리된다. 목표점 \(G\)에 불이 처음 도달했을 때의 거리값이 \(S\)에서 \(G\)까지의 최단 거리이다.

최단 경로는 거리 계산이 완료된 후 목표점에서 시작점 방향으로 거리값이 1씩 감소하는 인접 셀을 차례대로 선택하면 얻을 수 있다. 즉, 목표점에서 가장 가까운 거리값을 갖는 이웃을 반복적으로 따라가면 최단 경로가 역순으로 복원된다.

Grassfire Algorithm은 모든 이동 비용이 동일한 격자 환경에서는 너비 우선 탐색(Breadth-First Search, BFS) 과 동일한 원리로 동작하며, 항상 최단 경로를 찾을 수 있다. 알고리즘이 단순하고 효율적이어서 로봇의 경로 계획(path planning), 미로 탐색, 게임 AI, 그리고 영상 처리에서의 거리 변환(distance transform) 등에 널리 사용된다.

blue cell: obstacles, black cell = start( or end)

$$\text{distance measure}:~\text{Manhattan distance}=|x_2 - x_1 | + |y_2 - y_1|$$

void grassfire(CPoint q, int **map, int w, int h, int **dist) {
    // left-top-right-bottom;
    const int dx[] = {-1,  0, 1, 0};
    const int dy[] = { 0, -1, 0, 1};
    for (int y = 0; y < h; y++) 
        for (int x = 0; x < w; x++) 
            dist[y][x] = INF;  //unvisited cells;

    std::queue<CPoint> Q;
    dist[q.y][q.x] = 0;     //start( or end) position: distance = 0;
    Q.push(q);
    while (!Q.empty()) {
        CPoint p = Q.front(); Q.pop();
        int distance = dist[p.y][p.x];
        // 4-way search;
        for (int i = 0; i < 4; i++) {
            CPoint q = CPoint(p.x + dx[i], p.y + dy[i]);
            if (q.x < 0|| q.y < 0|| q.x >= w|| q.y >= h) continue;
            if (map[q.y][q.x] == 0 && dist[q.y][q.x] == INF) {
                dist[q.y][q.x] = distance + 1;
                Q.push(q);
            }
        }
    }
};
// back tracking;
CPoint back_track(CPoint p, int **dist, int w, in h) {
    // left-top-right-bottom;
    const int dx[] = {-1,  0, 1, 0};
    const int dy[] = { 0, -1, 0, 1};
    int depth = dist[p.y][p.x]; 
    if (--depth < 0) return p;
    for (int i = 0; i < 4; i++) {
        CPoint q = CPoint(p.x + dx[i], p.y + dy[i]);
        if (q.x < 0 || q.y < 0 || q.x >= w || q.y >= h) continue; // out of ROI;
        else if (dist[q.y][q.x] == depth)
            return q;
    }
    return p; // never hit;
}