Вложений: 1
во вложении Вложение 20229тестовая флэшка по Badim'овскому алгоритму - переделан в класс Astra
Собственно сам класс (AS2)
Код:
// Поиск кратчайшего пути по алгоритму A*
class Astar
{
var map:Array;
var mapStatus:Array;
var openList:Array;
var mapH:Number;
var mapW:Number;
// подсчет времени выполнения
var startFind:Number;
var stopFind:Number;
// Constants/configuration - change here as needed! --------------------------------
var HV_COST = 10; // "Movement cost" for horizontal/vertical moves
var D_COST = 14; // "Movement cost" for diagonal moves
var log='';
function Astar(_map)
{
map = _map;
}
function isOpen(y, x) {
// Return TRUE if the point is on the open list, false if otherwise
return mapStatus[y][x].open;
}
function isClosed(y, x) {
// Return TRUE if the point is on the closed list, false if otherwise
return mapStatus[y][x].closed;
}
function nearerSquare() {
// Returns the square with a lower movementCost + heuristic distance
// from the open list
var minimum = 999999;
var indexFound = 0;
var thisF = undefined;
var thisSquare = undefined;
var i = openList.length;
// Finds lowest
while (i-->0) {
thisSquare = mapStatus[openList[i][0]][openList[i][1]];
thisF = thisSquare.heuristic + thisSquare.movementCost;
if (thisF <= minimum) {
minimum = thisF;
indexFound = i;
}
}
// Returns lowest
return indexFound;
}
function closeSquare(y, x) {
// Drop from the open list
var len = openList.length;
for (var i=0; i < len; i++) {
if (openList[i][0] == y) {
if (openList[i][1] == x) {
openList.splice(i, 1);
break;
}
}
}
// Closes an open square
mapStatus[y][x].open = false;
mapStatus[y][x].closed = true;
}
function openSquare(y, x, parent, movementCost, heuristic, replacing) {
// Opens a square
if (!replacing) {
openList.push([y,x]);
mapStatus[y][x] = {heuristic:heuristic, open:true, closed:false};
}
mapStatus[y][x].parent = parent;
mapStatus[y][x].movementCost = movementCost;
}
function findPath( startX, startY, endX, endY) {
startFind = new Date().getTime().valueOf();
if (startY == undefined || startX == undefined) return null; // Error: no starting point
if (endY == undefined || endX == undefined) return null; // Error: no ending point
// Error: Closed start/end point
if (map[startY][startX]==0 || map[endY][endX]==0)
{
log = "Closed start/end point: " + map[startY][startX] + "," + map[endY][endX];
trace(log);
return null;
}
// Caches dimensions
mapH = map.length;
mapW = map[0].length;
//trace (map);
// New status arrays
mapStatus = [];
for (var i=0; i<mapH; i++){
mapStatus[i] = [];
for (var j=0; j<mapW; j++){
mapStatus[i][j]={};
}
}
// Finds the way given a certain path
// Ok, now go back to our regular schedule. Find the path!
// Now really starts
openList = new Array();
openSquare (startY, startX, undefined, 0);
// Loops until there's no other way to go OR found the exit
while (openList.length > 0 && !isClosed(endY, endX)) {
// Browse through open squares
var i = nearerSquare();
var nowY = openList[i][0]/1;
var nowX = openList[i][1]/1;
// Closes current square as it has done its purpose...
closeSquare (nowY, nowX);
// Opens all nearby squares, ONLY if:
//trace('__now:['+nowX+","+nowY+"]");
for (var j=nowY-1; j<(nowY+2); j++) {
for (var k=nowX-1; k<(nowX+2); k++) {
if (j >= 0 && j < mapH && k >= 0 && k < mapW && map[j][k] != 0)
{
// If not outside the boundaries or at the same point or a diagonal (if disabled) or a diagonal (with a wall next to it)...
// And if not a wall...
if (!isClosed(j,k)) {
// And if not closed... THEN open.
var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]);
if (isOpen(j,k)) {
// Already opened: check if it's ok to re-open (cheaper)
if (movementCost < mapStatus[j][k].movementCost) {
// Cheaper: simply replaces with new cost and parent.
//trace('__replace:('+k+','+j+') for ('+nowX+','+nowY+")");
openSquare (j, k, [nowY, nowX], movementCost, undefined, true); // heuristic not passed: faster, not needed 'cause it's already set
}
}
else
{
// Empty: open.
var heuristic = (Math.abs (j - endY) + Math.abs (k - endX)) * 10;
openSquare (j, k, [nowY, nowX], movementCost, heuristic, false);
}
} else {
// Already closed, ignore.
}
}
}
}
}
//Ended
var pFound = isClosed(endY, endX); // Was the path found?
if (pFound) {
// Ended with path found; generates return path
var returnPath = [];
var nowY = endY;
var nowX = endX;
var movCost=mapStatus[nowY][nowX].movementCost;
while ((nowY != startY || nowX != startX)) {
returnPath.push([nowX,nowY,movCost]);
var newY = mapStatus[nowY][nowX].parent[0];
var newX = mapStatus[nowY][nowX].parent[1];
nowY = newY;
nowX = newX;
movCost=mapStatus[nowY][nowX].movementCost;
}
returnPath.push([startX,startY,0]);
var path_xy=[];
for(var i=returnPath.length-1;i>-1;i--){
path_xy.push(returnPath[i]);
}
stopFind = new Date().getTime().valueOf();
log="finding time:" + (stopFind - startFind)+"\npath:" + path_xy.join('|');
trace (log);
return path_xy;
}
else
{
log="Ended with 0 open squares; ran out of squares, path NOT found";
trace (log);
return null;
}
}
}
|
