# “AS3.0高级动画编程”学习：第四章 寻路（AStar/A星/A*）算法 (上)

g代表(从指定节点到相邻)节点本身的代价--即上图中的1或1.4

h代表从指定节点到目标节点（根据不同的估价公式--后面会解释估价公式）估算出来的代价。

```package {
public class Node
{
public var x:int;
public var y:int;
public var f:Number;
public var g:Number;
public var h:Number;
public var walkable:Boolean=true;//是否可穿越（通常把障碍物节点设置为false）
public var parent:Node;
public var costMultiplier:Number=1.0;//代价因子

public function Node(x:int, y:int)
{
this.x=x;
this.y=y;
}
}
}```

```package
{

public class Grid
{
private var _startNode:Node;//开始节点
private var _endNode:Node;//目标节点
private var _nodes:Array;//节点数组
private var _numCols:int;//列数
private var _numRows:int;//行数

public function Grid(numCols:int, numRows:int)
{
_numCols=numCols;
_numRows=numRows;
_nodes=new Array();
for (var i:int=0; i < _numCols; i++)
{
_nodes[i]=new Array();
for (var j:int=0; j < _numRows; j++)
{
_nodes[i][j]=new Node(i, j);
}
}
}

public function getNode(x:int, y:int):Node
{
return _nodes[x][y] as Node;
}

public function setEndNode(x:int, y:int):void
{
_endNode=_nodes[x][y] as Node;
}

public function setStartNode(x:int, y:int):void
{
_startNode=_nodes[x][y] as Node;
}

public function setWalkable(x:int, y:int, value:Boolean):void
{
_nodes[x][y].walkable=value;
}

public function get endNode():Node
{
return _endNode;
}

public function get numCols():int
{
return _numCols;
}

public function get numRows():int
{
return _numRows;
}

public function get startNode():Node
{
return _startNode;
}
}
}```

```//曼哈顿估价法
private function manhattan(node:Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
}

//几何估价法
private function euclidian(node:Node):Number
{
var dx:Number=node.x - _endNode.x;
var dy:Number=node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}

//对角线估价法
private function diagonal(node:Node):Number
{
var dx:Number=Math.abs(node.x - _endNode.x);
var dy:Number=Math.abs(node.y - _endNode.y);
var diag:Number=Math.min(dx, dy);
var straight:Number=dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}```

“几何算法”的最好解释就是“勾股定理”，算出起点与终点之间的直线距离，然后乘上代价因子。

“对角算法”综合了以上二种算法，先按对角线走，一直走到与终点水平或垂直平行后，再笔直的走。

```package
{
import flash.display.Sprite;

public class GridTest extends Sprite
{
private var _endNode:Node;
private var _startNode:Node;
private var _straightCost:Number=1.0;
private var _diagCost:Number = 1.4;

public function GridTest()
{
var g:Grid=new Grid(5, 5);
g.setStartNode(0, 3);
g.setEndNode(4, 1);

_endNode = g.endNode;
_startNode = g.startNode;

var c1:Number = manhattan(_startNode);//8
var c2:Number = euclidian(_startNode);//4.47213595499958
var c3:Number = diagonal(_startNode);//4.8

trace(c1,c2,c3);
}

//曼哈顿估价法
private function manhattan(node:Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y - _endNode.y) * _straightCost;
}

//几何估价法
private function euclidian(node:Node):Number
{
var dx:Number=node.x - _endNode.x;
var dy:Number=node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}

//对角线估价法
private function diagonal(node:Node):Number
{
var dx:Number=Math.abs(node.x - _endNode.x);
var dy:Number=Math.abs(node.y - _endNode.y);
var diag:Number=Math.min(dx, dy);
var straight:Number=dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}
}
}```

0 条评论

• ### flash：二次贝塞尔曲线应用-生成飞机路径示意图

本周听到公司其它项目组同事在讨论一个小需求： 给定3个点（其实是飞机经过的航站，比如：从浦东-西安-北京），在UI上生成一段曲线，用来示意飞机的路线图（其实用直...

• ### springBoot学习（三）springBoot事件监听和部分注解的运用

1.springBoot启动类会使用@SpringBootApplication 2.点进入源代码发现改注解是一个复合注解，由好几个注解共同组合而成

• ### springBoot学习（三）springBoot事件监听和部分注解的运用

1.springBoot启动类会使用@SpringBootApplication 2.点进入源代码发现改注解是一个复合注解，由好几个注解共同组合而成

• ### Spring注解浅入浅出——不吹牛逼不装逼

上文书咱们说了《Spring浅入浅出》，对Spring的核心思想看过上篇的朋友应该已经掌握了，此篇用上篇铺垫，引入注解，继续深入学习。

• ### 聊聊skywalking的spring-webflux-plugin

skywalking-6.6.0/apm-sniffer/optional-plugins/optional-spring-plugins/spring-web...

• ### Java并发编程实战系列15之原子遍历与非阻塞同步机制(Atomic Variables and Non-blocking Synchronization)

近年来，在并发算法领域的大多数研究都侧重于非阻塞算法，这种算法用底层的原子机器指令来代替锁来确保数据在并发访问中的一致性，非阻塞算法被广泛应用于OS和JVM中实...

• ### Spring Boot整合Ehcache实现缓存功能

这里介绍Spring Boot结合JPA，MySQL和Ehcache实现缓存功能，提高程序访问效率。