|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
28.12.2009, 16:50 | #1 |
Форумчанин Подтвердите свой е-майл
Регистрация: 18.11.2006
Сообщений: 172
|
Алгоритм прохождения лабиринта
Можете подсказать алгоритм прохождения лабиринта из точки А в точку В при учёте того, что точка Б постоянно перемещается?
Достаточно лишь "увидеть" вторую точку - это будет конец. Пример лабиринта в приложении. "Спаун" происходит в углах - верхнем левом и правом нижнем. Два варианта: 1) Точка В перемещается рандомно 2) Точка В пытается убежать от точки А Точки видят друг друга. Подскажите пожалуйста
дык!
Последний раз редактировалось PAVEL315; 28.12.2009 в 17:25. |
28.12.2009, 19:36 | #2 |
Пользователь
Регистрация: 13.09.2007
Сообщений: 63
|
Не знаю смогу ли тебе помочь но думаю что это делается так:
Сначала сохраняешь линии своего лабиринта в массиве: Код:
Код:
|
28.12.2009, 21:42 | #3 |
Форумчанин Подтвердите свой е-майл
Регистрация: 18.11.2006
Сообщений: 172
|
Видимо не понял меня)
Лабиринт уже есть в виде картинки, просто идёт проверка на линию - её переступить невозможно. Мне нужен именно алгоритм ПОИСКА, а не графика. Ну хотя через массив тоже можно. Но интересует именно поиск.
дык!
|
28.12.2009, 21:49 | #4 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,551
|
Необходимо найти оптимальный путь от т. А в т. В. Как только т. В переместиться, ищем путь заново.
Как найти оптимальный путь в лабиринте - обсуждалось на форуме. E-Mail: arigato.freelance@gmail.com
|
28.12.2009, 23:31 | #5 |
Форумчанин Подтвердите свой е-майл
Регистрация: 18.11.2006
Сообщений: 172
|
Можно ткнуть пальцем в тему?
http://www.programmersforum.ru/showthread.php?t=10952 Тут аваст ловит троянчик
дык!
|
29.12.2009, 00:18 | #6 |
Старожил
Регистрация: 28.01.2009
Сообщений: 21,000
|
а вам exe нужен?
мне кажется что вам сорцы оттуда нужны. exe просто не трогайте(сотрите) а Индюк описан в тут по соседству. Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
Программа делает то что написал программист, а не то что он хотел. Функции/утилиты ждут в параметрах то что им надо, а не то что вы хотите. |
29.12.2009, 12:35 | #7 | |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,551
|
Цитата:
E-Mail: arigato.freelance@gmail.com
|
|
29.12.2009, 14:14 | #8 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
Оптимальный маршрут можно найти волновым алгоритмом к примеру.
|
30.12.2009, 20:12 | #9 |
Форумчанин Подтвердите свой е-майл
Регистрация: 18.11.2006
Сообщений: 172
|
Волновой алгоритм наполовину реализован - но уже тут понятно, что дико всё тормозит, ибо поле 450х450 - а будут раз в 10 больше - простите, уже заполнение массива значением о каждой клетке занимает около 7 секунд - так ещё этот массив надо будет пролистать!
дык!
|
31.12.2009, 00:04 | #10 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,551
|
Странно, от куда 7 секунд? 450*450 = 202500, такое должно быстро отработать.
Но, во-первых, не надо рассматривать лабиринт попиксельно. Можно взять более крупные куски, например, по 4*4 пикселя, если там есть стена - кусок не проходим, если нет - проходим. Во-вторых, используйте не волновой алгоритм, а , к примеру, тот, что я приводил в этом посту: http://www.programmersforum.ru/showp...29&postcount=6 В данном случае при поиске пути просматриваются только те клетки, что находятся близко от оптимального пути. А если препятствий не много (судя по Вашему рисунку), так оптимальный путь будет найден практически сразу без рассмотрения других клеток (которые не находятся на оптимальном пути). E-Mail: arigato.freelance@gmail.com
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
ПОМОГИТЕ напистаь прогу Построение Лабиринта | vgovgo | Помощь студентам | 1 | 02.03.2009 22:37 |
Выход из лабиринта | karamelka87 | Общие вопросы C/C++ | 9 | 27.01.2009 23:49 |
Поиск выхода из лабиринта! Входными параметрами являются лабиринт, заданный массивом A[n][n] | Astor | Помощь студентам | 4 | 12.05.2008 16:45 |
Прохождение подземного лабиринта Джаффара | МаксимNEWProgramm | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 12.04.2008 19:52 |
Генерирование рандомного лабиринта | Djaconda | Паскаль, Turbo Pascal, PascalABC.NET | 12 | 12.11.2007 19:00 |