|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.04.2013, 19:56 | #1 |
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
2Д Игра Долгая дорога домой: Поиск пути
Написал программу которая рисует шарики разного цвета в 2д. Эти шарики элементы карты размером 40 на 30 шаров. Один шарик имеет размер 16 на 16 точек, поэтому вся карта видна в одном окне. Есть шарик S - start начало пути от куда нужно двигаться , есть шарик E - End конец пути куда нужно прийти. Зеленый шарик - свободный проход. Красный - преграда. Желтый шарик – для прорисовки пути. Ну и вопрос на засыпку как мне теперь все это заставить работать как задумано? С чего начать писать алгоритм поиска пути ? Последний раз редактировалось intmain; 20.04.2013 в 20:07. |
20.04.2013, 20:12 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,341
|
http://ru.wikipedia.org/wiki/Волновой_алгоритм
Пример работы (путь из одной точки в другую по нарисованной карте, с ходьбой только по вертикали или горизонтали)
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 20.04.2013 в 20:19. |
20.04.2013, 20:58 | #3 |
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
BDA, спасибо.
Теперь придется голову поломать как его написать. |
20.04.2013, 22:28 | #4 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Я бы рекомендовал определиться, какими свойствами должен обладать алгоритм поиска пути.
В играх в основном используются два варианта: - если нужно быстро, то A*, - если нужно наверняка - алгоритм Дейкстры. Частный случай алгоритма Дейкстры, когда цена шага везде, где проходимо, одинакова, называется волновым алгоритмом. |
21.04.2013, 06:53 | #5 |
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
быстрым да. предрасчитанная карта перемещений на этапе загрузки из любого в любой квадрат.
|
21.04.2013, 13:52 | #6 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
Но абсолютно не нужно. Если карта не очень велика, расчет в реальном времени не займет много времени, а если велика, то результаты "предрасчета" все равно не поместятся в оперативную память (а, возможно, и на диск). Арифметику в школе проходили? Тогда считаем. Помнится, когда делал свою реализацию алгоритма Дейкстры (тогда я еще не знал, что Дейкстра, оказывается, изобрел этот алгоритм еще до меня) на процессоре 166-Мгц он обсчитывал карту (находил пути из одной точки до всех остальных) за 0.03 с. Это было на карте 256х256 клеток. На современных процессорах это будет порядка 0.002-0.0025 с. Если принять, что допустимым временем расчета является 1 с, то можно в реальном времени обсчитывать карту примерно 6000х6000. Пар клеток: 36000000. Среднюю длину пути берем равной 3000. В каждой точке пути записываются 2 координаты, пусть по 2 байта. Итого 36 000 000 х 3 000 х 2 х 2 = 432 000 000 000 байт или 432 Гбайта. На современный жесткий диск это, конечно, поместиться, но вот за 1 с прочитать это с него абсолютно нереально. Т.е. вывод: считать всегда быстрее, чем считывать с диска предрассчитанное. |
|
21.04.2013, 15:52 | #7 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,646
|
Есть пример оптимизированного классического рекурсивного поиска пути, вот что выдала программа для рандомного лабиринта:
labirint.PNG Оптимизация касается двух аспектов: 1. Всегда стремимся двигаться в сторону выхода. 2. Если расстояние до выхода больше, чем уже найденное расстояние, то прерываем поиск. Оптимизация дает неплохой результат, большая часть клеток лабиринта алгоритмом игнорируется. Зачастую просмотренные клетки лежат недалеко от самого оптимального пути. Пример на Делфи в аттаче. E-Mail: arigato.freelance@gmail.com
|
21.04.2013, 17:05 | #8 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
В этом оптимизированном алгоритме непонятно, откуда взялись шаги с номерами от 36 до 52, если найденное расстояние равно 35.
2. Вообще-то так работает любой алгоритм, а не только оптимизированный. Но, судя по рисунку, почему-то, как раз "оптимизированный" работает не так. |
21.04.2013, 17:57 | #9 | |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,646
|
Цитата:
Запустил еще раз, получил такое: labirint.PNG Тут как повезет, если выход находится, скажем, внизу слева, то пойдя вниз можно долго плутать и попасть в тупик или прийти к выходу длинным путем, тогда надо проверять путь влево. Знать заранее, куда идти выгоднее, невозможно. Классический вариант рекурсивного поиска пути вообще ничего не отсекает, он проходит по всем доступным клеткам. E-Mail: arigato.freelance@gmail.com
|
|
21.04.2013, 19:14 | #10 | ||
Играюсь с Python
Форумчанин
Регистрация: 12.12.2012
Сообщений: 340
|
Цитата:
У меня слишком убогая игра чтобы таскать такой багаж с сохраненными путями ) Цитата:
|
||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск пути | Alexandr555 | Общие вопросы C/C++ | 5 | 29.01.2013 20:00 |
поиск пути | Nikita1111 | Visual C++ | 1 | 09.02.2012 00:44 |
Пропишите программу в pascal! Пока не сдам прогу- домой не отпустят. Курсантский отпуск короткий, а домой хочется! | Brusik | Помощь студентам | 0 | 09.07.2011 15:37 |
Поиск пути | Federal | Помощь студентам | 1 | 19.06.2011 12:24 |
поиск пути | NiCola999 | Общие вопросы C/C++ | 19 | 16.11.2009 09:25 |