반복 홍수 채우기 최적화

Question

나는 경로를 찾기 위해 A *가있는 교차 가능하고 교차 불가능한 사각형을 사용하는 그리드 기반 시스템을 사용하고 있으며 경로를 찾을 수 있는지를 확인하기 위해 홍수 채우기를 사용합니다 (두 영역이 연결되어 있는지 확인하기 위해).).

제 문제는 새로운 교차 불가능 영역을 아주 자주 (초당 최대 16 회) 도입 할 수 있고 그리드가 상당히 (약 500x500) 도입 할 수 있기 때문에 O (mn) 홍수 채우기 솔루션조차도 상당히 오랜 시간. floodfill의 다른 구현을 살펴본 결과 내가 원하는 것과 비슷한 것을 찾을 수 없었습니다.

내 질문은 이전의 그리드와 새로운 교차 불가능 영역 (항상 직사각형) 목록을 기반으로 반복되는 홍수 채우기 호출을 최적화하는 방법이 있습니까?

Answer 1

먼저 교차 채우기 사각형을 연결된 채우기 구성 요소로 플러드 채우기 알고리즘으로 분할합니다.

영역을 교차 불가능으로 표시 할 때 해당 영역에서 이전에 교차 가능한 사각형에 인접한 영역 외부의 모든 교차 가능한 사각형의 집합 S를 고려하십시오. S에 적어도 두 개의 구성원이있는 각 구성 요소 C에 대해 플러드 채우기를 사용하여 C의 연결이 끊어 졌는지 확인합니다. 당신이 crossable로 영역을 표시하면

, 나는 경우 죄송