Синтаксис:
Используется javascript
class _GridNode{
var _value;
var _f;
var _g;
var _h;
var _debug;
var _parent;
var _x;
var _y;
function _GridNode(value,f,g,h,debug,parent,x,y){
_value=value;
_f=f;
_g=g;
_h=h;
_debug=debug;
_parent=parent;
_x=x;
_y=y;
}
function Search (grid, start, end) {
var openList = new Array();
var closedList = new Array();
openList.push(start);
while(openList.length > 0) {
// Ищем наименьший f
var lowInd = 0;
for(var i=0; i<openList.length; i++) {
if(openList[i]._f < openList[lowInd]._f) { lowInd = i; }
}
var currentNode = openList[lowInd];
//Если пришли в финиш
if(currentNode._x == end._x && currentNode._y == end._y ) {
var curr = currentNode;
var ret = new Array();
while(curr._parent) {
ret.push(curr);
curr = curr._parent;
}
return ret.reverse();
}
//Если не пришли - текущую перемещаем из открытого списка в закрытый, проверяем всех соседей
for(var k=0; k<openList.length; k++) {
if(openList[k]==currentNode) { openList.RemoveAt(k); }
}
closedList.push(currentNode);
var neighbors = Neighbors(grid, currentNode);
for(var n=0; n<neighbors.length;n++) {
var neighbor = neighbors[n];
if(findGraphNode(closedList,neighbor) || neighbor._value==0) {
// не правильная клетка
continue;
}
// g - это кратчайший путь от старта до текуще клетки , нужно проверить что путь по которому мы прриходим в соседнюю клетку кратчайший
var gScore = currentNode._g + 1; // 1 это путь из этой клетки в соседнюю
var gScoreIsBest = false;
if(!findGraphNode(openList,neighbor)) {
// первый раз посещаем клетку, это лучший путь
// так же считаем h
gScoreIsBest = true;
neighbor._h = Heuristic(neighbor._x, neighbor._y,end._x,end._y);
openList.push(neighbor);
}
else if(gScore < neighbor._g) {
// Мы уже были в этой клетке , но с худшим g (расстояние от старта)
gScoreIsBest = true;
}
if(gScoreIsBest) {
// нашли пока что лучший путь к ячейке, запоминаем как пришли сюда
neighbor._parent = currentNode;
neighbor._g = gScore;
neighbor._f = neighbor._g + neighbor._h;
neighbor._debug = "F: " + neighbor._f + "<br />G: " + neighbor._g + "<br />H: " + neighbor._h;
}
}
}
// Ничего не нашли- пустой массив
return <img src="./images/smilies/unmarked.gif" alt="[]" title="Запланировано" />;
}//,
function Heuristic (x0,y0, x1,y1) {
// Расстояние по Манхеттану
var d1 = Mathf.Abs (x1 - x0);
var d2 = Mathf.Abs (y1 - y0);
return d1 + d2;
}//,
function Neighbors(grid, node) {
var ret = new Array();
var x = node._x;
var y = node._y;
if(x>0 && grid[x-1][y]._value) {
ret.push(grid[x-1][y]);
}
if(x<grid.length-1 && grid[x+1][y]._value) {
ret.push(grid[x+1][y]);
}
if(y>0 && grid[x][y-1]._value) {
ret.push(grid[x][y-1]);
}
if(y<grid[x].length-1 && grid[x][y+1]._value) {
ret.push(grid[x][y+1]);
}
return ret;
}
function findGraphNode(searchin,searchwhat){
for(var l=0; l<searchin.length; l++) {
if(searchin[l]==searchwhat) { return 1 ;}
}
}
var _value;
var _f;
var _g;
var _h;
var _debug;
var _parent;
var _x;
var _y;
function _GridNode(value,f,g,h,debug,parent,x,y){
_value=value;
_f=f;
_g=g;
_h=h;
_debug=debug;
_parent=parent;
_x=x;
_y=y;
}
function Search (grid, start, end) {
var openList = new Array();
var closedList = new Array();
openList.push(start);
while(openList.length > 0) {
// Ищем наименьший f
var lowInd = 0;
for(var i=0; i<openList.length; i++) {
if(openList[i]._f < openList[lowInd]._f) { lowInd = i; }
}
var currentNode = openList[lowInd];
//Если пришли в финиш
if(currentNode._x == end._x && currentNode._y == end._y ) {
var curr = currentNode;
var ret = new Array();
while(curr._parent) {
ret.push(curr);
curr = curr._parent;
}
return ret.reverse();
}
//Если не пришли - текущую перемещаем из открытого списка в закрытый, проверяем всех соседей
for(var k=0; k<openList.length; k++) {
if(openList[k]==currentNode) { openList.RemoveAt(k); }
}
closedList.push(currentNode);
var neighbors = Neighbors(grid, currentNode);
for(var n=0; n<neighbors.length;n++) {
var neighbor = neighbors[n];
if(findGraphNode(closedList,neighbor) || neighbor._value==0) {
// не правильная клетка
continue;
}
// g - это кратчайший путь от старта до текуще клетки , нужно проверить что путь по которому мы прриходим в соседнюю клетку кратчайший
var gScore = currentNode._g + 1; // 1 это путь из этой клетки в соседнюю
var gScoreIsBest = false;
if(!findGraphNode(openList,neighbor)) {
// первый раз посещаем клетку, это лучший путь
// так же считаем h
gScoreIsBest = true;
neighbor._h = Heuristic(neighbor._x, neighbor._y,end._x,end._y);
openList.push(neighbor);
}
else if(gScore < neighbor._g) {
// Мы уже были в этой клетке , но с худшим g (расстояние от старта)
gScoreIsBest = true;
}
if(gScoreIsBest) {
// нашли пока что лучший путь к ячейке, запоминаем как пришли сюда
neighbor._parent = currentNode;
neighbor._g = gScore;
neighbor._f = neighbor._g + neighbor._h;
neighbor._debug = "F: " + neighbor._f + "<br />G: " + neighbor._g + "<br />H: " + neighbor._h;
}
}
}
// Ничего не нашли- пустой массив
return <img src="./images/smilies/unmarked.gif" alt="[]" title="Запланировано" />;
}//,
function Heuristic (x0,y0, x1,y1) {
// Расстояние по Манхеттану
var d1 = Mathf.Abs (x1 - x0);
var d2 = Mathf.Abs (y1 - y0);
return d1 + d2;
}//,
function Neighbors(grid, node) {
var ret = new Array();
var x = node._x;
var y = node._y;
if(x>0 && grid[x-1][y]._value) {
ret.push(grid[x-1][y]);
}
if(x<grid.length-1 && grid[x+1][y]._value) {
ret.push(grid[x+1][y]);
}
if(y>0 && grid[x][y-1]._value) {
ret.push(grid[x][y-1]);
}
if(y<grid[x].length-1 && grid[x][y+1]._value) {
ret.push(grid[x][y+1]);
}
return ret;
}
function findGraphNode(searchin,searchwhat){
for(var l=0; l<searchin.length; l++) {
if(searchin[l]==searchwhat) { return 1 ;}
}
}
![[nuklear]](./images/smilies/5nuclear.gif "Bomb")
