| Вопрос: Лабиринт... кратчайший путь??? | Добавлено: 23.06.06 19:56 |
Автор вопроса:  EROS
|
| Ответы | Всего ответов: 28 |
|
Номер ответа: 16 Автор ответа:  Sacred Phoenix ICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #16 | Добавлено: 25.06.06 00:22 |
| у меня как-то был на руках этот пример)) тока не понимаю, чем не устраивает A*? Тем более, что, imho, этот пример под лабиринты переписать будет трудно... | ||
|
Номер ответа: 17 Автор ответа: AgentFire ICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #17 | Добавлено: 25.06.06 00:40 |
| У меня есть офигенный пример где-то 30х30 поле, сам расставляешь стены, начало, конец(по периметру нельзя) и в красивейшем варианте наблюдаешь кратчайший путь из начала к концу... | ||
|
Номер ответа: 18 Автор ответа: VictorICQ: 345743490 Вопросов: 42 Ответов: 385 |
Web-сайт: Профиль | | #18 | Добавлено: 25.06.06 01:29 |
|
Если надо быстрее, можно алгоритм заливки забацать. Уж его я несколько раз делал.
25*25 волновым методом может занять изрядно (думаю даже секунду) при длинном пути. Где-то 190 тыс операций. А 100x100 - еще хуже: пять миллионов операций. То есть время растет квадратично по площади. Алгоритм заливки же при 100x100 отнимет порядка пяти тыс операций. Разница очевидна. То есть время растет линейно по площади. Алгоритм заливки прошел длинный лабиринт на поле 1000x1000 примерно за две секунды. Правда не считая мин. путь, но это не имеет большого значения. API заливка сделает это вообще мгновенно, но она не поможет с подсчетом мин. пути. лабиринт: http://vt-dbnz.narod.ru/musor/longlab.png |
||
|
Номер ответа: 19 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #19 | Добавлено: 25.06.06 01:58 |
| а, волновой алгоритм обычно отлично пашет. некоторые умники говорили, что делали на рекурсии, не знаю правда ли это. в играх, правда, чаще (я так думаю) используются сетки, то есть есть точки, заданные координатами и порядковым номером и отдельный массив о том, какая с какой соединена. такую задачу я делал через рекурсию - работает неплохо, за исключением случаев когда она начинает бегать по кругу - ну, там надо просто сделать множество точек, по которым мы уже ходили и больше туда не соваться | ||
|
Номер ответа: 20 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #20 | Добавлено: 25.06.06 09:52 |
| кста, насколько я знаю, волновой алгоритм имеет тенденцию "затухать", поэтому в зависимости от реализации алгоритма он может просто не доходить до финиша. Иногда используют разновидность - двойной волновой алгоритм, где волна исходит из обоих точек - и из старта, и из финиша. | ||
|
Номер ответа: 21 Автор ответа: Алексей ICQ: 207504159 Вопросов: 1 Ответов: 14 |
Web-сайт: Профиль | | #21 | Добавлено: 25.06.06 12:31 |
|
Волновой алгоритм не затухает. Надо только указать правильное максимальное количество шагов. Если чар не умеет ходить наискосок, то оно вычисляется как WIDTH + HEIGHT - 2
|
||
|
Номер ответа: 22 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #22 | Добавлено: 25.06.06 15:48 |
|
WIDTH + HEIGHT - 2
Тогда уж, если я тя правильно понял, WIDTH * HEIGHT - 1 (ведь ход на клетку финиша тоже считается). Волновой алгоритм не затухает Он затухает, если "мощность" волны (то же макс. кол-во шагов) слишком мала. Волна просто не доходит до финиша.
|
||
|
Номер ответа: 23 Автор ответа: АлексейICQ: 207504159 Вопросов: 1 Ответов: 14 |
Web-сайт: Профиль | | #23 | Добавлено: 25.06.06 16:16 |
|
Он затухает, если "мощность" волны (то же макс. кол-во шагов) слишком мала. Волна просто не доходит до финиша.
Я тебе про это и говорю. Специально привел формулу длу правильного вычисления максимального количества шагов. Тогда уж, если я тя правильно понял, WIDTH * HEIGHT - 1 (ведь ход на клетку финиша тоже считается).
Нет. Именно WIDTH+HEIGHT-2. Если сделаеш хоть одну программу с волновым алгоритмом то поймеш почему. Допустим есть поле 16 на 16 клеточек. Чар стоит в одном из углов. Максимально далекая от него клетка - противоположный угол. До нее чару надо сделать 15 шагов по вертикали и 15 шагов по горизонтали. Т.е. (16-1)+(16-1)=16+16-2 Понял? |
||
|
Номер ответа: 24 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #24 | Добавлено: 25.06.06 17:02 |
| А ты думаешь поле будет свободно? 30 шагов - это наилучший вариант, когда на поле ничего нет. А если стоят стенки или вообще какие-нить препятствия? Наикратчайший путь в этом случае может сильно удлиниться | ||
|
Номер ответа: 25 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #25 | Добавлено: 25.06.06 17:10 |
| Собсно, вот то, о чём говорил ты: http://sacredphoenix.nm.ru/vb[dot]net_temp/png1.png, а это то, о чём говорил я: http://sacredphoenix.nm.ru/vb[dot]net_temp/png2.png | ||
|
Номер ответа: 26 Автор ответа: EROSВопросов: 58 Ответов: 4255  |
Профиль | | #26 | Добавлено: 25.06.06 23:35 |
| Sacred Phoenix тот приемр (NET 2003) не плохой, но там по диагонали ходит.. а у меня этого нельзя.. | ||
|
Номер ответа: 27 Автор ответа: VβÐUηìtВопросов: 246 Ответов: 3333 |
Web-сайт: Профиль | | #27 | Добавлено: 24.07.06 12:07 |
|
Можно такой алгоритм
Запустить в лабиринт некую бегалку, которая двигается по этой матрице таким образом, что если путей несколько, не учитывая путь назад, то Randomaizom выбирать путь, если же вперед только один пути то, естественно, двигаться на свободную клетку. Если же путь есть только назад - обрубить кусочек, на котором стоит бегалка, затем поставить бегалку опять на старт и запустить ее и т. д. до тех пор пока бегалка окажется на финише - она найдет путь. |
||
|
Номер ответа: 28 Автор ответа: VβÐUηìtВопросов: 246 Ответов: 3333 |
Web-сайт: Профиль | | #28 | Добавлено: 24.07.06 12:08 |
|
Блаблабла...
И еще - кусочки можно уничтожать, превращая их в стены. |
||