A* algorithm
Yes, there are already many visualizations in this site and others, but I wanted my own version..
you can change startPoint, endPoint, and wall. or you can reset everything.
Reference - http://www.policyalmanac.org/games/aStarTutorial.htm
/**
* Copyright greentec ( http://wonderfl.net/user/greentec )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/sNHA
*/
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;
public class FlashTest extends Sprite {
public var backBitmap:Bitmap;
public var open:Array = [];
public var closed:Array = [];
public var cellArray:Array = [];
public var cellWidthNum:int = 10;
public var pathBitmap:Bitmap;
public var pathBitmapData:BitmapData;
public var randomWallNum:int = cellWidthNum * cellWidthNum * 0.2;
public var wallArray:Array = [];
public var cellWidth:int = 44;
public var startShape:Shape;
public var endShape:Shape;
public var cellType:Object = {
ROAD : 0,
WALL : 1,
START: 2,
END : 3
}
public var startCell:Cell;
public var endCell:Cell;
public var dir:Array = [[ -1, -1], [ -1, 0], [ -1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]];
public var resetButton:PushButton;
public var startButton:PushButton;
public var endButton:PushButton;
public var wallButton:PushButton;
public function FlashTest() {
// write as3 code here..
stage.scaleMode = "noScale";
backBitmap = new Bitmap(new BitmapData(465, 465, false, 0x292929));
addChild(backBitmap);
var i:int;
var j:int;
for (i = 0; i < cellWidthNum; i += 1)
{
cellArray[i] = [];
for (j = 0; j < cellWidthNum; j += 1)
{
cellArray[i].push(new Cell(i, j));
}
}
startShape = new Shape();
startShape.graphics.clear();
startShape.graphics.lineStyle(1, 0xcccccc);
startShape.graphics.beginFill(0x1861FF, 0.7);
startShape.graphics.drawCircle(22, 22, 16);
startShape.graphics.endFill();
endShape = new Shape();
endShape.graphics.clear();
endShape.graphics.lineStyle(1, 0xcccccc);
endShape.graphics.beginFill(0xF7360F, 0.7);
endShape.graphics.drawCircle(22, 22, 16);
endShape.graphics.endFill();
initRandomWall();
drawCell();
drawStartEnd();
calcH();
closed.push(startCell);
var cell:Cell;
var cx:int;
var cy:int;
var dx:int;
var dy:int;
for (i = 0; i < dir.length; i += 1)
{
cx = startCell._x + dir[i][0];
cy = startCell._y + dir[i][1];
if (cx >= 0 && cx < cellWidthNum && cy >= 0 && cy < cellWidthNum)
{
cell = cellArray[cx][cy];
if (cell._type != cellType.WALL)
{
open.push(cell);
if (i % 2 == 0)
{
cell._g += 14;
}
else
{
cell._g += 10;
}
cell._f = cell._g + cell._h;
cell.drawLabel();
cell._parent = startCell;
cell.drawPath();
}
}
}
calcG();
pathBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
pathBitmap = new Bitmap(pathBitmapData);
addChild(pathBitmap);
drawPath();
resetButton = new PushButton(this, 0, cellWidth * cellWidthNum, "Reset", onReset);
resetButton.width = 110;
resetButton.height = 465 - cellWidth * cellWidthNum;
startButton = new PushButton(this, 110, resetButton.y, "Start Change", onStartChange);
startButton.width = 110;
startButton.height = resetButton.height;
startButton.toggle = true;
endButton = new PushButton(this, 220, resetButton.y, "End Change", onEndChange);
endButton.width = 110;
endButton.height = resetButton.height;
endButton.toggle = true;
wallButton = new PushButton(this, 330, resetButton.y, "Wall Change", onWallChange);
wallButton.width = 110;
wallButton.height = resetButton.height;
wallButton.toggle = true;
}
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 cell:Cell;
for (i = 0; i < cellWidthNum; i += 1)
{
for (j = 0; j < cellWidthNum; j += 1)
{
cell = cellArray[i][j];
cell._parent = null;
cell._type = 0;
cell._f = 0;
cell._g = 0;
cell._h = 0;
}
}
initRandomWall();
for (i = 0; i < cellWidthNum; i += 1)
{
for (j = 0; j < cellWidthNum; j += 1)
{
cell = cellArray[i][j];
cell.drawCell();
cell.drawPath();
cell.drawLabel();
}
}
drawStartEnd();
calcH();
closed.push(startCell);
var cx:int;
var cy:int;
var dx:int;
var dy:int;
for (i = 0; i < dir.length; i += 1)
{
cx = startCell._x + dir[i][0];
cy = startCell._y + dir[i][1];
if (cx >= 0 && cx < cellWidthNum && cy >= 0 && cy < cellWidthNum)
{
cell = cellArray[cx][cy];
if (cell._type != cellType.WALL)
{
open.push(cell);
if (i % 2 == 0)
{
cell._g += 14;
}
else
{
cell._g += 10;
}
cell._f = cell._g + cell._h;
cell.drawLabel();
cell._parent = startCell;
cell.drawPath();
}
}
}
calcG();
drawPath();
}
private function drawPath():void
{
var nowCell:Cell = endCell;
var pathRect:Rectangle;
pathBitmapData.fillRect(pathBitmapData.rect, 0x00ffffff);
pathRect = new Rectangle(nowCell.x, nowCell.y, cellWidth, cellWidth);
pathBitmapData.fillRect(pathRect, 0x8000dd00);
if (open.length > 0)
{
while (true)
{
nowCell = nowCell._parent;
pathRect = new Rectangle(nowCell.x, nowCell.y, cellWidth, cellWidth);
pathBitmapData.fillRect(pathRect, 0x8000dd00);
if (nowCell._x == startCell._x && nowCell._y == startCell._y)
break;
}
}
}
private function calcG():void //main A* algorithm
{
var minScore:int;
//var minCell:Cell;
var minIndex:int;
var nowCell:Cell;
var i:int;
var j:int;
var k:int;
var cell:Cell;
var cx:int;
var cy:int;
var closedCell:Cell;
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)
{
cell = open[i];
if (cell._f < minScore)
{
minScore = cell._f;
minIndex = i;
}
}
nowCell = open[minIndex];
if (nowCell._x == endCell._x && nowCell._y == endCell._y) //found endCell
{
break;
}
else
{
open.splice(minIndex, 1);
closed.push(nowCell); //nowCell from open to closed
for (j = 0; j < dir.length; j += 1)
{
cx = nowCell._x + dir[j][0];
cy = nowCell._y + dir[j][1];
if (cx >= 0 && cx < cellWidthNum && cy >= 0 && cy < cellWidthNum)
{
cell = cellArray[cx][cy];
if (cell._type == cellType.WALL) //wall - cannot go
{
continue;
}
else
{
if (isInArray(closed, cell) == true) //already in closed - would not go
{
continue;
}
else
{
if(isInArray(open, cell) == false) //not in open - push it
{
open.push(cell);
if (j % 2 == 0)
{
cell._g = nowCell._g + 14;
}
else
{
cell._g = nowCell._g + 10;
}
cell._f = cell._g + cell._h;
cell.drawLabel();
cell._parent = nowCell;
cell.drawPath();
}
else //already in open
{
if (j % 2 == 0)
{
goCost = 14;
}
else
{
goCost = 10;
}
if (cell._g > nowCell._g + goCost)
{
cell._g = nowCell._g + goCost;
cell._f = cell._g + cell._h;
cell.drawLabel();
cell._parent = nowCell;
cell.drawPath();
//cell._parent = nowCell;
//cell.drawPath();
}
}
}
}
}
}
}
}
}
private function isInArray(arr:Array, cell:Cell):Boolean
{
var i:int;
var arrCell:Cell;
for (i = 0; i < arr.length; i += 1)
{
arrCell = arr[i];
if (arrCell._x == cell._x && arrCell._y == cell._y)
{
return true;
}
}
return false;
}
private function calcH():void
{
var i:int, j:int;
var cell:Cell;
var dx:int;
var dy:int;
for (i = 0; i < cellWidthNum; i += 1)
{
for (j = 0; j < cellWidthNum; j += 1)
{
cell = cellArray[i][j];
if (cell._type == cellType.WALL)
{
continue;
}
else if(cell._type == cellType.START)
{
continue;
}
else
{
dx = cell._x - endCell._x;
dx = (dx ^ dx >> 31) - (dx >> 31);
dy = cell._y - endCell._y;
dy = (dy ^ dy >> 31) - (dy >> 31);
if (dx > dy)
cell._h = 14 * dy + 10 * (dx - dy);
else
cell._h = 14 * dx + 10 * (dy - dx);
cell._f = cell._g + cell._h;
cell.drawLabel();
}
}
}
}
private function drawStartEnd():void
{
var startIndex:int = wallArray[randomWallNum];
var endIndex:int = wallArray[randomWallNum + 1];
startCell = cellArray[startIndex % cellWidthNum][int(startIndex / cellWidthNum)];
startCell._type = cellType.START;
startShape.x = startCell.x;
startShape.y = startCell.y;
endCell = cellArray[endIndex % cellWidthNum][int(endIndex / cellWidthNum)];
endCell._type = cellType.END;
endShape.x = endCell.x;
endShape.y = endCell.y;
if (startShape.parent == null)
{
addChild(startShape);
}
if (endShape.parent == null)
{
addChild(endShape);
}
}
private function drawCell():void
{
var i:int;
var j:int;
var cell:Cell;
for (i = 0; i < cellWidthNum; i += 1)
{
for (j = 0; j < cellWidthNum; j += 1)
{
cell = cellArray[i][j];
cell.drawCell();
cell.x = cell._x * cellWidth;
cell.y = cell._y * cellWidth;
cell.addEventListener(MouseEvent.CLICK, onCellClick);
cell.addEventListener(MouseEvent.MOUSE_OVER, onCellMouseOver);
cell.addEventListener(MouseEvent.MOUSE_OUT, onCellMouseOut);
addChild(cell);
}
}
}
private function search():void
{
open = [];
closed = [];
var i:int;
var j:int;
var cell:Cell;
for (i = 0; i < cellWidthNum; i += 1)
{
for (j = 0; j < cellWidthNum; j += 1)
{
cell = cellArray[i][j];
cell._parent = null;
cell._f = 0;
cell._g = 0;
cell._h = 0;
cell.drawLabel();
cell.drawPath();
}
}
drawStartEnd();
calcH();
closed.push(startCell);
var cx:int;
var cy:int;
var dx:int;
var dy:int;
for (i = 0; i < dir.length; i += 1)
{
cx = startCell._x + dir[i][0];
cy = startCell._y + dir[i][1];
if (cx >= 0 && cx < cellWidthNum && cy >= 0 && cy < cellWidthNum)
{
cell = cellArray[cx][cy];
if (cell._type != cellType.WALL)
{
open.push(cell);
if (i % 2 == 0)
{
cell._g += 14;
}
else
{
cell._g += 10;
}
cell._f = cell._g + cell._h;
cell.drawLabel();
cell._parent = startCell;
cell.drawPath();
}
}
}
calcG();
drawPath();
}
private function onCellClick(e:MouseEvent):void
{
var cell:Cell = e.target as Cell;
if (startButton.selected == true)
{
if (startCell._x == cell._x && startCell._y == cell._y) //same - do nothing
{
}
else if (endCell._x == cell._x && endCell._y == cell._y) //overlap - do nothing
{
}
else if (cell._type != cellType.WALL)
{
startCell._type = 0;
wallArray[randomWallNum] = cell._x + cell._y * cellWidthNum;
search();
}
}
else if (endButton.selected == true)
{
if (startCell._x == cell._x && startCell._y == cell._y) //overlap - do nothing
{
}
else if (endCell._x == cell._x && endCell._y == cell._y) //same - do nothing
{
}
else if (cell._type != cellType.WALL)
{
endCell._type = 0;
wallArray[randomWallNum + 1] = cell._x + cell._y * cellWidthNum;
search();
}
}
else if (wallButton.selected == true)
{
cell.alpha = 1;
cell._type = 1 - cell._type; // 1->0, 0->1
cell.drawCell();
cell.drawLabel();
if (cell._type == cellType.WALL)
{
cell._parent = null;
}
cell.drawPath();
search();
}
}
private function onCellMouseOver(e:MouseEvent):void
{
var cell:Cell = e.target as Cell;
if (cell._type != cellType.WALL)
cell.alpha = 0.5;
}
private function onCellMouseOut(e:MouseEvent):void
{
var cell:Cell = e.target as Cell;
if (cell._type != cellType.WALL)
cell.alpha = 1;
}
private function initRandomWall():void
{
var i:int;
var cell:Cell;
wallArray = printRandomNumber(cellWidthNum * cellWidthNum, randomWallNum + 2); // wall + startPoint + endPoint
for (i = 0; i < randomWallNum; i += 1)
{
cell = cellArray[wallArray[i] % cellWidthNum][int(wallArray[i] / cellWidthNum)];
cell._type = cellType.WALL;
}
}
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;
}
}
}
Class
{
import com.bit101.components.Label;
import flash.display.Shape;
import flash.display.Sprite;
/**
* ...
* @author ypc
*/
class Cell extends Sprite
{
public var _parent:Cell = null;
public var _x:int;
public var _y:int;
public var _type:int = 0;
public var _f:int = 0;
public var _g:int = 0;
public var _h:int = 0;
public var fLabel:Label;
public var gLabel:Label;
public var hLabel:Label;
public var cellWidth:int = 44;
public var cellBorderColor:uint = 0x443d2f;
public var cellColor:uint = 0xffe0ab;
public var wallColor:uint = 0x7f7056;
public var pathShape:Shape;
public var cellType:Object = {
ROAD : 0,
WALL : 1,
START: 2,
END : 3
}
public function Cell(x:int, y:int)
{
this._x = x;
this._y = y;
pathShape = new Shape();
addChild(pathShape);
fLabel = new Label(this, 0, 0, "");
gLabel = new Label(this, 0, 25, "");
hLabel = new Label(this, 25, 25, "");
}
public function drawPath():void
{
var dx:int, dy:int;
if (this._parent != null)
{
pathShape.graphics.clear();
pathShape.graphics.lineStyle(1, 0xff00ff);
pathShape.graphics.drawCircle(cellWidth / 2 , cellWidth / 2, cellWidth / 8);
pathShape.graphics.moveTo(cellWidth / 2, cellWidth / 2);
dx = this._parent._x - this._x;
dy = this._parent._y - this._y;
if ((dx + dy) % 2 == 0) //diagonal
{
pathShape.graphics.lineTo(cellWidth / 2 + dx * 10, cellWidth / 2 + dy * 10);
}
else
{
pathShape.graphics.lineTo(cellWidth / 2 + dx * 14, cellWidth / 2 + dy * 14);
}
}
else //parent null -> clear
{
pathShape.graphics.clear();
}
}
public function drawCell():void
{
this.graphics.clear();
this.graphics.lineStyle(1, cellBorderColor);
if(this._type == cellType.WALL)
{
this.graphics.beginFill(cellBorderColor);
}
else
{
this.graphics.beginFill(cellColor);
this.drawLabel();
}
this.graphics.drawRect(0, 0, cellWidth, cellWidth);
this.graphics.endFill();
}
public function drawLabel():void
{
if (this._type != cellType.WALL)
{
fLabel.text = String(this._f);
gLabel.text = String(this._g);
hLabel.text = String(this._h);
}
else
{
fLabel.text = "";
gLabel.text = "";
hLabel.text = "";
}
}
}
}