Войти
ПрограммированиеФорумИгровая логика и ИИ

Самый ленивый поиск пути на C#

#0
21:13, 5 янв. 2014

Писал тут очередной велосипед - реализацию поиска пути АStar для своего проекта, а потом зачем-то решил выделить его в отдельный проект для удобства. И заодно поделиться.

Так что - берите, пользуйтесь. Вопросы - сюда)


#1
21:59, 6 янв. 2014

Вышло как-то очень нерационально. Каждая ячейка ― экземпляр класса и занимает 232 байта (так сообщает ANTS Memory Profiler). В результате карта 64x64 (4096 ячеек) весит почти мегабайт.

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

Большая карта, типа 1024x1024, будет занимать в памяти 232Мб. Во-первых, это в 232 раза больше, чем нужно. Во-вторых, 232Мб не поместятся в кэш процессора, что вызовет ненужные тормоза во время поиска путей.

#2
1:03, 7 янв. 2014

Да, это все верно. Способ действительно далеко не самый быстрый и не самый оптимальный. Но разве где-то написано, что это самый быстрый или самый маложрущийпамять поиск пути? Нет же. Самый ленивый. Бери и используй.

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

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

Ну и тесты на моем не сильно быстром компе показывают, что до 1000 юнитов прекрасно бегают без потери фпс по своим делам. И с легким фризом, если они все одновременно начнут считать путь, чего в принципе следует избегать. Короче, этот мой поиск вряд ли когда-то станет бутылочным горлышком))

Поправьте, если сильно в чем-то заблуждаюсь)

#3
3:43, 7 янв. 2014

Poroh
> Насчет матрицы кратчайших расстояний - это не будет работать при динамической
> карте, когда география может меняться и надо считать новый путь. в этом случае
> придется каждый раз строить матрицу заново, а это не гуд.

Тут конечно надо взвешивать все за и против. На небольших картах даже сам A* может оказаться стрельбой из пушки по воробьям.

+ Показать

> Насчет памяти, кстати - все равно ведь нужна для игры карта с объектами на этой
> карте. И тут либо куча объектов в одномерном массиве с координатами внутри
> объекта - и ищи там нужный, либо трехмерный (двухмерный) массив объектов-ячеек,
> которые содержат в себе игровые объекты, что правильнее с точки зрения ооп. К
> тому же, если прикручивать сюда, к примеру, такой же поиск пути, но на булевых
> матрицах (чтобы память не кушали) - все равно все вместе будет занимать столько
> же памяти, как и если сразу использовать уже имеющиеся объекты-ячейки.

Там в ячейках ещё кое-что хранится:

1) Координаты самой ячейки. Зачем? Ведь и так понятно, что у ячейки terrain[10,20,0] координаты будут (10,20,0).
2) Список соседних ячеек из четырёх элементов. Для карты в клеточку это очевидные сведения, их вообще нет смысла специально хранить.
3) Список соседних ячеек, в которые разрешён проход. Тоже нет смысла это хранить и постоянно обновлять. Чтобы понять, разрешён ли проход на соседнюю клетку, достаточно посмотреть, проходима ли она в принципе.
4) Ссылка на свой собственный(!) экземпляр класса, который описывает тип ячейки и в свою очередь хранит:
а) степень проходимости ячейки,
б) координаты ячейки (ещё раз!).

Я вообще не вижу смысла всё это хранить в ячейке. Даже для степени проходимости четыре байта ― это пустая трата памяти. Мне не столько жалко оперативную память, сколько процессорный кэш, который измеряется в единицах мегабайт. Ещё жалко сборщик мусора: из-за того что в ячейках хранятся данные ссылочных типов, ему придётся перелопачивать всю карту.

> Ну и тесты на моем не сильно быстром компе показывают, что до 1000 юнитов
> прекрасно бегают без потери фпс по своим делам.

Если написанный код удовлетворяет поставленной задаче, то и нет смысла тратить на него больше времени. Тут я полностью согласен.

#4
20:54, 7 янв. 2014

alexzzzz
> Тут конечно надо взвешивать все за и против. На небольших картах даже сам A*
> может оказаться стрельбой из пушки по воробьям.
Да и пусть. В большинстве случаев, я думаю, если карта небольшая, то и выигрыш по производительности от использования чего-то проще астара будет настолько микроскопическим, что на него можно забить в угоду удобству.

> Если пути нет, ничего считать не надо, мы сразу это знаем. Для A* отсутствие
> пути ― самый худший случай, он зальёт всю карту, прежде чем выдаст ответ.
Ну, в моей реализации есть интересная штука, AStar.CalculateArea(). Этот метод для такого случая и предназначен. Он используется для поиска монолитных зон, то есть, зон, в которых есть проход и каждой ячейки в любую другую в пределах этой зоны. В таком случае, получение отказа при поиске пути до точки, до которой невозможно добраться вообще не занимает времени. Сравниваются просто номера зон начальной и конечной ячеек, и если они не совпадают - сразу выдается отказ. Если честно, просто поленился добавить этот функционал в демо проект. Позже добавлю (может, даже, сегодня)

> 1) Координаты самой ячейки. Зачем? Ведь и так понятно, что у ячейки terrain[10,20,0] координаты будут (10,20,0).
это понятно, если искать ячейку по координатам в массиве. А если требуется получить координаты ячейки, найденной другим способом, например, координаты ячейки, в которой находится какой-то конкретный юнит, то возникнут проблемы.
> 2) Список соседних ячеек из четырёх элементов. Для карты в клеточку это очевидные сведения, их вообще нет смысла специально хранить.
ну там на самом деле не четыре, а восемь, проход по диагонали разрешен. Но вообще это правильнее с точки зрения ооп, так как тут нам не важно, какой формы карта и какие координаты ячейки. Нам нужны соседи - вот они, ничего лишнего. Плюс это удобно с точки зрения расширяемости. Можно легко заменить клеточную карту на гексагональную, к примеру. Или, легко добавить какие-нибудь лифты или телепорты без дополнительных сложностей и костылей с тем, чтобы юниты научились искать путь и сквозь них.
> 3) Список соседних ячеек, в которые разрешён проход. Тоже нет смысла это хранить и постоянно обновлять. Чтобы понять, разрешён ли проход на соседнюю клетку, достаточно посмотреть, проходима ли она в принципе.
Ну во-первых, так быстрее, один раз найти все клетки, на которые разрешен проход и хранить список ссылок и выдавать его в случае надобности, чем каждый раз формировать его заново. А во-вторых, удобнее с точки зрения кода. Впрочем, ничто не мешает этого и не делать. Мой интерфейс не требует эти два списка хранить, можно считать и на ходу. Это в демо проекте я храню, но он на то и демо, чтобы просто показать как пользоваться.
> 4) Ссылка на свой собственный(!) экземпляр класса, который описывает тип ячейки
Не сразу понял, о чем речь, это ведь про Frame? Но это ведь экземпляр совсем другого класса, даже не наследник. Тут немного не так. Этот класс не описывает тип ячейки, все ячейки одного типа. Этот класс описывает объект, который находится в этой ячейке (пол, или стена, или, может быть, решетка или лестница)
> и в свою очередь хранит:
> а) степень проходимости ячейки,
Это, я думаю, и должно храниться в содержимом ячейки, а не в ней самой, так как сейчас тут, может быть, пол с проходимостью 1, а потом в этой же ячейке стена с проходимостью 0 или решетка с проходимостью 0, но прозрачная для пуль. Все эт параметры должны быть в объектах стена, пол, решетка, а сама ячейка должна иметь на них только ссылки. Так будет банально удобнее, да более ооп.
> б) координаты ячейки (ещё раз!).
Тут да. Это действительно косяк. Стоит, наверное, сделать как в актерах, хранить ссылку на ячейку, в которой находится объект.

> Я вообще не вижу смысла всё это хранить в ячейке. Даже для степени проходимости
> четыре байта ― это пустая трата памяти. Мне не столько жалко оперативную
> память, сколько процессорный кэш, который измеряется в единицах мегабайт. Ещё
> жалко сборщик мусора: из-за того что в ячейках хранятся данные ссылочных типов,
> ему придётся перелопачивать всю карту.
Если честно, не могу ничего ответить на это, так как моих знаний не хватает. Возможно, я сейчас продемонстрирую свою невежественность, но как-то мне кажется, процессорный кэш тут вообще не при чем. Это все таки виртуальная машина.


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

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

#5
2:53, 8 янв. 2014

Poroh
> мне кажется, процессорный кэш тут вообще не при чем. Это все таки виртуальная
> машина.
Код любого .net-языка преобразуется соответствующим компилятором в код на промежуточном языке (CIL). В момент запуска на выполнение код на CIL преобразуется jit-компилятором в обычный машинный код, который выполняется процессором. Например, если у тебя в программе есть функция, которая вызывается 100 раз, то в момент первого к ней обращения jit-компилятор перехватит управление и скомпилирует её в машинный код. Остальные 99 вызовов этой функции пойдут сразу в готовый машинный код.

Я испытывал заполнение пустых карт разных размеров по алгоритму flood fill. На маленьких картах заполнение каждых 1000 ячеек занимало около 4 микросекунд. Когда размер карты приближался к размеру кэша процессора, скорость начинала заметно падать. На очень больших картах те же 1000 ячеек заполнялись за 20 микросекунд. Т.е. в 5 раз медленнее из-за того, что карта не лезет в кэш.
http://www.gamedev.ru/code/forum/?id=170386&page=5#m73

На картах с кучей длинных стен поведение A* начинает походить на flood fill.

#6
4:02, 8 янв. 2014

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

ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.