С какой стороны обойти "неведомую..."

[Mkey]

Привет всем.
Прикрепил картинку, на ней изображено два пути движения объекта к цели.
Мне бы узнать как найти нужный коэффициент, чтобы Объект поворачивал и шел по короткому пути.
Что за коэффициент?
Он отвечает за поворот Объекта или +15 градусов или -15 градусов, с этим смещением угла мы будем проверять перед нами есть "неведомая..." или нету.
И еще бонусный вопрос: Для избежания цикла, который будет пробегать по всем объектам на сцене которые нужно обходить я хочу создать пустой мувиклип и в него создать те объекты. Так вот прокатит ли ХитТестПоинт?За один раз по идее должен проверить все, если сделать Мувиклипдляобьектов.hitTestPoint(x,y,true)

[Korchy]

Может лучше использовать стандартный алгоритм обхода препятствий А* (А-стар, А-звездочка) ?

[Hauts]

http://coolisee.com/2010/05/21/poisk-puti-pathfinding/

[expl]

Не стандартным алгоритмом без использования сетки, говорят, тоже можно:
http://www.flasher.ru/forum/showpost...29&postcount=2

[wvxvw]

Такая задача лучше решается аппроксимацией препядствий к многоугольникам. В таком случае самый короткий путь будет однозначно опираться на вершины этих многоугольников.
Далее, существует много разновидностей А* алгоритма, но в чистом виде А* интересен только как теория - на практике он очень медленный. Отличие этого алгоритма заключается в том, что у него есть эвристическая функция которая "примерно"* рассчитывает расстояние до цели. Благодаря этой функции можно строить стек по приоритетам какие узлы просматривать следующими.
В вашем случае эвристической функцией может быть расстояние по прямой до цели. Таким образом будет выбран узел (точка пересечения пути и многоугольника ограничивающего препядствие) который ближе всего к конечной цели. На следующем этапе будут опять проверены все узлы-потомки на предмет приближенности к цели, и, скорее всего будет раскрыт не потом узла раскрытого на предыдущем этапе, а его сосед (см. картинку).

|  (1) |  (2) |  (3) |  (4)   |  (5)
      / \    / \    / \      / \
[]    []   / []   / []  \  / []  \
                           \
*     *      *      *        *

Т.е. при близких значениях полученных из f(N,P) = h(P) + c(N,P), где N - текущий узел, P - потомок, h - эвристическая функция, c - цена перехода от одного узла к другому, полученных из функции f - неизбежно получается, что нужно проверить какое-то дополнительное количество узлов (тем более, что в общем случае нет гарантии того, что вообще лучшее решение - единственное). Чем лучше эвристическая функция, тем меньше процент "ненужных" узлов, которые прийдется посетить за время поиска.

Есть несколько вариантов тактик обхода дерева, можно при нахождении узла-соседа с лучшим показателем записывать в предыдущем значение лучшего узла-наследника и "закрывать" его, переходя в проверку нового найденного лучшего узла. Можно пытаться не смотря ни на что добраться до целевого узла, а потом проверять остальные "хорошие" узлы, которые были встречены на пути - при обнаружении лучшего пути, заменить им бывший выбранный, и повторить процедуру.

Но что самое хорошее в этом деле, так это то, что алгоритмы поиска пути еще все не найдены, и у вас есть все шансы найти лучший

* - эвристическая функция должна быть "оптимистической" - т.е. она никогда не должна переоценивать сложность перехода к целевому узлу.

[Mkey]

Да читал про А стар, еще когда мне указывали о нем в старой теме.
Но я просто не понимаю как работать с этой сеткой. Например как по координатам объекта определить в какой клетке он находится?
И поэтому отказался от этого.
И подошел к способу как на "хитри", в общем сделал почти как там, упустив несколько моментов. И у меня получилась так, что Персонаж начал обходить препятствие по длинному пути,а это зависит от того коффа который мне нужно определить. И опять же

И еще бонусный вопрос: Для избежания цикла, который будет пробегать по всем объектам на сцене которые нужно обходить я хочу создать пустой мувиклип и в него создать те объекты. Так вот прокатит ли ХитТестПоинт?За один раз по идее должен проверить все, если сделать Мувиклипдляобьектов.hitTestPoint(x,y,true)

[expl]

Например как по координатам объекта определить в какой клетке он находится?

Как-бы:

var i:int = object.x / CELL_SIZE;
var j:int = object.y / CELL_SIZE;

Но коли сетка не потребовалась - и ладно.

[wvxvw]

А* не имеет непосредственного отношения к сетке. Сетка имеет смысл если объекты могут передвигаться исключительно квадратно-гнездовым способом. Но если объекты передвигаются так, как у вас показано на рисунке, то лучше строить направленный граф в котором ребра - цена перехода от одной вершины многоугольника описывающего препядствие до другой вершины. Получится невпример быстрее.

Очень хорошо, подробно и с иллюстрациями алгоритмы поиска пути разбирает Питер Норвиг (Peter Norvig, Artificial Intelligence A Modern Approach / AIMA). Это практически должно быть настольной книжкой игродела

[Mkey]

Сообщение от expl

Как-бы:

var i:int = object.x / CELL_SIZE;
var j:int = object.y / CELL_SIZE;

Но коли сетка не потребовалась - и ладно.

------------------------------------------------------
Апну тему, коли не закрыта и вопрос актуален.

Что я делаю и хочу сделать.
Я создаю объекты через цикл и записываю в переменный координаты квадрата, где они находятся. Нооооооо...
Вообщем выложу код

var arrHostile:Array=new Array();
		private function createEnemy():void {
 
			var _enemy:Hostile;
			for (var i = 0; i < 10; i++) {
				_enemy = new Hostile();
				addChild(_enemy);
				arrHostile.push(_enemy);
 
				_enemy.x = Math.round((Math.random()*(-60) - 2));
				_enemy.y = Math.round(Math.random()*80+150);
				x_sq[i]=_enemy.x/5;///По формуле приведенной выше типа находим квадрат и записываем его в массиве, тоже делаем снизу.
				y_sq[i]=_enemy.y/5;
			}
		}
 
		var hspeedx=1;///Ну это скорость объекта.
		var hspeedy=1;
		//var Hero:HeroControl=new HeroControl();
 
 
		public function MovedHostile(event:Event):void
		{
 
		if(create==true){
			var Alfa:Number;
		var _xlenvec:Number;
		var _ylenvec:Number;
			for(var i=0;i<arrHostile.length;i++)
			{	_xlenvec=hero.x-arrHostile[i].x;
				_ylenvec=hero.y-arrHostile[i].y;
				Alfa=Math.atan2(_ylenvec,_xlenvec);
				if(Math.sqrt(Math.pow((hero.x-arrHostile[i].x),2)+Math.pow((hero.y-arrHostile[i].y),2))>10){ x_next=hspeedx*Math.cos(Alfa);
 
		x_squad=Math.round((arrHostile[i].x+x_next)/1);///Тут мы типа записываем в какой квадрат попадет объект
 
	y_next=hspeedx*Math.sin(Alfa);
	//trace("Speed Y:"+y_next);
	y_squad=Math.round((arrHostile[i].y+y_next)/1);///Тут мы типа записываем в какой квадрат попадет объект
	//trace("Squad Y:"+y_squad);
				for(var j:int=0;j<x_sq.lenght;j++)///Тут мы проверяем есть ли в квадрате куда мы перейдем кто-то. Сравнивая координаты.
				{
						if(x_sq[j]==x_squad && y_sq[j]==y_squad){
						y_next=0;x_next=0;}
 
				}
 
				arrHostile[i].x+=x_next;
				arrHostile[i].y+=y_next;
				x_sq[i]=Math.round(arrHostile[i].x/5);
				y_sq[i]=Math.round(arrHostile[i].y/5);
				}
			}
		}
		}
	}
 
}

Если посмотреть код и почитать комментарии то выяснится что это нихера не работает, так как координаты "квадрата" сетки это не центр "квадрата" сетки. Мне бы его как-то найти?

[strangedk]

Сообщение от Mkey

координаты "квадрата" сетки это не центр "квадрата" сетки. Мне бы его как-то найти?

square.x + square.width /2
square.x + square.height /2

?