基于Godot的A*寻路算法
基于Godot的A*寻路算法
以下写的是四连通的情况，但其实完全可以类推到六连通和八连通
首先是Astar寻路的四个要点：
- 寻路消耗公式f = g + h（虽然我并不知道为什么一定是这三个字母而不是a = b + c）
- open开启列表
- close关闭列表
- 反向遍历
寻路消耗公式
f = g + h
其中，f为寻路消耗，g为起点到计算点的切比雪夫距离，h为计算点到终点的曼哈顿距离
为什么是切比雪夫距离？经典的版本是欧氏距离，但依旧如题，这里要涉及到消耗，所以我会更偏向使用切比雪夫距离，下方解释一下三个距离
三个距离
欧几里得距离（欧氏距离）的计算公式是横坐标差的平方加纵坐标差的平方的和开根号，当对ai体的灵活度有要求时，就会用这个距离代表g
曼哈顿距离的计算公式是横坐标差的绝对值加纵坐标差的绝对值，一般用来衡量计算点到终点的远近
切比雪夫距离没有很明确的计算公式，如果非要有的话那应该就是对经过的所有格子的消耗求和，所以一般说到消耗都是切比雪夫距离
open开启列表和close关闭列表
open用来存储已访问但未放入路径的格子，close用来存储放入路径的格子，Astar计算出的路径就是close的子集
open通常需要包含的数据有：计算格父级的坐标，计算格的f，g，h，计算格的坐标 close需要包含的数据有：计算格父级的坐标，计算格的坐标
实现理论过程
前提：假设所有格子都继承于一个类Grid(父类是Node2D)，访问格子时可以访问到它的坐标，移动消耗，同时有一个格子管理器GridManager(父类是Node)，所有格子都是这个管理器的子节点
我们要求Astar脚本的核心功能：输入起点和终点坐标，格子管理器的引用，若寻路成功，输出下一步要移动到的格子坐标
步骤如下：
- 把起点放入开启列表中
- 开始循环，在开启列表中寻找f最小的最优格，将其放入关闭列表，并从开启列表中移除（可能会存在有几个格子的情况，所以这里存储找到的格子需要是一个列表，但返回到后续过程的结果一定是一个格子，假如f相同就找h，再相同就找g，再相同就随机）
- 遍历最优格四连通区域的格子，将这些格子放入开启列表中（需要注意一下放入到开启列表中的元素，最优格的坐标会作为这些放入开启列表的格子的父级坐标一并放进去）
- 持续循环，直到开启列表为空或最优格为终点，若开启列表为空，则返回寻路失败，若最优格为终点，则寻路成功，则将终点放入关闭列表并结束循环
- 反向遍历，从关闭列表的最后一个元素（即终点）开始，访问其计算格父级坐标，与关闭列表中元素的计算格坐标比对，以此找到其父级，以此循环，知道访问到父级坐标为起点坐标时结束遍历，返回计算格坐标，即为输出
代码实现
(约定地图起始格子坐标为(0,0)，那么(-1,-1)格即为不存在格，用作初始化)
首先我们需要明确一下格子类内包含的变量是哪些
extends Node_2D
class_name Grid
var index : Vector2i
var cost : float
var parent : GridManager
func initialize(parameter : GridManager) -> void:
parent = parameter
#这里是依赖注入的写法，写习惯了带一笔接下来是GridManager的脚本，A*算法主要得从这里根据坐标返回格子对象
extends Node
class_name GridManager
var parent : Node #这里的是GridManager的父级
func initialize(parameter : Node) -> void:
parent = parameter
for child in get_children():
if child is Grid:
child.initialize(self)
func index2grid(index : Vector2i) -> Grid:
for child in get_children():
if child is Grid:
if child.index == index:
return child接下来就是寻路算法的核心脚本，输入管理器、起点和终点坐标，输出接下来要走的坐标，具体看注释，这里不赘述了
extends Node
class_name AStar
func main(grid_manager : GridManager , start_index : Vector2i , end_index : Vector2i) -> Vector2i: #明确算法的输入输出
var result : Vector2i #结果
var open_list : Dictionary
var close_list : Dictionary
#这里明确这两个list中的数据结构分别为{计算点坐标 : [[计算点父级坐标] , [f,g,h]]}和{计算点坐标 : 计算点父级坐标}
open_list[start_index] = [[Vector2i(-1,-1)] , [get_MHD(start_index , end_index),0,get_MHD(start_index , end_index)]]
#初始化open_list
var end_flag : bool = false
while end_flag == false:
var best_element_index : Vector2i = get_best_element_index(open_list)
var best_element_parent_index : Vector2i = open_list[best_element_index][0][0]
#以上是对open_list的处理
close_list[best_element_index] = best_element_parent_index
#把最优格放入close_list
var cross_grids_index : Array[Vector2i] = get_cross_grids_index(grid_manager,best_element_index)
for cross_grid_index in cross_grids_index:
var cross_grid_index_dictionary : Dictionary
#数据结构为{计算点坐标 : [f,g,h]}
var g : float = grid_manager.index2grid(cross_grid_index).cost + open_list[best_element_index][1][1]
var h : int = get_MHD(cross_grid_index,end_index)
var f : float = g + h
cross_grid_index_dictionary[cross_grid_index] = [f,g,h]
#这个要着重看，精髓在此
open_list[cross_grid_index] = [[best_element_index] , cross_grid_index_dictionary[cross_grid_index]]
#处理父级
if h == 0:
close_list[end_index] = best_element_index
end_flag = true
break
open_list.erase(best_element_index)
#记住一定要删，不然会重复选中
if open_list.size() == 0:
return Vector2i(-1,-1)
end_flag = false
result = end_index
while end_flag == false:
if close_list[result] == start_index:
end_flag = true
return result
result = close_list[result]
#下面补充工具函数
#这个函数的目的是返回open_list中的最优元素的格子坐标
func get_best_element_index(open_list : Dictionary) -> Vector2i:
var result : Vector2i = Vector2i(-1,-1)
var f_result : Array[Vector2i] = []
#用于存储比较值可能重复的结果
var calculation_index : Array[Vector2i]
var calculation_index_parameter : Array[Array]
var min_f_index_array : Array[Vector2i]
var min_g_index_array : Array[Vector2i]
var min_h_index_array : Array[Vector2i]
for key in open_list.keys():
calculation_index.append(key)
calculation_index_parameter.append(open_list[key][1])
for index in calculation_index:
if result == Vector2i(-1,-1):
result = index
#这里是初始化
var num : int = calculation_index.find(index)
#这个是计算点坐标的索引
var result_num : int = 0
if calculation_index_parameter[num][0] <= calculation_index_parameter[result_num][0]:
result = calculation_index[num]
result_num = num
f_result.append(result)
if f_result.size() == 1:
return result
else:
var g_result : Array[Vector2i] = []
for index in f_result:
var num : int = calculation_index.find(index)
var result_num : int = 0
if calculation_index_parameter[num][1] <= calculation_index_parameter[result_num][1]:
result = calculation_index[num]
result_num = num
g_result.append(result)
if g_result.size() == 1:
return result
else:
var h_result : Array[Vector2i] = []
for index in g_result:
if calculation_index_parameter[num][2] <= calculation_index_parameter[result_num][2]:
result = calculation_index[num]
result_num = num
h_result.append(result)
if h_result.size() == 1:
return result
else:
var size = h_result.size()
var random_num = randi(0,size)
return h_result[random_num]
#这里的f,g,h属实屎山了,但没办法,为了理解简单就这样写吧，反正就是优先找f最小，然后g最小，最后h最小，假如有都相同的，那就随机返回
#这个函数的目的是返回目标坐标四连通区域的格子坐标
func get_cross_grids_index(grid_manager : GridManager,best_element_index : Vector2i) -> Array[Vector2i]:
var result : Array[Vector2i]
var directions : Array[Vector2i] = [Vector2i(0,1),Vector2i(0,-1),Vector2i(-1,0),Vector2i(1,0)]
for direction in directions:
target : Vector2i = best_element_index + direction
if grid_manager.index2grid(target):
result.append(target)
return result
#这个函数的目的是得到两个坐标间的曼哈顿距离
func get_MHD(start_index : Vector2i,end_index : Vector2i) -> int:
return abs(start_index.x - end_index.x)+abs(start_index.y - end_index.y)英明神武的ai大人告诉我我写的代码非常屎，是的，它是对的，以上的代码仅仅停留在能看和能用的阶段，距离好用还差很长的一段距离，比如其中某些函数有更好的写法，某些地方缺乏健壮性等（其实我不喜欢这个词，我就理解为更安全更经得住乱造）
但没关系，本篇仅供用于参考A*算法的思路，至于写进游戏，还需要更多的适配性（比如Grid和GridManager还需要优化等）
（狗头叠甲）
以上
最后更新于