обхождение препятствий

[Ноябрь]

дано:
игровое поле
по нему, по клеточкам(шестигранникам) ходит чел
как ему обойти препятствие?

чего я добился в решении данного вопроса.. сначала примитивными условиями я таки заставил его их обходить, но он не всегда выбирает кратчайший путь, тогда я решил, а проверю-ка я все варианты.
Все варианты я решил проверять при помощи хмл дерева, и все бы хорошо, НО уже на 7-ом шаге флэш предложил мне остановить выполнение скрипта - не мудрено, просчитать (3..6)^7 вариантов, и на том спасибо.
Сейчас у меня есть продолжения:
1 - доработать примитивные условия обхода, но как с их помощью обойти такое препятствие..
|---------
|. . . .[*] |
| . . . . . .|
| . -------
| . |
| . |-------
| . . . . . . .
|----------
..хотя в принципе условие можно написать для всего..

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

[wvxvw]

http://en.wikipedia.org/wiki/Shortest_path_problem
А еще ключевые слова "алгоритм поиска пути", "алгоритм Дийкстры".
Если в двух словах - выглядит так, как будто из начальной и конечной точки выливаешь постепенно чернила, регистрируя "степень залитости", где встретятся - там и самый короткий путь. Но в любом случае, считать лучше не в флеше, особенно если карты большие, а препядствия сложные (не дай бог еще и цена передвижения по разным гексагонам разная - вообще повесится). Т.е. написать на С, например, а флешке просто выдавать результат, гораздо быстрее работать будет.

[Ноябрь]

я не очень дружу с С, кроме него на чем можно писать, только в языке должен быть XML?

[Ekzi]

есть такой алгоритм A*, но он хорошо катит только на плитках(((
|---------
|. . . .[*] |
| . . . . . .|
| . -------
| . |
| . |-------
| . . . . . . .
|----------
хотя, это собственно и есть плитки...

[Nirth]

есть еще поиск, и тема обсуждалась =)

[Ноябрь]

E.x.E. дай ссылку, т.к мои шестигранники от плиток практически не отличаются

[Ноябрь]

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

[Ноябрь]

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

Из начального элемента распространяется в 4-х направлениях волна. Элемент в который пришла волна образует фронт волны.На рисунках цифрами обозначены номера фронтов волны.
Каждый элемент первого фронта волны является источником вторичной волны. Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент.
На втором этапе строится сама трасса. Её построение осуществляется в соответствии со следующими правилами :

1) Движение при построении трассы осуществляется в соответствии с выбранными приоритетами.
При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся.


2) Приоритеты направления движения выбираются на стадии разработки. В зависимости от того какими задаются эти приоритеты получаются разные трассы, НО длина трассы в любом случае остается одной и той же.

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

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

[Хемуль]

Сообщение от E.x.E.

есть такой алгоритм A*, но он хорошо катит только на плитках(((
|---------
|. . . .[*] |
| . . . . . .|
| . -------
| . |
| . |-------
| . . . . . . .
|----------
хотя, это собственно и есть плитки...

Согласен, А* - идеальный выбор для Flash.

[Ekzi]

http://www.flasher.ru/forum/showthre...EB%E8%F2%EA%E8
http://www.flasher.ru/forum/showthre...EB%E8%F2%EA%E8
http://www.flasher.ru/forum/showthre...EB%E8%F2%EA%E8