2012-07-14 3 views
2

변화하는 환경을 처리하기 위해 A * 알고리즘을 적용하는 데 문제가 있습니다. 최소 예를 들어,이 불량 같은 맵을 고려해경로 찾기 변경 가능한 환경을위한 알고리즘

###### 
#! # 
### # 
#S # 
##+### 
##F### 
###### 

목표는 S에서 F에 도착하는 것이지만,이를 위해 그렇게 플레이어가 문을 열어 !에 단계를해야합니다. 내가 가지고있는 문제는 일단 격자 점을 방문하면 "닫히고"다시 입력 할 수 없다는 것입니다. 이 수수께끼를 풀기 위해 어떻게 알고리즘을 수정할 수 있습니까?

당신은 두 번 A *를 실행할 수 있습니다
+0

플레이어가 *를 사용하여 '!'를 누르면 '+'문이 열리는 것을 알고 있습니까? 어떤 문을 열 었는지 표시가없는 스위치가 여러 개있는 경우 A * 정보가 모두 가정되지 않으며 알고리즘이 문제를 해결할 수 없기 때문입니다. (또한, 바닐라 A *는 미로를 다루는 데 꽤 나쁩니다.) –

답변

2

문제가있는 점은 A *에서 점 (x, y 코드)을 방문했을 때 다시 같은 점을 방문하지 않는다는 것입니다.

그 이유는 상태가 그리드의 위치와 각 도어의 상태 (열림 또는 닫음) 때문입니다. 처음에는 예제에서 초기 상태는 (3,1, {false})입니다. (거짓은 문이 닫혀 있음을 의미).

'!' 새로운 상태는 (1,1, {true})이 될 것이므로 지금 문에 도달하면 문을 통과 할 것입니다.

3

:

  1. 먼저 문이 벽 그런
  2. 스위치에서 끝으로 최단 경로를 찾을 수에게 처럼 스위치 (!)에 최단 경로를 찾아 문 은 빈 타일입니다.

가장 짧은 경로는이 두 경로의 조합입니다.

+0

+1 웨이 포인트와 함께 길 찾기를하는 방법입니다. –