A-Star (A*)를 사용하여 가장 "자연스럽게"직접 경로를 찾는 방법
https://stackoverflow.com/questions/845626
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
AS3에서 A* 알고리즘을 구현했으며 한 가지를 제외하고는 훌륭하게 작동합니다. 종종 결과 경로는 대상으로 가장 "자연스러운"또는 부드러운 경로를 취하지 않습니다. 내 환경에서 물체는 수평 또는 수직으로 움직일 수 있으므로 대각선으로 저렴하게 움직일 수 있습니다. 다음은 매우 간단한 예입니다. 시작점은 S로 표시되고 끝 (또는 마감)은 F에 의해 표시됩니다.
| | | | | | | | | |
|S| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
보시다시피, 첫 번째 발견 중에 노드 [0,2], [1,2], [2,2]는 모두 N의 점수를 가지므로 가능한 노드 목록에 모두 추가됩니다. 문제는 다음과 같은 시점에오고 있습니다. 위의 예에서는 다음 노드를 선택하기 위해 possiblenodes [0]를 사용하고 있습니다. 이것을 possiblenodes [possiblenodes.length-1]로 변경하면 다음 경로를 얻습니다.
| | | | | | | | | |
|S| | | | | | | | |
| |x| | | | | | | |
| | |x| | | | | | |
| | | |x| | | | | |
| | |x| | | | | | |
| |x| | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
그리고 가능하면 possiblenextnodes [math.round (possiblenextnodes.length / 2) -1
| | | | | | | | | |
|S| | | | | | | | |
|x| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
이 모든 경로는 모두 같은 수의 단계를 포함하는 것과 동일한 비용을 가지고 있지만,이 상황에서 가장 합리적인 경로는 다음과 같습니다.
| | | | | | | | | |
|S| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
공식적으로 받아 들여진 방법이 수학적으로 정확하기보다는 경로를 더 합리적으로 보이게하는 방법이 있습니까?
해결책
휴리스틱 기능에 타이 브레이커를 추가해야합니다. 여기서 문제는 동일한 비용을 가진 많은 경로가 있다는 것입니다.
직접 경로를 선호하는 간단한 타이 브레이커의 경우 교차 제품을 사용할 수 있습니다. 즉, S가 시작이고 E가 끝이고 X는 알고리즘의 현재 위치 인 경우 SE와 XE의 교차 제품을 계산하고 휴리스틱에 페널티를 추가 할 수 있습니다. 노선).
코드 :
dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*0.001
또한보십시오 http://theory.stanford.edu/~amitp/gameprogramming/heuristics.html#s12, 이것은 일반적으로 A*에 대한 훌륭한 튜토리얼입니다.
다른 팁
자연스럽게 보이는 경로를 원한다면 비용이 직교 좌표계의 길이에 해당하는지 확인해야합니다. 이는 대각선으로 이동하는 데 드는 비용이 SQRT (2) 수직 또는 수평으로 이동하는 데 드는 비용이어야한다는 것을 의미합니다.
각 정사각형의 비용 계산에 '제어 노력'을 추가 할 수 있습니다. 배우는 경로에 비용이 추가되므로 방향을 너무 많이 돌리거나 변경하지 않으려 고 노력할 것입니다.
내가 올바르게 기억한다면, 이에 대한 트릭은 비용 함수에 추가 매개 변수를 추가하는 것입니다 (인접한 노드 사이 또는 사각형의 모든 단계에 대해) 회전을 처벌합니다 정상보다 약간 더 sqrt(2) Digonal 이동의 경우). 이제 경로를 부드럽게하는 것과 실제로 경로의 최적 성을 감소시키는 것 사이에는 미세한 선이있을 수 있습니다 (그러나 그것을 확장). 어떤 식 으로든이를 피할 수는 없습니다. 자신의 응용 프로그램에 따라 다루어야 할 특정 트레이드 오프가 있으며 테스트를 통해서만 실제로 달성 할 수 있습니다.
게임 데브 사이트에 기사가 있었는데, 이것이 어떻게이를 수행 할 수 있는지 정확하게 자세히 설명했지만 지금은 찾을 수없는 것 같습니다. 어쨌든 비용 기능을 가지고 놀고 어떤 결과를 얻었는지 확인하십시오.
더 '현명한'이란 무엇입니까? 똑바로? 알고리즘이 그것에 대해 무엇이든 할 예정이라면 올바르게 정량화해야합니다.
대각선으로 이동하는 것은 수평/수직으로 이동하는 것만 큼 저렴하기 때문에 모든 경로는 a*에서 사용 가능한 모든 기준에 따라 동일합니다. 보다 '현명한'경로를 원한다면 알고리즘에 일부 경로가 다른 경로보다 더 바람직하다는 사실을 알리고, 대각선보다 '더 나은'수평/수직을 효과적으로 가중시킵니다. 내가 볼 수있는 한, 그것은 당신의 환경의 매개 변수를 변경하는 것입니다.
