A* algorithm for Hex
forked from A* algorithm (diff: 720)
ActionScript3 source code
/**
* Copyright greentec ( http://wonderfl.net/user/greentec )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/rn3H
*/
// forked from greentec's A* algorithm
package {
import com.bit101.components.PushButton;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
import flash.geom.Matrix;
public class FlashTest extends Sprite {
public var backBitmap:Bitmap;
public var open:Array = [];
public var closed:Array = [];
public var pathBitmap:Bitmap;
public var pathBitmapData:BitmapData;
public var startShape:Shape;
public var endShape:Shape;
public var cellType:Object = {
ROAD : 0,
WALL : 1,
START: 2,
END : 3
}
public var startCell:HexCell;
public var endCell:HexCell;
public var resetButton:PushButton;
public var startButton:PushButton;
public var endButton:PushButton;
public var wallButton:PushButton;
public var mapSizeMax:int = 12;
public var mapsizeMaxDouble:int = mapSizeMax * 2 + 1;
public var mapSize:int = 12;
public var map:Vector.<Vector.<Vector.<HexCell>>> = new Vector.<Vector.<Vector.<HexCell>>>(2 * mapSizeMax + 1);
public var edgeLength:int = 14 //30; //18;
public var edgeW:int;
public var edgeH:int;
public var mapSerialArray:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(); //최적화를 위한 직렬화 Array
public var neighbors:Array = [];
public var cellSprite:Sprite;
public var _width:int = 465;
public var _height:int = 465;
public var randomWallNum:int = mapSizeMax * mapSizeMax * 0.2;
public var wallArray:Array = [];
public var cellBorderColor:uint = 0x443d2f;
public var cellColor:uint = 0xffe0ab;
public var wallColor:uint = 0x7f7056;
public var oneCellShape:Shape;
public var mat:Matrix;
public function FlashTest() {
// write as3 code here..
stage.scaleMode = "noScale";
backBitmap = new Bitmap(new BitmapData(465, 465, false, 0x004040));
addChild(backBitmap);
var i:int;
for (i = 0; i < 6; i += 1)
{
neighbors[i] = [];
}
neighbors[0] = [+1, -1, 0];
neighbors[1] = [+1, 0, -1];
neighbors[2] = [0, +1, -1];
neighbors[3] = [-1, +1, 0];
neighbors[4] = [-1, 0, +1];
neighbors[5] = [0, -1, +1];
edgeW = edgeLength * 3 / 2;
edgeH = edgeLength * Math.sqrt(3) / 2;
cellSprite = new Sprite();
addChild(cellSprite);
initMap(map);
drawMap(map);
startShape = new Shape();
startShape.graphics.clear();
startShape.graphics.lineStyle(1, 0xcccccc);
startShape.graphics.beginFill(0x1861FF, 0.7);
startShape.graphics.drawCircle(0, 0, 14);
startShape.graphics.endFill();
endShape = new Shape();
endShape.graphics.clear();
endShape.graphics.lineStyle(1, 0xcccccc);
endShape.graphics.beginFill(0xF7360F, 0.7);
endShape.graphics.drawCircle(0, 0, 14);
endShape.graphics.endFill();
oneCellShape = new Shape();
oneCellShape.graphics.beginFill(0x00dd00, 0.5);
oneCellShape.graphics.moveTo(edgeLength, 0);
var angle:Number;
for (i = 1; i <= 6; i += 1)
{
angle = 2 * Math.PI / 6 * i;
oneCellShape.graphics.lineTo(edgeLength * Math.cos(angle), edgeLength * Math.sin(angle));
}
oneCellShape.graphics.endFill();
initRandomWall();
//drawCell();
//drawStartEnd();
calcH();
closed.push(startCell);
var hexCell:HexCell;
var cx:int, cy:int, cz:int;
for (i = 0; i < 6; i += 1)
{
cx = startCell._x + neighbors[i][0];
cy = startCell._y + neighbors[i][1];
cz = startCell._z + neighbors[i][2];
if (calcBoundary(cx, cy, cz) == true)
{
hexCell = map[cx + mapSizeMax][cy + mapSizeMax][cz + mapSizeMax];
if (hexCell._type != cellType.WALL)
{
open.push(hexCell);
hexCell._g += 1;
hexCell._f = hexCell._g + hexCell._h;
hexCell._parent = startCell;
hexCell.drawPath();
}
}
}
calcG();
pathBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
pathBitmap = new Bitmap(pathBitmapData);
addChild(pathBitmap);
drawPath();
resetButton = new PushButton(this, 0, 0, "Reset", onReset);
resetButton.width = 116;
resetButton.height = 28;
startButton = new PushButton(this, 116, resetButton.y, "Start Change", onStartChange);
startButton.width = 116;
startButton.height = resetButton.height;
startButton.toggle = true;
endButton = new PushButton(this, 232, resetButton.y, "End Change", onEndChange);
endButton.width = 116;
endButton.height = resetButton.height;
endButton.toggle = true;
wallButton = new PushButton(this, 348, resetButton.y, "Wall Change", onWallChange);
wallButton.width = 116;
wallButton.height = resetButton.height;
wallButton.toggle = true;
}
private function drawMap(map:Vector.<Vector.<Vector.<HexCell>>>):void
{
var i:int, j:int, k:int;
var r:int;
var hexCell:HexCell;
var mat:Matrix;
cellSprite.addEventListener(MouseEvent.CLICK, onHexCellClick, true); //이벤트 캡쳐 사용
cellSprite.addEventListener(MouseEvent.MOUSE_OVER, onHexCellMouseOver, true);
cellSprite.addEventListener(MouseEvent.MOUSE_OUT, onHexCellMouseOut, true);
//직렬화로 그리면 빠르잖아. 일을 두 번 할 필요가 없다.
for (i = 0; i < mapSerialArray.length; i += 1)
{
hexCell = map[mapSerialArray[i][0] + mapSizeMax][mapSerialArray[i][1] + mapSizeMax][mapSerialArray[i][2] + mapSizeMax];
if (calcBoundary(mapSerialArray[i][0], mapSerialArray[i][1], mapSerialArray[i][2]) == true)
{
cellSprite.addChild(hexCell);
hexCell.edgeLength = edgeLength;
hexCell.x = _width / 2 + hexCell._x * edgeW;
hexCell.y = _height / 2 + (0 - hexCell._y + hexCell._z) * edgeH;
//일단 이 부분을 없애 놓는다.
hexCell.drawCell(hexCell._G.graphics, true, cellColor);
hexCell.drawCell(hexCell._GLine.graphics, false, cellBorderColor); //라인 그리기
}
}
}
private function onHexCellClick(e:MouseEvent):void
{
var hexCell:HexCell = e.target.parent as HexCell;
if (startButton.selected == true)
{
if (startCell._x == hexCell._x && startCell._y == hexCell._y && startCell._z == hexCell._z) //same - do nothing
{
}
else if (endCell._x == hexCell._x && endCell._y == hexCell._y && endCell._z == hexCell._z) //overlap - do nothing
{
}
else if (hexCell._type != cellType.WALL)
{
startCell._type = 0;
hexCell._type = cellType.START;
startCell = hexCell;
startShape.x = hexCell.x;
startShape.y = hexCell.y;
//wallArray[randomWallNum] = cell._x + cell._y * cellWidthNum;
search();
}
}
else if (endButton.selected == true)
{
if (startCell._x == hexCell._x && startCell._y == hexCell._y && startCell._z == hexCell._z) //overlap - do nothing
{
}
else if (endCell._x == hexCell._x && endCell._y == hexCell._y && endCell._z == hexCell._z) //same - do nothing
{
}
else if (hexCell._type != cellType.WALL)
{
endCell._type = 0;
hexCell._type = cellType.END;
endCell = hexCell;
endShape.x = hexCell.x;
endShape.y = hexCell.y;
//wallArray[randomWallNum + 1] = cell._x + cell._y * cellWidthNum;
search();
}
}
else if (wallButton.selected == true)
{
hexCell.alpha = 1;
hexCell._type = 1 - hexCell._type; // 1->0, 0->1
if (hexCell._type == cellType.ROAD)
{
hexCell.drawCell(hexCell._G.graphics, true, cellColor);
}
else
{
hexCell.drawCell(hexCell._G.graphics, true, wallColor);
}
if (hexCell._type == cellType.WALL)
{
hexCell._parent = null;
}
hexCell.drawPath();
search();
}
//trace(hexCell._x, hexCell._y, hexCell._z, "_f : ", hexCell._f);
}
private function calcBoundary(x:int, y:int, z:int):Boolean
{
var r:int = z + (x - (x & 1)) / 2;
if (r<=mapSize * 2 / 3 && r >= -mapSize * 2 / 3 &&
x<=mapSize * 2 / 3 && x >= -mapSize * 2 / 3) //정사각형
{
return true;
}
else
{
return false;
}
}
private function initMap(map:Vector.<Vector.<Vector.<HexCell>>>):void
{
var hexCell:HexCell;
var i:int, j:int, k:int;
var r:int;
var serialIndex:int = 0;
for (i = -1 * mapSizeMax; i < mapSizeMax + 1; i += 1)
{
map[i + mapSizeMax] = new Vector.<Vector.<HexCell>>(mapsizeMaxDouble);
for (j = -1 * mapSizeMax; j < mapSizeMax + 1; j += 1)
{
map[i + mapSizeMax][j + mapSizeMax] = new Vector.<HexCell>(mapsizeMaxDouble);
for (k = -1 * mapSizeMax; k < mapSizeMax + 1; k += 1)
{
if (i + j + k == 0)
{
hexCell = new HexCell(i, j, k, edgeLength);
map[i + mapSizeMax][j + mapSizeMax][k + mapSizeMax] = hexCell;
mapSerialArray[serialIndex] = new Vector.<int>(3);
mapSerialArray[serialIndex][0] = i;
mapSerialArray[serialIndex][1] = j;
mapSerialArray[serialIndex][2] = k;
serialIndex += 1;
}
}
}
}
}
private function onStartChange(e:Event):void
{
if (startButton.selected == true)
{
endButton.selected = false;
wallButton.selected = false;
}
}
private function onEndChange(e:Event):void
{
if (endButton.selected == true)
{
startButton.selected = false;
wallButton.selected = false;
}
}
private function onWallChange(e:Event):void
{
if (wallButton.selected == true)
{
startButton.selected = false;
endButton.selected = false;
}
}
private function onReset(e:Event):void
{
open = [];
closed = [];
var i:int;
var j:int;
var hexCell:HexCell;
var cx:int, cy:int, cz:int;
for (i = 0; i < mapSerialArray.length; i += 1)
{
cx = mapSerialArray[i][0];
cy = mapSerialArray[i][1];
cz = mapSerialArray[i][2];
if (calcBoundary(cx, cy, cz) == true)
{
hexCell = map[cx + mapSizeMax][cy + mapSizeMax][cz + mapSizeMax];
hexCell._parent = null;
hexCell._type = 0;
hexCell._f = 0;
hexCell._g = 0;
hexCell._h = 0;
hexCell.drawPath();
hexCell.drawCell(hexCell._G.graphics, true, cellColor);
}
}
initRandomWall();
calcH();
closed.push(startCell);
for (i = 0; i < 6; i += 1)
{
cx = startCell._x + neighbors[i][0];
cy = startCell._y + neighbors[i][1];
cz = startCell._z + neighbors[i][2];
if (calcBoundary(cx, cy, cz) == true)
{
hexCell = map[cx + mapSizeMax][cy + mapSizeMax][cz + mapSizeMax];
if (hexCell._type != cellType.WALL)
{
open.push(hexCell);
hexCell._g += 1;
hexCell._f = hexCell._g + hexCell._h;
hexCell._parent = startCell;
hexCell.drawPath();
}
}
}
calcG();
drawPath();
}
private function drawPath():void
{
var nowCell:HexCell = endCell;
var pathRect:Rectangle;
pathBitmapData.fillRect(pathBitmapData.rect, 0x00ffffff);
mat = new Matrix();
mat.translate(nowCell.x, nowCell.y);
pathBitmapData.draw(oneCellShape, mat);
if (open.length > 0)
{
while (true)
{
nowCell = nowCell._parent;
mat = new Matrix();
mat.translate(nowCell.x, nowCell.y);
pathBitmapData.draw(oneCellShape, mat);
if (nowCell._x == startCell._x && nowCell._y == startCell._y && nowCell._z == startCell._z)
break;
}
}
}
private function calcG():void //main A* algorithm
{
var minScore:int;
//var minCell:Cell;
var minIndex:int;
var nowCell:HexCell;
var i:int;
var j:int;
var k:int;
var hexCell:HexCell;
var cx:int, cy:int, cz:int;
var closedCell:HexCell;
var goCost:int;
while (open.length > 0) //until fail to find
{
minScore = int.MAX_VALUE;
minIndex = -1;
for (i = 0; i < open.length; i += 1)
{
hexCell = open[i];
if (hexCell._f < minScore)
{
minScore = hexCell._f;
minIndex = i;
}
}
nowCell = open[minIndex];
if (nowCell._x == endCell._x && nowCell._y == endCell._y && nowCell._z == endCell._z) //found endCell
{
break;
}
else
{
open.splice(minIndex, 1);
closed.push(nowCell); //nowCell from open to closed
for (j = 0; j < 6; j += 1)
{
cx = nowCell._x + neighbors[j][0];
cy = nowCell._y + neighbors[j][1];
cz = nowCell._z + neighbors[j][2];
if (calcBoundary(cx, cy, cz) == true)
{
hexCell = map[cx + mapSizeMax][cy + mapSizeMax][cz + mapSizeMax];
if (hexCell._type == cellType.WALL) //wall - cannot go
{
continue;
}
else
{
if (isInArray(closed, hexCell) == true) //already in closed - would not go
{
continue;
}
else
{
if(isInArray(open, hexCell) == false) //not in open - push it
{
open.push(hexCell);
hexCell._g += 1;
hexCell._f = hexCell._g + hexCell._h;
hexCell._parent = nowCell;
hexCell.drawPath();
}
else //already in open
{
goCost = 1;
if (hexCell._g > nowCell._g + goCost)
{
hexCell._g = nowCell._g + goCost;
hexCell._f = hexCell._g + hexCell._h;
hexCell._parent = nowCell;
hexCell.drawPath();
}
}
}
}
}
}
}
}
}
private function isInArray(arr:Array, hexCell:HexCell):Boolean
{
var i:int;
var arrCell:HexCell;
for (i = 0; i < arr.length; i += 1)
{
arrCell = arr[i];
if (arrCell._x == hexCell._x && arrCell._y == hexCell._y && arrCell._z == hexCell._z)
{
return true;
}
}
return false;
}
private function calcH():void
{
var i:int;
var hexCell:HexCell;
var dx:int, dy:int, dz:int;
for (i = 0; i < mapSerialArray.length; i += 1)
{
dx = mapSerialArray[i][0];
dy = mapSerialArray[i][1];
dz = mapSerialArray[i][2];
if (calcBoundary(dx, dy, dz) == true)
{
hexCell = map[dx + mapSizeMax][dy + mapSizeMax][dz + mapSizeMax];
if (hexCell._type == cellType.WALL)
{
continue;
}
else if (hexCell._type == cellType.START)
{
continue;
}
else
{
hexCell._h = hex_distance([hexCell._x, hexCell._y, hexCell._z], [endCell._x, endCell._y, endCell._z]);
hexCell._f = hexCell._g + hexCell._h;
}
}
}
}
private function search():void
{
open = [];
closed = [];
var i:int;
var j:int;
var hexCell:HexCell;
var cx:int, cy:int, cz:int;
for (i = 0; i < mapSerialArray.length; i += 1)
{
cx = mapSerialArray[i][0];
cy = mapSerialArray[i][1];
cz = mapSerialArray[i][2];
if (calcBoundary(cx, cy, cz) == true)
{
hexCell = map[cx + mapSizeMax][cy + mapSizeMax][cz + mapSizeMax];
hexCell._parent = null;
//hexCell._type = 0;
hexCell._f = 0;
hexCell._g = 0;
hexCell._h = 0;
hexCell.drawPath();
//hexCell.drawCell(hexCell._G.graphics, true, cellColor);
}
}
//initRandomWall(); //not necessary
calcH();
closed.push(startCell);
for (i = 0; i < 6; i += 1)
{
cx = startCell._x + neighbors[i][0];
cy = startCell._y + neighbors[i][1];
cz = startCell._z + neighbors[i][2];
if (calcBoundary(cx, cy, cz) == true)
{
hexCell = map[cx + mapSizeMax][cy + mapSizeMax][cz + mapSizeMax];
if (hexCell._type != cellType.WALL)
{
open.push(hexCell);
hexCell._g += 1;
hexCell._f = hexCell._g + hexCell._h;
hexCell._parent = startCell;
hexCell.drawPath();
}
}
}
calcG();
drawPath();
}
private function onHexCellMouseOver(e:MouseEvent):void
{
var cell:HexCell = e.target.parent as HexCell;
if (cell != null)
{
if (cell._type != cellType.WALL)
cell.alpha = 0.5;
}
}
private function onHexCellMouseOut(e:MouseEvent):void
{
var cell:HexCell = e.target.parent as HexCell;
if (cell != null)
{
if (cell._type != cellType.WALL)
cell.alpha = 1;
}
}
private function initRandomWall():void
{
var i:int;
var hexCell:HexCell;
wallArray = printRandomNumber(mapSerialArray.length, mapSerialArray.length); // wall + startPoint + endPoint
var wallNum:int = 0;
var index:int = 0;
var dx:int;
var dy:int;
var dz:int;
while (wallNum < randomWallNum + 2)
{
dx = mapSerialArray[wallArray[index]][0];
dy = mapSerialArray[wallArray[index]][1];
dz = mapSerialArray[wallArray[index]][2];
if (calcBoundary(dx, dy, dz) == true)
{
hexCell = map[dx + mapSizeMax][dy + mapSizeMax][dz + mapSizeMax];
hexCell._type = cellType.WALL;
if (wallNum == 0)
{
startCell = hexCell;
hexCell._type = cellType.START;
startShape.x = startCell.x;
startShape.y = startCell.y;
}
else if (wallNum == 1)
{
endCell = hexCell;
hexCell._type = cellType.END;
endShape.x = endCell.x;
endShape.y = endCell.y;
}
else
{
hexCell.drawCell(hexCell._G.graphics, true, wallColor);
}
wallNum += 1;
}
index += 1;
}
//init start, end
if (startShape.parent == null)
{
addChild(startShape);
}
if (endShape.parent == null)
{
addChild(endShape);
}
}
private function printRandomNumber(n:int, k:int) : Array
{
var original:Array=[];
var result:Array=[];
var i:int;
var randInt:int;
var temp:Object;
for(i=0;i<n;i+=1)
{
original.push(i);
}
for(i=0;i<k;i+=1)
{
randInt = Math.random()*(n-i) + i;
temp = original[i];
original[i] = original[randInt];
original[randInt] = temp;
result.push(original[i]);
}
return result;
}
private function hex_distance(cube1:Array, cube2:Array):int
{
var xDist:int, yDist:int, zDist:int;
xDist = cube1[0] - cube2[0];
xDist = (xDist ^ (xDist >> 31)) - (xDist >> 31);
yDist = cube1[1] - cube2[1];
yDist = (yDist ^ (yDist >> 31)) - (yDist >> 31);
zDist = cube1[2] - cube2[2];
zDist = (zDist ^ (zDist >> 31)) - (zDist >> 31);
return (xDist + yDist + zDist) / 2;
}
}
}
Class
{
import com.bit101.components.Label;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Graphics;
import flash.display.Shape;
import flash.display.Sprite;
import flash.geom.ColorTransform;
/**
* ...
* @author ypc
*/
class HexCell extends Sprite
{
public var _x:int;
public var _y:int;
public var _z:int;
public var _G:Sprite;
public var _GLine:Shape;
public var _pathShape:Shape;
public var edgeLength:int = 20;
public var _parent:HexCell = null;
public var _f:int = 0;
public var _g:int = 0;
public var _h:int = 0;
public var _type:int = 0;
public function HexCell(_x:int, _y:int, _z:int, edge:int=20)
{
this._x = _x;
this._y = _y;
this._z = _z;
this.edgeLength = edge;
_G = new Sprite();
_GLine = new Shape();
_pathShape = new Shape();
addChild(_G);
addChild(_GLine);
addChild(_pathShape);
}
public function drawPath():void
{
var dx:int, dy:int;
if (this._parent != null)
{
_pathShape.graphics.clear();
_pathShape.graphics.lineStyle(1, 0xff00ff);
_pathShape.graphics.drawCircle(0, 0, edgeLength / 3);
_pathShape.graphics.moveTo(0, 0);
dx = this._parent._x - this._x;
dy = ( -this._parent._y + this._parent._z) - ( -this._y + this._z);
_pathShape.graphics.lineTo(dx * edgeLength / 2, dy * edgeLength / 2);
}
else //parent null -> clear
{
_pathShape.graphics.clear();
}
}
public function drawCell(_G:Graphics, fill:Boolean, color:uint=0xffffff):void
{
var angle:Number;
_G.clear();
if (fill == true)
{
_G.beginFill(color);
}
else
{
_G.lineStyle(1, color);
}
_G.moveTo(edgeLength, 0);
for (var i:int = 1; i <= 6; i += 1)
{
angle = 2 * Math.PI / 6 * i;
_G.lineTo(edgeLength * Math.cos(angle), edgeLength * Math.sin(angle));
}
if(fill == true)
{
_G.endFill();
}
}
}
}