Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Обсуждение работ > Не сайты

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 10.07.2008, 23:54
TERRORist вне форума Посмотреть профиль Отправить личное сообщение для TERRORist Найти все сообщения от TERRORist
  № 11  
Ответить с цитированием
TERRORist
 
Аватар для TERRORist

блогер
Регистрация: Jun 2005
Адрес: RU
Сообщений: 1,540
Записей в блоге: 12
догадался ^_^

Старый 20.08.2008, 13:02
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 12  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
во вложении 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;
		  }
		}

}
__________________
Отряд Котовскага

Старый 20.08.2008, 14:32
MrPoma вне форума Посмотреть профиль Отправить личное сообщение для MrPoma Посетить домашнюю страницу MrPoma Найти все сообщения от MrPoma
  № 13  
Ответить с цитированием
MrPoma
 
Аватар для MrPoma

Регистрация: Jul 2006
Адрес: Питер
Сообщений: 2,083
Отправить сообщение для MrPoma с помощью Skype™
А че ему передавать надо?
__________________
жж | твттр | гглплс | фсбк | вкнткт | гтхб

Старый 20.08.2008, 17:00
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 14  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
при инициализации
Код:
astra = new Astra (map)
map[y][x] - двумерный массив 0,1 - 0 -стена, 1 и более проходимость
затем вызывается метод поиска пути возвращающий двумерный массив точек пути
Код:
function findPath( startX, startY, endX, endY)
в тестовом примере все расписано в инклудном файле
__________________
Отряд Котовскага

Старый 20.08.2008, 20:28
TERRORist вне форума Посмотреть профиль Отправить личное сообщение для TERRORist Найти все сообщения от TERRORist
  № 15  
Ответить с цитированием
TERRORist
 
Аватар для TERRORist

блогер
Регистрация: Jun 2005
Адрес: RU
Сообщений: 1,540
Записей в блоге: 12
Во первых таймер некорректно работает, выбирать new Date для нахождения времени глупо...

во вторых, он работает ужасно медленно, 250 мсек для маленького поля 100*100 при переходе наискосок...

Старый 21.08.2008, 12:09
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 16  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
Цитата:
Сообщение от TERRORist Посмотреть сообщение
Во первых таймер некорректно работает, выбирать new Date для нахождения времени глупо...

во вторых, он работает ужасно медленно, 250 мсек для маленького поля 100*100 при переходе наискосок...
А как по другому выбрать точное время работы скрипта? Подскажи - очень нужно.
Насчет медленности.. может быть - требуется оптимизация КОДА, но сам алгоритм один самых быстрых и точных для нахождения пути. можно поколдовать со значениями эвристики, и стоимости диагоналей (у меня в тесте диагональ=14 дороже прямых =10, поэтому алгоритм все равно выискивает пути по прямой, и лишь потом выдает вариант с диагональю, как самый дешевый)
__________________
Отряд Котовскага

Старый 21.08.2008, 22:03
TERRORist вне форума Посмотреть профиль Отправить личное сообщение для TERRORist Найти все сообщения от TERRORist
  № 17  
Ответить с цитированием
TERRORist
 
Аватар для TERRORist

блогер
Регистрация: Jun 2005
Адрес: RU
Сообщений: 1,540
Записей в блоге: 12
getTimer().. Для двойки)

Оптимизировать можно, но сначала лучше на тройке писать...

Старый 21.08.2008, 22:22
Яски вне форума Посмотреть профиль Отправить личное сообщение для Яски Найти все сообщения от Яски
  № 18  
Ответить с цитированием
Яски

блогер
Регистрация: May 2008
Адрес: (0, 10, 185) в локальной системе
Сообщений: 721
Записей в блоге: 6
getTimer() для тройки - быстрее new Date() в 10 раз.

Старый 22.08.2008, 11:51
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 19  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
Цитата:
Сообщение от TERRORist Посмотреть сообщение
getTimer().. Для двойки)
Ок) Я почему-то думал это Deprecated функция
Цитата:
Сообщение от TERRORist Посмотреть сообщение
Оптимизировать можно, но сначала лучше на тройке писать...
Дело в том что он написан для существующего и развивающегося AS2 проекта, переписывание на AS3 только предстоит.
__________________
Отряд Котовскага

Старый 16.03.2009, 22:36
KOHMAR вне форума Посмотреть профиль Отправить личное сообщение для KOHMAR Найти все сообщения от KOHMAR
  № 20  
Ответить с цитированием
KOHMAR
 
Аватар для KOHMAR

Регистрация: Sep 2007
Сообщений: 37
Люди а у кого то есть реализация *А на AS3 ?
__________________
План это очень хороший предмет! Если он есть то его сразу нет! Слишком ярко.

Создать новую тему Ответ Часовой пояс GMT +4, время: 19:26.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 19:26.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.