|
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
во вложении astar.zipтестовая флэшка по 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; } } }
__________________
Отряд Котовскага |
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
при инициализации
map[y][x] - двумерный массив 0,1 - 0 -стена, 1 и более проходимость затем вызывается метод поиска пути возвращающий двумерный массив точек пути в тестовом примере все расписано в инклудном файле
__________________
Отряд Котовскага |
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
Цитата:
Насчет медленности.. может быть - требуется оптимизация КОДА, но сам алгоритм один самых быстрых и точных для нахождения пути. можно поколдовать со значениями эвристики, и стоимости диагоналей (у меня в тесте диагональ=14 дороже прямых =10, поэтому алгоритм все равно выискивает пути по прямой, и лишь потом выдает вариант с диагональю, как самый дешевый)
__________________
Отряд Котовскага |
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
Ок) Я почему-то думал это Deprecated функция
Дело в том что он написан для существующего и развивающегося AS2 проекта, переписывание на AS3 только предстоит.
__________________
Отряд Котовскага |
|
|||||
Регистрация: Sep 2007
Сообщений: 37
|
Люди а у кого то есть реализация *А на AS3 ?
__________________
План это очень хороший предмет! Если он есть то его сразу нет! Слишком ярко. |
Часовой пояс GMT +4, время: 19:26. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|