타일 기반 A * 길 찾기 (폭탄 포함)

Question

타일을 기반으로하는 지하 감옥을 통해 벽 정보를 빠르게 찾을 수있는 간단한 A * 경로 찾기 알고리즘을 작성했습니다.

지하 감옥의 예 (단순 만 1 경로) :

그러나

지금은 경로 생성을 허용 할 알고리즘에 "폭탄"의 변수 금액을 추가 할 1 개의 벽을 무시하는 것을 발견했다. 실제로이과 같습니다 :

편집 : 그러나 지금은 더 이상 생성 된 경로가 여기에 첫 번째 이미지처럼 보이는 단지 1 폭탄의 사용과 예를 들어

를 최적의 경로를 찾을 수없는 https://i.stack.imgur.com/kPoAA.png

올바른 경로는

문제는 두 번째 이미지는 것하지만 이제 "청산 노드"내가 가능한 경로를 따라야한다. 이 문제를 해결하는 방법에 대한 아이디어는 매우 높이 평가 될 것입니다!

Answer 1

귀하의 "게임 상태"는 더 이상 귀하의 위치에 의해서만 정의되지 않으며 남겨진 폭탄의 수를 나타내는 정수로도 정의됩니다. wikipedia에 A *의 의사 코드를 따르는 중이면 closedSet을 간단히 구현할 수 없다는 뜻입니다. Y는 폭탄

수가

좌측 좌표

가

• X
• 좌표 : 아마도 예를 들어, 각 엔트리는 다음의 데이터를 보유 해시 맵/해시 세트는,로서 구현되어야

  검색 과정에서 특정 위치를 방문하면 더 이상 해당 위치를 닫은 것으로 표시하지 않습니다. 위치 + 폭탄의 수를 닫은 채로 표시합니다. 그런 식으로, 동일한 검색 과정에서 나중에 동일한 위치에 있지만 더 많은 폭탄이 남아있는 위치로 들어가면 닫힌 것처럼 무시하지 않고 실제로 그 가능성을 검색합니다.

  폭탄의 가능한 최대 개수가 상대적으로 적 으면 closedSet을 부울 그리드의 배열로 구현할 수 있습니다. 먼저 폭탄 수로 색인을 생성 한 다음 x 및 y 좌표로 if 특정 위치가 닫혔는지 여부.

Answer 2

의 벽이 전혀없는 것처럼 보이는 것은 아닙니다.?

처음부터 끝까지 최단 경로를 찾은 다음 통과해야하는 벽의 수를 확인하려면 A *를 사용하십시오. 폭탄이 충분하다면 길을 사용할 수 있습니다. 그렇지 않으면 다음으로 긴 경로를 시도해보십시오.

그런데 질문 : http://gamedev.stackexchange.com을 확인해보세요.

Answer 3

폭탄을 구입하기 위해 비용 기능을 조정해야합니다. 그런 다음 알고리즘을 일반적으로 두 번째 폭탄을위한 무한 비용으로 실행하십시오. 대략 절반 정도의 폭탄을 얻으려면 비용 함수를 가지고 놀아라. 휴리스틱 스 A-B 거리와 빈 타일의 비용을 곱하면된다. 폭탄이 두 개인 경우 비용의 절반은 물론 폭탄 3 개를 사용하면 무한 비용이 발생합니다.

하지만 아주 좋은 결과는 기대하지 마십시오. A *는 그런 종류의 최적화를 위해 설계되지 않았습니다.