(4/10) 2D SRPG 만들기 선행학습 — 이동 범위와 A* 길찾기
Summary
파랜드 택틱스에서 유닛을 선택하면 이동 가능한 칸이 파랗게 표시되고, 그중 한 칸을 찍으면 유닛이 장애물을 피해 또박또박 걸어갑니다. 이 두 가지 — 이동 범위 계산과 길찾기 — 가 SRPG 의 정체성이에요. 오늘이 이 시리즈에서 알고리즘 밀도가 가장 높은 편입니다.
겁먹을 필요는 없어요. 필요한 알고리즘은 대학 알고리즘 수업의 단골손님인 다익스트라와 A* 두 개뿐이고, 둘 다 파이썬 표준 라이브러리 heapq 로 30줄 안에 끝납니다. 그리고 한 번 짜두면 어떤 SRPG 를 만들든 평생 재사용해요.
💡 이 글에서 다루는 것
- 타일맵을 그래프로 보기 — 이웃과 이동 비용
- 이동 범위 계산 — 이동력 안에서 갈 수 있는 모든 칸 (다익스트라)
- A* 길찾기 — 목적지까지의 최단 경로
- 경로 보간 — 계산된 경로를 따라 부드럽게 걷기
- 실습 — 유닛 선택 → 파란 칸 → 클릭한 곳으로 걸어가는 데모
1. 타일맵은 그래프다
2편에서 만든 타일맵을 알고리즘의 눈으로 다시 봅시다. 각 타일이 노드, 상하좌우로 붙은 타일 사이가 간선입니다. 지형에 따라 간선을 지나는 비용이 달라요. 2편의 지형표를 그대로 규칙으로 옮깁니다.
| 타일 ID | 지형 | 이동 비용 |
|---|---|---|
| 0 | 풀밭 | 1 |
| 1 | 물 | 통행 불가 |
| 2 | 산 | 2 |
코드로는 함수 두 개면 됩니다. “이 칸의 이웃은 어디인가”와 “이 칸에 들어가는 비용은 얼마인가”예요.
MOVE_COST = {0: 1, 1: None, 2: 2} # None = 못 들어감
def neighbors(gx, gy):
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = gx + dx, gy + dy
if 0 <= nx < COLS and 0 <= ny < ROWS:
yield nx, ny
def enter_cost(gx, gy):
return MOVE_COST[MAP[gy][gx]]
이 두 함수가 지형 규칙의 전부를 캡슐화합니다. 나중에 “숲은 비용 2”, “아군이 서 있는 칸은 통과 가능하지만 멈출 수 없음” 같은 규칙이 늘어나도 이 함수들만 고치면 아래의 알고리즘은 그대로예요.
2. 이동 범위 — 파란 칸은 다익스트라가 만든다
“이동력 4인 유닛이 갈 수 있는 모든 칸”을 구해봅시다. 모든 지형의 비용이 1이라면 단순한 BFS(너비 우선 탐색)로 충분한데, 우리는 산이 비용 2라서 비용이 싼 경로부터 확정해나가는 다익스트라가 필요합니다. 파이썬에선 heapq(우선순위 큐)로 구현해요.
import heapq
def movement_range(start, mov):
"""start 에서 이동력 mov 안에 도달 가능한 칸과 소요 비용을 돌려줘요."""
dist = {start: 0}
pq = [(0, start)]
while pq:
d, cur = heapq.heappop(pq)
if d > dist.get(cur, 10**9):
continue # 이미 더 싼 경로로 확정된 칸
for nb in neighbors(*cur):
cost = enter_cost(*nb)
if cost is None:
continue # 물 — 못 들어감
nd = d + cost
if nd <= mov and nd < dist.get(nb, 10**9):
dist[nb] = nd
heapq.heappush(pq, (nd, nb))
return dist
2편의 8×8 맵에서 (3, 4) 에 선 이동력 3짜리 유닛으로 돌려보면 이렇게 나옵니다.
reach = movement_range((3, 4), mov=3)
print(len(reach), "칸 도달 가능")
print(sorted(reach.items())[:5])
19 칸 도달 가능
[((0, 4), 3), ((1, 4), 2), ((1, 5), 3), ((2, 4), 1), ((2, 5), 2)]
반환된 딕셔너리의 키가 곧 파랗게 칠할 칸들이고, 값은 거기까지 드는 비용입니다. 왼쪽의 물 타일(1, 2 열의 호수)은 목록에 없고, 산을 거치는 경로는 비용이 2씩 늘어난 걸 볼 수 있어요. 렌더링은 이 키들을 2편의 draw_tile 로 파란 반투명 마름모로 그리면 끝입니다.
💡 파랜드 택틱스류의 “지형마다 이동 소모가 다르고, 물은 못 건너는” 규칙이 전부 이 30줄 안에 들어 있습니다. 비행 유닛을 만들고 싶으면 그 유닛에 한해
enter_cost가 항상 1을 돌려주게만 하면 돼요.
3. A* — 목적지가 정해졌을 때의 최단 경로
이동 범위는 “갈 수 있는 곳 전부”였고, 이제 플레이어가 그중 한 칸을 찍었을 때 어떤 경로로 갈지가 필요합니다. 다익스트라도 경로를 찾을 수 있지만, 목적지가 정해져 있을 땐 A* 가 더 빨라요. 핵심 아이디어는 하나입니다 — “지금까지 온 비용 + 목적지까지 남은 거리 추정치” 가 작은 칸부터 탐색하는 것.
추정치(휴리스틱)로는 격자 게임의 표준인 맨해튼 거리(가로 차이 + 세로 차이)를 씁니다.
def astar(start, goal):
def h(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1]) # 맨해튼 거리
pq = [(h(start, goal), 0, start)]
came = {start: None}
g = {start: 0}
while pq:
_, d, cur = heapq.heappop(pq)
if cur == goal: # 도착 — 경로 복원
path = []
while cur is not None:
path.append(cur)
cur = came[cur]
return path[::-1]
for nb in neighbors(*cur):
cost = enter_cost(*nb)
if cost is None:
continue
nd = d + cost
if nd < g.get(nb, 10**9):
g[nb] = nd
came[nb] = cur
heapq.heappush(pq, (nd + h(nb, goal), nd, nb))
return None # 길이 없음
호수 왼쪽 (0, 2) 에서 오른쪽 (4, 3) 으로 가는 길을 찾아보면, 호수 위쪽으로 빙 둘러가는 경로가 나옵니다.
path = astar((0, 2), (4, 3))
print(path)
[(0, 2), (0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (4, 3)]
경로 복원 트릭이 재밌는 부분이에요. 탐색 중에 came[다음칸] = 현재칸 으로 “어디서 왔는지”를 기록해두고, 도착하면 그 기록을 거꾸로 따라가서 뒤집습니다. 빵조각을 흘려두고 되짚어오는 헨젤과 그레텔 방식이죠.
⚠️ 실전 SRPG 에선 “이동 범위 안의 칸”만 목적지로 허용해야 합니다. 2장의
movement_range결과에 있는 칸인지 먼저 확인하고 A* 를 부르세요. 범위 밖 칸을 허용하면 이동력 제한이 무의미해져요.
4. 경로 보간 — 순간이동 말고 걸어가기
path 는 칸 목록일 뿐이라, 그대로 좌표를 바꾸면 유닛이 순간이동합니다. 걸어가는 것처럼 보이려면 다음 칸을 향해 매 프레임 조금씩(속도 × dt) 다가가고, 도착하면 그 칸을 경로에서 지우는 로직이 필요해요.
def update_walk(unit, dt, speed=180):
if not unit["path"]:
return
tx, ty = tile_center(*unit["path"][0]) # 다음 칸의 화면 중앙
vx, vy = tx - unit["px"], ty - unit["py"]
dist = (vx * vx + vy * vy) ** 0.5
step = speed * dt
if dist <= step: # 이번 프레임에 도착
unit["px"], unit["py"] = tx, ty
unit["gx"], unit["gy"] = unit["path"].pop(0)
else: # 방향 벡터 정규화 후 전진
unit["px"] += vx / dist * step
unit["py"] += vy / dist * step
포인트는 두 가지입니다. 도착 판정을 dist <= step 으로 하는 것 — “남은 거리보다 이번 프레임 이동량이 크면 도착”이라, 목표를 지나쳐 덜덜 떠는 버그가 안 생겨요. 그리고 방향 벡터를 거리로 나눠 정규화하는 것 — 대각선 구간에서도 속도가 일정해집니다. 3편의 애니메이터를 여기 연결하면(이동 중일 때만 anim.update) 걷기 모션까지 완성이에요.
5. 실습 — 선택하고, 파란 칸 보고, 걸어가기
전부 합칩니다. 유닛(원)을 클릭하면 파란 이동 범위가 뜨고, 범위 안 칸을 클릭하면 A* 경로로 걸어가요. 2편의 맵/변환 함수와 이번 편의 알고리즘 함수(movement_range · astar · update_walk)는 본문 그대로라 생략 표시를 했습니다 — 이어 붙이면 그대로 돌아갑니다.
import pygame, heapq
pygame.init()
screen = pygame.display.set_mode((960, 540))
pygame.display.set_caption("SRPG 선행학습 4편 — 이동 범위와 길찾기")
clock = pygame.time.Clock()
MAP = [ ... ] # 2편의 8x8 맵 그대로
ROWS, COLS = len(MAP), len(MAP[0])
TILE_W, TILE_H = 64, 32
ORIGIN_X, ORIGIN_Y = 480, 120
COLORS = {0: (106, 168, 79), 1: (61, 133, 198), 2: (127, 106, 79)}
MOVE_COST = {0: 1, 1: None, 2: 2}
# grid_to_screen / screen_to_grid / draw_tile ← 2편 그대로
# neighbors / enter_cost / movement_range / astar / update_walk ← 본문 그대로
def tile_center(gx, gy):
sx, sy = grid_to_screen(gx, gy)
return sx, sy + TILE_H // 2
unit = {"gx": 1, "gy": 1, "px": 0.0, "py": 0.0, "mov": 4, "path": []}
unit["px"], unit["py"] = tile_center(1, 1)
selected, reach = False, {}
running = True
while running:
dt = clock.tick(60) / 1000
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.MOUSEBUTTONDOWN and not unit["path"]:
g = screen_to_grid(*event.pos)
if g == (unit["gx"], unit["gy"]):
selected = True # 유닛 클릭 → 선택
reach = movement_range(g, unit["mov"])
elif selected and g in reach:
unit["path"] = astar((unit["gx"], unit["gy"]), g)[1:]
selected, reach = False, {} # 출발 칸은 빼고 걷기 시작
update_walk(unit, dt)
screen.fill((30, 30, 46))
for gy in range(ROWS):
for gx in range(COLS):
draw_tile(gx, gy, COLORS[MAP[gy][gx]])
for g in reach:
draw_tile(*g, (90, 140, 230)) # 파란 이동 범위
pygame.draw.circle(screen, (94, 198, 214),
(int(unit["px"]), int(unit["py"]) - 8), 10)
pygame.display.flip()
pygame.quit()
유닛을 클릭하는 순간 물을 피한 파란 범위가 좌악 펼쳐지고, 클릭한 칸까지 유닛이 마름모 능선을 따라 걸어가는 걸 보면 — 이제 진짜 SRPG 같아 보이기 시작합니다.
✅ 디버깅 팁: 범위나 경로가 이상하면 화면 말고 콘솔에 먼저 print 하세요.
movement_range/astar는 pygame 없이도 도는 순수 함수라, 파이썬 REPL 에서 맵만 놓고 단독 테스트가 됩니다. 로직과 렌더링을 분리해두면 이런 게 좋아요.
6. 정리
- 타일맵 = 그래프.
neighbors+enter_cost두 함수로 지형 규칙 캡슐화 - 이동 범위 = 다익스트라. 반환 딕셔너리 키가 곧 파란 칸
- 최단 경로 = A*. 맨해튼 휴리스틱 +
came기록으로 경로 복원 - 경로 보간 —
dist <= step도착 판정과 벡터 정규화 - 알고리즘은 순수 함수로 — pygame 없이 테스트 가능하게
이제 유닛이 규칙대로 움직이니, 남은 건 서로 싸우게 하는 것뿐이에요.
일단 오늘은 여기까지….. 다음 글에서는 턴제 전투 시스템과 상태머신을 정리해볼게요.
← 이전 글: (3/10) 2D SRPG 만들기 선행학습 — 스프라이트와 애니메이션 ｜ 다음 글 →: (5/10) 2D SRPG 만들기 선행학습 — 턴제 전투와 상태머신
