로봇이 그리드가 아닌 평면에서 한 지점에서 다른 지점으로 이동해야한다고 생각하십시오. 숲 등의 것들이 있다면 최단 경로를 어떻게 찾습니까? 그리드가 A * 알고리즘을 사용할 수 있다는 것을 알고 있습니다. 그러나 내가 달성하려고하는 또 다른 예는 인간에게 가장 짧은 길을 찾는 테란에 대한 훌륭한 지식을 가진 좀비 일 것입니다.장애물 회피 로봇의 여유 공간에 최단 경로를 찾는 알고리즘이 있습니까?
간단한 몇 가지 가정을하면 로봇/좀비가 중요한 포인트입니다.
적합 여부를 확인하는 등의 작업을 피하는 것입니다. 로봇/좀비가 원형 인 경우 장애물의 모든 가장자리를 원의 바깥쪽으로 객체 바깥쪽으로 이동하여 다른 모든 객체를 '더 살짝'만들 수 있습니다. 로봇/좀비가 사각형 인 경우에도 가장자리를 밀어 내고 큐브 차원을 사용하여 수행 할 수 있지만 사각형을 회전해야하는 경우에는 작동하지 않습니다.
단일 점에 대한 경로를 찾으려고하면 더 간단 해집니다. '뚱뚱한'폴리곤 장애물의 모든 꼭지점을 그래프의 노드로 변형하고 직접 볼 수있는 다른 모든 노드에 연결하십시오 (장애물을 통과하지 않음). 3d에서 당신이 가장자리를 고려해야하고 문제가 좀 더 지루 해집니다.
그래프가 생기면 문제를 해결할 수있는 A */Dijkstra/뭐든 할 수 있습니다.
정확한 결과를 원한다면 로봇/콤비가 원일 경우 모서리 주변을 돌아 다니는 것이 원호 세그먼트에서 움직이기 때문에 모서리 주변을 조심해야합니다. 게임/시뮬레이션을 실행하는 경우 매우 얇은 장애물과 상대적으로 큰 원/로봇/좀비를 제외하고는 그 차이가 눈에 띄지 않습니다.
성능면에서 설정이 정적 인 경우 그래프를 미리 계산할 수 있습니다. 또한 노드 수는 장애물의 꼭지점 수에 따라 다르므로 경로 찾기를 위해 품질이 낮은 객체로 실행하는 것이 좋습니다.
[Dijkstra의 알고리즘] (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) –
그러나 이것은 여유 공간입니다. Dijkstra의 알고리즘에서 그리드 나 노드는 어떻게 적용됩니까? –
그래프는 추상화입니다. 비행기의 한 점을 노드로 간주하고 두 점 사이의 직선 경로 (있는 경우)를 모서리로 간주합니다. 그리드가 없습니다. –