package
{
import flash.display.Graphics;
import flash.display.Shape;
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.utils.getTimer;
/**
* [description]
* @author Jave.Lin
* @date 2017-11-11
*/
[SWF(width=800,height=600,frameRate=60)]
public class TestingAStar extends Sprite
{
public static const w : int = 800;
public static const h : int = 600;
public static const divNum : int= 20;
public static const gs : int = w /divNum;
public static const xCount : int = w / gs;
public static const yCount : int = h / gs;
public function TestingAStar()
{
stage.frameRate = 60;
stage.color = 0xbbbbbb;
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;
function __calH( from : Node, to : Node ) : int
{
return ( Math.abs( to.x - from.x ) + Math.abs( to.y - from.y ) ) * 10;
}
function __drawNode( g : Graphics, node : Node, setColor : Boolean = false, settingColor : uint = 0, alpha : Number = 1, line : Number = 0, lineColor : uint = 0 ) : void
{
if ( setColor )
{
color = settingColor;
}
else
{
if ( node.block )
{
color = 0;
}
else
{
// brightness = 255 * ( node.g / colorRange );
// color = ( brightness = map.length ) return null;
return map[ y ][ x ];
}
function __getRanWalkable() : Node
{
var node : Node;
do
{
var y : int = Math.random() * yCount;
var x : int = Math.random() * xCount;
node = __getNode( x, y );
} while ( node.block );
return node;
}
const nearOffset : Array = [
0,-1,//up
0,1,//down
-1,0,//left
1,0,//right
-1,-1,//up left
1,-1,//up right
-1,1,//down left
1,1//down right
];
var map : Array = [];
for ( var yI : int = 0; yI < yCount; ++yI )
{
var colsArr : Array = [];
map.push( colsArr );
for ( var xI : int = 0; xI < xCount; ++xI )
{
var node : Node = new Node();
node.x = xI;
node.y = yI;
node.block = Math.random() < 0.3;
node.g = 10;
colsArr.push( node );
}
}
var color : uint;
var startNode : Node = __getRanWalkable();
var endNode : Node;
do
{
endNode = __getRanWalkable();
} while ( endNode.x == startNode.x && endNode.y == startNode.y );
const ACT_OPEN : int = 1;
const ACT_CLOSED : int = 2;
const ACT_PATH : int = 3;
const DIAGONAL : Boolean = true;
var openList : Array = [];
var closedList : Array = [];
var pathList : Array = [];
var actionShape : Shape = new Shape();
var startX : int = startNode.x;
var startY : int = startNode.y;
var endX : int = endNode.x;
var endY : int = endNode.y;
var curX : int = startX;
var curY : int = startY;
trace( "sx,sy:", startX, startY, "ex,ey:", endX, endY, "cx,cy:", curX, curY );
var actionIdx : int = 0;
var iterateNearOffsetActionIdx : int = 0;
addChild( actionShape );
openList.length = 0;
closedList.length = 0;
closedList.push( startNode );
var gridInfoViewPool : Array = [];
var gridInfoViewList : Array = [];
function __allocateGridView() : GridInfoView
{
var ret : GridInfoView = gridInfoViewPool.pop();
if ( ret == null ) ret = new GridInfoView();
return ret;
}
function __recycleGridView( item : GridInfoView ) : void
{
gridInfoViewPool.push( item );
if ( item.parent ) item.parent.removeChild( item );
}
function __iterateNearOffset() : Node
{
var idx : int = iterateNearOffsetActionIdx;
var tx : int = nearOffset[ idx * 2 + 0 ] + curX;
var ty : int = nearOffset[ idx * 2 + 1 ] + curY;
var ret : Node = __getNode( tx, ty );
++iterateNearOffsetActionIdx;
return ret;
}
function __iterateNearOffsetOneRound() : Boolean
{
var ret : Boolean = false;
var idx : int = iterateNearOffsetActionIdx;
if ( DIAGONAL )
{
trace( "idx:", idx , " >= 8" );
if ( idx >= 8 )
{
ret = true;
}
}
else
{
trace( "idx:", idx , " >= 4" );
if ( idx >= 4 )
{
ret = true;
}
}
iterateNearOffsetActionIdx = idx;
return ret;
}
function __drawActionNode( node : Node, type : int ) : void
{
var color : uint = 0;
if ( type == ACT_OPEN )
{
color = 0x00ff00;
}
else if ( type == ACT_CLOSED )
{
color = 0xff0000;
}
else if ( type == ACT_PATH )
{
color = 0x0000ff;
}
__drawNode( actionShape.graphics, node, true, color, 0.3, 1 );
}
var lastOneRound : Boolean = false;
function __step() : void
{
var curNode : Node = __getNode( curX, curY );
do
{
var b : Boolean = __iterateNearOffsetOneRound();
if ( b )
{
break;
}
var node : Node = __iterateNearOffset();
b = __iterateNearOffsetOneRound();
if ( node )
{
if ( closedList.indexOf( node ) != -1 )
{
// node = null;
continue;
}
else
{
if ( node.block == false )
{
trace( "push to open list : ", node );
if ( openList.indexOf( node ) == -1 )
{
openList.push( node );
}
node.g = curNode.g + ( iterateNearOffsetActionIdx > 3 ? 14 : 10 );
// node.g = 1 + ( iterateNearOffsetActionIdx > 3 ? 14 : 10 );
// node.g = ( iterateNearOffsetActionIdx > 3 ? 14 : 10 );
node.h = __calH( node, endNode );
node.f = node.g + node.h;
node.from = curNode;
if ( node.x == endNode.x && node.y == endNode.y )
{
var tempNode : Node = endNode;
while ( tempNode )
{
if ( tempNode.from )
{
pathList.push( tempNode.from );
}
tempNode = tempNode.from;
}
trace( "path was reached!" );
removeEventListener( Event.ENTER_FRAME, __onEnterFrame );
return;
}
}
else
{
node = null;
}
}
}
if ( b )
{
break;
}
} while ( node == null || node.block );
var oneRound : Boolean = b;
if ( oneRound == true )
{
// optimize with binary-tree
var bestNode : Node;
if ( openList.length > 0 )
{
openList.sortOn( "f", Array.NUMERIC );
if ( node && node.f == openList[ 0 ].f )
{
bestNode = node;
var idx : int = openList.indexOf( node );
if ( idx != -1 )
{
openList.splice( idx, 1 );
}
}
else
{
bestNode = openList.shift();
}
}
if ( bestNode == null )
{
trace( "un reachable path" );
removeEventListener( Event.ENTER_FRAME, __onEnterFrame );
return;
}
else if ( bestNode.x == endNode.x && bestNode.y == endNode.y )
{
var tempNode : Node = endNode;
while ( tempNode )
{
if ( tempNode.from )
{
pathList.push( tempNode.from );
}
tempNode = tempNode.from;
}
trace( "path was reached!" );
removeEventListener( Event.ENTER_FRAME, __onEnterFrame );
return;
}
curX = bestNode.x;
curY = bestNode.y;
iterateNearOffsetActionIdx = 0;
if ( closedList.indexOf( bestNode ) == -1 )
{
closedList.push( bestNode );
}
var idx : int = openList.indexOf( bestNode );
if ( idx != -1 )
{
openList.splice( idx, 1 );
}
}
lastOneRound = oneRound;
}
function __updateGridInfoViews() : void
{
for each ( var item : GridInfoView in gridInfoViewList )
{
__recycleGridView( item );
}
gridInfoViewList.length = 0;
// open list
for each ( var node : Node in openList )
{
item = __allocateGridView();
item.reset();
item.setValue( node.f, node.g, node.h );
item.refreshParentDirection(
node.from.x, node.from.y,
node.x, node.y, 0 );
addChild( item );
item.x = node.x * gs;
item.y = node.y * gs;
gridInfoViewList.push( item );
}
// closed list
for each ( node in closedList )
{
item = __allocateGridView();
item.reset();
item.setValue( node.f, node.g, node.h );
addChild( item );
item.x = node.x * gs;
item.y = node.y * gs;
gridInfoViewList.push( item );
}
// path list
for each ( node in pathList )
{
item = __allocateGridView();
item.reset();
item.setPathFlag();
item.clearValue();
addChild( item );
item.x = node.x * gs;
item.y = node.y * gs;
gridInfoViewList.push( item );
}
}
function __draws() : void
{
graphics.clear();
actionShape.graphics.clear();
for ( yI = 0; yI < yCount; ++yI )
{
for ( xI = 0; xI < xCount; ++xI )
{
node = __getNode( xI, yI );
__drawNode( graphics, node, false, 0, 1, 1 );
}
}
__drawNode( graphics, startNode, true, 0xffff00, 0.5 );
__drawNode( graphics, endNode, true, 0xff0000, 0.5 );
for each ( node in openList )
{
__drawActionNode( node, ACT_OPEN );
}
for each ( node in closedList )
{
__drawActionNode( node, ACT_CLOSED );
}
graphics.endFill();
actionShape.graphics.endFill();
__updateGridInfoViews();
}
function __onEnterFrame( e : Event ) : void
{
var nowT : int = getTimer();
var et : int = nowT - time;
if ( et >= interval )
{
time = nowT;
et -= interval;
for ( var i : int = 0; i < step; ++i )
{
__step();
}
actionShape.graphics.endFill();
}
__draws();
}
var interval : int = 10;
var time : int = getTimer();
var step : int = Math.max( divNum / gs, 1 ); ;
addEventListener( Event.ENTER_FRAME, __onEnterFrame );
}
}
}
import flash.display.Graphics;
import flash.display.Sprite;
import flash.filters.BitmapFilterQuality;
import flash.filters.GlowFilter;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
class Node
{
public function toString() : String
{
return "x,y:" + x + "," + y + ", b:" + block + ", g:" + g + ", h:" + h + ", f:" + f + ( from ? ", from:" + "[" + from.x + "," + from.y + "]": "" );
}
public var x : int, y : int;
public var block : Boolean;
public var g : int, h : int;
public var f : int;
public var from : Node;
}
class GridInfoView extends Sprite
{
private static const FILTERS : Array = [
new GlowFilter(0,1,1.2,1.2,10,BitmapFilterQuality.HIGH)
];
private static const BAS : int = 4;
private static const SAS : int = 3;
private static const SP : Number = 0.4;
private static const BP : Number = 0.6;
private static function _top( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * 0.5;
var sy : int = gs * BP;
var tx : int = gs * 0.5;
var ty : int = gs * SP;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx - SAS;
sy = ty + SAS;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx + SAS;
sy = ty + SAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _bottom( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * 0.5;
var sy : int = gs * SP;
var tx : int = gs * 0.5;
var ty : int = gs * BP;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx - SAS;
sy = ty - SAS;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx + SAS;
sy = ty - SAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _left( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * BP;
var sy : int = gs * 0.5;
var tx : int = gs * SP;
var ty : int = gs * 0.5;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx + SAS;
sy = ty + SAS;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx + SAS;
sy = ty - SAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _right( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * SP;
var sy : int = gs * 0.5;
var tx : int = gs * BP;
var ty : int = gs * 0.5;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx - SAS;
sy = ty + SAS;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx - SAS;
sy = ty - SAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _top_left( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * SP;
var sy : int = gs * BP;
var tx : int = gs * BP;
var ty : int = gs * SP;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx - BAS;
sy = ty;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx;
sy = ty + BAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _top_right( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * BP;
var sy : int = gs * BP;
var tx : int = gs * SP;
var ty : int = gs * SP;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx + BAS;
sy = ty;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx;
sy = ty + BAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _bottom_left( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * SP;
var sy : int = gs * SP;
var tx : int = gs * BP;
var ty : int = gs * BP;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx - BAS;
sy = ty;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx;
sy = ty - BAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
private static function _bottom_right( g : Graphics, color : uint = 0x00ff00 ) : void
{
var gs : int = TestingAStar.gs;
var sx : int = gs * BP;
var sy : int = gs * SP;
var tx : int = gs * SP;
var ty : int = gs * BP;
g.lineStyle( 1, color );
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx + BAS;
sy = ty;
g.moveTo( sx, sy );
g.lineTo( tx, ty );
sx = tx;
sy = ty - BAS;
g.moveTo( sx, sy );
g.moveTo( tx, ty );
}
public function GridInfoView()
{
super();
function __createTF() : TextField
{
var ret : TextField = new TextField();
var format : TextFormat = ret.defaultTextFormat;
format.size = TestingAStar.gs / 4;
format.color = 0xffffff;
format.align = "left";
ret.defaultTextFormat = format;
ret.autoSize = TextFieldAutoSize.LEFT;
ret.text = "0";
ret.filters = FILTERS;
return ret;
}
tf_TL = __createTF();
tf_TL.x = 0;
tf_TL.y = 0;
addChild( tf_TL );
tf_BL = __createTF();
tf_BL.x = 0;
tf_BL.y = TestingAStar.gs - tf_BL.height;
addChild( tf_BL );
tf_BR = __createTF();
tf_BR.x = TestingAStar.gs - tf_BR.width;
tf_BR.y = TestingAStar.gs - tf_BL.height;
addChild( tf_BR );
mouseChildren = false;
mouseEnabled = false;
if ( tf_TL.defaultTextFormat.size < 4 )
{
clearValue();
}
}
public function setValue( f : int, g : int, h : int ) : void
{
if ( tf_TL.defaultTextFormat.size > 4 )
{
tf_TL.text = f.toString();
tf_BL.text = g.toString();
tf_BR.text = h.toString();
_layout();
}
else
{
clearValue();
}
}
public function clearValue() : void
{
tf_TL.text = "";
tf_BL.text = "";
tf_BR.text = "";
}
public function setPathFlag() : void
{
var gs : int = TestingAStar.gs;
graphics.beginFill( 0xff0000, 0.5 );
graphics.drawCircle( gs * 0.5, gs * 0.5, gs * 0.25 );
graphics.endFill();
}
public function refreshParentDirection(
parentX : int, parentY : int,
subX : int, subY : int,
color : uint = 0x00ff00 ) : void
{
if ( tf_TL.defaultTextFormat.size < 4 )
{
return;
}
var func : Function;
if ( parentX == subX && parentY > subY )
{
func = _bottom;
}
else if ( parentX == subX && parentY < subY )
{
func = _top;
}
else if ( parentX > subX && parentY == subY )
{
func = _right;
}
else if ( parentX < subX && parentY == subY )
{
func = _left;
}
else if ( parentX < subX && parentY > subY )
{
func = _bottom_right;
}
else if ( parentX > subX && parentY > subY )
{
func = _bottom_left;
}
else if ( parentX < subX && parentY < subY )
{
func = _top_right;
}
else if ( parentX > subX && parentY < subY )
{
func = _top_left;
}
else
{
throw new Error();
}
graphics.clear();
if ( func != null )
{
func( graphics, color );
}
}
public function reset() : void
{
graphics.clear();
}
private function _layout() : void
{
tf_TL.x = 0;
tf_TL.y = 0;
tf_BL.x = 0;
tf_BL.y = TestingAStar.gs - tf_BL.height;
tf_BR.x = TestingAStar.gs - tf_BR.width;
tf_BR.y = TestingAStar.gs - tf_BL.height;
}
public var tf_TL : TextField;
public var tf_BL : TextField;
public var tf_BR : TextField;
}
这个运行效果是可以看到寻路过程的 算法未优化
