티스토리 뷰
2D 자동 전투 시뮬레이션을 만드는데 AI에 필요한 길찾기 구현에서 애를 많이 먹어서 정리해둔다.
주 참고 자료:
https://www.david-gouveia.com/pathfinding-on-a-2d-polygonal-map
Pathfinding on a 2D Polygonal Map
I haven’t had much time to update the blog lately (mostly due to having to crunch work on my thesis) and for that I apologize. But since it’s been one month since my last post, I decided to write something up today, even if it’s not a full blown article wi
www.david-gouveia.com
https://redblobgames.github.io/circular-obstacle-pathfinding/
Circular Obstacle Pathfinding
Mar 2017 Navigating a forest The A* pathfinding algorithm is a powerful method for quickly generating optimal paths. Typically, people demonstrate A* navigating grid-based maps, but A* isn’t just a grid algorithm! It can work on any graph. We can use A* to
redblobgames.github.io
이 자료들이 설명 아주 잘 해놓았음
요구 사항
1. 특정 대상을 향해 다가가기
1-1. 도달 불가능한 경우, 최대한 가까이 가기
2. 특정 대상으로부터 일정 거리만큼 떨어지기
2-1. 불가능한 경우, 최대한 멀리 떨어지기
대부분의 경우 위 두가지 조건을 만족하는 길찾기만 가능하면 되는데, 가까이 다가가는 건 그렇게 어렵지 않은데 일정 거리만큼 떨어지는 부분이 문제였다. 이것 때문에 각 캐릭터를 원으로 표현해야 하나, polygon으로 표현해야하나도 고민을 많이 했는데, 일단은 polygon과 circle을 섞어 쓰는 구현은 좀 과도하게 복잡하고 고려해야할 게 많아서 전부 polygon으로 사용하는 방향으로 정했다.
각 오브젝트는 그 오브젝트의 반경 r을 가지는데, 이 r 값의 크기에 따라 적당히 원의 형태에 가까운 정다각형으로 근사해서 쓰는 방식. 어차피 오브젝트들 사이즈가 그렇게 크지 않아서 이걸로도 충분하다고 생각했다. "일정 거리만큼 떨어지기"는 각 캐릭터의 반경 r에 거리 d만큼을 더한 r + d 위치에 정점을 도달하는 식으로 만들면 구현이 가능하다.
'연구' 카테고리의 다른 글
| pixel art renderer 연구 (2) (0) | 2019.12.04 |
|---|---|
| pixel art renderer 연구 (1) (0) | 2019.11.27 |