广度优先遍历算法

说明

参考 Hello 算法

广度优先遍历算法是一种搜索算法。在游戏开发中经常使用该算法寻找路径或区域。

和他对应的算法为深度优先遍历

详述

需要遍历的数据结构通常应为多维矩阵、树或图。遍历中需要维护一个临时队列（存放找到但还没遍历的节点），根据结果不同，需要不同的输出类型（节点或队列）。

广度优先遍历通常先遍历与起始节点相邻的所有节点集合（S1），然后再遍历S1中所有相邻节点的集合（S2），然后依次类推，一层一层遍历，直到没有相邻节点或所有节点都已经遍历过。

举例

对于一个3*3二维矩阵A，需要从左上角开始遍历，则遍历代码如下。

extends Node2D

# 声明要遍历的矩阵和尺寸
var a = [
	[1,2,3],
	[4,5,6],
	[7,8,9]
]
var width = 3
var height = 3

func _ready() -> void:
	var start_pos = Vector2i(0, 0)
    # 将开始位置添加到遍历队列中
	var queue = [start_pos]
    # 设置遍历方向为右方和下方
	const direction = [
		Vector2i(0, 1),
		Vector2i(1, 0),
	]
    # 设置游标开始位置为0
	var index = 0
    # 游标移动到末尾后则停止
	while queue.size() > index:
		var temp_pos = queue[index]
		for direct in direction:
			var next_pos = direct + temp_pos
            # 判断是否越界
			if next_pos.x >= width or next_pos.y >= height:
				continue
            # 判断是否已经添加到queue中，未添加的则添加
			if not queue.has(next_pos):
				queue.push_back(next_pos)
        # 打印当前遍历的节点
		print(a[temp_pos.x][temp_pos.y])
        # 游标向后移动
		index += 1


# 输出结果为  1 2 4 3 5 7 6 8 9