건물로가는 길 찾기 (여러 좌표가있는 A *)?

Question

1) 저는 타일이 많은 건물을 짓는 게임을 생각합니다 (예 : 3x3).

그래서 빌드를 시작하기 전에 인접한 타일로 문자를 이동해야합니다. 그래서 건축 면적에 대한 최단 경로를 찾는 알고리즘이 있습니까?

우리는 지역 건물의 타일마다 A *를 사용해야하며 가장 짧은 것을 선택합니까?

편집, exemple :

지도 :; : 당신의 캐릭터에 상상이 exemple에 대한

, (0, 0) 좌표가 왼쪽이 랜드 마크와 이미지에있다 (0; 0)

이미지에서 왼쪽으로 채우기에 가장 가까운 문자를 이동하는 알고리즘을 찾고 있습니다. [좌표 : (1, 2), (8,2), (1,10), (8,10)]

목표는 "일반적인"경우와 같은 단일 좌표가 아니지만 4 전철기).

단일 시작 좌표 [여기, (0,0)]에서 가장 가까운 위치 (대각선 제외)를 찾는 가장 좋은 방법은 [여기서 (1, 2), (8,2), (1,10), (8, 10)]?

나는 솔루션의 알 고리 반환 배열을 원합니다. 따라서이 예제에서와 같이 여러 가지 경우 : [(0,2), (1,1)]은 솔루션을 선택하지 않고 모든 동등한 솔루션을 제공합니다.

2) 타일이없는지도 시스템과 동일한 질문이지만 좌표가 맞습니까?

Answer 1

우리는 지역 건물의 타일마다 A *를 사용해야하며 가장 짧은 것을 선택합니까?

아니, A *는 쉽게 일부을 포함 할 때 전류가 좌표 "할 수있다, 목표를"현재는 이 좌표에 해당 좌표 때 "일 필요는 없습니다 조건를 취할 수 있습니다 설정/영역 ". 이것은 알고리즘의 전역 구조에 대해서는 아무 것도 변경하지 않고 exit-test 만 변경합니다.

당연히 당신은 당신의 발견 적 사고를 지켜야합니다. 당신이있을 수 있습니다

current := the node in openSet having the lowest fScore[] value 
    if current = goal 
     return reconstruct_path(cameFrom, current) 

(위키에서 복사) :

current := the node in openSet having the lowest fScore[] value 
    if current ∈ goals 
     return reconstruct_path(cameFrom, current) 

또는이 :

대신이 "좁은"A *에 대한 의사의, 명확히하기 위해

current := the node in openSet having the lowest fScore[] value 
    if satisfiesGoalCondition(current) 
     return reconstruct_path(cameFrom, current) 

"현재 좌표가 목표 사각형 안에 있음"과 같은 일부 테스트가 될 수 있습니다.

Answer 2

글쎄 array/grid version of A*은 대상 영역의 모든 조회에서 중지 될 수 있으므로 시작 지점에서 목적지 좌표 중 하나에 도달 할 때까지 증가하고 backtrack입니다.

그래, 노드로 장애물을 설정 한 그래프/벡터 버전에서도이 작업을 수행 할 수 있습니다.

타일이 (반) 걸을 수있는 경우 그리드 버전 A*을 사용하는 것이 좋습니다. 2D을 타일 마킹 각자와 벽면으로 표현할 수 있습니다. 이런 식으로 뭔가 : 내 건 당신이 생각하지 않았다, 그래서 당신도 당신의 건물을 탐색 할 수

• Algorithm Trax Winning Condition

... 나는 그러나 당신의 건물의 내부에 표시되지 않습니다 지금까지. 를 살펴 보자 나는 3D 그리드 그래서 나는 3D 지형을 가지고 건물도 수준을 가질 수를 사용하고

일부 내부 건물 아이디어를

• 2D Diamond (isometric) map editor을 ... 당신은 단지 필요 이 같은 플레이어 뭔가 위의 수준을 잘라 선택적으로보기를 조정합니다