장애물이있는 그리드에서 가장 가까운 지점 찾기

Question

나는 금을 수집하는지도를 돌아 다니고 나서 출구로 이동해야하는 게임을 가지고 있습니다. 나는 현재이 게임을 할 인공 지능을 작성하려고하지만 어떤 알고리즘을 사용해야 객체의 가장 가까운 인스턴스를 찾아야하는지 알고 싶습니다. 예를 들어, 금의 가장 가까운 조각 또는 가장 가까운 알려지지 않은지도 광장. 문제는 플레이어가 이동할 수없는 벽이 있다는 것입니다. 가장 가까운 대상을 찾는 것보다는 최단 경로가있는 대상을 찾는 것입니다. 이 작업을 수행 할 수있는 알고리즘이 있습니까?

Answer 1

찾고있는 알고리즘을 A * 검색 알고리즘이라고합니다. 그것은 출발점에서 시작하여 일련의 가능한 경로 (가능한 경로가 아니기 때문에 장애물을 통과하는 것을 제외하고)를 구축 한 다음, 최소 비용을 찾기 위해 경로를 채점하여 가장 먼저 수행되는 검색 알고리즘입니다. 귀하의 경우 경로를 따라 물체를 기준으로 비용을 줄이고 거리별로 비용을 높여 점수를 사용자 정의해야합니다. http://qiao.github.io/PathFinding.js/visual/

기타 리소스 :

이

멋진 인터랙티브 여기 데모 (GitHub의에 또한 코드)있다 : 여기에 당신을 도울 것입니다 몇 가지 정보가있다

• https://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/
• What is a good 2D grid-based path-finding algorithm?

나는 봇 전체지도를 알고하지 않은 경우 작업이 알고리즘을 수정하는 것이 어떻게