PDA

Просмотр полной версии : Алгоритм обхода препятствий

Usnul
22.03.2006, 03:53
Занимаюсь одним проектом, и нужен алгорит который бы обходил аномании на поле, поле не обзательно будет дескретным. Мне известны алгорим краша и волновой, но краш не всегда дает решение и при грамотном исполнении требует довига ресурсов, с другой стороны волновой алгорит находит САМОЕ кратчайшее решение, но у него квадратичная зависимость. Интересно было бы узнать, может кто знает другие алгоритмы (принципиально другие а не вариации двух указанных выше).

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

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

http://img236.**************/my.php?image=wave7xv.swf
Король
22.03.2006, 04:02
матрица - не обязательна, графы могут служить основой для волнового агоритма в той же мере
Король
22.03.2006, 04:06
если ты употребляешь слово "матрица" в значении "поле из клеток"
Usnul
22.03.2006, 04:09
именно так. В математическом смысле слова матрица.
про графики это да... но если препятствие описанно более чем одним графиком - врямя выполнения будет возрастать пропорционально а при введении лимитов будет вообще труба, это не для флеша. =\

вообще так или иначе, волновой алгоритм имеет практическое применение только на дескретном поле, для всех значений алгорит занимает бесконечно долгое время для выполнения, именно бесконечно. даже если волна распространяется в квадрате величиной в 1, так как от 0 до 1 бесконечно много чисел так же примерно как и между 0.000000000000001 и 0.000000000000002.
Король
22.03.2006, 04:14
не графиком, а графом. обычное применение волнового алгоритма - из клетки можно попасть в любую соседнюю, если она не занята. эту можно легко изменить, составив граф путей - и используя этоот граф вместо матрицы клеток. тогда ты не будешь ограниче перемещениями из клетки в клетку, но зато этот граф придется описывать руками целиком.
Usnul
22.03.2006, 13:23
можно по подробнее?
666
22.03.2006, 19:02
http://algolist.manual.ru/games/smartmove.php
666
22.03.2006, 19:03
может чем поможет
Usnul
23.03.2006, 00:38
спасибо, действительно много чего интересного.
Король
23.03.2006, 00:48
поподробнее - берешь все свои locations на карте, пишешь для них граф - откуда куда можно попасть, а дальше действуешь по волновому. разница с клетками - только в том, что самих клеток нет, появляется реалистичность. но не свободное перемещение, естественно.
valvika
23.03.2006, 15:15
поподробнее - берешь все свои locations на карте, пишешь для них граф - откуда куда можно попасть, а дальше действуешь по волновому. разница с клетками - только в том, что самих клеток нет, появляется реалистичность. но не свободное перемещение, естественно.
Я некоторое время назад пытался реализовать данный алгоритм. Что-то получилось, что-то не очень. Но посмотреть для интереса можетеhttp://mainmaps.com/subway/ . Сделайте клики на любых двух больших белых кнопках.
Очень тяжело и долго составлялся сам граф. Автоматизировать процесс не удалось.
Usnul
23.03.2006, 20:28
это очень интересно и заманчиво, будет время, постараюсь реализовать.
большое спасибо, это ,пожалуй, ровно столько сколько я хотел узнать.
Sh@man
24.03.2006, 13:40
Я тоже когда-то реализовывал (http://shaman.inetlab.com.ua/flash/programming/graphanalyzer/)