寻路算法

寻路算法，可以看成是在一个图上，给定一个起始节点和结束节点，然后找到它们之间的联通路径。

• 可视化网站

---

以下的几种算法都是从开始点不断向外探索邻居节点，直到成功与终点相连。 它们共同维护以下的几个信息集合

• open_set：待处理节点
• closed_set：标记已遍历节点
• path_set：记录路径 而如果节点能够唯一映射成一个key，那么利用字典，就可以大大提高查找和比较的速度，为此需要引入
• get_node_key()：获取节点的key
• nodes_set：节点和key的字典，用于获取节点 除此之外，也需要实现
• get_neighbors() 用以获取节点周围的邻居。

那么其大致流程可以看做

获取邻居-->加入open_set-->按某种规则处理节点--->移入closed_set--->循环至无节点可处理

而下列几种算法的区别只在于处理规则上面

BFS算法

BFS全称广度优先算法，即优先处理比较近节点。

注意，BFS默认了处理的图是等权的，即节点距离是均匀的。 因为这个前提，只需建立一个普通队列(FIFO)，也就是open_set，而无需额外计算代价。

而lua中表的特性使得其十分容易实现。 下列代码中采用的方法是，插入表头，读取表尾，从而形成一个简单队列。

function bfs(config)
	--配置
	local start = config.start
	local goal = config.goal 
	local get_node_key = config.get_node_key
	local get_neighbors = config.get_neighbors
			
	--内部设置
	local open_set={
	local closed_set={}
	local path_set = {}
	local nodes_set = {}
	
	local start_key = get_node_key(start)
	local goal_key = get_node_key(goal)
	table.insert(open_set,start_key)
	nodes_set[start_key] = start
		
	while next(open_set) do
		--优先队列
		local curr_key = open_set[#open_set]
		--判断是否抵达
		if curr_key == goal then
			--恢复路径
			local path = {}
			local key = curr_key 
			while key do 
				table.insert(path)
				key = path_set[key]
			end
			return path 
		end
		--标记已处理
		closed_set[key] = true 
		--处理邻居
		local neighbors = get_neighbors(curr_key)
		for _,neighbor in ipairs(neighbors) do
			local key = get_node_key(neighbor)
			--加入节点网络中
			if not nodes_set[key] then
				nodes_set[key] = neighbor
			end
			-- 处理邻居		
			if not closed_set then
				table.insert(open_set,1,key)	
				path_set[key] = curr_key							
			end						
		end						
	end
	return nil 	
end

DFS算法

Astar算法

Astar算法是启发式的，与BFS算法不同的是，Asta算法在搜索过程中是知道终点的信息的，即在此引入的代价：

代价更新

---