Path Searching for Game

게임에서는 빠르고 효율적인 경로 탐색이 중요하기 때문에, 다양한 경로 탐색 알고리즘이 사용된다. 환경적 특성과 요구사항에 따라 선택할 수 있는 여러 가지 알고리즘이 존재한다.특히, RPG 게임에서 경로 탐색 알고리즘이 어떻게 적용될 수 있는지 이 포스팅에서 다루려고 한

Dijkstra 알고리즘은 가중치가 있는 그래프에서 한 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 데 유용하며, GPS, 네트워크 라우팅, 게임 AI 등 다양한 분야에서 널리 사용됩니다.Dijkstra 알고리즘은 "탐욕적 접근법(Greedy approach)"을

Dijkstra 알고리즘 in Python이전 글에서는 Dijkstra 알고리즘을 나에게 가작 익숙한 언어인 Python으로 구현해보았다.C++은 20살 이후로 처음 써보는데, 그 당시에는 A학점을 받았지만 지금 다시 써보려니 어색하고 낯설다.또한 맥북에서 C++을 사

A\* 알고리즘 (A star 알고리즘)은 Dijkstra와 유사하지만, 추가적인 휴리스틱 함수(heuristic function)을 사용하여 목표 노드까지의 예상 거리를 고려함으로써 더 효율적으로 최단 경로를 찾는 알고리즘이다. 휴리스틱은 경로를 찾는 데 있어서 탐색

파이썬으로 구현한 A\* 알고리즘은 아래 링크에서...A\* 알고리즘 in PythonA\* 알고리즘 (A star 알고리즘)은 Dijkstra와 유사하지만, 추가적인 휴리스틱 함수(heuristic function)을 사용하여 목표 노드까지의 예상 거리를 고려함으로써

기본 목표 : JPS(Jump Point Search)는 A\* 알고리즘의 확장 개념으로, 격자(grid)기반의 맵에서, 시작점부터 목표 지점까지의 최단 경로를 찾는 알고리즘이다.점프 포인트(Jump Point) 직선이나 대각선으로 이동할 때 장애물이 나오거나 방향을

JPS in Python에서 Python으로 우선 구현해보았으니, 이번엔 JPS 알고리즘을 C++로도 작성해보려고 한다.Python 코드의 모든 주요 요소를 C++로 변환하여 구현하기!점프 함수와 JPS 함수에서 Python의 논리를 그대로 가져오되, C++의 자료 구

JPS 알고리즘을 C++로 구현하기에서 이어서, 이 JPS 알고리즘을 통해 간단한 2D 맵에서 NPC가 경로를 따라 이동하는 것을 시각적으로 구현해보고자 한다.C++에서 2D 맵 시각화를 구현하는 방법은, 주로 SFML (Simple and Fast Multimedia

이전 글에서 C++에서 구현한 JPS 알고리즘을 시각화했다. 이번에는 좀더 나아가서, 더 복잡한 맵상에서 JPS알고리즘의 동작을 확인해보고자 한다.다양한 크기의 맵과 장애물 배치를 테스트.알고리즘 성능(경로 길이, 시간) 비교.GRID_ROWS와 GRID_COLS를 동

Dijkstra, A\*, JPS 세 가지 경로 탐색 알고리즘에 대하여 이 시리즈에서 다루었다. 먼저 알고리즘의 원리를 이해하기 위해 능숙하게 사용할 수 있는 파이썬으로 먼저 구현해보고, 다시 C++에서 재구현해보았다.이제 이 세 가지 알고리즘을 동일한 복잡한 맵에서