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

[greyshaman]

Оригинал написал(а) D12
greyshaman ну ты же умный парень

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

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

глюки прерогатива реализаций.

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

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

[BrainSmasher]

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

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

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