AStar2D

A* 的一种实现，用于查找 2D 空间中连通图上两个顶点之间的最短路径。

AStarGrid2D

A* 的一种实现，用于寻找疏松 2D 网格中两点之间的最短路径。

官方 navigation_astar 项目解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
extends TileMap
# 定义了一个枚举。这是一种给数字起名字的方式(0,1,2)，让代码更具可读性。
enum Tile { OBSTACLE, START_POINT, END_POINT }

# 定义瓦片尺寸（宽和高）
const CELL_SIZE = Vector2i(64, 64)
# 定义用于绘制路径的线条
const BASE_LINE_WIDTH = 3.0 # 宽度
const DRAW_COLOR = Color.WHITE * Color(1, 1, 1, 0.5) # 颜色

# 创建 AStarGrid2D 实例
# Godot 内置专门用于2D网格上进行路径寻找的工具，底层使用 A* 算法。
var _astar = AStarGrid2D.new()

# 用于存储路径计算的起点和终点在瓦片坐标系（Grid-based）位置
var _start_point = Vector2i()
var _end_point = Vector2i()
# 用于存储计算的路径上所有点的局部坐标系（Pixel-based）位置
var _path = PackedVector2Array()

func _ready():
    # 定义 A* 算法工作的网格范围
    # Rect2i(x, y, width, height)
    # 注意：这里的尺寸是硬编码的（18x10）如果地图大小会改变需要动态计算,例如通过 get_used_rect()
	_astar.region = Rect2i(0, 0, 18, 10)
    # 将 A* 网格的单元格大小设置为与瓦片大小一致
	_astar.cell_size = CELL_SIZE
    # 将 A* 节点的位置设置在瓦片中心
	_astar.offset = CELL_SIZE * 0.5
    # 设置 A* 启发式函数为曼哈顿距离
	_astar.default_compute_heuristic = AStarGrid2D.HEURISTIC_MANHATTAN
	_astar.default_estimate_heuristic = AStarGrid2D.HEURISTIC_MANHATTAN
	_astar.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_NEVER # 禁止对角线移动
	_astar.update() # 应用以上所有设置

    # 遍历 _astar.region 定义的整个网格范围
	for i in range(_astar.region.position.x, _astar.region.end.x):
		for j in range(_astar.region.position.y, _astar.region.end.y):
			var pos = Vector2i(i, j)
			if get_cell_source_id(0, pos) == Tile.OBSTACLE:
				_astar.set_point_solid(pos)


func _draw():
	if _path.is_empty():
		return

	var last_point = _path[0] # 获取路径的第一个点
	for index in range(1, len(_path)): # 从路径的第二个点开始遍历
		var current_point = _path[index]
		draw_line(last_point, current_point, DRAW_COLOR, BASE_LINE_WIDTH, true) # 绘制线段
		draw_circle(current_point, BASE_LINE_WIDTH * 2.0, DRAW_COLOR) # 绘制圆形
		last_point = current_point # 更新 last_point，为下一次循环做准备

# 接收一个像素坐标，先将其转换为瓦片坐标 (local_to_map)，然后再转换回像素坐标 (map_to_local)。
# 这样做的效果是，无论你传入哪个像素点，它都会返回该像素点所在瓦片的左上角像素坐标。
# 这常用于将一个自由移动的物体 “吸附” 到网格上。
func round_local_position(local_position):
	return map_to_local(local_to_map(local_position))

# 判断一个像素点所在的瓦片是否可以通过
func is_point_walkable(local_position):
	var map_position = local_to_map(local_position)
	if _astar.is_in_boundsv(map_position):
		return not _astar.is_point_solid(map_position)
	return false

# 用于清除上一次计算的路径
func clear_path():
	if not _path.is_empty():
		_path.clear()
		erase_cell(0, _start_point)
		erase_cell(0, _end_point)
		# 触发 _draw() 函数，清除屏幕上已绘制的路径线条和圆点
		queue_redraw()

# 这是外部调用者最常用的函数，用于计算新路径
func find_path(local_start_point, local_end_point):
	clear_path()
	# 将传入的像素坐标转换为瓦片坐标
	_start_point = local_to_map(local_start_point)
	_end_point = local_to_map(local_end_point)

	# 调用 A* 算法，返回一个包含路径上所有点（像素坐标，且是瓦片中心）的 PackedVector2Array。如果找不到路径，该数组将为空。
	_path = _astar.get_point_path(_start_point, _end_point)

	if not _path.is_empty():
		# 放置瓦片
		set_cell(0, _start_point, 0, Vector2i(Tile.START_POINT, 0))
		set_cell(0, _end_point, 0, Vector2i(Tile.END_POINT, 0))

	# 触发 _draw() 函数，在屏幕上绘制出新的路径。
	queue_redraw()

	return _path.duplicate()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
extends Node2D

# 定义了角色两种状态
enum State { IDLE, FOLLOW }
# 用于 “转向行为” 的一个物理参数。可以理解为“惯性”。
const MASS = 10.0
# 到达距离。当角色与目标点的距离小于这个值时，就认为它已经到达了该点。
const ARRIVE_DISTANCE = 10.0

@export var speed: float = 200.0

var _state = State.IDLE # 角色当前状态
var _velocity = Vector2() # 角色当前速度向量

@onready var _tile_map = $"../TileMap"

var _click_position = Vector2() # 存储玩家最后一次点击鼠标的全局位置
var _path = PackedVector2Array() # 存储从 TileMap 获取的路径点数组
var _next_point = Vector2() #存储路径中下一个要移动到的目标点

func _ready():
	_change_state(State.IDLE) # 初始化为 IDLE 状态


func _process(_delta):
	if _state != State.FOLLOW:
		return
	# 调用 _move_to 函数，让角色向 _next_point 移动。该函数会返回一个布尔值，表示是否到达了目标点。
	var arrived_to_next_point = _move_to(_next_point)
	if arrived_to_next_point:
		_path.remove_at(0)
		if _path.is_empty():
			_change_state(State.IDLE)
			return
		_next_point = _path[0]

# Godot 的输入处理函数之一，接收所有未被其他 UI 元素（如按钮）消耗掉的输入事件。
func _unhandled_input(event):
	_click_position = get_global_mouse_position() # 无论点击什么，都先更新 _click_position 为当前鼠标的全局坐标。
	if _tile_map.is_point_walkable(_click_position): # 调用 TileMap 脚本中的 is_point_walkable 函数，判断鼠标点击的位置是否是可通过瓦片
		if event.is_action_pressed(&"teleport_to", false, true): #  判断是否按下了 teleport_to 动作（鼠标右键）
			_change_state(State.IDLE)
			global_position = _tile_map.round_local_position(_click_position) # 直接设置位置
		elif event.is_action_pressed(&"move_to"): # 判断是否按下了 move_to 动作（鼠标左键）
			_change_state(State.FOLLOW)

#  接收一个目标点（_next_point）作为参数
func _move_to(local_position):
	var desired_velocity = (local_position - position).normalized() * speed # 得到速度向量
	var steering = desired_velocity - _velocity # 获取“转向行为”向量
	_velocity += steering / MASS # 将转向力除以质量，得到加速度。
	position += _velocity * get_process_delta_time() # 根据更新后的速度和帧时间（delta）来移动角色的位置
	rotation = _velocity.angle() # 让角色的旋转角度始终朝向其移动的方向
	return position.distance_to(local_position) < ARRIVE_DISTANCE # 判断是否到达目标点

# 这是一个状态机的核心，负责处理状态切换时的逻辑。
func _change_state(new_state):
	if new_state == State.IDLE:
		_tile_map.clear_path() # 调用 TileMap 的 clear_path() 函数
	elif new_state == State.FOLLOW:
		#  调用 TileMap 的 find_path 函数，传入角色当前的位置和之前记录的鼠标点击位置，获取一条路径。
		_path = _tile_map.find_path(position, _click_position)
		if _path.size() < 2: # 路径数组的大小小于 2，意味着 TileMap 没有找到有效路径
			_change_state(State.IDLE)
			return
		_next_point = _path[1] # 设置下一个目标点
	_state = new_state # 更新状态

六边形瓦片地图

竖向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
extends Node2D

@export var tileMap : TileMapLayer
@export var offSet = Vector2(0, -6) # 位置偏移量

var isMoving = false

func _input(event: InputEvent) -> void:
	if Input.is_action_just_pressed("leftClick"):
		_move()
		
func _move():
	if isMoving: return
	# 获取鼠标在游戏世界中的全局坐标
	var mousePosition = get_global_mouse_position()
	# 检查点击位置
	var isTargetPositionValid = get_tile_global_position(mousePosition)
	if not isTargetPositionValid: return

	isMoving = true
	
	# 调用路径计算函数
	var movementArray = _get_route(mousePosition)

	for movement in movementArray:
		var playerTilePosition = tileMap.local_to_map(global_position)
		var targetTilePosition = playerTilePosition + movement
		var targetPosition = tileMap.map_to_local(targetTilePosition) + offSet
		
		var tween := create_tween()
		tween.tween_property(get_parent(), "global_position", targetPosition, 0.3)
		
		await tween.finished
	
	isMoving = false
	
func get_tile_global_position(mousePosition):
	var mouseTilePosition := tileMap.local_to_map(mousePosition)
	var mouseTileData = tileMap.get_cell_atlas_coords(mouseTilePosition)

	if mouseTileData == Vector2i(-1, -1): return
	
	var tileGlobalPosition = tileMap.map_to_local(mouseTilePosition)
	
	return Vector2i(tileGlobalPosition)

# 贪婪算法来计算路径
func _get_route(targetPosition):
	var routeArray = []
	
	var direction = tileMap.local_to_map(targetPosition) - tileMap.local_to_map(global_position)
	var currentTilePosition = tileMap.local_to_map(global_position)

	while direction:
		var newPoint = _snap(direction, 1)

		# 检查是否是 (1,1) 或 (-1,-1) 的对角线移动
		if newPoint.y and newPoint.x and newPoint.y == newPoint.y:
			# 尝试先进行垂直方向的移动
			var checkPoint = Vector2i(newPoint.y, 0)
			
			# 检查垂直方向的格子是否有效（存在瓦片）
			if not _has_tile(currentTilePosition + checkPoint):
				# 如果垂直方向无效，则放弃垂直移动，只保留水平移动
				newPoint.y = 0
			else:
				# 如果垂直方向有效，则放弃水平移动，只保留垂直移动
				newPoint.x = 0
		
		#handle border
		if not _has_tile(currentTilePosition + newPoint):
			var points = [Vector2i(0,newPoint.y), Vector2i(newPoint.x, 0)]
			
			for point in points:
				if point == Vector2i.ZERO: continue
				
				if _has_tile(currentTilePosition + point):
					newPoint = point
				
		routeArray.append(newPoint)
		direction -= newPoint
		currentTilePosition += newPoint
	
	return routeArray
	
func _snap(vector, step: int):
	if vector.x > 0: vector.x = 1
	elif vector.x < 0: vector.x = -1
	
	if vector.y > 0: vector.y = 1
	elif vector.y < 0: vector.y = -1
	
	return vector
	
func _has_tile(tilePosition):
	var tileData = tileMap.get_cell_atlas_coords(tilePosition)
	return tileData != Vector2i(-1, -1)

横向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
extends Node2D

@export var tileMap : TileMapLayer
@export var offSet = Vector2(0, -6) # 这个偏移量可能需要根据你的精灵原点重新调整

var isMoving = false

func _input(event: InputEvent) -> void:
	if Input.is_action_just_pressed("leftClick"):
		_move()
		
func _move():
	if isMoving: return
	
	var mousePosition = get_global_mouse_position()
	var targetGlobalTilePosition = get_tile_global_position(mousePosition)
	
	if not targetGlobalTilePosition: return

	isMoving = true
	
	var movementArray = _get_route(mousePosition)

	for movement in movementArray:
		var playerTilePosition = tileMap.local_to_map(global_position)
		var targetTilePosition = playerTilePosition + movement
		var targetPosition = tileMap.map_to_local(targetTilePosition) + offSet
		
		var tween := create_tween()
		tween.tween_property(self, "global_position", targetPosition, 0.3) # 建议用 self 而不是 get_parent()
		
		await tween.finished
	
	isMoving = false
	
func get_tile_global_position(mousePosition):
	var mouseTilePosition := tileMap.local_to_map(mousePosition)
	var mouseTileData = tileMap.get_cell_atlas_coords(mouseTilePosition)

	if mouseTileData == Vector2i(-1, -1): return
	
	var tileGlobalPosition = tileMap.map_to_local(mouseTilePosition)
	
	return tileGlobalPosition # 返回 Vector2 即可

# --- 主要修改部分 ---
func _get_route(targetPosition: Vector2) -> Array:
	var routeArray = []
	
	var startTile = tileMap.local_to_map(global_position)
	var endTile = tileMap.local_to_map(targetPosition)

	# 如果已经在目标位置，直接返回空数组
	if startTile == endTile:
		return routeArray

	var currentTile = startTile

	# 使用一个简单的、朝向目标的步进算法（与横版六边形适配）
	while currentTile != endTile:
		var direction = endTile - currentTile
		var nextStep = Vector2i.ZERO

		# 优先处理对角线方向，因为横版六边形的对角线移动是最直接的
		# (1, -1) 和 (-1, 1)
		if direction.x > 0 and direction.y < 0:
			nextStep = Vector2i(1, -1)
		elif direction.x < 0 and direction.y > 0:
			nextStep = Vector2i(-1, 1)
		else:
			# 如果不能对角线移动，则按轴移动
			# 优先考虑 x 轴
			if direction.x != 0:
				nextStep.x = direction.x / abs(direction.x)
			# 如果 x 轴方向一致，则考虑 y 轴
			else:
				nextStep.y = direction.y / abs(direction.y)

		# 检查下一步是否有效（是否在地图上且是一个有效的瓦片）
		var targetNextTile = currentTile + nextStep
		if _is_tile_valid(targetNextTile):
			routeArray.append(nextStep)
			currentTile = targetNextTile
		else:
			# 如果对角线不可行，尝试单个轴向上的移动
			var possibleSteps = [Vector2i(nextStep.x, 0), Vector2i(0, nextStep.y)]
			var moved = false
			for step in possibleSteps:
				if step == Vector2i.ZERO:
					continue
				var targetTile = currentTile + step
				if _is_tile_valid(targetTile):
					routeArray.append(step)
					currentTile = targetTile
					moved = true
					break
			if not moved:
				# 如果两个方向都被阻挡，则路径失败，中断循环
				break

	return routeArray

# --- 辅助函数 ---

# 检查一个瓦片位置是否有效（存在且在地图边界内）
func _is_tile_valid(tilePosition: Vector2i) -> bool:
	# 检查是否超出地图边界
	if tilePosition.x < 0 or tilePosition.y < 0:
		return false
	if tilePosition.x >= tileMap.get_layer_width() or tilePosition.y >= tileMap.get_layer_height():
		return false
	
	# 检查该位置是否有瓦片
	var tileData = tileMap.get_cell_atlas_coords(tilePosition)
	return tileData != Vector2i(-1, -1)

# 这个函数在新的 _get_route 逻辑中不再被使用，可以删除
# func snap(vector, step: int):
# 	if vector.x > 0: vector.x = 1
# 	elif vector.x < 0: vector.x = -1
# 	
# 	if vector.y > 0: vector.y = 1
# 	elif vector.y < 0: vector.y = -1
# 	
# 	return vector

func _has_tile(tilePosition):
	var tileData = tileMap.get_cell_atlas_coords(tilePosition)
	return tileData != Vector2i(-1, -1)