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

[NDG]

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

[aaanet]

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

[Iv]

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

[Nox Noctis]

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

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

[NDG]

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

[Nox Noctis]

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

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

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

[Iv]

илья делал (http://213.221.40.20/v1.5/) - вроде алгоритм высосали до упора.

[NDG]

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

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

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

[Nox Noctis]

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

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

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

[NDG]

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

[greyshaman]

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

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

ЗЫ могу дать ссылку на готовый алгоритм lines, тока боюсь у тебя крыша съедет, от того что я предложу :)

[NDG]

.......мля я хочу создать функцию которая назначает клавмшам события в фильме т.е. чтоб мой персонаж двигался вперед я прописываю в консоли(консоль появляеться тоже в результате нажатия клавиши) код к примеру "bind w forward" Enter, назад bind s backpedal ...... bind fire mouse1. понятное дело что клавиши можно будет назначить и с менюшки игрушки, но функциями, так как я хочу - быстрее. И с внешнего файла легче будет раздуплять флэшу какая кнопка к чему. Объект Key мне не подходит так как мои клавиши будут прописаны в текстовике в иде bind w forward, bind s backpedal..... и мне ни как не получиться объяснить игре клавиши по другому кроме как описанным выше методом, так что ребята не будем разводить дискуссии....
нащет стиля програмирования то у меня есть свои причины так писать т.к. я пишу на флэш 5 да еще и черновик для основной проги так что мой стиль в порядке!!!
была идея сравнивать стринги но так долго, но сеорее всего так прийдеться и сделать

[NDG]

!!!там сообщение не туда попало не обращайте внимания!!!!!
сбрасывай алгоритм на ящик nitrox@diawest.net.ua

[D12]

куда кликнеш туда он и попрется огибая препятствия)))

[greyshaman]

D12 а через стены ходить, это хинт?

[greyshaman]

то, что я, имел ввиду.

[D12]

greyshaman
ну ты же умный парень, это всеголиш пример : ) по поводу стен сделаеш сам ) темболее исходник не мой а посему в стенах вини не меня )


P.S. сомнительно мне чегото что в твоем примере персонаж допрется до нужной точки , подобный метод имеет целый ряд глюков и мало приспособлен для динамических игр )
а вообще если на то пошло то нужно просто персонаж наделят чувствами создовая как ауру вокруг него своебразное поле , с помощь которого подходя к обьекту он определял препятствие по картотеке в своей базе данных , с данными длинны и ширины , сравнивания свое место нахождение относительно центра обьекта , и после определения обходил его с кратчайшей стороны )

[Stone]

Оригинал написал(а) BitSky
илья делал (http://213.221.40.20/v1.5/) - вроде алгоритм высосали до упора.
алгоритм бы этого чуда посмотреть

хотя для стратегии он не подойдет... если будет больше одного юнита (((

[Iv]

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

[Stone]

зашол - машина начала притормаживать.

[greyshaman]

Оригинал написал(а) D12
greyshaman ну ты же умный парень
да не старый я, для парня. Попробуй профилактически увеличить размер приведенного лабиринта до 32*32, это минимальная карта в виденных стратегиях, не считая шахмат, и посчитать на нем путь. Таймер не забудь включить результаты сообщи. :) я уверен они тебя удивят

подобный метод имеет целый ряд глюков и мало приспособлен для динамических игр
глюки прерогатива реализаций.

ты этим методом в сеть лазишь :)

ЗЫ вторая серия будет

[BrainSmasher]

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

В данном примере, волновой алгоритм тоже вполне неплох и торможения сильно не добавит, грубо говоря, при современных процессорах заполнение поля ну например 100x 100 волной займет несколько миллисекунд, если не меньше.
Флеш, конечно не ассемблер, но мне кажется и он потянет.

На вскидку могу предложить другой вариант, алгоритмически более сложный, но как мне кажется более эффективный на полях больших площадей с невысокой концентрацией препятствий (ибо для остальных случаев волновой алгоритм рулит). В общем суть его такова:
Сначала найти один из возможных путей из точки A в точку B, а потом попытаться его оптимизировать спрямляя и "перекидывая" через препятствия.
В качестве примера рассмотрим возможную вариацию:
Итак, большое поле на нем замкнутые ограниченные препятствия (стены, озера и т.п.) и две точки А и B.
Из начальной точки A (X0,Y0) отправляемся прямиком по вектору к конечной точке B и топаем так пока нам не встретится препятствие. Если не встретилось, ОК пришли, а если встретилось начинаем его обход по границе препятствия в сторону уменьшения расстояния до точки B. Идем так "вдоль забора" до тех пор, пока не появится возможность сделать шаг по азимуту в сторону точки B. И так до тех пор пока не дойдем до точки B. Получили путь. Теперь можно попытаться его оптимизировать. Оптимизация пути может быть выполенна различными методами. В общем случае необходимо попытаться спрямить путь между вынужденными поворотами (которые неизбежны при огибании препятствий).
Мы изначально можем описывать наш путь векторами, и попытаться избавиться от лишних вершин, т.е. заменить несколько векторов одним. А это довольно просто, достаточно проверить наличие препятствия на прямом пути между концами векторов, и если его не встретится удалить промежуточные вектора.
Еще конечно можно подоптимизировать кое-какие моменты, но времени у меня сейчас для этого маловато.