概述
对于2D平台跳跃或飞机大战，以及一些直接用键盘方向键操控玩家的游戏，是根本用不到寻路的，因为只需要检测碰撞就可以了。
但是对于像RTS或战棋这样需要操控玩家到地图指定位置的移动方式，就绝对绕不开寻路了。
导航、碰撞与寻路
在Godot中导航(navigation)可以被理解为是可通行区域。
而碰撞(collision)是体积，指代障碍物，提示“不可通行”。
所以可以把导航和碰撞看做是反义的。也可以看做是0和1，true和false。有导航的地方就能通行，有碰撞的地方就不能通形。
而寻路(Pathfinding)则是指在可通行区域和不可通行区域中找出一条可以行走的路径，而且这条路径往往是最短的。
寻路算法
任何计算机问题，都会有多种不同的编程解法，计算机问题的编程解法就可以称为“算法”。而算法是跨语言的，同样的算法你可以用不同编程语言实现。
对于寻路问题，也会有不同的编程解法，也就是不同寻路算法。
A*(A-Star)就是前辈大神们创造的寻路算法之一。它的特点是基于网格，而且可以快速的求解某个点到另一个点的最短有效路径。
Godot的AStar是封装了A*(A-Star)算法的类，2D版本的AStar2D、AStarGrid2D也是如此。封装的好处是你不必从头实现算法，而是专注于使用。
Godot的AStar2D
AStar2D的使用思路是：
- 添加可以到达的位置
- 将可以行走的点两两连接，形成路径
- 通过其方法直接求取某个位置到目标位置的最短路径
- 让玩家或其他角色按照路径上点的顺序依次前进，直到到达目标位置
以下是对应上图的代码实现：
extends Node2D
var astar = AStar2D.new() # 实例化
func _ready():
# 添加可以到达的位置
astar.add_point(0,Vector2(0,0))
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 默认权重为 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 0))
# 在点之间创建连接，形成路径
astar.connect_points(1, 2, false)
astar.connect_points(2, 3, false)
astar.connect_points(4, 3, false)
astar.connect_points(1, 4, false)
# 查询某两个位置之间的路径
var res = astar.get_id_path(1, 4) # [1,4]
AStar2D就是如此简单。
add_point()的时候传入了一个ID，可以将其想象为是一个唯一索引值，对点的标记。get_id_path()方法获取的是两个对应ID的点之间的最短路径，返回的是包含路径经过的所有点的ID所组成的数组。- 你也可以用
get_point_path()方法直接获取两个点之间的最短路径，返回的额是包含所有经过的点数组。
定义网格
你可以看到，如果是单纯的使用Vector2(0,0)到Vector2(2,1)这样的坐标是毫无意义的，因为它们只代表屏幕上一个很小的像素区域，根本无法实现移动。
回过头看看上面对A*(A-Star)算法的描述:
A*(A-Star)就是前辈大神们创造的寻路算法之一。它的特点是基于网格，而且可以快速的求解某个点到另一个点的最短有效路径。
可以看到它是“基于网格”的。所以我们要使用AStar2D就需要基于网格。
这个网格可以是你自己用代码创建的，也可以是基于TileMap这样现成的网格体系。
比如如下代码，我们自定义了一个网格，并在屏幕上绘制。
extends Node2D
var astar = AStar2D.new() # 实例化
# 定义网格
var grid_size = Vector2i(32,32) # 尺寸 - 有多少行、多少列
var cell_size = Vector2i(32,32) # 单元格大小
func _ready():
# 添加可以到达的位置
astar.add_point(0,Vector2(0,0))
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 默认权重为 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 0))
# 在点之间创建连接，形成路径
astar.connect_points(1, 2, false)
astar.connect_points(2, 3, false)
astar.connect_points(4, 3, false)
astar.connect_points(1, 4, false)
# 查询某两个位置之间的路径
var res = astar.get_id_path(1, 4) # [1,4]
func _draw():
# 绘制网格
for x in grid_size.x:
for y in grid_size.y:
draw_rect(Rect2i(Vector2i(x,y) * cell_size,cell_size),Color.YELLOW,false,1)
运行效果：
绘制Astar的点和路径到网格
extends Node2D
var astar = AStar2D.new() # 实例化
# 定义网格
var grid_size = Vector2i(32,32) # 尺寸 - 有多少行、多少列
var cell_size = Vector2i(32,32) # 单元格大小
func _ready():
# 添加可以到达的位置
astar.add_point(0,Vector2(0,0))
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 默认权重为 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 0))
# 在点之间创建连接，形成路径
astar.connect_points(1, 2, false)
astar.connect_points(2, 3, false)
astar.connect_points(4, 3, false)
astar.connect_points(1, 4, false)
# 查询某两个位置之间的路径
var res = astar.get_id_path(1, 4) # [1,4]
func _draw():
# 绘制网格
for x in grid_size.x:
for y in grid_size.y:
draw_rect(Rect2i(Vector2i(x,y) * cell_size,cell_size),Color.YELLOW,false,1)
# 绘制点
for i in range(astar.get_point_count()):
var pos = astar.get_point_position(i) * Vector2(cell_size) + Vector2(cell_size/2)
draw_circle(pos,10,Color.YELLOW)
extends Node2D
var astar = AStar2D.new() # 实例化
# 定义网格
var grid_size = Vector2i(32,32) # 尺寸 - 有多少行、多少列
var cell_size = Vector2i(32,32) # 单元格大小
func _ready():
# 添加可以到达的位置
astar.add_point(0,Vector2(0,0))
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 默认权重为 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 0))
# 在点之间创建连接，形成路径
astar.connect_points(1, 2, false)
astar.connect_points(2, 3, false)
astar.connect_points(4, 3, false)
astar.connect_points(1, 4, false)
# 查询某两个位置之间的路径
var res = astar.get_point_connections(1)
print(res)
func _draw():
# 绘制网格
for x in grid_size.x:
for y in grid_size.y:
draw_rect(Rect2i(Vector2i(x,y) * cell_size,cell_size),Color.YELLOW,false,1)
# 绘制点
for i in range(astar.get_point_count()):
var pos = get_grid_pos(astar.get_point_position(i))
draw_circle(pos,5,Color.YELLOW)
# 绘制所有路径
for i in range(astar.get_point_count()):
var pos = get_grid_pos(astar.get_point_position(i))
if i+1 <= astar.get_point_count():
var pos2 = get_grid_pos(astar.get_point_position(i+1))
draw_line(pos,pos2,Color.GREEN_YELLOW,2)
# 返回屏幕中的点或路径中的点对应在网格中的坐标
func get_grid_pos(point_pos:Vector2):
return point_pos * Vector2(cell_size) + Vector2(cell_size/2)
extends Node2D
var astar = AStar2D.new() # 实例化
# 定义网格
var grid_size = Vector2i(32,32) # 尺寸 - 有多少行、多少列
var cell_size = Vector2i(32,32) # 单元格大小
func _ready():
# 添加可以到达的位置
astar.add_point(0,Vector2(0,0))
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 默认权重为 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 0))
# 在点之间创建连接，形成路径
astar.connect_points(1, 2, false)
astar.connect_points(2, 3, false)
astar.connect_points(4, 3, false)
astar.connect_points(1, 4, false)
# 查询某两个位置之间的路径
var res = astar.get_point_connections(1)
print(res)
func _draw():
# 绘制网格
for x in grid_size.x:
for y in grid_size.y:
draw_rect(Rect2i(Vector2i(x,y) * cell_size,cell_size),Color.YELLOW,false,1)
# 绘制点
for i in range(astar.get_point_count()):
var pos = get_grid_pos(astar.get_point_position(i))
draw_circle(pos,5,Color.YELLOW)
# 绘制所有路径
for i in range(astar.get_point_count()):
var pos = get_grid_pos(astar.get_point_position(i))
if i+1 <= astar.get_point_count():
var pos2 = get_grid_pos(astar.get_point_position(i+1))
draw_line(pos,pos2,Color.GREEN_YELLOW,2)
# 绘制寻找到的路径
var path = astar.get_point_path(1,4)
for i in path.size()-1:
var pos = get_grid_pos(path[i])
if i+1 <= path.size():
var pos2 = get_grid_pos(path[i+1])
draw_line(pos,pos2,Color.RED,2)
# 返回屏幕中的点或路径中的点对应在网格中的坐标
func get_grid_pos(point_pos:Vector2):
return point_pos * Vector2(cell_size) + Vector2(cell_size/2)
