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

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - С какой стороны обойти "неведомую..." (http://www.flasher.ru/forum/showthread.php?t=180027)

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

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

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

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

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

Код:

|  (1) |  (2) |  (3) |  (4)   |  (5)

      / \    / \    / \      / \

[]    []   / []   / []  \  / []  \

                           \

*     *      *      *        *

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

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

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

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

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

Цитата:

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

Цитата:

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

Как-бы:

Код AS3:

var i:int = object.x / CELL_SIZE;

var j:int = object.y / CELL_SIZE;

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

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

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

Цитата:

Сообщение от expl (Сообщение 1081571)

Как-бы:

Код AS3:

var i:int = object.x / CELL_SIZE;

var j:int = object.y / CELL_SIZE;

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

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

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

Код AS3:

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);

                                }

                        }

                }

                }

        }

 

}

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

Цитата:

Сообщение от Mkey (Сообщение 1081670)

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

Код AS3:

square.x + square.width /2

square.x + square.height /2