forked from: A*（A-star)探索アルゴリズム(ご指摘を受けて修正)
参考
http://itpro.nikkeibp.co.jp/article/COLUMN/20070223/263174/
===追記===
miyaokaさん < 確かに最短になってないですねorz
ちょっとソースコードを修正してみました。
どなたか、ここおかしいなと思うところがあったら連絡ください（汗
// forked from rsakane's A*（A-star)探索アルゴリズム(ご指摘を受けて修正)
package
{
/*
* 参考
* http://itpro.nikkeibp.co.jp/article/COLUMN/20070223/263174/
*
* ===追記===
* miyaokaさん < 確かに最短になってないですねorz
* ちょっとソースコードを修正してみました。
* どなたか、ここおかしいなと思うところがあったら連絡ください（汗
*/
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.text.TextFormat;
import flash.text.TextFieldAutoSize;
[SWF(width="465", height="465", frameRate="30", backgroundColor="0xFFFFFF")]
public class Main extends Sprite
{
private const WIDTH:int = 12;
private const HEIGHT:int = 12;
private const BLOCKSIZE:int = 30;
private const pos:Array = [[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
//
private const DIR4:Array = [[0, -1], [ -1, 0], [0, 1], [1, 0]]; // 上下左右の4方向に対応
private const DIR8:Array = [[0, -1], [ -1, 0], [0, 1], [1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]]; // 上下左右斜めの8方向に対応
private var map:Array;
private var searchQue:Array;
private var clickable:Boolean;
private var useDir4:Boolean = true;
private var tf:TextField;
public function Main()
{
// Wonderfl.capture_delay(20);
clickable = true;
init();
drawMap();
stage.addEventListener(MouseEvent.CLICK, onMouseClick);
var button:Sprite = new Sprite();
button.x = 170;
button.y = 410;
button.graphics.beginFill(0xFBE1F9);
button.graphics.drawEllipse(-18, -6, 63, 35);
button.buttonMode = true;
button.graphics.endFill();
button.addEventListener(MouseEvent.CLICK, buttonClick);
tf = createTextField(button, "OFF");
addChild(button);
createTextField(null, "斜め移動を可能にする - ", 0, 410);
createTextField(null, "のマスをクリックをすると最短経路を表示します(スタート位置は固定)", 31, 370);
}
private function buttonClick(event:MouseEvent):void
{
if (useDir4) useDir4 = false, tf.text = "ON"
else useDir4 = true, tf.text = "OFF";
}
private function init():void
{
map = new Array(HEIGHT);
for (var y:int = 0; y < HEIGHT; y++)
{
map[y] = new Array(WIDTH); // 二次元配列生成
for (var x:int = 0; x < WIDTH; x++)
{
var node:Node = new Node();
node.pos.x = x;
node.pos.y = y;
if (pos[y][x]) node.attr = ATTR.WALL // // WALL = 壁
else node.attr = ATTR.EMPTY; // EMPTY = 空間
map[y][x] = node;
}
}
}
private function onMouseClick(event:MouseEvent):void
{
if (!clickable) return; // 探索中はクリックしても反応しないようにする
init();
var start:Pos = new Pos(); // スタートからゴールの位置へ
var goal:Pos = new Pos(); //
start.y = 7, start.x = 0; // スタート位置は固定で
var dy:int = mouseY / BLOCKSIZE; // マップの座標に直す
var dx:int = mouseX / BLOCKSIZE; //
if (dy < 0 || HEIGHT <= dy || dx < 0 || WIDTH <= dx) return; // マップの外側をクリックされていたらスルーで
if (pos[dy][dx] || (dy == start.y && dx == start.x)) return; // 壁 または スタート地点をクリックされていたらスルーで
goal.y = dy, goal.x = dx; // クリックした地点をゴールとする
rootSearch(start, goal);
}
private function rootSearch(start:Pos, goal:Pos):void
{
clickable = false; // 探索中なのでクリック禁止
map[start.y][start.x].attr = ATTR.START; // スタートの印を入れる
map[goal.y][goal.x].attr = ATTR.GOAL; // ゴールの印を入れる
searchQue = new Array();
searchQue.push(map[start.y][start.x]); // 探索リストにスタート位置の情報を入れる
do
{
searchQue.sortOn(["count"], Array.DESCENDING | Array.NUMERIC); // countプロパティの値を基準に降順に並べる。(pop()したときに値が一番小さいやつを出したい)
var cpos:Node = searchQue.pop();
if (cpos == null) return; // もう移動するマスがないということで処理終了。 ゴールが見つからなかった。
var dir:Array;
if (useDir4) dir = DIR4;
else dir = DIR8;
for (var i:int = 0; i < dir.length; i++)
{
var cx:int = cpos.pos.x + dir[i][0];
var cy:int = cpos.pos.y + dir[i][1];
if (cx < 0 || WIDTH <= cx || cy < 0 || HEIGHT <= cy) continue; // マップからはみ出ていたらスルーで
if (map[cy][cx].attr == ATTR.GOAL) // ゴールが見つかった
{
map[cy][cx].backpos.x = cpos.pos.x; // 後でゴールからスタート位置まで辿る為に今居る位置をゴールnodeのbackposに入れておく
map[cy][cx].backpos.y = cpos.pos.y;
break; // ゴールが見つかったのでcpos.posの8方向はもう調べる必要がない。
}
if (map[cy][cx].attr == ATTR.WALL || map[cy][cx].attr == ATTR.START)
{
continue; // 調べている所が壁、もしくはスタート位置だった。関係ないので次の対象マスへ。
}
// まだ調査していないマス
if (map[cy][cx].count == 999)
{
map[cy][cx].count = cpos.count + 1; // 一歩進める
map[cy][cx].backpos.x = cpos.pos.x; // 後でゴールからスタート位置まで辿る為に今居る位置をゴールnodeのbackposに入れておく
map[cy][cx].backpos.y = cpos.pos.y;
searchQue.push(map[cy][cx]); // このマスを移動候補にする
}
// 既に調査済みのマスだけど、今来た道のほうが近道(?)だった場合。歩数、backposの更新
else if (cpos.count + 1 < map[cy][cx].count)
{
map[cy][cx].count = cpos.count + 1; // 一歩進める
map[cy][cx].backpos.x = cpos.pos.x; // 後でゴールからスタート位置まで辿る為に今居る位置をゴールnodeのbackposに入れておく
map[cy][cx].backpos.y = cpos.pos.y;
}
}
// (α) ループを抜け出た時点でcxとcyが配列外の値になる可能性がある(と思う)。一応チェックして、はみだしていたら安全な値に変更しておく
if (cx < 0 || WIDTH <= cx || cy < 0 || HEIGHT <= cy) cx = cpos.pos.x, cy = cpos.pos.y;
}
while (map[cy][cx].attr != ATTR.GOAL);
drawMap();
graphics.beginFill(0xFF0000);
graphics.drawRect(start.x * 30, start.y * 30, 30, 30);
graphics.drawRect(goal.x * 30, goal.y * 30, 30, 30);
graphics.endFill();
var bpos:Pos = new Pos();
bpos.y = goal.y;
bpos.x = goal.x;
do
{
bpos = map[bpos.y][bpos.x].backpos;
if (bpos.x == start.x && bpos.y == start.y) break;
graphics.beginFill(0xE4AA7A);
graphics.drawRect(bpos.x * 30, bpos.y * 30, 30, 30);
graphics.endFill();
}
while (true);
clickable = true; // 探索おわたのでクリック許可
}
private function drawMap():void
{
graphics.clear();
for (var y:int = 0; y < HEIGHT; y++)
{
for (var x:int = 0; x < WIDTH; x++)
{
if (pos[y][x]) graphics.beginFill(0x995030);
else graphics.beginFill(0xF4F0E5);
graphics.drawRect(x * 30, y * 30, 30, 30);
graphics.endFill();
}
}
// 説明部分
graphics.beginFill(0xF4F0E5);
graphics.drawRect(0, 365, 30, 30);
graphics.endFill();
}
private function createTextField(parent:Sprite = null, text:String = "", x:int = 0, y:int = 0, fontSize:int = 13):TextField
{
var tf:TextField = new TextField();
tf.x = x, tf.y = y;
tf.defaultTextFormat = new TextFormat("_typeWriter", fontSize, 0x393939);
tf.text = text;
tf.selectable = false;
tf.autoSize = TextFieldAutoSize.LEFT;
if (parent) parent.addChild(tf);
else this.addChild(tf);
return tf;
}
}
}
class Pos
{
public var x:int;
public var y:int;
public function Pos(){}
}
class Node
{
public var pos:Pos = new Pos();
public var backpos:Pos = new Pos();
public var count:int = 999;
public var attr:int;
public function Node(){}
}
class ATTR
{
public static const START:int = 0; // スタート地点
public static const GOAL:int = 1; // ゴール地点
public static const EMPTY:int = 2; // 空間
public static const WALL:int = 3; // 壁
public function ATTR(){}
}