eagle
%Europe/Berlin %850 %2005, 21:24
Gegroet flashers,
Naar aanleiding van Dauntless' A* zoekalgoritme, zijn wij(Thomas Van Durme en Thomas Devriendt) zelf een zoekalgoritme gaan samenstellen.
Wij noemden het BMP (Bidirectional Matrix Pathfinder) en het heeft zijn wortels in Dijkstra's zoekalgoritme. Het werd herschreven naar een bidirectional matrix systeem. Het algoritme zoekt in een binaire ruimte het korste 'path' tussen twee opgegeven punten.
Het bestaat uit 1 class en 1 ondersteunende class voor visualisatie.
De class van het zoekalgoritme:
class classes.cof.algorithms.Bmp {
//member arrays
private var _binmap:Array = Array();
private var _openstack_s:Array = Array();
private var _openstack_e:Array = Array();
private var _closedstack_s:Array = Array();
private var _closedstack_e:Array = Array();
private var _path:Array = Array();
//member objects
private var _startpoint:Object = Object();
private var _endpoint:Object = Object();
private var _connectionpoint:Object = Object();
//member booleans
private var _nopath:Boolean = false;
//public functions
public function initiate():Void {
setStartData();
matrixAddItem();
}
public function setMap(_a:Array):Void {
_binmap = _a;
}
public function setStartpoint(x:Number, y:Number):Void {
_startpoint.x = x;
_startpoint.y = y;
}
public function setEndpoint(x:Number, y:Number):Void {
_endpoint.x = x;
_endpoint.y = y;
}
public function getPath() {
//returns an array if there is a path
//returns false if no path was found
if (!_nopath) {
return _path;
} else {
return false;
}
}
//private functions
private function setStartData():Void {
var a:Object = _startpoint;
var b:Object = _endpoint;
_openstack_s.push(Array(a.x, a.y, a.x, a.y, "S"));
_openstack_e.push(Array(b.x, b.y, b.x, b.y, "E"));
}
private function setConnectionPoint(x:Number, y:Number):Void {
_connectionpoint.x = x;
_connectionpoint.y = y;
}
private function getCoorSpecs(_a:Array):Object {
var f:Object = Object();
var dim:Object = getMapDimension();
f.xMin = _a[0]-1;
f.yMin = _a[1]-1;
f.x = _a[0];
f.y = _a[1];
f.px = _a[2];
f.py = _a[3];
return f;
}
private function coorHeigthWidth(a:Number, str:String):Number {
var dim:Object = getMapDimension();
if (str == "y") {
if (a<0) {
a = 0;
}
if (a>dim.h-1) {
a = dim.h-1;
}
} else if (str == "x") {
if (a<0) {
a = 0;
}
if (a>dim.w-1) {
a = dim.w-1;
}
}
return a;
}
private function getMapDimension():Object {
var dim:Object = Object();
dim.w = Number(_binmap[0].length);
dim.h = Number(_binmap.length);
return dim;
}
private function matrixAddItem():Void {
var _abort:Boolean = false;
while (!_abort) {
if (_openstack_e.length == 0 or _openstack_s.length == 0) {
_nopath = true;
_abort = true;
break;
}
var s:Object = getCoorSpecs(_openstack_s[0]);
var e:Object = getCoorSpecs(_openstack_e[0]);
for (var j = 0; j<3; j++) {
for (var i = 0; i<3; i++) {
var sx:Number = coorHeigthWidth(s.xMin+i, "x");
var sy:Number = coorHeigthWidth(s.yMin+j, "y");
var ex:Number = coorHeigthWidth(e.xMin+i, "x");
var ey:Number = coorHeigthWidth(e.yMin+j, "y");
if (checkWalkability(sx, sy) and notUsed(sx, sy, "S")) {
_openstack_s.push(Array(sx, sy, s.x, s.y, "S"));
}
if (checkWalkability(ex, ey) and notUsed(ex, ey, "E")) {
_openstack_e.push(Array(ex, ey, e.x, e.y, "E"));
}
if (isPath(ex, sx, ey, sy)) {
_abort = true;
break;
}
}
if (_abort) {
break;
}
}
_closedstack_s.push(Array(s.x, s.y, s.px, s.py, "S"));
_closedstack_e.push(Array(e.x, e.y, e.px, e.py, "E"));
_openstack_s.shift();
_openstack_e.shift();
}
}
private function checkWalkability(x:Number, y:Number):Boolean {
var bool:Boolean = true;
if (_binmap[y][x] == 0) {
bool = false;
}
return bool;
}
private function notUsed(x:Number, y:Number, _a:String):Boolean {
var bool:Boolean = true;
var _b:Array = Array();
var _c:Array = Array();
if (_a == "S") {
_b = _openstack_s;
_c = _closedstack_s;
} else if (_a == "E") {
_b = _openstack_e;
_c = _closedstack_e;
}
bool = notUsedLoop(x, y, _b);
if (bool) {
bool = notUsedLoop(x, y, _c);
}
return bool;
}
private function notUsedLoop(x:Number, y:Number, _a:Array):Boolean {
var bool:Boolean = true;
for (var i = 0; i<_a.length; i++) {
if ((_a[i][0] == x and _a[i][1] == y) or (_a[i][2] == x and _a[i][3] == y)) {
bool = false;
break;
}
}
return bool;
}
private function getParent(x:Number, y:Number, _a:Array):Object {
var dt:Object = Object();
dt.bool = false;
for (var i = 0; i<_a.length; i++) {
if (_a[i][0] == x and _a[i][1] == y) {
dt.bool = true;
dt.x = _a[i][2];
dt.y = _a[i][3];
break;
}
}
return dt;
}
private function checkForMatch(x:Number, y:Number, a:Array, b:Array):Boolean {
//returns true if match, false if no match
var match:Boolean = false;
for (var c = 0; c<a.length; c++) {
if (a[c][0] == x and a[c][1] == y) {
match = true;
break;
}
}
if (!match) {
for (var d = 0; d<b.length; d++) {
if (b[d][0] == x and b[d][1] == y) {
match = true;
break;
}
}
}
return match;
}
private function isPath(ex:Number, sx:Number, ey:Number, sy:Number):Boolean {
var match_s:Boolean = checkForMatch(sx, sy, _openstack_e, _closedstack_e);
var match_e:Boolean = checkForMatch(ex, ey, _openstack_s, _closedstack_s);
if (match_s) {
setConnectionPoint(sx, sy);
pathRebuilt(sx, sy);
return true;
} else if (match_e) {
setConnectionPoint(ex, ey);
pathRebuilt(ex, ey);
return true;
}
return false;
}
private function pathRebuilt(x:Number, y:Number):Void {
var path:Array = Array();
path = pathRebuiltLoop(x, y, "S");
path.reverse();
path.push(Array(x, y));
_path = path.concat(pathRebuiltLoop(x, y, "E"));
}
private function pathRebuiltLoop(x:Number, y:Number, str:String):Array {
var dt:Object = Object();
dt.bool = true;
var _point:Object = Object();
var _a:Array = Array();
var _b:Array = Array();
var path:Array = Array();
if (str == "S") {
_a = _openstack_s;
_b = _closedstack_s;
_point.x = _startpoint.x;
_point.y = _startpoint.y;
} else if (str == "E") {
_a = _openstack_e;
_b = _closedstack_e;
_point.x = _endpoint.x;
_point.y = _endpoint.y;
}
var z:Number = 0;
var _abort:Boolean = false;
while (!_abort) {
dt = getParent(x, y, _a);
if (!dt.bool) {
dt = getParent(x, y, _b);
}
if (dt.bool) {
path.push(Array(dt.x, dt.y));
x = dt.x;
y = dt.y;
}
if (x == _point.x and y == _point.y) {
_abort = true;
}
}
return path;
}
}
De code van de visualisatie-class; deze genereert een random binaire map
de link naar de swf file vind je onderaan
class classes.cof.visual.Visualbmp {
private var _map:Array = Array();
private var _frequency:Number;
private var _w:Number;
private var _h:Number;
private var _tilew:Number;
private var _tileh:Number;
private var _mc:MovieClip;
private var _startpoint:Object = Object();
private var _endpoint:Object = Object();
public function setMc(a:MovieClip):Void {
_mc = a;
}
public function setMap(w:Number, h:Number):Void {
_w = w;
_h = h;
}
public function setTilesize(w:Number, h:Number):Void {
_tilew = w;
_tileh = h;
}
public function setBlackFrequency(a:Number):Void {
//a number bewteen 0 and 100 wich defines the not walkable areas
if (_frequency<0 and _frequency>100) {
a = 50;
}
_frequency = a;
}
public function getStartpoint():Object {
return _startpoint;
}
public function getEndpoint():Object {
return _endpoint;
}
public function getMap():Array {
return _map;
}
public function getMapDimension():Object {
var a:Object = Object();
a.w = _w;
a.h = _h;
return a;
}
public function initiate() {
buildBinary();
setSpecialPoints();
buildVisual();
}
public function buildSolution(a:Array) {
for (var i = 0; i<a.length; i++) {
var x:Number = a[i][0];
var y:Number = a[i][1];
var b:MovieClip = _mc["tile"+x+"_"+y];
b.gotoAndStop(3);
}
}
private function getType():Boolean {
//returns false if not walkable
//returns true if walkable
var r:Number = Number(Math.random()*100);
if (r<_frequency) {
return false;
} else {
return true;
}
}
private function toBinary(a:Boolean):Number {
//changes booleans to binary values
if (a) {
return 1;
} else {
return 0;
}
}
private function buildBinary():Void {
var dim:Object = Object(getMapDimension());
for (var y = 0; y<dim.h; y++) {
_map[y] = new Array();
for (var x = 0; x<dim.w; x++) {
_map[y][x] = Number(toBinary(getType()));
}
}
}
private function setStartpoint(x:Number, y:Number):Void {
_startpoint.x = x;
_startpoint.y = y;
}
private function setEndpoint(x:Number, y:Number):Void {
_endpoint.x = x;
_endpoint.y = y;
}
private function setSpecialPoints():Void {
var dim:Object = Object(getMapDimension());
var ex:Number = dim.w-1;
var ey:Number = dim.h-1;
var sx:Number = 0;
var sy:Number = 0;
_map[sx][sy] = Number(1);
_map[ex][ey] = Number(1);
setStartpoint(sx, sy);
setEndpoint(ex, ey);
}
private function buildVisual():Void {
var dim:Object = Object(getMapDimension());
for (var y = 0; y<dim.h; y++) {
for (var x = 0; x<dim.w; x++) {
var a:MovieClip = _mc.attachMovie("tile", "tile"+x+"_"+y, _mc.getNextHighestDepth());
a._x = _tilew*x;
a._y = _tileh*y;
a.gotoAndStop(Number(_map[y][x]+1));
}
}
}
}
De code van de fla:
import classes.cof.algorithms.Bmp;
import classes.cof.visual.Visualbmp;
var a:Visualbmp = new Visualbmp();
var b:Bmp = new Bmp();
a.setMap(12, 12);
//het percentueel voorkomen van zwarte vakjes
a.setBlackFrequency(30);
a.setTilesize(40, 40);
a.setMc(_root);
a.initiate();
var startp:Object = a.getStartpoint();
var endp:Object = a.getEndpoint();
b.setMap(a.getMap());
b.setStartpoint(startp.x, startp.y);
b.setEndpoint(endp.x, endp.y);
var t1:Number = getTimer();
b.initiate();
var solution = b.getPath();
var t2:Number = getTimer()-t1;
if (solution == false) {
nopath.text = "No path found";
} else {
a.buildSolution(solution);
}
time.text = "bmp terminated after "+t2+" microseconds";
Klik hier voor een live preview, druk F5 of refresh om een andere random map te genereren.
Link naar cities-of-faith.com (http://www.cities-of-faith.com/bmp.php)
Een volledige source code volgt later.
Graag je commentare/suggesties/verbeteringen!
Groeten,
Thomas Van Durme & Thomas Devriendt
Naar aanleiding van Dauntless' A* zoekalgoritme, zijn wij(Thomas Van Durme en Thomas Devriendt) zelf een zoekalgoritme gaan samenstellen.
Wij noemden het BMP (Bidirectional Matrix Pathfinder) en het heeft zijn wortels in Dijkstra's zoekalgoritme. Het werd herschreven naar een bidirectional matrix systeem. Het algoritme zoekt in een binaire ruimte het korste 'path' tussen twee opgegeven punten.
Het bestaat uit 1 class en 1 ondersteunende class voor visualisatie.
De class van het zoekalgoritme:
class classes.cof.algorithms.Bmp {
//member arrays
private var _binmap:Array = Array();
private var _openstack_s:Array = Array();
private var _openstack_e:Array = Array();
private var _closedstack_s:Array = Array();
private var _closedstack_e:Array = Array();
private var _path:Array = Array();
//member objects
private var _startpoint:Object = Object();
private var _endpoint:Object = Object();
private var _connectionpoint:Object = Object();
//member booleans
private var _nopath:Boolean = false;
//public functions
public function initiate():Void {
setStartData();
matrixAddItem();
}
public function setMap(_a:Array):Void {
_binmap = _a;
}
public function setStartpoint(x:Number, y:Number):Void {
_startpoint.x = x;
_startpoint.y = y;
}
public function setEndpoint(x:Number, y:Number):Void {
_endpoint.x = x;
_endpoint.y = y;
}
public function getPath() {
//returns an array if there is a path
//returns false if no path was found
if (!_nopath) {
return _path;
} else {
return false;
}
}
//private functions
private function setStartData():Void {
var a:Object = _startpoint;
var b:Object = _endpoint;
_openstack_s.push(Array(a.x, a.y, a.x, a.y, "S"));
_openstack_e.push(Array(b.x, b.y, b.x, b.y, "E"));
}
private function setConnectionPoint(x:Number, y:Number):Void {
_connectionpoint.x = x;
_connectionpoint.y = y;
}
private function getCoorSpecs(_a:Array):Object {
var f:Object = Object();
var dim:Object = getMapDimension();
f.xMin = _a[0]-1;
f.yMin = _a[1]-1;
f.x = _a[0];
f.y = _a[1];
f.px = _a[2];
f.py = _a[3];
return f;
}
private function coorHeigthWidth(a:Number, str:String):Number {
var dim:Object = getMapDimension();
if (str == "y") {
if (a<0) {
a = 0;
}
if (a>dim.h-1) {
a = dim.h-1;
}
} else if (str == "x") {
if (a<0) {
a = 0;
}
if (a>dim.w-1) {
a = dim.w-1;
}
}
return a;
}
private function getMapDimension():Object {
var dim:Object = Object();
dim.w = Number(_binmap[0].length);
dim.h = Number(_binmap.length);
return dim;
}
private function matrixAddItem():Void {
var _abort:Boolean = false;
while (!_abort) {
if (_openstack_e.length == 0 or _openstack_s.length == 0) {
_nopath = true;
_abort = true;
break;
}
var s:Object = getCoorSpecs(_openstack_s[0]);
var e:Object = getCoorSpecs(_openstack_e[0]);
for (var j = 0; j<3; j++) {
for (var i = 0; i<3; i++) {
var sx:Number = coorHeigthWidth(s.xMin+i, "x");
var sy:Number = coorHeigthWidth(s.yMin+j, "y");
var ex:Number = coorHeigthWidth(e.xMin+i, "x");
var ey:Number = coorHeigthWidth(e.yMin+j, "y");
if (checkWalkability(sx, sy) and notUsed(sx, sy, "S")) {
_openstack_s.push(Array(sx, sy, s.x, s.y, "S"));
}
if (checkWalkability(ex, ey) and notUsed(ex, ey, "E")) {
_openstack_e.push(Array(ex, ey, e.x, e.y, "E"));
}
if (isPath(ex, sx, ey, sy)) {
_abort = true;
break;
}
}
if (_abort) {
break;
}
}
_closedstack_s.push(Array(s.x, s.y, s.px, s.py, "S"));
_closedstack_e.push(Array(e.x, e.y, e.px, e.py, "E"));
_openstack_s.shift();
_openstack_e.shift();
}
}
private function checkWalkability(x:Number, y:Number):Boolean {
var bool:Boolean = true;
if (_binmap[y][x] == 0) {
bool = false;
}
return bool;
}
private function notUsed(x:Number, y:Number, _a:String):Boolean {
var bool:Boolean = true;
var _b:Array = Array();
var _c:Array = Array();
if (_a == "S") {
_b = _openstack_s;
_c = _closedstack_s;
} else if (_a == "E") {
_b = _openstack_e;
_c = _closedstack_e;
}
bool = notUsedLoop(x, y, _b);
if (bool) {
bool = notUsedLoop(x, y, _c);
}
return bool;
}
private function notUsedLoop(x:Number, y:Number, _a:Array):Boolean {
var bool:Boolean = true;
for (var i = 0; i<_a.length; i++) {
if ((_a[i][0] == x and _a[i][1] == y) or (_a[i][2] == x and _a[i][3] == y)) {
bool = false;
break;
}
}
return bool;
}
private function getParent(x:Number, y:Number, _a:Array):Object {
var dt:Object = Object();
dt.bool = false;
for (var i = 0; i<_a.length; i++) {
if (_a[i][0] == x and _a[i][1] == y) {
dt.bool = true;
dt.x = _a[i][2];
dt.y = _a[i][3];
break;
}
}
return dt;
}
private function checkForMatch(x:Number, y:Number, a:Array, b:Array):Boolean {
//returns true if match, false if no match
var match:Boolean = false;
for (var c = 0; c<a.length; c++) {
if (a[c][0] == x and a[c][1] == y) {
match = true;
break;
}
}
if (!match) {
for (var d = 0; d<b.length; d++) {
if (b[d][0] == x and b[d][1] == y) {
match = true;
break;
}
}
}
return match;
}
private function isPath(ex:Number, sx:Number, ey:Number, sy:Number):Boolean {
var match_s:Boolean = checkForMatch(sx, sy, _openstack_e, _closedstack_e);
var match_e:Boolean = checkForMatch(ex, ey, _openstack_s, _closedstack_s);
if (match_s) {
setConnectionPoint(sx, sy);
pathRebuilt(sx, sy);
return true;
} else if (match_e) {
setConnectionPoint(ex, ey);
pathRebuilt(ex, ey);
return true;
}
return false;
}
private function pathRebuilt(x:Number, y:Number):Void {
var path:Array = Array();
path = pathRebuiltLoop(x, y, "S");
path.reverse();
path.push(Array(x, y));
_path = path.concat(pathRebuiltLoop(x, y, "E"));
}
private function pathRebuiltLoop(x:Number, y:Number, str:String):Array {
var dt:Object = Object();
dt.bool = true;
var _point:Object = Object();
var _a:Array = Array();
var _b:Array = Array();
var path:Array = Array();
if (str == "S") {
_a = _openstack_s;
_b = _closedstack_s;
_point.x = _startpoint.x;
_point.y = _startpoint.y;
} else if (str == "E") {
_a = _openstack_e;
_b = _closedstack_e;
_point.x = _endpoint.x;
_point.y = _endpoint.y;
}
var z:Number = 0;
var _abort:Boolean = false;
while (!_abort) {
dt = getParent(x, y, _a);
if (!dt.bool) {
dt = getParent(x, y, _b);
}
if (dt.bool) {
path.push(Array(dt.x, dt.y));
x = dt.x;
y = dt.y;
}
if (x == _point.x and y == _point.y) {
_abort = true;
}
}
return path;
}
}
De code van de visualisatie-class; deze genereert een random binaire map
de link naar de swf file vind je onderaan
class classes.cof.visual.Visualbmp {
private var _map:Array = Array();
private var _frequency:Number;
private var _w:Number;
private var _h:Number;
private var _tilew:Number;
private var _tileh:Number;
private var _mc:MovieClip;
private var _startpoint:Object = Object();
private var _endpoint:Object = Object();
public function setMc(a:MovieClip):Void {
_mc = a;
}
public function setMap(w:Number, h:Number):Void {
_w = w;
_h = h;
}
public function setTilesize(w:Number, h:Number):Void {
_tilew = w;
_tileh = h;
}
public function setBlackFrequency(a:Number):Void {
//a number bewteen 0 and 100 wich defines the not walkable areas
if (_frequency<0 and _frequency>100) {
a = 50;
}
_frequency = a;
}
public function getStartpoint():Object {
return _startpoint;
}
public function getEndpoint():Object {
return _endpoint;
}
public function getMap():Array {
return _map;
}
public function getMapDimension():Object {
var a:Object = Object();
a.w = _w;
a.h = _h;
return a;
}
public function initiate() {
buildBinary();
setSpecialPoints();
buildVisual();
}
public function buildSolution(a:Array) {
for (var i = 0; i<a.length; i++) {
var x:Number = a[i][0];
var y:Number = a[i][1];
var b:MovieClip = _mc["tile"+x+"_"+y];
b.gotoAndStop(3);
}
}
private function getType():Boolean {
//returns false if not walkable
//returns true if walkable
var r:Number = Number(Math.random()*100);
if (r<_frequency) {
return false;
} else {
return true;
}
}
private function toBinary(a:Boolean):Number {
//changes booleans to binary values
if (a) {
return 1;
} else {
return 0;
}
}
private function buildBinary():Void {
var dim:Object = Object(getMapDimension());
for (var y = 0; y<dim.h; y++) {
_map[y] = new Array();
for (var x = 0; x<dim.w; x++) {
_map[y][x] = Number(toBinary(getType()));
}
}
}
private function setStartpoint(x:Number, y:Number):Void {
_startpoint.x = x;
_startpoint.y = y;
}
private function setEndpoint(x:Number, y:Number):Void {
_endpoint.x = x;
_endpoint.y = y;
}
private function setSpecialPoints():Void {
var dim:Object = Object(getMapDimension());
var ex:Number = dim.w-1;
var ey:Number = dim.h-1;
var sx:Number = 0;
var sy:Number = 0;
_map[sx][sy] = Number(1);
_map[ex][ey] = Number(1);
setStartpoint(sx, sy);
setEndpoint(ex, ey);
}
private function buildVisual():Void {
var dim:Object = Object(getMapDimension());
for (var y = 0; y<dim.h; y++) {
for (var x = 0; x<dim.w; x++) {
var a:MovieClip = _mc.attachMovie("tile", "tile"+x+"_"+y, _mc.getNextHighestDepth());
a._x = _tilew*x;
a._y = _tileh*y;
a.gotoAndStop(Number(_map[y][x]+1));
}
}
}
}
De code van de fla:
import classes.cof.algorithms.Bmp;
import classes.cof.visual.Visualbmp;
var a:Visualbmp = new Visualbmp();
var b:Bmp = new Bmp();
a.setMap(12, 12);
//het percentueel voorkomen van zwarte vakjes
a.setBlackFrequency(30);
a.setTilesize(40, 40);
a.setMc(_root);
a.initiate();
var startp:Object = a.getStartpoint();
var endp:Object = a.getEndpoint();
b.setMap(a.getMap());
b.setStartpoint(startp.x, startp.y);
b.setEndpoint(endp.x, endp.y);
var t1:Number = getTimer();
b.initiate();
var solution = b.getPath();
var t2:Number = getTimer()-t1;
if (solution == false) {
nopath.text = "No path found";
} else {
a.buildSolution(solution);
}
time.text = "bmp terminated after "+t2+" microseconds";
Klik hier voor een live preview, druk F5 of refresh om een andere random map te genereren.
Link naar cities-of-faith.com (http://www.cities-of-faith.com/bmp.php)
Een volledige source code volgt later.
Graag je commentare/suggesties/verbeteringen!
Groeten,
Thomas Van Durme & Thomas Devriendt