基于js的A星算法自动寻路的实现VIP

第8章Canvas游戏,利用A*算法查找最短路径,JS的递归,JS中递归的另一种实现arguments是任何函数对象都具有的一个属性对象，当我们调用一个函数时，传递给函数的参数都填写在这个属性对象中。这个用来保存参数的属性对象自身也有一个callee属性，它指向容纳它的函数对象。左上图代码中，arguments包含在函数对象a中，arguments的callee就是a。把左上图代码换成左下图代码，效果完全相同，但左下图由于引用了函数外面的变量a，不能体现封装的思想。比如想把函数变量名a改变为b，就得函数内部本身,定义函数的同时进行调用,第31-32是定义一个函数，然后调用它。我们通常这么做。第34-35行我们换一种形式定义一个函数然后调用它。第37行定义一个函数立即调用它，函数名为a第38行也是定义一个函数立即调用它，函数名为a第39行也定义一个函数立即调用它，没有函数名总结：把函数定义放在一对小括号内表示执行函数再用一对小括号来给正在执行的函数传参数当一个函数不需要被多次调用时，也就是说只会被调用一次，其函数名根本没任何作用，我们就可以采用第39行的方式来定义并调用这个函数,闭包,21-27行定义了函数a，并a内部定义了一个函数b，把函数对象b作为a的返回值第28行右边执行a()后得到一个函数对象，把它赋给c第29行执行c对象，实际上就是执行b函数。左下图代码与左上图代码执行效果完全相同,使用闭包的一个明显的好处就是不使用全局变量，但又可以让局部变量象全局变量一样一直保存在内存中，在需要的时候可以随时通过某种方式来访问它。思考：运行结果,思考下列代码运行结果？如果把第50行的3换成2输出结果又是多少？,A*算法是什么,A*算法的作用是用于寻找从起点到终点的最短路径。绿方块表示起点，红方块表示终点，蓝方块表示障碍物,代价的计算G：从起点出发沿当前路径到达自己的路径长度，方格左下角数字H：从自己出发到达终点的估计长度，方格右下角数字F：路径代价。方格左上角数字算法核心思路每次选择路径代价最小作为理想节点，沿着理想节点一直走下去，如果走不通，再回过头来选择次理想节点再走，直到能走通。,A*算法的伪代码,将起始节点加入到Open表while(Open表不空)从Open表中选择代价最低的节点作为当前节点if（当前节点是目标节点）得到最短路径，结束算法else将当前节点移入到Closed表找出当前节点的所有邻居foreach(邻居节点)if(节点不在Open表中并且不在Closed表中并且不是障碍物计算节点的路径代价然后把它移到Open表,算法实现,定义相关数据结构open和close分别代表待处理的节点列表和已处理完毕的节点列表tra_marker：可通过标记。如果一个节点的标记值不是tra_marker，则表示此节点为障碍物。,代码总体结构,第1行声明了一个window的属性对象AStar，AStar为一个空对象，它不起任何实质性的作用，只是利用它来封装find_path等函数第2行到第88行定义并执行了一个匿名函数，AStar对象作为参数被传递到了匿名函数内部，匿名函数内部将为它定义一个find_path方法。匿名函数内部另外还定义了二个方法arr_sort和is_exist，这两个方法在find_path方法中要用到，接下来首先介绍这两个方法。,arr_sort方法第70行的“=”号右边开始的匿名函数执行后返回的函数对象被arr_sort所引用。第71-73行定义了一个函数用于比较两个节点a和b的大小。在这个算法的实现代码用一个长度为5的数组x,y,G,F,father表示一个节点，所以下面代码中的a3，b3指的是节点a和b的F值，也就是节点的路径代价，它被用作排序的依据。如果a的F值小于b的F值，则s函数将返回一个负数，数组的sort方法就会认为a对象小于b对象，从而把a排在b前面。,is_exist方法,判断一个点p是否在数组arr中p是一个长度为2的数组，p0表示横坐标，p1表示纵坐标这里的arr对象要么是open表，要么就是close表，不管哪个表，里面存储的每个元素都是节点五元组（x,y,G,F,father），所以arri0表示节点i的横坐标,arri1表示节点i的纵坐标如果arr中存在一个与p相同的横纵坐标，则表明p已经存在于arr中，返回其位置，此位置值是一个非负数。如果不存在，则返回一个负数。,A*算法的JS实现,find_path方法利用传入的参数初始化局部变量将起始节点放入open表返回第25行定义的匿名函数的执行结果。这个匿名函数的作用是处理指定节点。说明：为了演示方便，截图时对源代码进行了格式上的更改，所以同样的代码不同的截图中行号并不一致，阅读时请注意。,这个用于处理一个节点的匿名函数实际上是一个递归函数，它不断地从open表中取出第0个元素作为参数调用自己，直到open表为空。递归结束后最终返回一个数组，包含了最短路径上的所有节点，如果路径不存在，将返回空数组。对照A*算法，这个匿名函数利用递归来实现算法中的while循环，函数内部的代码将完成while循环内要完成的工作。,函数定义结束后立即调用,Open表不空条件下递归调用,处理一个节点,整个匿名函数的工作分为四个部分，如图。其中第36行和第61行描述的工作是可以互换的,如果obj是目标节点，则输出路径回顾下节点五元组：x,y,G,F,father，obj0和obj1及e_p0和e_p1分别表示当前节点及终点的横、纵坐标，如果它们相等，说明当前节点就是终点。ele4表示ele节点的父节点，unshift函数用于将一个元素加入数组的前面。输出路径的过程就是不断地根据father指针进行回溯（30-33行），依次将当前节点的父节点加入到ways数组的前面，当回溯到起点时，由于起点的father为null，故循环结束，得到了完整路径。,遍历obj的全部邻居,穿越情况：如图，绿色表示起点，黑色表示障碍物，蓝色表示路径。显然，路径穿越了障碍物，不符合实际情况。排除穿越的思路出现穿越时一定是邻居与当前节点处于对角线的情况，比如图中的绿色方块和左起第一个蓝色方块故只需检查另一条对角线上的两个方块是否是障碍物，如果是，则忽略此邻居。因为它被阻挡了与当前节点呈对角关系的邻居的坐标特点是横、纵坐标均不相同，另一对角线的的两个点的坐标特点是横、纵坐标一个与当前节点相同，另一个与邻居节点相同。当前节点坐标分别是obj0，obj1，邻居节点坐标为i,j，,如果邻居既不在open表，也不在close表，并且可通过，则计算其代价后放入open表is_exist用于判断当前节点是否在一个数组中G的计算方式：如果邻居与当前节点横纵坐标有一个相同，则新距离为1，否则为1.4，然后将当前节点的G值与新距离相加作为当前邻居的G值。H的计算方式：使用两点之间的距离公式计算当前邻居与终点的距离open.push(i,j,G,F,obj);这行代码将邻居放入open表。放入open表的邻居节点除了坐标属性i和j之外，还增加G，F，和obj三个属性：其中G保存了到起点的实际距离F是一个估价函数，主要用于排序，它的大小反映了节点的“好坏”，越小说明越好。obj是父节点，也就是把当前节点作为邻居的父节点，用于回溯路径。,将open表排序，递归处理open0arr_sort是按F值对节点进行排序的，估价值最小的节点始终排列在open表的最前面如果open表不空，则继续取出open0作为当前节点递归处理如果open表为空，说明路径不存在，所以返回空数组。如果路径存在，则在进入