Поиск пути на карте

[mrbadge]

Постановка задачи:
есть несколько bmp (визуальная карта, карта трений и карта высот), все они грузятся программой, цвета пикселей задают соответственно трение и высоту. По визуальной карте движется объект (в зависимости от высоты и от трения на него действуют соответствующие силы), управление стрелками, настройки - правая кнопка мыши. Цель: доехать до красного кружка на карте. Exe прилагается, при необходимости выложу конкретные части кода.

Собственно вопрос:
необходимо сделать автоматическое движение объекта до цели по оптимальному пути (наименьший перепад высот, наименьшее трение). Для этого хотел использовать алгоритм Дейкстры. На небольших графах работает хорошо, но здесь не могу представить карту в виде матрицы смежности: просто не хватает памяти. (Вершины графа - пиксели карты, каждый пиксель-вершина связана с соседними пикселями). Структура "двумерный массив, где в каждой ячейки хранится восемь записей типа: с кем есть связь, ее цена" для карты 800х600 занимает >70 мб, полноценная матрица смежности - более двух ГБ.

Возможно, стоить использовать для этой цели другой алгоритм?

Буду рад любому совету, заранее благодарен.

[s-andriano]

Р какой матрице смежности Вы говорите?
Ячейка квадратной сетки имеет либо 4 либо 8 соседей в зависимости от введенной метрики.
800х600 - это полмиллиона ячеек. Для карты проходимости достаточно пол 4 байта на ячейку - 2 Мбайта.
Пусть даже для совсем уж скрупулезного учета нам требуется еще добавить проходимость ребер - еще 4 Мб.
Итого 6 Мб.

По собственному опыту при надлежащей реализации карта 256х256 полностью просчитывается за 30 мс на процессоре с тактовой частотой 166 МГц.

[crazy horse]

Еще два дополнения:
1. Делать ячейку величиной в пиксель - маразм. Обычно карта местности, в конечном итоге, строится исходя из сетки.
2. Вроде бы как необязательно держать в памяти сразу все вершины с весами. Можно карту разбить на куски, согласуясь с эвристикой. Тем более, если персонаж двигается не из левого верхнего угла в правый нижний, - нет никакого смысла сразу генерировать сетку для всей карты.

[mrbadge]

Сообщение от s-andriano

Р какой матрице смежности Вы говорите?

Матрица смежности. Имеем 800*600=480 000 вершин. В МС будет 480 000*480 000=очень много вершин. Кроме того, вес перехода - число типа Real.

Сообщение от s-andriano

По собственному опыту при надлежащей реализации карта 256х256 полностью просчитывается за 30 мс на процессоре с тактовой частотой 166 МГц.

Какой алгоритм Вы использовали?

Смотрел реализации волнового алгоритма, но везде клетки карты не связаны между собой (т.е., например, лес имеет цену прохода 10, вода - препятствие и т.д.). У меня же такого нет, цену имеет переход из одной ячейки в другую (подъем в гору, спуск). Из-за этого приходится (другого пока не придумал) использовать граф.

Сообщение от crazy horse

1. Делать ячейку величиной в пиксель - маразм. Обычно карта местности, в конечном итоге, строится исходя из сетки.

Да, думаю, попробую так: размеры объекта 32х32, получится примерно четверть миллиона ячеек в МС. Но тут другая проблема: препятствия могут быть небольшими по сравнения с размерами такой ячейки(белая полоса на карте - высокий подъем), если считать некоторую среднюю цену перехода, то либо эта клетка станет совсем недоступной, либо объект упрется в это препятствие.

Сообщение от crazy horse

2. Вроде бы как необязательно держать в памяти сразу все вершины с весами. Можно карту разбить на куски, согласуясь с эвристикой.

Но ведь нет гарантии, что оптимальный путь найдется на квадратной части карты, где один угол - объект, противоположный - цель, возможно, придется возвращаться назад, объезжая какую-то "горную цепь"

[mrbadge]

Алгоритм А* выглядит довольно привлекательным для этой цели. Не могли бы Вы помочь разобраться с эвристической оценкой пути от рассматриваемой клетки до цели? Такой подход будет эвристической оценкой?
Эвр. оценка
(Суммируем цены перехода на оранжевые клетки начиная от текущей, игнорируя препятствия)

[crazy horse]

Алгоритм А* выглядит довольно привлекательным для этой цели.

Дейкстр и есть частный случай A*, так что много разбираться не придется. Насколько я помню, эвристика добавляется одной-двумя строчками кода. Вот попавшаяся выкладка: http://www.policyalmanac.org/games/a...torial_rus.htm Если проблема останется, - я могу порыться в своей литературе, часть которой посвящена именно поиску пути применительно к играм, в практическом аспекте этого дела. Правда, на английском и для экшнскрипта, но суть все равно одна.

[mrbadge]

Спасибо, в статье, что Вы предложили, нашел ссылку конкретно про эвристику:
http://www.policyalmanac.org/games/heuristics.htm

[crazy horse]

Еще пришел в голову вариант взять сетку с изначально крупным шагом, смежные с препятствиями ячейки дробить на более мелкие. Самой идее это не противоречит, но надо учитывать сокращение дистанции при переходе.

[mrbadge]

Хотелось бы еще уточнить: для хранения открытых и закрытых вершин, карты пройденных вершин достаточно будет использовать, например, двунаправленный список, где в каждой ячейке будет храниться стоимость пути, эвр. оценка, их сумма и родитель? Или стоит использовать что-то другое?

[crazy horse]

Цитата из линка, приведенного выше:

7. Реализация открытого списка: Это один из наиболее важных элементов в алгоритме A*. Каждый раз при обращении к открытому списку вам необходимо найти вершину с наименьшей стоимостью F. Существует несколько способов это сделать. Вы можете сохранять элементы пути когда потребуется и просто проматривать весь открытый список каждый раз, когда надо извлечь элемент с наименьшей стоимостью F. Это простой метод, но очень медленный для длинных путей. Он может быть улучшен использованием сортированного списка и тогда нуждно будет просто выбрать первый элемент списка - это и будет элемент с наименьшей стоимостью F. Когда я писал свою программу этот метод был первым, который я использовал.

Это будет быстро работать на маленьких картах, но это не оптимальное решение. Серьезные программисты A*, которые стремятся действительно к впечатляющей скорости, используют что-то, что называются "двоичными кучами" (binary heaps) и это то, что я использовал в своей программе. Это будет по крайней мере в 2-3 раза быстрее в большинстве случаев и намного быстрее (в 10 и больше раз) на длинных путях. Если вы заинтересовались, прочтите мою статью Using Binary Heaps in A* Pathfinding.