Astarの練習
/ コード元
/ http://shin-ishimaru.cocolog-nifty.com/blog/2008/10/aactionscript30.html
/// コード元
/// http://shin-ishimaru.cocolog-nifty.com/blog/2008/10/aactionscript30.html
package {
import flash.display.*;
import flash.events.*;
import flash.utils.*;
import flash.filters.*;
import caurina.transitions.Tweener;
import flash.geom.Point;
[SWF(width=465, height=465, backgroundColor=0x888888)]
/// A*法での経路検索
public class AStar extends Sprite
{
public static const G:int = 0; ///< ゴール
public static const S:int = 1; ///< スタート
public static const O:int = 2; ///< なにもない通れる所
public static const X:int = 3; ///< 通れない
public static const SCREEN_W:int = 465; ///< 画面幅
public static const SCREEN_H:int = 465; ///< 画面高さ
public static const TILE_W:int = SCREEN_W/16; ///< タイル一枚の大きさ
private var myChr:Shape = null; ///< 自キャラ
private var mapNode:Array = new Array();///< マップデータの管理
private var routeList:Array = new Array;///< 最短経路が保存される
private var openList:Array = null; ///< 経路計算用
private var closeList:Array = null; ///< 経路計算用
private var startNode:Node = null; ///< スタート地点
private var goalNode:Node = null; ///< ゴール地点
private var moveState:int = 0; ///< 移動状態
// コンストラクタ
public function AStar()
{
//ステージの設定
stage.quality = "MEDIUM";
stage.scaleMode = "noScale";
stage.align = StageAlign.TOP_LEFT;
// ベーススプライト作成。マウスクリック用
var base:Sprite=new Sprite();
base.graphics.beginFill(0x50AAB3);
base.graphics.drawRect(0,0,SCREEN_W,SCREEN_H);
base.graphics.endFill();
addChild(base);
// マップデータの作成
var mapData:Array = new Array();
mapData[0] = [O,S,O,O,O,O,O,O,O,O,O,O,X,X,X,X];
mapData[1] = [O,O,O,O,X,X,X,X,O,O,O,O,X,X,X,X];
mapData[2] = [X,X,X,O,O,O,O,O,O,O,O,O,O,O,O,O];
mapData[3] = [O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O];
mapData[4] = [O,O,O,X,X,X,X,X,O,O,O,O,O,O,O,O];
mapData[5] = [O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O];
mapData[6] = [O,X,X,O,X,O,O,O,O,O,O,O,O,O,O,O];
mapData[7] = [O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O];
mapData[8] = [O,O,O,O,O,O,O,O,X,O,X,X,X,O,O,O];
mapData[9] = [O,O,O,X,X,X,X,X,O,O,O,O,X,O,O,O];
mapData[10] = [O,O,O,X,O,O,O,X,O,O,O,X,O,O,O,X];
mapData[11] = [O,O,O,X,O,O,O,X,O,O,O,X,O,O,O,X];
mapData[12] = [O,O,O,X,O,O,O,O,O,O,O,X,O,O,O,X];
mapData[13] = [O,O,O,X,O,X,X,X,O,O,O,O,X,O,O,O];
mapData[14] = [O,O,O,O,O,O,O,O,X,X,X,X,X,O,O,O];
mapData[15] = [O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,G];
// filter使ったほうがかっこいいよね！
var wFilters:Array = new Array;
wFilters.push(makeDropShadowFilter());
wFilters.push(makeBevelFilter());
for(var y:int = 0; y < mapData.length; ++y){
var a:Array = new Array();
for(var x:int = 0; x < mapData[y].length; ++x){
var newNode:Node = new Node(x, y, mapData[y][x]);
a.push(newNode);
if(mapData[y][x] == X){
// 壁を描画
var s:Shape = makeRoundRect(TILE_W, TILE_W, 10, 0x1200D9);
s.x = x*TILE_W;
s.y = y*TILE_W;
s.filters = wFilters;
addChild(s);
}else if(mapData[y][x] == S){
// スタート地点にタマを置く
myChr = makeShape(0xF2C200, x*TILE_W+TILE_W/2, y*TILE_W+TILE_W/2, TILE_W/2);
myChr.filters = wFilters;
addChild(myChr);
startNode = newNode;
}else if(mapData[y][x] == G){
goalNode = newNode;
}
}
mapNode.push(a);
}
// マウスクリックイベント追加
base.addEventListener(MouseEvent.CLICK, mouseDownHandler);
}
/// 移動完了したときの呼び出しコールバック
private function moveComp():void{
move();
}
/// 玉の移動
private function move():void{
if( routeList.length == 0 ){
return;
}
if(moveState >= routeList.length){
routeList = new Array;
moveState = 0;
return;
}
var retNode:Node = routeList[moveState];
var xpos:int = retNode.x*TILE_W+TILE_W/2;
var ypos:int = retNode.y*TILE_W+TILE_W/2;
Tweener.addTween(myChr,{x:xpos, y:ypos, time:0.15, transition:"easeinoutquad", onComplete:moveComp});
++moveState;
}
/// 画面上の座標をマップデータ上の座標に変換する
private function getMapPos(x:int, y:int):Point{
var ret:Point = new Point;
ret.x = x/TILE_W;
ret.y = y/TILE_W;
return ret;
}
/// マウスダウンイベントの処理
private function mouseDownHandler(evt:MouseEvent):void {
if(routeList.length != 0){
// 移動中は受け付けない
return;
}
// スタートとゴールを再設定
// ゴールを設定
var goalPos:Point = getMapPos(mouseX, mouseY);
var goal:Node = getNode(goalPos.x, goalPos.y);
if(!goal.isWalk()){
// ゴールがいけないところだったら移動しない
return;
}
startNode.state = O;
goalNode.state = O;
goalNode = goal;
goalNode.state = G;
// スタート地点を設定
var startPos:Point = getMapPos(myChr.x, myChr.y);
startNode = getNode(startPos.x, startPos.y);
startNode.state = S;
// ルート計算
if( !processAStar() ){
return;
}
move();
}
/// mからnに移動したときのコストを計算する
private function cost(m:Node, n:Node):int{
var disx:int = Math.abs(m.x - n.x);
var disy:int = Math.abs(m.y - n.y);
return disx + disy;
}
/// h*を計算する
private function h_star(node:Node):int{
return cost(goalNode, node);
}
/// ノードの取得
private function getNode(x:int, y:int):Node{
if( x < 0 || y < 0 ){
return null;
}
if(y >= mapNode.length){
return null;
}
if(x >= mapNode[0].length){
return null;
}
return mapNode[y][x];
}
/// ノードのデータを初期化する
private function nodeClear():void{
for(var y:int = 0; y < mapNode.length; ++y){
for(var x:int = 0; x < mapNode[y].length; ++x){
var node:Node = mapNode[y][x];
if(node!=null){
node.clear();
}
}
}
}
/// 隣接するノードの配列を作って返す
private function getMNodeArray(node:Node):Array{
// 左
var ret:Array = new Array;
var movex:Array = [-1, 0, 1, 0];
var movey:Array = [0, 1, 0, -1];
for(var i:int = 0;i < movex.length; ++i){
var n:Node = getNode(node.x+movex[i], node.y+movey[i]);
if(n != null){
if(n.isWalk()){
ret.push(n);
}
}
}
return ret;
}
/// openListの中に指定のnodeはあるか判定する
private function inOpenList(node:Node):int{
for(var i:int = 0;i < openList.length; ++i){
var n:Node = openList[i];
if(n.x == node.x && n.y == node.y){
return i;
}
}
return -1;
}
/// closeListの中に指定のnodeはあるか判定する
private function inCloseList(node:Node):int{
for(var i:int = 0;i < closeList.length; ++i){
var n:Node = closeList[i];
if(n.x == node.x && n.y == node.y){
return i;
}
}
return -1;
}
/// 最短経路を求める。成功なら、routeListに最短距離の経路が保存される
private function processAStar():Boolean{
nodeClear();
this.openList = new Array;
this.closeList = new Array;
// スタート位置を探す
if(startNode == null){
return false;
}
if(goalNode == null){
return false;
}
startNode.f_star = this.h_star(startNode);
// Openリストに追加
openList.push(startNode);
var loopCount:int = 0;
// Openリストが空ならば検索は失敗
while(openList.length > 0){
// f_starが最小の値のものを探す
openList.sortOn("f_star", Array.NUMERIC);
var n:Node = openList[0];
// GOALだったら検索終了
if(n.isGoalNode()){
break;
}
// Closeリストへnを移す
openList.shift();
closeList.push(n);
// 隣のノードの配列を作る
var mNodeArray:Array = getMNodeArray(n);
for(var i:int = 0;i < mNodeArray.length; ++i){
var m:Node = mNodeArray[i];
// f_starを計算
m.f_star = (n.f_star - h_star(n)) + h_star(m) + cost(n,m);
// 条件分岐
var openIndex:int = inOpenList(m);
var closeIndex:int = inCloseList(m);
var oldM:Node;
if( openIndex < 0 && closeIndex < 0 ){
// openListにもcloseListにもmがない
m.parent = n;
openList.push(m);
}else if( openIndex >= 0 ){
// openListにある
oldM = openList[openIndex];
if( m.f_star < oldM.f_star ){
openList[openIndex] = m;
}
}else if( closeIndex >= 0 ){
// closeListにある
oldM = closeList[closeIndex];
if( m.f_star < oldM.f_star ){
// closeから削除(mが入っていたところを先頭の0で上書きして、先頭削除）
closeList[closeIndex] = closeList[0];
closeList.shift();
// openへ
openList.push(m);
}
}
// 無限ループ回避措置(バグ回避用)
loopCount++;
if(loopCount > 1000){
return false;;
}
}
}
// 経路を並び替えてrouteListに入れる
var ret:Array = new Array;
var node:Node = openList[0];
while(node.parent != null){
ret.push(node);
node = node.parent;
}
ret.reverse();
routeList = ret;
this.openList = new Array;
this.closeList = new Array;
return true;
}
//角丸矩形の生成
private function makeRoundRect(w:uint,h:uint,ew:uint,color:uint):Shape {
var rrect:Shape=new Shape();
rrect.graphics.lineStyle(2,0x000000); //線幅・線色
rrect.graphics.beginFill(color); //塗り潰し色
rrect.graphics.drawRoundRect(0,0,w,h,ew);//XY座標,幅,高さ,角丸幅
rrect.graphics.endFill(); //塗り潰し終了
return rrect;
}
/// 円を作成する
private function makeShape(color:uint, x:int, y:int, r:int):Shape {
var s:Shape = new Shape();
s.x = x;
s.y = y;
s.graphics.beginFill(color); //塗り潰し色
s.graphics.lineStyle(3, 0x000000);
s.graphics.drawCircle(0, 0, r);
s.graphics.endFill(); //塗り潰し終了
return s;
}
//ベベルフィルタの生成
private function makeBevelFilter():BitmapFilter {
var filter:BevelFilter=new BevelFilter();
filter.angle =45; //角度
filter.blurX =3; //水平方向のぼかし量
filter.blurY =3; //垂直方向のぼかし量
filter.distance =10; //オフセットの距離
filter.highlightAlpha=0.5; //ハイライトカラーの透明度
filter.highlightColor=0xddddff;//ハイライトカラー
filter.knockout =false; //ノックアウト効果有無
filter.quality =BitmapFilterQuality.HIGH;//クォリティ
filter.shadowAlpha =0.8; //シャドウカラーの透明度
filter.shadowColor =0x000000;//シャドウカラー
filter.strength =0.5; //インプリントやスプレッドの長さ
filter.type =BitmapFilterType.INNER;//ベベルの種類
return filter;
}
//ドロップシャドウフィルタの生成
private function makeDropShadowFilter():BitmapFilter {
var filter:DropShadowFilter=new DropShadowFilter();
filter.alpha =1.0; //シャドウカラーの透明度
filter.angle =45; //シャドウの角度
filter.blurX =5; //水平方向のぼかし量
filter.blurY =5; //垂直方向のぼかし量
filter.color =0x000000;//シャドウのカラー
filter.distance =5; //シャドウのオフセット距離
filter.hideObject=false; //シャドウのみの表示
filter.inner =false; //内部シャドウか
filter.knockout =false; //ノックアウト効果の有無
filter.quality =BitmapFilterQuality.HIGH;//クォリティ
filter.strength =1; //インプリントやスプレッドの長さ
return filter;
}
}
}
/// マップのノード管理
class Node
{
public var parent:Node; ///< 親
public var state:int; ///< 状態
public var x:int; ///< X座標
public var y:int; ///< Y座標
public var f_star:Number = 0; ///< f*
/// コンストラクタ
public function Node(x:int, y:int, state:int):void
{
this.x = x;
this.y = y;
this.state = state;
parent = null;
}
/// 初期化
public function clear():void{
this.parent = null;
this.f_star = 0;
}
/// ゴールか？
public function isGoalNode():Boolean{
if(this.state == AStar.G){
return true;
}
return false;
}
/// 歩けるところか？
public function isWalk():Boolean{
if(this.state != AStar.X){
return true;
}
return false;
}
}