타일이없는 NPC의 & 문자에 A *와 같은 길 찾기 사용하기

Question

"iOS Games by Tutorials"(iPhone 게임을 만드는 데 관심이있는 사람에게 추천합니다) & 나는 만드는 법을 배우고 있습니다. 오버 헤드 뷰 (젤다 링크의 각성의 전설처럼)가있는 스프라이트 키트가있는 타일 맵. 지금까지 32x32 크기의 타일을 사용하여 바둑판 식으로 맵을 만들었습니다. 플레이어의 캐릭터는 세계에 여러 개의 NPC가 &입니다. 비록 NPC가 무작위로지도 주위를 돌았지만, 책에서 가르치는 방식은 타일에서 타일로 이동하는 것입니다 (NPC를 둘러싼 8 개 타일 중 언제든지 타일이 카테고리 BitMask와 같은 일부 속성을 가진 경우 해당 타일로 이동하지 않습니다).

플레이어 캐릭터가 지금 당장 가지고있는 것과 같이 (플레이어 캐릭터처럼 physicsBody가있는 오브젝트와 NPC가 충돌한다는 의미 인 것처럼) NPC 이동을 물리 기반 (자체 문제 임)으로 변경하려고합니다. 더 유동적입니다. & 동적입니다.

하지만 여기서 질문이 시작됩니다. NPC &에 Pathfinding (예 : A * 알고리즘)을 구현하려는 경우 건물, 물, 나무 등이 포함 된지도로 인해 플레이어 캐릭터가 자신의 물리 기관과 함께 움직이기를 원합니다. NPC의 무작위 움직임을 제한하거나 미리 결정된 길을 걷도록 강요하는 것 (이 게임의 요점을 없애는 것)이 있지만, 플레이어 캐릭터가 모든 건물/나무를 피하도록하기 위해 화면을 자주 가볍게 두 드려야하는 또 다른 방법입니다 그는 과거를 걸어야한다. 그리드 시스템을 사용하고 싶지 않습니다. x, y 좌표에 길 찾기 알고리즘을 구현할 수 있습니까? 자원 집약적입니까? 이것에 관해 당신의 생각을 이야기 해 주시겠습니까?

감사합니다.

Answer 1

이것은 매우 흥미로운 주제입니다.

연속 된 공간에서 경로를 찾는 알고리즘이 있습니다. 예를 들어 잠재력이 매우 낮고 장애물이 "언덕"인 잠재력 기반 방법을 사용할 수 있습니다 (약간의주의가 필요하지만 아마도 무한히 높을 수 있습니다). 잠재적 인 방법의 단점은 지역 최소로 갇히지 않도록 특별한 예방 조치를 취해야한다는 것입니다. 이 상황은 다음과 같습니다.

 P 
+----+ 
| M| 
| | 
+ ---+ 

여기서 M은 플레이어에 도착하려고하는 괴물이며 P가 발생할 수 있습니다. 이 예에서 괴물은 지역 최소 거리에 있으며 건물의 왼쪽 하단에있는 문을 꺼내려면 더 높은 잠재력을 가져야합니다. 잠재적 인 알고리즘의 변형 (실제로는 하나의 알고리즘으로 축소하는 것이 유용합니다)은 장애물과 중력에 중력을 중력 목표에 할당하는 것입니다. 이것은 또한 다소 비 결정적이며 "막히는"것을 피하기 위해 특별한 예방 조치가 필요합니다.

@rickster으로 지적하면 SpriteKit은 잠재적 인 기반 솔루션을 구현하는 데 도움이되는 SKFieldNode 클래스를 제공합니다.

다른 접근법은 "wall follow"(예 : Pledge's algorithm)를 포함하며 미로와 같은 환경에서 길 찾기에 유용합니다.

연속적인 방법의 한 가지 단점은 NPC 이동이 종종 부자연스러워 보일 수 있다는 것입니다. 예를 들어 위의 예에서 몬스터가 지역 최소값에 해당 몬스터의 "온도"를 증가시킬 수 있다고하더라도 검색 (즉, 잠재적 인 그라디언트에 대해 무작위로 큰 움직임을 만들 때), 문을 향해 곧게가는 대신 바운스 할 것입니다.

연속 된 공간에서 검색하는 대신 공간을 양자화하는 것입니다. 간단한 방법은 그것을 바둑판 식으로 배열하거나, 다각형으로 덮거나, quadtree으로 표현하는 것입니다.기본적으로 연속 공간의 모든 점을 양자화 된 공간을 나타내는 그래프의 꼭지점에 매핑하는 방법을 원합니다. 이 시점에서 A * 및 친구와 같은 그래프 검색 알고리즘을 적용 할 수 있습니다.

그래프 검색은 다소 리소스 집약적이지만 2 차원 젤다 게임의 경우 모바일 장치에서 가능해야하며 특히 플레이어의 일정한 거리 내에있는 NPC 만 "깨우는"등 다양한 최적화 기능이 있어야합니다 화남).

This page은 구현 세부 사항이 약간 얇지 만 Google에 적합한 용어를 제공합니다.

언제나처럼 간단하게 시작하고 반복합니다. 타일링은 매우 쉽고 최적화하기 전에 그래프 검색 방법을 실험 할 수 있습니다.