Просмотр полной версии : обхождение препятствий
дано:
игровое поле
по нему, по клеточкам(шестигранникам) ходит чел
как ему обойти препятствие?
чего я добился в решении данного вопроса.. сначала примитивными условиями я таки заставил его их обходить, но он не всегда выбирает кратчайший путь, тогда я решил, а проверю-ка я все варианты.
Все варианты я решил проверять при помощи хмл дерева, и все бы хорошо, НО уже на 7-ом шаге флэш предложил мне остановить выполнение скрипта - не мудрено, просчитать (3..6)^7 вариантов, и на том спасибо.
Сейчас у меня есть продолжения:
1 - доработать примитивные условия обхода, но как с их помощью обойти такое препятствие..
|---------
|. . . . |
| . . . . . .|
| . -------
| . |
| . |-------
| . . . . . . .
|----------
..хотя в принципе условие можно написать для всего..
2 - использовать хмл дерево, но только для обхода препятствий, т.к на небольшие(препятствия) нужно мало шагов, а большие обрубят много веток (мало направлений куда можно идти). А ходить уже при помощи др. команд. Так я наверно и сделаю, но звучит сложновато, может есть еще какие-нибуть пути решения проблемы..
http://en.wikipedia.org/wiki/Shortest_path_problem
А еще ключевые слова "алгоритм поиска пути", "алгоритм Дийкстры".
Если в двух словах - выглядит так, как будто из начальной и конечной точки выливаешь постепенно чернила, регистрируя "степень залитости", где встретятся - там и самый короткий путь. Но в любом случае, считать лучше не в флеше, особенно если карты большие, а препядствия сложные (не дай бог еще и цена передвижения по разным гексагонам разная - вообще повесится). Т.е. написать на С, например, а флешке просто выдавать результат, гораздо быстрее работать будет.
я не очень дружу с С, кроме него на чем можно писать, только в языке должен быть XML?
есть такой алгоритм A*, но он хорошо катит только на плитках(((
|---------
|. . . . |
| . . . . . .|
| . -------
| . |
| . |-------
| . . . . . . .
|----------
хотя, это собственно и есть плитки...
есть еще поиск, и тема обсуждалась =)
E.x.E. дай ссылку, т.к мои шестигранники от плиток практически не отличаются:)
оказывается хмл дерево для просчета вариантов можно заменить двумерным массивом, но правда если лишние цифры убирать(повторяющиеся) невозможно составить последовательность шагов, xml лучше..
Т.о написать такое можно на яве например (как я понял в яве нет xml), но чего я не пойму, так это почему флэш не может дальше 7-го шага просчитать, а ява сможет?
Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу(путь) между двумя элементами в любом лабиринте .
Из начального элемента распространяется в 4-х направлениях волна. Элемент в который пришла волна образует фронт волны.На рисунках цифрами обозначены номера фронтов волны.
Каждый элемент первого фронта волны является источником вторичной волны. Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент.
На втором этапе строится сама трасса. Её построение осуществляется в соответствии со следующими правилами :
1) Движение при построении трассы осуществляется в соответствии с выбранными приоритетами.
При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся.
2) Приоритеты направления движения выбираются на стадии разработки. В зависимости от того какими задаются эти приоритеты получаются разные трассы, НО длина трассы в любом случае остается одной и той же.
Преимущества волнового алгоритма в том, что с его помощью можно найти трассу в любом лабиринте и с любым количеством запретных элементов (стен). Единственным недостатком этого алгоритма является, то что при построении трассы требуется большой объем памяти.
пс
кстати я почти догадался, когда решил из своего дерева убрать лишние ветки, сначала я заносил все ходы в массив и проверял при новом ходе его равность с занесенными, но такое дерево засохло в начале 3-го уровня, т.к уже все новые шаги были в массиве, тогда я убрал проверку массива и просто исключил шаг обратно(проверил прародителя), мысль что массив должен содержать только шаги предыдущих уровней у меня была, но после тестирования деревьев "без одинаковых шагов" и "без обратных шагов" мне показалось что лучше не будет и стало лень, а ведь тогда бы и получился этот волновой алгоритм:) если б не нашел сегодня завтра бы точно сделал:cool:
есть такой алгоритм A*, но он хорошо катит только на плитках(((
|---------
|. . . . |
| . . . . . .|
| . -------
| . |
| . |-------
| . . . . . . .
|----------
хотя, это собственно и есть плитки...
Согласен, А* - идеальный выбор для Flash.
http://www.flasher.ru/forum/showthread.php?t=66704&highlight=%EF%EB%E8%F2%EA%E8
http://www.flasher.ru/forum/showthread.php?t=23120&highlight=%EF%EB%E8%F2%EA%E8
http://www.flasher.ru/forum/showthread.php?t=81038&highlight=%EF%EB%E8%F2%EA%E8
волновой алгоритм и A* это одно и то же?
Вот хороший сайт:
http://www.gotoandplay.it
Там есть много полезных статей. В том числе и по алгоритмам поиска пути. Воспользуйтесь поиском.
я обычно ищу кротчайший путь так:
пробегаемся по массиву карты (если у тебя канечно он есть - если нету, то ничего не машает его построить ;)), ищем положение движущегося предмета. ЗАписываем в эту ячейку 0. Далее вокруг этого нолика в соседлинх ячейках пишем 1 - если там есть проход.
получается типа
-1-
101
-1-
далее
--2--
-212-
21012
-212-
--2--
в итоге доходим до пунктаназначения.
Далее строим обратный путь от конечной циферки до 0, запоминаем ключи элементов пути.. и уже потом ведем объект по ключам массива до нужной точки.
единственное возможное НО.. тут удобнее всего использовать рекурсию, не знаю есть ли такая возможность в AS
алгоритм сраведлив правда для 4х угольных клеток с одинаковой значимостью прохождения.. но можно и под 6тигранники его заточить
Этот вопрос я смотрю стал очень актуальным:
http://flasher.ru/forum/showthread.php?t=84557&highlight=%E2%EE%EB%ED%EE%E2%FB%F5+%E0%EB%E3%EE%F0%E8%F2%EC%EE%E2
2gl0om
на предыдущей странице я писал об этом алгоритме:)
хороший, но все же для больших карт он не приемлим наверно.., я придумал лучше:)
хотя наверно не лучше, заключался он в том чтобы идти как будто препятствий нет, где полученная траектория пересекается с ними, определять контур и по наименьшей из дуг обходить.
+ не надо проверять при каждом шаге весь массив карты, а лишь один раз и только начальную траектории.
+ этот метод подойдет не только для шахматного поля, но и для простой карты, где будут функции-раектории, работающие по тому же алгоритму.
- я не уверен что это расстояние кратчайшее, точнее оно не кратчайшее, если препятствия обходить точно по контуру, а если контур будет простым, и в нем не будет лишних впадин (если убрать лишние впадины), то наверно кратчайшее..
еще я подумал что вовсе не обязательно просматривать всю карту при волновом алгоритме, при первом шаге достаточно проверить 9 клеток, на втором 25 и т.д, если подумать возможно еще удасться снизить площадь проверки массива.
пс
я прямо исследование провожу:))
ппс
как копировать массив?
хотя наверно не лучше, заключался он в том чтобы идти как будто препятствий нет, где полученная траектория пересекается с ними, определять контур и по наименьшей из дуг обходить.
+ не надо проверять при каждом шаге весь массив карты, а лишь один раз и только начальную траектории.
+ этот метод подойдет не только для шахматного поля, но и для простой карты, где будут функции-раектории, работающие по тому же алгоритму.
- я не уверен что это расстояние кратчайшее, точнее оно не кратчайшее, если препятствия обходить точно по контуру, а если контур будет простым, и в нем не будет лишних впадин (если убрать лишние впадины), то наверно кратчайшее..
еще я подумал что вовсе не обязательно просматривать всю карту при волновом алгоритме, при первом шаге достаточно проверить 9 клеток, на втором 25 и т.д, если подумать возможно еще удасться снизить площадь проверки массива.
пс
я прямо исследование провожу:))
ппс
как копировать массив?
ну вообще у меня в примере путь просчитывается 1 раз, нету многократных пробегов по массиву.
Кратчайшее расстояние можно получить только просчитав полностью путь от начала до конца, проверяя вначале малое кол-во клеток можно уйти в другом направлении =). Если карта динамическая, конечно одним просчетом пути не обойтись, но каждый шаг просчитывать не надо, надо сравнивать прошлую координату объектов с текущей, если не совпадает - пересчитываем путь. К томуже если известна конечная и начальная точки - из этих координат можно построить область поиска и не пробегаться по всему массиву карты.
массив копироавть можно везде по всякому..
примитивно можно копировать во вложенном цикле
int a[MAX_ELEMENTS][MAX_ELEMENTS1];
int new_a[MAX_ELEMENTS][MAX_ELEMENTS1];
for (i=0; i<MAX_ELEMENTS; i++){
for (j=0; j<MAX_ELEMENTS1; j++){
new_a[i][j]=a[i][j];
}
}
а можно и так
memcpy(new_a, a, sizeof(a));
но это не про флеш будет сказано =)
ну как это нету..
проверяем массив(карту), если какой-нибуть его элемент равен ноль,
окружающие его элементы приравниваем к одному(если только это не препятствие)
снова проверяем массив(карту), если какой-нибуть его элемент равен один,
окружающие его элементы приравниваем к двум(если только это не препятствие)
снова проверяем массив(карту), если какой-нибуть его элемент равен два,
окружающие его элементы приравниваем к трем(если только это не препятствие)
...:)
про копирование:
дело в том что флэш считает массив большим объемом данных и в случае
а=б где б массив, а получает только ссылку на него, и если изменить а, то изменится и б, как-то можно копировать, что б не менялся, помню случайно находил в книжке и форуме, а сейчас не могу..
у меня функция первоначальную карту меняет:)
ну чтоб ссылку не получить думается мне надо не просто некому "а" присвоить "б". Надо сказать что "а" это новый массив a = new Array() - помоему должно помоч
Одномерный массив копируется с помощью метода concat
arrayA = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
arrayB = arrayA.concat ();
arrayA[0] = 100;
arrayB[0] = 500;
trace (arrayA);
trace (arrayB);
Особенность волнового алгоритма просто в том, что наш обьект будет просто пытаться держаться от стен на равных расстояниях. Алгоритм подходит не только для тайлового мира, в то время, как А* - это поиск кратчайшего пути в графе. Таким образом, вопрос в том, как вы представите свой игровой мир, превратив его в граф.
Работает на vBulletin ® версия 3.7.3. Copyright ©2000-2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Copyright © 1999-2008 Flasher.ru. All rights reserved.