A 寻路算法，用于在 六边形网格
2026-03-04 14:40:24
我们要实现一个 A 寻路算法，用于在 六边形网格 上：
- 找出从起点到终点的最短路径；
- 考虑移动距离限制（如最多走 5 步）；
- 支持地形代价（如山地更难走）、敌人阻挡；
- 实现“可移动范围”显示（类似游戏中的蓝色高亮区域）。
🧩 一、六边形网格基础
1. 六边形坐标系统
常用两种表示方式：
- 轴向坐标（Axial Coordinates）
- 立方体坐标（Cube Coordinates）
我们使用 轴向坐标（q, r），因为简单且适合 A。
🔹 坐标示例（轴向）
text
编辑
(0,1)
(-1,1) (0,0) (1,0)
(-1,0) (0,-1)
(1,-1)
🔹 六边形邻居
每个六边形有 6 个邻居，方向如下：
python
编辑
directions = [
(1, 0), # 右
(1, -1), # 右下
(0, -1), # 左下
(-1, 0), # 左
(-1, 1), # 左上
(0, 1) # 右上
]
注意：实际布局取决于六边形是“平顶”还是“尖顶”，这里假设为“平顶”。
💡 二、A 在六边形上的实现（Python）
python
编辑
import heapq
from typing import List, Tuple, Optional
class HexGrid:
def __init__(self, width: int, height: int):
self.width = width
self.height = height
# grid[r][q] 表示位置 (q, r) 的状态
# 0: 可通行, 1: 障碍物, 2: 敌人, 3: 友军
self.grid = [[0 for _ in range(width)] for _ in range(height)]
def is_valid(self, q: int, r: int) -> bool:
return 0 <= q < self.width and 0 <= r < self.height
def is_blocked(self, q: int, r: int) -> bool:
if not self.is_valid(q, r):
return True
return self.grid[r][q] == 1 # 障碍物不可通行
def get_cost(self, q: int, r: int) -> float:
"""返回移动到该格子的代价"""
if not self.is_valid(q, r):
return float('inf')
terrain = self.grid[r][q]
if terrain == 0: # 平地
return 1.0
elif terrain == 1: # 障碍
return float('inf')
elif terrain == 2: # 敌人
return 2.0 # 可移动但代价更高
elif terrain == 3: # 友军
return 1.0 # 可移动
return 1.0
def a_star_hex(grid: HexGrid, start: Tuple[int, int], goal: Tuple[int, int], max_steps: int = 5) -> Optional[List[Tuple[int, int]]]:
"""
六边形网格上的 A* 寻路
:param grid: HexGrid 对象
:param start: 起点 (q, r)
:param goal: 终点 (q, r)
:param max_steps: 最大移动步数（如 5）
:return: 路径列表 或 None
"""
# 方向：六个邻居
directions = [(1, 0), (1, -1), (0, -1), (-1, 0), (-1, 1), (0, 1)]
def heuristic(a: Tuple[int, int], b: Tuple[int, int]) -> int:
"""六边形曼哈顿距离（也叫 Chebyshev 距离）"""
q1, r1 = a
q2, r2 = b
return (abs(q1 - q2) + abs(q1 + r1 - q2 - r2) + abs(r1 - r2)) // 2
open_set = []
heapq.heappush(open_set, (0, 0, start))
came_from = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}
while open_set:
_, current_g, current = heapq.heappop(open_set)
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
return path[::-1]
# 如果已走超过最大步数，跳过
if current_g >= max_steps:
continue
for dq, dr in directions:
neighbor = (current[0] + dq, current[1] + dr)
nq, nr = neighbor
if not grid.is_valid(nq, nr) or grid.is_blocked(nq, nr):
continue
tentative_g = current_g + grid.get_cost(nq, nr)
if tentative_g >= max_steps:
continue # 超过最大移动距离，跳过
if neighbor not in g_score or tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score[neighbor], tentative_g, neighbor))
return None # 无路径
🎮 三、如何实现“可移动范围”？
在游戏中，点击武将时会显示一个蓝色区域，表示他能移动到的所有格子。
声明：该内容由作者自行发布，观点内容仅供参考，不代表平台立场；如有侵权，请联系平台删除。
标签：
