一 演示效果
二 参考教程
《ActionScript3.0 高级动画教程》 + 源码
http://download.csdn.net/download/zhengchengpeng/7756023
三 AStar源码
Main.ts新建Game，即可看Demo
this.addChild(new Game())
源码地址：
https://files.cnblogs.com/files/gamedaybyday/astar_ts.rar
AStar核心类
/**
* A星寻路
* @author chenkai
* @since 2017/11/3
*/
namespace astar{
export class AStar
{
private _open:Array<any>; //待考察表
private _closed:Array<any>; //已考察表
private _grid:astar.Grid; //网格
private _endNode:Node; //终点Node
private _startNode:Node; //起点Node
private _path:Array<any>; //保存路径
private _heuristic:Function; //寻路算法
private _straightCost:number = 1.0; //上下左右走的代价
private _diagCost:number = Math.SQRT2; //斜着走的代价
public constructor()
{
//this._heuristic = this.manhattan;
//this._heuristic = this.euclidian;
this._heuristic = this.diagonal;
}
//寻路
public findPath(grid:Grid):boolean
{
this._grid = grid;
this._open = [];
this._closed = [];
this._startNode = this._grid.startNode;
this._endNode = this._grid.endNode;
this._startNode.g = 0;
this._startNode.h = this._heuristic(this._startNode);
this._startNode.f = this._startNode.g + this._startNode.h;
return this.search();
}
//查找路径
public search():boolean
{
var node:Node = this._startNode;
while(node != this._endNode)
{
var startX = Math.max(0, node.x - 1);
var endX = Math.min(this._grid.numCols - 1, node.x + 1);
var startY = Math.max(0, node.y - 1);
var endY = Math.min(this._grid.numRows - 1, node.y + 1);
for(var i = startX; i <= endX; i++)
{
for(var j = startY; j <= endY; j++)
{
//不让斜着走
if(i != node.x && j != node.y){
continue;
}
var test:Node = this._grid.getNode(i, j);
if(test == node ||
!test.walkable ||
!this._grid.getNode(node.x, test.y).walkable ||
!this._grid.getNode(test.x, node.y).walkable)
{
continue;
}
var cost:number = this._straightCost;
if(!((node.x == test.x) || (node.y == test.y)))
{
cost = this._diagCost;
}
var g = node.g + cost * test.costMultiplier;
var h = this._heuristic(test);
var f = g + h;
if(this.isOpen(test) || this.isClosed(test))
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}
else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
this._open.push(test);
}
}
}
for(var o = 0; o < this._open.length; o++)
{
}
this._closed.push(node);
if(this._open.length == 0)
{
console.log("AStar >> no path found");
return false
}
let openLen = this._open.length;
for(let m=0;m<openLen;m++){
for(let n=m+1;n<openLen;n++){
if(this._open[m].f > this._open[n].f){
let temp = this._open[m];
this._open[m] = this._open[n];
this._open[n] = temp;
}
}
}
node = this._open.shift() as Node;
}
this.buildPath();
return true;
}
//获取路径
private buildPath():void
{
this._path = new Array();
var node:Node = this._endNode;
this._path.push(node);
while(node != this._startNode)
{
node = node.parent;
this._path.unshift(node);
}
}
public get path()
{
return this._path;
}
//是否待检查
private isOpen(node:Node):boolean
{
for(var i = 0; i < this._open.length; i++)
{
if(this._open[i] == node)
{
return true;
}
}
return false;
}
//是否已检查
private isClosed(node:Node):boolean
{
for(var i = 0; i < this._closed.length; i++)
{
if(this._closed[i] == node)
{
return true;
}
}
return false;
}
//曼哈顿算法
private manhattan(node:Node)
{
return Math.abs(node.x - this._endNode.x) * this._straightCost + Math.abs(node.y + this._endNode.y) * this._straightCost;
}
private euclidian(node:Node)
{
var dx = node.x - this._endNode.x;
var dy = node.y - this._endNode.y;
return Math.sqrt(dx * dx + dy * dy) * this._straightCost;
}
private diagonal(node:Node)
{
var dx = Math.abs(node.x - this._endNode.x);
var dy = Math.abs(node.y - this._endNode.y);
var diag = Math.min(dx, dy);
var straight = dx + dy;
return this._diagCost * diag + this._straightCost * (straight - 2 * diag);
}
public get visited()
{
return this._closed.concat(this._open);
}
}
}
Grid网格
/**
* 网格类
* @author chenkai
* @since 2017/11/3
*/
namespace astar{
export class Grid {
private _startNode:Node; //起点
private _endNode:Node; //终点
private _nodes:Array<any>; //Node数组
private _numCols:number; //网格行列
private _numRows:number;
public constructor(numCols:number, numRows:number) {
this._numCols = numCols;
this._numRows = numRows;
this._nodes = [];
for(let i:number=0;i<numCols;i++){
this._nodes[i] = [];
for(let j:number=0;j<numRows;j++){
this._nodes[i][j] = new Node(i,j);
}
}
}
public getNode(x:number , y:number):Node{
return this._nodes[x][y];
}
public setEndNode(x:number, y:number){
this._endNode = this._nodes[x][y];
}
public setStartNode(x:number, y:number){
this._startNode = this._nodes[x][y];
}
public setWalkable(x:number, y:number, value:boolean){
this._nodes[x][y].walkable = value;
}
public get endNode(){
return this._endNode;
}
public get numCols(){
return this._numCols;
}
public get numRows(){
return this._numRows;
}
public get startNode(){
return this._startNode;
}
}
}
Node节点
/**
* Node 节点
* @author chenkai
* @since 2017/11/3
*/
namespace astar{
export class Node {
public x:number; //列
public y:number; //行
public f:number; //代价 f = g+h
public g:number; //起点到当前点代价
public h:number; //当前点到终点估计代价
public walkable:boolean = true;
public parent:Node;
public costMultiplier:number = 1.0;
public constructor(x:number , y:number) {
this.x = x;
this.y = y;
}
}
}
演示Demo
class Game extends egret.Sprite
{
private _cellSize:number = 20;
private _grid:astar.Grid;
private _player:egret.Sprite;
private _index:number;
private _path:Array<any>;
public constructor()
{
super();
this.makePlayer();
this.makeGrid();
this.addEventListener(egret.Event.ADDED_TO_STAGE, ()=>{
this.stage.addEventListener(egret.TouchEvent.TOUCH_TAP, this.onGridClick, this);
},this);
}
/**
* Creates the player sprite. Just a circle here.
*/
private makePlayer()
{
this._player = new egret.Sprite();
this._player.graphics.beginFill(0xff0000);
this._player.graphics.drawCircle(0, 0, 5);
this._player.graphics.endFill();
this._player.x = Math.random() * 600;
this._player.y = Math.random() * 600;
this.addChild(this._player);
}
/**
* Creates a grid with a bunch of random unwalkable nodes.
*/
private makeGrid():void
{
this._grid = new astar.Grid(30,30);
for(var i = 0; i < 200; i++)
{
this._grid.setWalkable(Math.floor(Math.random() * 30),
Math.floor(Math.random() * 30),
false);
}
this.drawGrid();
}
/**
* Draws the given grid, coloring each cell according to its state.
*/
private drawGrid():void
{
this.graphics.clear();
for(let i = 0; i < this._grid.numCols; i++)
{
for(let j = 0; j <this._grid.numRows; j++)
{
var node:astar.Node =this._grid.getNode(i, j);
//这里有Bug, 绘制将近150次时， drawRect会出错
// this.graphics.lineStyle(0);
// this.graphics.beginFill(this.getColor(node));
// this.graphics.drawRect(i * this._cellSize, j * this._cellSize, this._cellSize, this._cellSize);
let sp:egret.Sprite = new egret.Sprite();
sp.graphics.beginFill(this.getColor(node));
sp.graphics.drawRect(0,0,20,20);
sp.graphics.endFill();
sp.x = i*this._cellSize;
sp.y = j*this._cellSize;
this.addChild(sp);
}
}
this.addChild(this._player);
}
/**
* Determines the color of a given node based on its state.
*/
private getColor(node:astar.Node)
{
if(!node.walkable) return 0;
if(node == this._grid.startNode) return 0xcccccc;
if(node == this._grid.endNode) return 0xcccccc;
return 0xffffff;
}
/**
* Handles the click event on the GridView. Finds the clicked on cell and toggles its walkable state.
*/
private onGridClick(event:egret.TouchEvent):void
{
var xpos = Math.floor(event.stageX / this._cellSize);
var ypos = Math.floor(event.stageY / this._cellSize);
this._grid.setEndNode(xpos, ypos);
xpos = Math.floor(this._player.x / this._cellSize);
ypos = Math.floor(this._player.y / this._cellSize);
this._grid.setStartNode(xpos, ypos);
this.drawGrid();
this.startTime = egret.getTimer();
this.findPath();
console.log("耗时:", egret.getTimer() - this.startTime);
}
private startTime = 0;
/**
* Creates an instance of AStar and uses it to find a path.
*/
private findPath():void
{
var aStar:astar.AStar = new astar.AStar();
if(aStar.findPath(this._grid))
{
this._path = aStar.path;
this._index = 0;
this.addEventListener(egret.Event.ENTER_FRAME, this.onEnterFrame, this);
}
}
/**
* Finds the next node on the path and eases to it.
*/
private onEnterFrame(event:egret.Event):void
{
var targetX = this._path[this._index].x * this._cellSize + this._cellSize / 2;
var targetY = this._path[this._index].y * this._cellSize + this._cellSize / 2;
var dx = targetX - this._player.x;
var dy = targetY - this._player.y;
var dist = Math.sqrt(dx * dx + dy * dy);
if(dist < 1)
{
this._index++;
if(this._index >= this._path.length)
{
this.removeEventListener(egret.Event.ENTER_FRAME, this.onEnterFrame, this);
}
}
else
{
this._player.x += dx * .5;
this._player.y += dy * .5;
}
}
}