経路探索 A*
A*による経路探索
クリックすると ■ がついてきます。
/**
* Copyright kenbu ( http://wonderfl.net/user/kenbu )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/yC53
*/
/**
A*による経路探索
クリックすると ■ がついてきます。
*/
package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.*;
import flash.geom.Rectangle;
import flash.geom.Point;
import flash.display.Graphics;
public class RogueLikeMapMainWonder extends Sprite
{
private var map:RogueLikeMap;
private var bitmap:Bitmap;
private var aStar:AStarSearch;
private const WIDTH:Number = 90;
private const HEIGHT:Number = 90;
private const SCALE:Number = 5;
private var startPoint:Point;
private var endPoint:Point;
private var cursor:Sprite;
public function RogueLikeMapMainWonder()
{
stage.scaleMode = StageScaleMode.NO_SCALE;
stage.align = StageAlign.TOP_LEFT;
var progressArray:Array = [];
map = new RogueLikeMap(WIDTH,HEIGHT, 4,4,5,progressArray);
var bitmapData:BitmapData = new BitmapData(WIDTH*SCALE, HEIGHT*SCALE);
bitmap = new Bitmap(bitmapData);
addChild(bitmap);
endPoint = new Point(0,0);
cursor = new Sprite();
addChild(cursor);
var g:Graphics = cursor.graphics;
g.beginFill(0xff00000);
g.drawRect(0,0,SCALE, SCALE);
g.endFill();
drawMap();
this.stage.addEventListener(MouseEvent.CLICK, clickHandler);
clickHandler();
}
private function clickHandler(e:MouseEvent = null):void
{
if(e)
{
endPoint.x = uint(mouseX/SCALE);
endPoint.y = uint(mouseY/SCALE);
}
else
{
var endRoom:Rectangle = map.roomArray[map.roomArray.length-1];
endPoint.x = uint(endRoom.x);
endPoint.y = uint(endRoom.y);
}
if(map.width < endPoint.x || map.height < endPoint.y)
{
return;
}
if(map.getData(endPoint.x, endPoint.y) != 0)
{
return;
}
if(!startPoint)
{
var room:Rectangle = map.roomArray[0];
startPoint = new Point(uint(room.x + 1) , uint(room.y + 1));
cursor.x = startPoint.x*SCALE;
cursor.y = startPoint.y*SCALE;
}
else
{
if(aStar.data.length < 0)
{
return;
}
startPoint.x = aStar.data[cnt-1].x;
startPoint.y = aStar.data[cnt-1].y;
}
cnt = 0;
aStar = new AStarSearch(map.data, map.width, map.height, startPoint , endPoint);
this.addEventListener(Event.ENTER_FRAME, enterFrameHandler);
}
private var cnt:int = 0;
private function enterFrameHandler(event:Event):void
{
if(!aStar)
{
return;
}
var l:int = 2;
for(var i:int = 0; i<l; i++)
{
draw();
}
if(cnt == aStar.data.length-1)
{
this.removeEventListener(Event.ENTER_FRAME, enterFrameHandler);
}
}
private function drawMap():void
{
var bitmapData:BitmapData = bitmap.bitmapData;
map.data.forEach(function(p:uint, i:int, arr:Array):void{
var x:int = i%map.width;
var y:int = int(i/map.height);
var color:Number;
if(p == 0)
{
color = 0xffffffff;
}
else
{
color = 0xff000000;
}
var scale:Number = 3;
rect.x = x*SCALE;
rect.y = y*SCALE;
rect.width = SCALE;
rect.height = SCALE;
bitmapData.fillRect(rect, color);
});
}
private var rect:Rectangle = new Rectangle(0,0,0,0);
private function draw():void
{
if(cnt == aStar.data.length)
{
return;
}
cursor.x = aStar.data[cnt].x * SCALE;
cursor.y = aStar.data[cnt].y * SCALE;
if(cnt < aStar.data.length)
{
cnt++;
}
}
}
}
import flash.display.Graphics;
import flash.display.Sprite;
import flash.geom.Point;
import flash.geom.Rectangle;
class RogueLikeMap
{
private var rectArray:Array;
public var roomArray:Array;
private var roadArray:Array;
public var width:uint;
public var height:uint;
private var minRoomWidth:uint;
private var minRoomHeight:uint;
private var maxCouple:uint;
public var data:Array;
public var buildProgressArray:Array;
public function RogueLikeMap(width:uint, height:uint, minRoomWidth:uint, minRoomHieght:uint, maxCouple:uint, buildProgressArray:Array = null)
{
//minRoomWidth 最小の部屋のサイズ width
//minRoomHeight 最小の部屋のサイズ height
//maxCouple 最大分割数。
this.width = width;
this.height = height;
this.minRoomWidth = minRoomWidth;
this.minRoomHeight = minRoomHieght;
this.maxCouple = maxCouple;
this.buildProgressArray = buildProgressArray;
initialize();
}
private function initialize():void
{
data = [];
rectArray = [];
roomArray = [];
roadArray = [];
setRect(new Rect(0,0,width, height, (Math.random()>0.5)));
setRoom();
setRoad();
setDataArray();
}
private var splitCnt:int;
private function setRect(rect:Rect):void
{
if(maxCouple <= splitCnt++)
{
return;
}
var x:uint = rect.x;
var y:uint = rect.y;
var w:uint = rect.width;
var h:uint = rect.height;
rectArray.push(rect);
//分割する
var nowRect:Rect;
if(rect.splitAline)
{
//縦に分割
var _x:uint = uint(w/2);
rect.width = _x;
nowRect = new Rect(x+_x, y, w-_x, h, !rect.splitAline);
setRect(nowRect);
}
else
{
//横に分割
var _y:uint = int(h/2);
rect.height = _y;
nowRect = new Rect(x, y+_y, w, h-_y, !rect.splitAline);
setRect(nowRect);
}
}
private function setRoom():void
{
rectArray.forEach(function(rect:Rect, i:int, array:Array):void{
var room:Rectangle = new Rectangle(rect.x, rect.y, rect.width, rect.height);
var w:uint = ((room.width-2) - minRoomWidth)*Math.random() + minRoomWidth;
var h:uint = ((room.height-2) - minRoomHeight)*Math.random() + minRoomHeight;
room.x = room.x + int((rect.width - w)/2);
room.y = room.y + int((rect.height - h)/2);
room.width = w;
room.height = h;
roomArray.push(room);
});
}
public function setRoad():void
{
//道を引く。
var prevRoomRect:Rectangle;
rectArray.forEach(function(rect:Rect, i:int, arr:Array):void{
//一個目は飛ばす。
if(i > 0)
{
var road:Road;
var prev:Rect = arr[i-1];
var room:Rectangle = roomArray[i];
var prevRoom:Rectangle = roomArray[i-1];
//中継点
var x0:uint;
var x1:uint;
var y0:uint;
var y1:uint;
if(rect.x < prev.x)
{
//ターゲットが右側。
//始点、
//終点
y0 = getRadomPos(room.y, room.height);
y1 = getRadomPos(prevRoom.y, prevRoom.height);
road = new Road(
//始点
new Point(room.x + room.width, y0),
//中継点
new Point(rect.x+rect.width, y0),
new Point(rect.x+rect.width, y1),
new Point(prevRoom.x, y1)
);
}
else if(rect.x > prev.x)
{
//ターゲットが左側
y0 = getRadomPos(room.y, room.height);
y1 = getRadomPos(prevRoom.y, prevRoom.height);
road = new Road(
//始点
new Point(room.x, y0),
//中継点
new Point(rect.x, y0),
new Point(rect.x, y1),
new Point(prevRoom.x+prevRoom.width, y1)
);
}
else if(rect.y > prev.y )
{
//ターゲットが上
x0 = getRadomPos(room.x, room.width);
x1 = getRadomPos(prevRoom.x, prevRoom.width);
road = new Road(
//始点
new Point(x0, room.y),
//中継点
new Point(x0, rect.y),
new Point(x1, rect.y),
new Point(x1, prevRoom.y+prevRoom.height)
);
}
else
{
//ターゲット下
x0 = getRadomPos(room.x, room.width);
x1 = getRadomPos(prevRoom.x, prevRoom.width);
road = new Road(
//始点
new Point(x0, room.y + room.height),
//中継点
new Point(x0,rect.y+rect.height),
new Point(x1, rect.y+rect.height),
new Point(x1, prevRoom.y)
);
}
roadArray.push(road);
}
});
}
private function getRadomPos(x:uint, w:uint):uint
{
//x ～ (x + w) の間のランダムな数値を返す。
var _w:int = int((w-1)*Math.random())
return x + _w + 1;
}
private function setDataArray():void
{
//壁を生成
var l:int = width * height;
for(var i:int = 0; i<l; i++)
{
setData(i%width, int(i/width), 1);
}
//部屋を生成
roomArray.forEach(function(rect:Rectangle, i:int, arr:Array):void
{
var n:int = rect.y + rect.height;
for(var y:int = rect.y; y<n; y++)
{
var l:int = rect.x + rect.width;
for(var x:int = rect.x; x<l; x++)
{
setData(x, y, 0);
}
}
});
//道を生成
roadArray.forEach(function(road:Road,i:int, arr:Array):void{
road.points.forEach(function(p:Point, i:int, array:Array):void{
if(i != 0)
{
setDataRoad(array[i-1], array[i]);
}
});
});
}
private function setDataRoad(point1:Point, point2:Point):void
{
//2点間を線でつなぎます。
if(point1.y == point2.y)
{
var l:int = (point1.x - point2.x);
var dirX:int = (l>0)?1:-1;
l = (l>0)?l:-l;
for(var i:int = 0; i<l; i++)
{
var x:uint = point2.x + dirX*i;
setData(x,point1.y,0);
}
}
else
{
var n:int = (point1.y - point2.y);
var dirY:int = (n>0)?1:-1;
n = (n>0)?n:-n;
for(var j:int = 0; j<n; j++)
{
var y:uint = point2.y + dirY*j;
setData(point1.x,y,0);
}
}
}
private function setData(x:uint, y:uint, value:uint):void
{
data[x+width*y] = value;
if(buildProgressArray)
{
buildProgressArray.push({x:x, y:y, value:value});
}
}
public function getData(x:uint, y:uint):uint
{
return data[x+width*y];
}
public function dump():Sprite
{
var sprite:Sprite = new Sprite();
return sprite;
var g:Graphics = sprite.graphics;
g.lineStyle(1);
rectArray.forEach(function(rect:Rectangle, i:int, arr:Array):void
{
g.drawRect(rect.x, rect.y, rect.width, rect.height);
});
roomArray.forEach(function(rect:Rectangle, i:int, arr:Array):void
{
g.beginFill(0xff0000);
g.drawRect(rect.x, rect.y, rect.width, rect.height);
});
g.endFill();
//道を引く
g.lineStyle(1, 0xff00ff);
roadArray.forEach(function(road:Road,i:int, arr:Array):void{
g.moveTo(road.points[0].x,road.points[0].y);
g.lineTo(road.points[1].x,road.points[1].y);
g.lineTo(road.points[2].x,road.points[2].y);
g.lineTo(road.points[3].x,road.points[3].y);
});
var traceLine:String = "";
var cnt:int = 0;
data.forEach(function(v:uint, i:int, arr:Array):void{
traceLine += v+""
cnt++;
if(cnt%width == 0)
{
traceLine ="";
cnt = 0;
}
});
return sprite;
}
}
class Rect extends Rectangle
{
public var splitAline:Boolean;
public function Rect(x:Number, y:Number, width:Number, height:Number ,splitAline:Boolean)
{
super(x, y, width, height);
this.splitAline = splitAline;
}
}
class Road
{
public var points:Array;
public function Road(startPoint:Point, jointPoint1:Point, jointPoint2:Point, endPoint:Point)
{
points = [startPoint, jointPoint1, jointPoint2, endPoint];
}
}
/**
* A*による経路探索
*
*
* ななめ移動は認めない。
* 地形効果はとりあえず虫
*
* */
class AStarSearch
{
private var openList:Array;
private var closeList:Array;
private var tmpListMap:Array;
public var data:Array;
private var mapData:Array;
private var width:uint;
private var height:uint;
private var startPoint:Point;
private var goalPoint:Point;
public function AStarSearch(mapData:Array, width:uint, height:uint, startPoint:Point, goalPoint:Point)
{
this.mapData = mapData;
this.width = width;
this.height = height;
this.startPoint = startPoint;
this.goalPoint = goalPoint;
this.initialize();
}
private function initialize():void
{
openList = [];
closeList = [];
tmpListMap = [].concat(mapData);
data = [];
search();
}
private function search():void
{
addOpenList(startPoint.x, startPoint.y);
var loop:Boolean = true;
var cnt:int = 0;
while( loop )
{
//ターゲットを決める。
var list:List = getLowScoreList();
if(list.x == goalPoint.x && list.y == goalPoint.y)
{
setMinRoad(list);
loop = false;
return ;
}
//上下左右にLISTを生成
if(isRoad(list.x, list.y-1))
{
//上
addOpenList(list.x, list.y-1, list);
}
if(isRoad(list.x+1, list.y))
{
//右
addOpenList(list.x+1, list.y, list);
}
if(isRoad(list.x, list.y+1))
{
//下
addOpenList(list.x, list.y+1, list);
}
if(isRoad(list.x-1, list.y))
{
//左
addOpenList(list.x-1, list.y, list);
}
//クローズ移動する
addCloseList(list);
openList.sortOn("score", Array.NUMERIC);
if(openList.length == 0)
{
//たどりつけない。
loop = false;
}
}
}
private var idCounter:uint = 0;
private function addOpenList(x:uint, y:uint, parent:List = null):void
{
var list:List = new List(x, y , parent);
list.id = idCounter++;
//ヒューリスティック値を設定
list.heuristic = getHeuristic(list);
//データを登録
setData(list);
openList.push(list);
}
private function addCloseList(list:List):void
{
//openListから削除
var l:uint = openList.length;
for(var i:int = 0; i<l; i++)
{
var li:List = openList[i];
if(li.id == list.id)
{
//オープンリストから削除
openList.splice(i, 1);
//クローズリストに移動
closeList.push(list);
return;
}
}
}
private function setMinRoad(list:List):void
{
//最短距離のリストを作る。
data.push(list);
if(list.parent)
{
setMinRoad(list.parent);
}
else
{
data.reverse();
}
}
private function isRoad(x:uint, y:uint):Boolean
{
var li:* = getData(x,y);
if(getData(x,y) as List)
{
return false;
}
return li == 0;
}
private function getLowScoreList():List
{
return openList[0];
}
private function getHeuristic(list:List):uint
{
//ヒューリスティック値を返す。
//ゴールまでの距離を返す。
var x:int = goalPoint.x - list.x;
x = (x > 0)?x:-x;
var y:int = goalPoint.y - list.y;
y = (y > 0)?y:-y;
return x + y;
}
private function setData(list:List):void
{
tmpListMap[list.x + list.y*width] = list;
}
private function getData(x:uint, y:uint):*
{
return tmpListMap[x + width*y];
}
}
class List
{
public var x:uint;
public var y:uint;
public var parent:List;
public var id:uint;
//原点からのコスト
private var cost:uint;
//ゴールまでの予測値
public var heuristic:uint;
public function List(x:uint, y:uint, parent:List = null):void
{
this.x = x;
this.y = y;
this.parent = parent;
cost = countCost();
}
public function get score():uint
{
return cost + heuristic;
}
//子のListから呼ばれる。
private function countCost():uint
{
//コストを計算する。
if(!parent)
{
return 0;
}
return parent.countCost() + 1;
}
}