최적의 패스 파인딩

Question

배경
그것에 몇 가지 장애물이있는 정사각형지도가 있습니다. 장애물은 다각형으로 표시됩니다. 다음 경로 찾기 알고리즘을 구현했습니다.
1) 정밀도를 선택하십시오 (K로 표시됩니다)
2)지도를 KXK 사각형으로 나눕니다.
3) 다음 규칙에 따라 해당 사각형의 그래프를 만듭니다.
- 모든 노드는 하나의 정사각형을 나타냅니다
- 두 개의 노드가 인접한 경우에만 연결되어 있으며 그 중 어느 것도 장애물을 공동으로 코스사합니다.
4)* 알고리즘 (또는 dijkstra 또는 기타 ...)을 사용하여 가장 짧은 경로를 찾으십시오.

이 알고리즘은 맵이 동적이지 않으면 상당히 잘 작동합니다. 그것은 장애물을 움직일 수 없다는 것을 의미합니다.

질문
1) 그 효율적인 접근 방식입니까?
2) 장애물을 움직일 수 있다면 어떻게해야합니까?
3) 다른 요원을 치료하는 방법? 방에 100AGENTS가있는 상황을 고려해 봅시다. 두 가지가 있습니다. 모든 에이전트는 한 그룹에 있고 해당 그룹은 출구 중 하나 근처에 있습니다. 모든 에이전트가 가장 가까운 출구로 가면 병목 현상이 발생합니다. 그들 중 일부는 종료하는 데 필요한 시간을 최소화하기 위해 다른 출구로 가야합니다. 그러한 결과를 얻는 방법?

Answer 1

A* 경로를 정적 장애물 주변의 일반적인 지침으로 사용하고 로컬을 수행하십시오. 장애물 회피 동적 (작은) 장애물의 경우. 레이놀즈에는 병목 현상 프로젝트에 대한 알고리즘도 있습니다. 그는 그것을 부릅니다 대기.