C++八方向Astar寻路算法大作业.pdfVIP

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 2 T 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 S 8 编程实现从S 到T 的最短路径算法，运动方向为上下左右。在图上给出最终的路径，以及有哪些信誉好的足球投注网站的过程。算法建 议使用A*。 作业上交时间：最后一节课前发送到课程邮箱。包括源代码，以及运行出来的效果图。 第1 页，共 9 页 Homework3： Solution: 1、算法分析： 地图的构建，需要定义一个整型二维数组，障碍位置为1，可通过点为0；同样定义坐标 点结构体，以存放每个点的行列GHF 父结点等信息。 Astar 算法要用到两个表来存放将要有哪些信誉好的足球投注网站的结点和还未有哪些信誉好的足球投注网站的结点，分别是开放列表 openList 和封闭列表openList，Astar 算法的计算步骤如下： ① S→openList ② S 邻居→openList openList→S→closeList ③ S 邻居有8 个如何确定先检查哪个？ G 移动成本(10/14) H Manhattan 距离 H=(|e_r-r|+|e_c-c|)*10 F=G+H S=F 最小的点 ④ 重复②③，openList=NULL 未到终点，说明无通路。当endPoint 在开放表中的 时候，说明已经找到通路，根据每个结点的父结点信息，通过回溯可以找出通 路。 NOTE : 在第②步中检查邻居时，以下几点需要注意： ① 若邻居结点已经在封闭表closeList 中，可以直接忽略。 ② 若邻居结点不在开放表openList 和封闭表closeList 中，计算GHF 的值，并设置 该结点的父亲结点 ③ 若邻居结点已经在开放表openList 中，若能得到更小的G 值则重新计算GHF 的值 并更新父结点 第2 页，共 9 页 2、程序实现： /************************************************************************* File Name: Astar.cpp Author: lx Created Time: Sat 15 Apr 2017 05:30:12 PM CST ************************************************************************/ #includeiostream #includemath.h #includefstream #includestring #def