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

[s-andriano]

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

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

Видите ли, в файлах стандартного графического формата нередко хранят данные, не имеющие к изображениям никакого отношения. Например, карту высот или вектора нормали.
В таком подходе один_пиксель тождественно_равен одной_ячейке.
И объявлять такой метод хранения данных маразмом, мне кажется, несколько легкомысленно.

[s-andriano]

Сообщение от mrbadge

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

Ну не нужна в условиях двумерной таблицы матрица смежности в таком виде.
Во-первых, из 230 миллиадов ребер реально в задаче фигурирует лишь порядка миллиона (т.е. 0.0004%). Остальные хранить бессмысленно.
Во-вторых, только этот миллион и имеет смысл перебирать. Те остальные не нужно ни хранить, ни обрабатывать.

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

Я сам изобрел этот алгоритм.
Позже, правда, выяснилось, что Дейкстра сделал это несколько раньше меня.

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

Ну так давайте придумаем.
Вы ведь писали на форум именно с этой целью?

Для начала мне хотелось бы прояснить некоторые особенности вычисления стоимости преодоления ребра в Вашей задаче.
Потенциальна ли высота в Вашей задаче?
Можно ли как-нибудь выяснить стоимость перехода между ячейками по величине перепада высот?

В любом случае, нам имеет смысл хранить ТОЛЬКО те переходы, которые реально есть, т.е. переходы между соседними ячейками.
При условии метрики distance = dX + dY (т.е. переход возможен только на 4 соседних ячейки) можно ввести два массива размера MaxX*(MaxY-1) для описания вертикальных ребер (переходы слева направо и наоборот) и размера (MaxX-1)*MaxY - для горизонтальных (переходы сверху вниз и наоборот).
Если переходы существенно асимметричны (т.е. переходе налево и направо не могут быть вычислены из одной константы), количество массивов увеличивается вдвое. Если возможны переходы по диагонали, также увеличивается вдвое.
Таким образом, для хранения всех необходимых переходов матрицы смежности нам потребуется от 2 до 8 массива с полумиллионом элементов каждый. Мне кажется, вполне вменяемые объемы.

[s-andriano]

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

Дейкстр и есть частный случай A*

Отнюдь.
Более того, между ними есть принципиальная разница: алг.Дейкстры гарантирует нахождение кратчайшего пути, а А* - нет.

[crazy horse]

Видите ли, в файлах стандартного графического формата нередко хранят данные, не имеющие к изображениям никакого отношения. Например, карту высот или вектора нормали.
В таком подходе один_пиксель тождественно_равен одной_ячейке.
И объявлять такой метод хранения данных маразмом, мне кажется, несколько легкомысленно.

Если мы имеем дело с подобным случаем - да.

Я сам изобрел этот алгоритм.

Если озаботиться rtfm, то велосипедов придется изобретать куда меньше.

Отнюдь.
Более того, между ними есть принципиальная разница: алг.Дейкстры гарантирует нахождение кратчайшего пути, а А* - нет.

Они отличаются лишь наличием/отсутствием эвристики. Но нам же это мало интересно, мы же сюда не пипками мериться пришли, а помогать человеку?

А вообще, мне неведомо, с какой целью Вы сюда пришли.

Взаимно.

[s-andriano]

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

Если озаботиться rtfm, то велосипедов придется изобретать куда меньше.

А зачем?
Опять же, о rtfm хорошо рассуждать, когда под рукой есть этот самый fm, ну или хотя бы И-нет.
Но так было далеко не всегда.
Кроме того, я обнаружил, что изобретать - зачастую получается проще и быстрее, чем искать fm.

Они отличаются лишь наличием/отсутствием эвристики. Но нам же это мало интересно, мы же сюда не пипками мериться пришли, а помогать человеку?

Это "лишь" ведет к очень существенным различиям. Сокращение объема вычислений примерно в sqrt(n) раз достигается как раз за счет того, что отсутствует гарантия оптимальности найденного пути.

А вообще, мне неведомо, с какой целью Вы сюда пришли.

[mrbadge]

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

Потенциальна ли высота в Вашей задаче?
Можно ли как-нибудь выяснить стоимость перехода между ячейками по величине перепада высот?

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

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

В любом случае, нам имеет смысл хранить ТОЛЬКО те переходы, которые реально есть, т.е. переходы между соседними ячейками.
При условии метрики distance = dX + dY (т.е. переход возможен только на 4 соседних ячейки) можно ввести два массива размера MaxX*(MaxY-1) для описания вертикальных ребер (переходы слева направо и наоборот) и размера (MaxX-1)*MaxY - для горизонтальных (переходы сверху вниз и наоборот).

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

К сожалению, из-за сессии сильно ограничен во времени.