DFdou's Blog Life is short,Be yourself.

AStar(A星算法)-Grid Class

A星算法中需要用到网格类，至于网格类是干嘛的，只不过是保存信息的网格，没有实际意义。
Grid.as:

package {
	/**
	* Holds a two-dimensional array of Nodes methods to manipulate them, start node and end node for finding a path.
	*/
	public class Grid{
		private var _startNode:Node;
		private var _endNode:Node;
		private var _nodes:Array;
		private var _numCols:int;
		private var _numRows:int;
		/**
		* Constructor.
		*/
		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 methods
		////////////////////////////////////////
		/**
		* Returns the node at the given coords.
		* @param x The x coord.
		* @param y The y coord.
		*/
		public function getNode(x:int,y:int):Node {
			return _nodes[x][y] as Node;
		}
		/**
		* Sets the node at the given coords as the end node.
		* @param x The x coord.
		* @param y The y coord.
		*/
		public function setEndNode(x:int,y:int):void {
			_endNode = _nodes[x][y] as Node;
		}
		/**
		* Sets the node at the given coords as the start node.
		* @param x The x coord.
		* @param y The y coord.
		*/
		public function setStartNode(x:int,y:int):void {
			_startNode = _nodes[x][y] as Node;
		}
		/**
		* Sets the node at the given coords as walkable or not.
		* @param x The x coord.
		* @param y The y coord.
		*/
		public function setWalkable(x:int,y:int,value:Boolean):void {
			_nodes[x][y].walkable = value;
		}
		////////////////////////////////////////
		// getters / setters
		////////////////////////////////////////
		/**
		* Returns the end node.
		*/
		public function get endNode():Node {
			return _endNode;
		}
		/**
		* Returns the number of columns in the grid.
		*/
		public function get numCols():int {
			return _numCols;
		}
		/**
		* Returns the number of rows in the grid.
		*/
		public function get numRows():int {
			return _numRows;
		}
		/**
		* Returns the start node.
		*/
		public function get startNode():Node {
			return _startNode;
		}
	}
}

代码简洁明了，传入行数和列数就可以构建一个网格，然后就是getters / setters。

AStar(A星算法)-Node Class

刚好在书上看到A星算法，今天先来讲下会用到的一些术语。
A星算法是一种静态路网中求解最短路径最有效的方法。恰当的使用，A星算法肯定能找出两点之间的最佳路径而且效率相当高。
节点(node)：本质上就是方形网格里的某一个方格(yujjj注：为什么不把他们描述为方格？因为在一些时候划分的节点不一定是方形的，矩形、六角形、或其它任意形状，本书中只讨论方格)。由此可以看出，路径将会由起点节点，终点节点，还有从起点到终点经过的节点组成。
代价(cost)：这是对节点优劣分级的值。代价小的节点肯定比代价大节点更好。代价由两部分组成：从起点到达当前点的代价和从这个点到终点的估计代价。代价一般由变量f，g和h，具体如下。
f：特定节点的全部代价。由g+h决定。
g：从起点到当前点的代价。它是确定的，因为你肯定知道从起点到这一点的实际路径。
h：从当前点到终点的估计代价。是用估价函数(heuristic function)计算的。它只能一个估算，因为你不知道具体的路线——你将会找出的那一条。
估价函数(heuristic)：计算从当前点到终点估计代价的公式。通常有很多这样的公式，但他们的运算结果，速度等都有差异(yujjj注：估价公式计算的估计值越接近实际值，需要计算的节点越少；估价公式越简单，每个节点的计算速度越快)。
待考察表(open list)：一组已经估价的节点。表里代价最小的节点将是下一次的计算的起点。
已考察表(closed list)：从待考察表中取代价最小的节点作为起点，对它周围8个方向的节点进行估价，然后把它放入“已考察表”。
父节点(parent node):以一个点计算周围节点时，这个点就是其它节点的父节点。当我们到达终点节点，你可以一个一个找出父节点直到起点节点。因为父节点总是带考察表里的小代价节点，这样可以确保你找出最佳路线。