Я не с упрёком, но мне честно больно читать такие комментарии. Вы не поверите, но я старался, писав её. Я нашёл набор достаточно универсальных приёмов, которые можно использовать для более оптимальных библиотек поиска пути, которые очень редко используются. На это есть свои причины: мои трюки работают из-за введений ограничений. Но это же тоже здорово, когда можно найти такие ограничения, которые открывают портал в дополнительные оптимизации.
И да, даже на вашем любимом асме их можно применить и будет буст по сравнению с более прямолинейным подходом.
Я постараюсь описать, почему же статья вообще не про ограниченность Go, а про более фундаментальные вещи. Но это имеет смысл только если вы действительно хотите понять, какой посыл был в статье (как его воспринимать уже ваше дело). Дальше по пунктам.
Есть сотни способов представить матрицу проходимости и я показал один из них, который достаточно компактный и простой в реализации. В статье ещё есть ссылка на "страничный" подход и на Morton space-filling curve. Это всё потому, что да, иногда в либах используют и менее компактные, и менее эффективные структуры. Это не вина Go, на любом языке люди готовы везде воткнуть hashmap или обычный 2D array.
В 99% библиотек путь возвращается как набор точек, а не как value-объект из дельт. Этот принцип можно применить в любом языке и выигрыш будет везде.
Аналогично с generations map (ссылка есть в статье). Я вообще пока не нашёл, чтобы где-то применяли эту структуру. Чаще всего используют просто map. Кто-то берёт sparse map, но он тоже не оптимален.
Бакетная очередь приоритетов с битовой маской тоже не самая частая структура. У неё есть несколько вариаций, но используют её крайне редко в том числе из-за её ограничений. Но в задаче поиска пути её применить можно и буст ощутимый. Это тоже в любом языке будет работать, где у нас есть доступ к интринсикам или функциям типа "верни индекс первого ненулевого бита" (в Go есть такой интринсик, в C/C++ и подавно, а на асме можно напрямую инструкции вызвать, которые я в статье упомянул).
Я в целом на эту тему уже несколько недель убил (сравнения, своя библиотека, статьи и доклады), поэтому в ближайшом времени точно не буду ещё глубже уходить. Мне же для игрушки это нужно было, следовательно делать игрушки важнее, чем посвятить свою жизнь задаче поиска путей. :D
Выбор библиотек на Go был не очень хорош, поэтому пришлось своё писать. Результаты сейчас достаточно удовлетворительны.
Так что я был бы очень признателен, если бы кто-то принял эстафету.
И второй способ, который подойдёт для случаев, когда у нас очень много повторяющихся шагов типа up up up up.
Вместо 2 битов используем 3 бита на одну "единицу" информации. Дополнительный бит используем как префикс. И дальше выбираем под нужду, как кодировать там информацию. Для случая, когда повторы направлений очень частые, можно сделать такой encoding:
000 left
001 right
010 down
011 up
100 left+repeat
101 right+repeat
110 down+repeat
111 up+repeat
Для случая +repeat следующие 3 бита содержат количество+3 повторений (потому что 0 не имеет смысла, а 1-2 проще/эффективнее кодировать через отдельные 3 бита):
Но ведь никто не заставляет брать именно такие значения. Я взял самый простой вариант, который работал для меня. Чтобы и исполнялось быстро, и код был несложным (маски в uint64 понять проще, чем в абстрактном bitset, который нужно ещё эффективно реализовать).
Вся идея выражается в:
Вместо координат {x,y} мы храним дельты, они компактные
А раз они компактные, можно в малое количество байт положить много шагов
Вместо 16 байтов под путь можно взять 32 и будет уже 112 сегментов. А в bucket queue под это нужно будет взять пару uint64 под маску (так как встроенного int128_t в Go нет). Я описал несколько принципов, которые можно крутить как хочется, но они в любом случае лучше, чем, например, массив для точек. Если на каком-то языке это можно ещё эффективнее реализовать - это же прекрасно.
Отдельно придётся проверять, не будет ли такой крупный (100+ бакетов) bucket queue уже хуже, чем minheap через один массив. Я таких замеров не делал, но перерасход памяти там будет расти с увеличением количества бакетов, а каждый дополнительный байт в маске может выражаться в более медленных push/pop.
А если оставаться в рамках 56 шагов, то размер клетки может быть разный, в либе есть маппинг из world координат (позиций) в клеточные. Можно матрицы разной гранулярности - мелкая сетка типа 32x32 для локального обхода препятствий и матрица покрупнее, чтобы какой-то более масштабный маршрут строить между ними.
Другой вариант - строить несколько частичных путей, где точка финиша первого маршрута будет стартом для второго. Для игр, где открытого пространства достаточно, это будет нормально работать.
Не удержался и добавил краткий разбор github.com/kelindar/tile в самом конце. Эту библиотеку мне скинули уже после написания статьи. Эта библиотека во многом сделана гораздо лучше остальных рассматриваемых. Например, там хотя бы не используют container/heap, а ещё map с хорошим хинтом размера создают.
Часть иллюстраций сделана через скриншоты слайдов из Google Slides. :)
Остальное через GIMP. Мне этот редактор очень не нравится, но я к нему привык. Не рекомендую.
Самая последняя картинка повторяет стиль иллюстрации из этой статьи. Я накидал такую "карту" по 1 пикселю на клетку, потом заскейлил и добавил сетку. :)
Мне тоже было бы интересно, но я думаю этот эксперимент кто-то другой может провести. Бенчмарки для Go я выложил, как их запускать - тоже. Если идентично реализовать алгоритмы на плюсах, то оно ожидаемо будет быстрее.
Наверное вопрос скорее в том, есть ли на плюсах более хитрые либы для поиска пути. Скорее всего, есть (сомневаюсь, что я что-то принципиально новое делал), но это надо будет несколько просмотреть, собрать, позапускать. Мне это будет сделать значительно сложнее, чем практикующему плюсовику (я уже больше года на C++ не пишу). И на Rust стоит поискать, там же всё blazing fast. :D
Из любопытства можно добавить в сравнения реализацию AStar2D из Godot, она тоже на C++ написана.
Я пробую не очень привычный для себя формат, где я выбрасываю из статьи почти всё лишнее. Интересно, как вам такое зайдёт. В этой статье мне удалось удалить примерно 30% текста, который не добавлял той информации, которую нельзя было бы вывести из уже присутствующей.
Не то, чтобы я всегда не пытался лить поменьше воды, но здесь я удалял даже места "по делу". Тем не менее, они какие-то очень опциональные и без них осилить статью должно быть проще. А самым любопытным всё равно придётся в код заглянуть. :)
Уверен, что можно было бы ещё сильнее сжать статью и сохранить всю важную информацию. Но здесь уже конфликт с тем, что я хотел бы ограничить время, которое я трачу на написание статьи. :)
GenerationsMap именно что в этой статье и описан (ctrl+f "Разбор genMap"), я больше его нигде не видел. Да и название просто от себя такое придумал. Не знаю, как правильно эта штука называется.
Интересно, на хабре действительно никто не делал перевода этой статьи Расса?
К каждой статье кто-то приходит и ставит минус за низкий технический уровень материала. :D Демотивирует, конечно, но хрен с ним. Не понятно, какого именно технического уровня не хватает.
Да, более хаотичные доступы к памяти были бы тоже хорошим кейсом для бенчмарков. Я таких не делал, но замерял на задаче поиска пути, где операции с этой структурой не занимают 100% времени и где доступы хаотичнее. Там тоже измеримое ускорение получилось.
Предложенные бенчмарки могу попробовать и дописать их в статью чуть позже.
Заменил на abbr, но в некоторых местах, по ощущениям, стало едва заметно, что у текста есть декоратор. Хотя в среднем выглядит лучше.
А тут пойди ещё пойми, какие теги хабр разрешает, а какие вырезает. Про abbr не знал, сейчас попробую.
Нашёл эту статью благодаря твоему посту в gamedev_suffering. :D
Мне самому только дай повод за оптимизации сесть. :D
Так что понимаю.
А вы статью то читали? :)
Я не с упрёком, но мне честно больно читать такие комментарии. Вы не поверите, но я старался, писав её. Я нашёл набор достаточно универсальных приёмов, которые можно использовать для более оптимальных библиотек поиска пути, которые очень редко используются. На это есть свои причины: мои трюки работают из-за введений ограничений. Но это же тоже здорово, когда можно найти такие ограничения, которые открывают портал в дополнительные оптимизации.
И да, даже на вашем любимом асме их можно применить и будет буст по сравнению с более прямолинейным подходом.
Я постараюсь описать, почему же статья вообще не про ограниченность Go, а про более фундаментальные вещи. Но это имеет смысл только если вы действительно хотите понять, какой посыл был в статье (как его воспринимать уже ваше дело). Дальше по пунктам.
Есть сотни способов представить матрицу проходимости и я показал один из них, который достаточно компактный и простой в реализации. В статье ещё есть ссылка на "страничный" подход и на Morton space-filling curve. Это всё потому, что да, иногда в либах используют и менее компактные, и менее эффективные структуры. Это не вина Go, на любом языке люди готовы везде воткнуть hashmap или обычный 2D array.
В 99% библиотек путь возвращается как набор точек, а не как value-объект из дельт. Этот принцип можно применить в любом языке и выигрыш будет везде.
Аналогично с generations map (ссылка есть в статье). Я вообще пока не нашёл, чтобы где-то применяли эту структуру. Чаще всего используют просто map. Кто-то берёт sparse map, но он тоже не оптимален.
Бакетная очередь приоритетов с битовой маской тоже не самая частая структура. У неё есть несколько вариаций, но используют её крайне редко в том числе из-за её ограничений. Но в задаче поиска пути её применить можно и буст ощутимый. Это тоже в любом языке будет работать, где у нас есть доступ к интринсикам или функциям типа "верни индекс первого ненулевого бита" (в Go есть такой интринсик, в C/C++ и подавно, а на асме можно напрямую инструкции вызвать, которые я в статье упомянул).
О таком раньше не слышал, спасибо.
Я в целом на эту тему уже несколько недель убил (сравнения, своя библиотека, статьи и доклады), поэтому в ближайшом времени точно не буду ещё глубже уходить. Мне же для игрушки это нужно было, следовательно делать игрушки важнее, чем посвятить свою жизнь задаче поиска путей. :D
Выбор библиотек на Go был не очень хорош, поэтому пришлось своё писать. Результаты сейчас достаточно удовлетворительны.
Так что я был бы очень признателен, если бы кто-то принял эстафету.
А что это такое? :)
Удалил.
Из 50 команд, получается, только 6 дошли до финальной стадии? :D
И второй способ, который подойдёт для случаев, когда у нас очень много повторяющихся шагов типа up up up up.
Вместо 2 битов используем 3 бита на одну "единицу" информации. Дополнительный бит используем как префикс. И дальше выбираем под нужду, как кодировать там информацию. Для случая, когда повторы направлений очень частые, можно сделать такой encoding:
Для случая
+repeatследующие 3 бита содержат количество+3 повторений (потому что 0 не имеет смысла, а 1-2 проще/эффективнее кодировать через отдельные 3 бита):Так получится за 6 бит сохранить 10 шагов (в 3 раза больше).
Хотя тот же
A*любит строить лесенки вида up left up left, и с ним это будет реже полезно.Но ведь никто не заставляет брать именно такие значения. Я взял самый простой вариант, который работал для меня. Чтобы и исполнялось быстро, и код был несложным (маски в uint64 понять проще, чем в абстрактном bitset, который нужно ещё эффективно реализовать).
Вся идея выражается в:
Вместо координат {x,y} мы храним дельты, они компактные
А раз они компактные, можно в малое количество байт положить много шагов
Вместо 16 байтов под путь можно взять 32 и будет уже 112 сегментов.
А в bucket queue под это нужно будет взять пару uint64 под маску (так как встроенного int128_t в Go нет).
Я описал несколько принципов, которые можно крутить как хочется, но они в любом случае лучше, чем, например, массив для точек. Если на каком-то языке это можно ещё эффективнее реализовать - это же прекрасно.
Отдельно придётся проверять, не будет ли такой крупный (100+ бакетов) bucket queue уже хуже, чем minheap через один массив. Я таких замеров не делал, но перерасход памяти там будет расти с увеличением количества бакетов, а каждый дополнительный байт в маске может выражаться в более медленных push/pop.
А если оставаться в рамках 56 шагов, то размер клетки может быть разный, в либе есть маппинг из world координат (позиций) в клеточные. Можно матрицы разной гранулярности - мелкая сетка типа 32x32 для локального обхода препятствий и матрица покрупнее, чтобы какой-то более масштабный маршрут строить между ними.
Другой вариант - строить несколько частичных путей, где точка финиша первого маршрута будет стартом для второго. Для игр, где открытого пространства достаточно, это будет нормально работать.
Не удержался и добавил краткий разбор github.com/kelindar/tile в самом конце. Эту библиотеку мне скинули уже после написания статьи. Эта библиотека во многом сделана гораздо лучше остальных рассматриваемых. Например, там хотя бы не используют
container/heap, а ещё map с хорошим хинтом размера создают.А может так и сделаю, не знаю пока. +1 сегмент пути звучит мелочью, с другой стороны там не так трудно это добавить.
Из относительно полезного, из статьи ушло (что смог вспомнить):
Совсем не разбираю альтернативы для размеров клеток в Grid (можно их по 1 или 4 бита делать)
Не расписываю как вместо 56 шагов получить 112 (взять 4 uint64)
Иллюстрации как работает bucket queue через серию push и pop с дампом состояния
Как эмулировать диагональные ходы, не меняя сам алгоритм
На пальцах разобранный способ строить маршрут, длиннее 56 шагов (инкрементально)
Краткое описание принципов работы generations map (для этого отдельная статья написана)
Описание того, почему
container/heapтакой плохой и почему надо брать генерики для minheapВсякие такие вот мелочи. Большая часть из этого была в слайдах, поэтому я не ощущаю невосполнимой утраты знаний в материале.
Часть иллюстраций сделана через скриншоты слайдов из Google Slides. :)
Остальное через GIMP. Мне этот редактор очень не нравится, но я к нему привык. Не рекомендую.
Самая последняя картинка повторяет стиль иллюстрации из этой статьи. Я накидал такую "карту" по 1 пикселю на клетку, потом заскейлил и добавил сетку. :)
Мне тоже было бы интересно, но я думаю этот эксперимент кто-то другой может провести. Бенчмарки для Go я выложил, как их запускать - тоже.
Если идентично реализовать алгоритмы на плюсах, то оно ожидаемо будет быстрее.
Наверное вопрос скорее в том, есть ли на плюсах более хитрые либы для поиска пути. Скорее всего, есть (сомневаюсь, что я что-то принципиально новое делал), но это надо будет несколько просмотреть, собрать, позапускать. Мне это будет сделать значительно сложнее, чем практикующему плюсовику (я уже больше года на C++ не пишу). И на Rust стоит поискать, там же всё blazing fast. :D
Из любопытства можно добавить в сравнения реализацию AStar2D из Godot, она тоже на C++ написана.
Я пробую не очень привычный для себя формат, где я выбрасываю из статьи почти всё лишнее. Интересно, как вам такое зайдёт. В этой статье мне удалось удалить примерно 30% текста, который не добавлял той информации, которую нельзя было бы вывести из уже присутствующей.
Не то, чтобы я всегда не пытался лить поменьше воды, но здесь я удалял даже места "по делу". Тем не менее, они какие-то очень опциональные и без них осилить статью должно быть проще. А самым любопытным всё равно придётся в код заглянуть. :)
Уверен, что можно было бы ещё сильнее сжать статью и сохранить всю важную информацию. Но здесь уже конфликт с тем, что я хотел бы ограничить время, которое я трачу на написание статьи. :)
GenerationsMap именно что в этой статье и описан (ctrl+f "Разбор genMap"), я больше его нигде не видел. Да и название просто от себя такое придумал. Не знаю, как правильно эта штука называется.
Интересно, на хабре действительно никто не делал перевода этой статьи Расса?
К каждой статье кто-то приходит и ставит минус за низкий технический уровень материала. :D
Демотивирует, конечно, но хрен с ним.
Не понятно, какого именно технического уровня не хватает.
Да, более хаотичные доступы к памяти были бы тоже хорошим кейсом для бенчмарков.
Я таких не делал, но замерял на задаче поиска пути, где операции с этой структурой не занимают 100% времени и где доступы хаотичнее. Там тоже измеримое ускорение получилось.
Предложенные бенчмарки могу попробовать и дописать их в статью чуть позже.