Astar算法详解.docx

A*算法详解 今天刚开通了百度博客，这也是我在这里的第一篇文章,以后会在此写下我学习AS3的一些心得和技巧,方便自己日后的复习也让一些新手门能快速的入门,那么，开门见山,第一篇就写AS3版的A*算法吧。 那么，我个人习惯不喜欢把简单的东西往复杂了搞，虽然复杂代表着规范，和严谨，但是处于学习的目的，我给出的A*算法，相当的简单和实用,当然重点是算法思想，下面就跟随我的指示太了解A*算法吧。 那么什么是A*，其实就是在很多障碍物的地图上，物体从A点移动到B点的路径,当然，光要路径也不对，我们要找的就是其中最短的一条，这样问题就来了，如何才能找到最短的一条呢？首先，我们得有一个标准来验证。我们需要一个探路器和节点,比如我们每走一步都会用探路器在我们周围的8个点上放上节点,然后每个节点会返回出他们的代价,我们根据探路器的指示，找到代价最少的节点，然后下一步就走到了那里，然后继续上面的操作,那么，原理是很简单的，我们先需要一个节点类(node),节点类要做的事情就是返回出代价，至于怎么返回请看下面: 假设我们在地图上每走一步都需要消耗代价,比如直线走一格是10代价,斜线走是14代价,那么我们可以根据以下的公式计算代价:F=H+G总代价=目标到当前的直线代价+从开始节点到当前节点的移动代价那么，其实看到这里我们就只要，需要3个函数,F函数和H函数还有G函数，那么可以写成:function F():int{H()+G();}好了，到了这里，A*算法我们已经完成一半了,现在只要去实现H和G了，那么继续看:public function getH():int { return Math.abs(h - Goal_node.h) * 10 + Math.abs(l - Goal_node.l) * 10; //返回目标到当前的直线代价 }哇，好少了啊，对，就一行,H计算的是目标节点到当前节点所消耗的代价,注意了：只需要计算行和列，斜线的不算，当然不能少了取绝对值,我们不需要负数,之前我们说了直线的代价是10，所以我们把他们的代价都*上10，当然你可以根据自己需求来*上不同的代价,OK,H搞定了,下面来看看G：public function getG():int { if (Math.abs(h - Start_node.h) == 1 Math.abs(l - Start_node.l) == 1) { return 14+Father_int; //返回父节点的带价值和当前节点到开始节点值等于一路走过来的带价值 } else { return Math.abs(h - Start_node.h) * 10 + Math.abs(l - Start_node.l) * 10 + Father_int; //同上 } } //返回从开始节点到当前节点的移动代价//G函数比H函数多了一点，就是计算斜角的代价，但是，记住，这个斜角只是当前节点的左上，左下，右上，右下的那一格，那么如何来计算是否是斜角呢？其实只要计算当前行减去父节点和列减去父节点的列是否都等于1，这里也一样需要取绝对值，如果都为1则说明不在同一行也不在同一列,Father_int是什么呢？是父节点的代价,G函数计算的是当前的代价还要加上父节点的代价，才能算出开始节点到当前节点的总代价,到了这里A*逻辑部分已经完成一大半了，最后我们还需要将找到的路径保存进一个数组里,看下面代码:public function getPath():Array { if (Father_node== this) { var ccc:Array=new Array(); ccc=[[h, l]]; return ccc; } else { var aa:Array = Father_node.getPath(); var answer:Array=aa.slice(0,aa.length); answer[aa.length] =[h, l]; return answer; } }太少了,对，就是这么简单啦,首先我们检测目标节点的父节点是否等于自己,等于自己说明达到了起点,因为起点是没有父节点的，所以我们就设为是自己,好,先就此打住，看看下面的else,这里我们用了递归来寻找节点,首先我们新建立一个数组等于父节点返回的节点,然后在把它拷贝一份进新的输入,因为FLASH的数组是动态的，所以我们直接在尾部answer[aa.length] 添加进当前节点的行和列,最后返回,直到返回到父节点也把自己的坐标返回了，整个递归调用结束,最后我们需要知道我们是否已经找到目标了,其实我们就可以直接判断当前的节点是否是目标节点:public function equals(me:Object):Boolean { if (me