Поиск пути методом потенциальных полей

[HorusWM]

Всем привет! Прошу помощи реализовать поиск пути методом потенциальных полей, у самого не получается. Видел только одну реализацию (и очень шуструю) для Game Maker, но перевести на as3 мне не удалось (какой-то совсем абстрактный там язык). Может кто имеет представление или даже уже готовую реализацию, пожалуйста, поделитесь алгоритмом или подскажите, какого вида он должен быть.

Добавлено через 7 часов 32 минуты
Неужели никто не пробовал эту реализацию?

[HorusWM]

То ли, действительно, никто тут не работал с этим методом, то ли не хотите признаваться) Если кого интересует - вот решение, к которому я пришел:

vDirection  =  new Point(destination.x -x, destination.y -y); // создаем вектор движения к цели, когда объект должен начать двигаться
 
                protected function Move():void
		{
			if (vDirection != null)
			{
				var angle:Number; // угол результирующего вектора
				var vector:Point = new Point(); // временный вектор
 
				if (collided.length > 0) // здесь проверяется длина списка, содержащего все объекты-препятствия на сцене
				{
					var i:int;
					var result:Point; // результирующий вектор
					var L:Number; // длина рез. вектора
 
					result = new Point(destination.x -x, destination.y -y); // создаем рез. вектор, равный вектору направления
 
					L = Math.sqrt(result.x * result.x + result.y * result.y); // вычисляем длину рез. вектора
 
                                        // нормализуем рез. вектор
					result.x /= L;
					result.y /= L;
 
					if (L == 0)
					{
						result.x = 1;
						result.y = 1;
					}
 
					for (i = 0; i < collided.length; i++)
					{
					  var e:Entity = collided[i] as Entity;
 
                                          // пробегаемся по списку и выбираем те объекты, которые попадают в радиус действия сил,
                                          // у меня это константа COLLIDE_RADIUS и равна 2, т.е. просчет начинается почти вплотную
					  if (distanceFrom(e, true) <= COLLIDE_RADIUS)
					  {
						var dist:Number = distanceFrom(e, true);
 
                                                // вычисляем силу отталкивания обратно пропорциональную расстоянию
                                                // эффект будет заметен при бОльших значениях COLLIDE_RADIUS, чем 2
						var magnitude:Number = (speed * COLLIDE_RADIUS -speed * dist) / (speed * COLLIDE_RADIUS);
 
                                               // создаем вектор противодействующей силы
						var force:Point = new Point((x -e.x), (y -e.y));
 
						var len:Number = Math.sqrt(force.x * force.x + force.y * force.y) /magnitude;
 
                                                // нормализация
						force.x /= len;
						force.y /= len;
 
						if (len == 0)
						{
							force.x = 1;
							force.y = 1;
						}
 
                                                // складываем результирующий и противодействующий вектора
						result.x += force.x;
						result.y += force.y;
					  }
					}
 
					vector.x = result.x;
					vector.y = result.y;
				}
				else
				{
					vector.x = vDirection.x;
					vector.y = vDirection.y;
				}
 
                                // угол вектора в радианах
				angle = Math.atan2(vector.y, vector.x);
 
                                // ну и задаем движение
				x += speed * Math.cos(angle);
				y += speed * Math.sin(angle);
			}
		}

Если кто-то знает решение проще или может оптимизировать данное - буду только рад

[caseyryan]

HorusWM, а есть где можно в действии этот алгоритм глянуть?
Просто я сейчас тоже пишу алгоритм поиска пути, но там комбинация А Стар, сплайнов и упрощения пути. Работает, но довольно тормозной.

[HorusWM]

Не работает что-то swfcabin, не могу загрузить. Как вариант вот. Правда тут на убегание от цели и карта совсем простенькая, но принцип тот же. Единственный недостаток этого метода - возможное попадание в локальный минимум, когда на объект действуют равнозначные силы с нескольких сторон, в этом случае результирующий вектор равен нулю (объект не может вырваться из под действия сил). Это препятствия вида П или V. Но это легко решается разными способами, я использую вспомогательные path-point'ы в качестве временной цели, которые расставляю в "опасных" местах. В случае попадания в такую ситуацию, объект переключается на ближайший path-point и по его достижении снова движется к сохраненной ранее цели. Работает очень хорошо и шустро.
А* у меня тоже жрал много ресурсов, так как препятствия меняются динамически, а карта большая.

[caseyryan]

У всех этих алгоритмов есть один существенный недостаток. Путь, в общем-то, получается совсем не реалистичный. Поэтому для своего алгоритма я писал еще и упрощение пути.
Смысл там такой: сначала с помощью а стар просчитывается весь путь в обход припятствия и точки помещаются в массив. Потом этот массив передается методу simplify(waypoint:Array):Array,
который сначала берет первую точку, и проверяет, а можно ли от нее провести прямую линию к каждой последующей точке так, чтобы линия не наткнулась на препятствие. Если, скажем, до четвертой точки можно провести линию, а до пятой уже нет, то в качестве исходной точки назначается четвертая, при этом вторая и третья точки игнорируются. И далее то же самое делается от четвертой точки, пока не будет проведена прямая линия до последней.
Получается ломаная, но более менее естественная траектория. К которой потом применяются сплайны. Сам класс сплайнов брал у Силина http://silin.su/#AS3/geom/spline/bin
В итоге получается очень даже неплохо. Но пока еще до ума не довел.
Главная проблема, тормознутость. Подумываю воркеров задействовать когда ФП с ними зарелизят

[Silicium]

Я сразу не понял вопроса. Делал такое (правда не на AS, но все же). По сути это метод спуска - вариантов может быть куча, все зависит от того, как именно должен двигаться объект. В моем случае это были "микробы" и двигались они не по экстремальному пути а прямыми отрезками по направлению уменьшения (увеличения) значения "поля" до тех пор, пока оно в каждой последующей точке уменьшлось (увеличивалось). Затем происходил разворот. Развороты были рандомными и путь получался ломанным, но правильным. Можно так-же в каждой точке искать направление, соответствующее максимальному уменьшению значения поля (я так понял, у Вас как раз такой вариант).

[HorusWM]

Мм.. caseyryan, мне кажется, что это крайне затратно. Хотя, тут уже смотря для каких целей. А если в качестве движущегося объекта использовать что-то вроде steering behavior? По идее, он тоже должен плавненько поворачивать от точки к точке, если использовать метод видимости точек.
Да, и что за воркеры такие?

[КорДум]

Подумываю воркеров задействовать когда ФП с ними зарелизят

Так 11.4 вышел же уже.

Да, и что за воркеры такие?

Псевдопотоки. По сути - еще одна невидимая копия ФП.

[caseyryan]

Так 11.4 вышел же уже.

Что-то я этот момент упустил.. Думал все еще бета.

Да, и что за воркеры такие?

http://help.adobe.com/ru_RU/FlashPla...em/Worker.html

Мм.. caseyryan, мне кажется, что это крайне затратно. Хотя, тут уже смотря для каких целей. А если в качестве движущегося объекта использовать что-то вроде steering behavior?

Да. Слишком затратно. Но для некоторых задач вполне подойдет. С рулёжкой тоже думал сделать. Скорее всего добавлю в поисковик пути еще один метод, как раз для неё.
Но меня больше интересует именно реалистичность траектории