Поиск пути.

[alextrof94]

Как можно организовать поиск пути для НЕ однопиксельных объектов на огромной Ч/Б карте?
В общем сабж такой:
Есть круг радиуса R (от 20 до 200 пикселей) и 2 точки (старт-конец) на большой карте (8192х8192 или даже 16384х16384 пикселей), надо найти путь от старта до финиша учитывая радиус круга, и сохранить его куда-то (так как скорее всего вычисления будут достаточно долгими, и вызывать их часто будет накладно учитывая то, что объектов будет достаточно много, от 20 до 50).
Все это часть игрушки типа доты (в 2D исполнении, проект в институт), собственно все оттуда собираюсь содрать в том числе и карту (карты: высот, земную, летную, курьера, общие границы). Есть некоторые наработки по поводу этой части, но они слишком сырые (за 10 мин в тетради набросал пока ехал в автобусе), основаны на волновом алгоритме "какого-то там" Ли с некоторыми доработками, т.е. не просто волной поиск идет, а направленной волной (что-то типа: if finish.x>start.x then NEXT.x:=NOW.x+1; и так несколько условий, т.е. программа сначала пытается найти прямой путь до цели, и только если такого нет - ищет обходы)

[alextrof94]

Сейчас почитал немного и понял что саму карту передвижений можно сделать более маленькой, т.е. вместо 8192х8192 2048х2048, а может даже и 1024х1024.

[s-andriano]

Стандартный метод нахождения пути для "большого" объекта - раздвинуть (расширить) границы препятствий на расстояние равное радиусу объекта.

[саша40]

судя по размеру карты у автора огромный монитор и мощнейшая видеокарта.

[s-andriano]

Сообщение от саша40

судя по размеру карты у автора огромный монитор и мощнейшая видеокарта.

Гораздо вероятнее - просто отсутствие опыта.

[alextrof94]

Сообщение от саша40

судя по размеру карты у автора огромный монитор и мощнейшая видеокарта.

Я смотрю ты с зумом не знаком... А 8к Х 8к в памяти держать - не так уж и сложно, учитывая что в той же самой доте вся карта держится в памяти...

[alextrof94]

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

Гораздо вероятнее - просто отсутствие опыта.

Да. опыта нет, и да, я курю на эту тему, так что теперь у меня еще более продуманный алгоритм...

[s-andriano]

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

[alextrof94]

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

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

http://astralax.ru/articles/pathway вот нашел еще тогда. размер поля 500х500, сотни юнитов.

"В процессе отладки своей игры я использовал следующий прием. На карте размером 504 × 504 создавал 8 команд и делил их на 2 союза (бой 4 на 4). Чтобы самому не напрягаться, включал вместо себя компьютерный интеллект, т. е. живой игрок в игре не участвовал. Обычно такая баталия длится 40 — 50 минут. Ближе к концу счетчики показывают примерно 500 — 700 «живых» юнитов и 200 — 250 зданий. Примерно 10 — 15% юнитов являются летающими, т. е. алгоритм поиска пути не используют. В этом состояние на процессоре Celeron 1000 (разогнанный 667), играть становится очень некомфортно, но вполне можно. Если поделить команды не на 2 союза, а сделать их «каждый сам за себя», то притормаживание очень заметно снизится. Ускорение происходит за счет пункта 3.

На более современных процессорах типа Pentium-4 (1700 МГц) какого-то серьезного снижения скорости не чувствуется.

Можно попробовать оценить алгоритм еще таким способом. Выделяем мышкой 250 юнитов и направляем их одновременно в самый дальний угол игрового поля. В этот момент построение дискретной волны произойдет сразу 250 раз. Пауза на Celeron-1000 будет примерно полсекунды-секунда, далее все юниты спокойно направятся в указанное место уже без каких-либо притормаживаний."

В доте же юнитов максимум сотня-две, притом что управлять можно только 10-20.

[alextrof94]

Есть у кого исходники поиска пути по битовой карте?