Как написать прогу прохода мувиклипа по лабиринту?

[NDG]

Есть мувиклип с лабиринтом (с препятствиями) и нужно добраться от одной точки до второй кратчайшим путем (кто играл в стратегии поймет, выбираешь юнит и назначаешь точку куда нада прийти, а он сам знает как пройти обходя горы и т.д., и т.п.)
Возможно у Вас есть какието наработки в этом вопросе, ато я даже не знаю с чего начать.

[aaanet]

мне кажется что решение этой задачи можно найти в if

[Iv]

есть различные алгоритмы поиска пути.
поищи в яндексе по словам "волновой алгоритм", "алгоритм поиска пути"
начитаешься на год вперед %)

[Nox Noctis]

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

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

[NDG]

......а можно как нибудь применимо к экшин скрипт, я алгоритм приблизительно понимаю, но вот как это сделать именно во флэшке. подозреваю что тут не обойтись без hitTest, getBounds... но как было замечено выше данный алгоритм ресурсы будет жрать ой-е-ей, а в моей задаче в добавок ко всему конечная точка пути будет меняться очень часто (я писал ожнажды програму обхода конем шахматной доски, так поле 8 на 8 конь обходил приблизительно за 30 сек но если я ставил значения доски на несколько едениц больше то время росло в геометрической прогресии т.е. нужно было на порядок больше времени 5 мин и более), но в игрушках же юниты не думают как пойти но 5 мин, при перемещении толпы юнитов не возникает ни малейших признаков торможения, почему??? и если среди Вас есть программеры которые знают как решить эту задачу плз помогите!!!

[Nox Noctis]

Оригинал написал(а) NDG
(я писал ожнажды програму обхода конем шахматной доски, так поле 8 на 8 конь обходил приблизительно за 30 сек но если я ставил значения доски на несколько едениц больше то время росло в геометрической прогресии т.е. нужно было на порядок больше времени 5 мин и более)

значит плохо писал. ОЧЕНЬ плохо :)

а алгоритм тебе никто на АС не изложит... или ищи исходники - некоторые выкладывают такие, сам видел.

тут нужно точно знать что у тебя за задача, в каком виде лучше всего представить поле, и т д... и придумать частное решение, которое будет оптимально по времени и ресурсоёмкости.

[Iv]

илья делал - вроде алгоритм высосали до упора.

[NDG]

2 BitSky спасиба посмотрю!!

2 Nox Noctis да не хочеться мне частного решения, я хочу нарисовать карту прямоугольниками и кругами, и чтоб бегали юниты обходя препятствия, я тут частного решения никакого придумать не могу. Есть идея разбить всю карту на квадраты, каждому квадрату соответствует ячейка матрицы, если есть стена в данном квадрате то ставим 0 если нет то 1 и дальше с матрицами работать О! аналог этой проги - Lines, была раньше такая игрулина, шарики перемещать нада было и линии из них складывать. может ее алгоритм мне получиться придумать.
....а вобще я хочу написать чтото вроде лабиринта с соперниками, как в примерах для Флэш МИкс 2004 но только там путь противника сделан как стационарный т.е. есть Guide линия по которой движеться противник - это не интерестно!!! а я хочу чтоб любой юзер мог нарисовать себе/другу лабиринт и соревноваться с противником и чтоб комп сам мозг попарил как же добраться до финальной точки.

з.ы. насчет плохо писал - я же не сказал что у меня было 4ГГц проц =), - была 486 и Си++.....

[Nox Noctis]

если есть стена в данном квадрате то ставим 0 если нет то 1 и дальше с матрицами работать О!

блин. да так обычно и делают... только зачастую еще есть градации не только ноль и один (проходимо-непроходимо) но еще и разные стоимости прохода по данной ячейке (например асфальт, трава, песок, и т д... все это разные числа-стоимости)

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

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

[NDG]

.....так что там со ссылками на алгоритм???