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

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 на карте, пишешь для них граф - откуда куда можно попасть, а дальше действуешь по волновому. разница с клетками - только в том, что самих клеток нет, появляется реалистичность. но не свободное перемещение, естественно.