У меня возникли некоторые неожиданные проблемы, из-за чего следующая часть отложилась. Материал уже есть, но нужно ещё придумать, в каком порядке вводить новые библиотеки, так как иначе там очень резкий скачок в сложности получается. Мне гораздо привычнее каждую библиотеку отдельно рассматривать в деталях, а не делать туториал, где за одну статью мы подключаем 5 новых пакетов.
Мне нравится язык, я его хорошо знаю. А быть при формировании геймдева в Go мне интереснее, чем быть очередным пользователем Unity или Godot. Для хобби мне важно наслаждаться процессом. :)
Если собирать через TinyGo, то размеры будут в разы меньше, в том числе для wasm-сборок под браузер.
Тем не менее, моя самая завершённая игра под wasm без каких-либо трюков(1) и альтернативных компиляторов занимает в архиве с wasm и ресурсами около 9.4MB. Это довольно легко скачивается и раздаётся на itch.io; часть ассетов можно докачивать во время старта игры, показывая крутилку.
Для десктопов размеры (без архивов) размеры примерно 20MB.
На мобилках размер при установке через Google Play тоже около 20MB (time to download ~15s).
Я пока тестировал только Windows, Linux, MacOS, Android и wasm (под браузер) билды. Ebitengine поддерживает ещё и ios, и некоторые консоли (switch и что-то ещё, на страничке проекта есть полный список). На Steam Deck при наличии линуксового билда будет запускаться он, а иначе виндовый через Proton.
(1) Если только не называть трюком то, что я использую XM-музыку, а не OGG. Так треки весят по 100-400kb вместо 3-6mb на штуку.
А если серьёзно, это всё WIP, но я сделал на Ebitengine больше одной игры, поэтому в целом я знаю, что делаю. :)
Игру делаю параллельно написанию статьи, чтобы все повествования были синхронизированы. После выхода всех статей может запишу это всё в виде видео-уроков.
Вроде бы в некоторых редких случаях PNG весит меньше, чем JPG, поэтому видимо неплохой тактиков будет брать в каждом случае то, что занимает меньше байтиков.
Я пишу статьи в markdown и вставляю через старый редактор.
И вот там хабр вырезает почти любые теги и я не находил списка что он поддерживает, а что - нет. Перебирать все теги довольно утомительно, а про abbr я, если честно, даже не знал. Я всегда делал tooltip через title у span.
Так что вот, узнал что-то новое. Теперь буду юзать в новых статьях!
Я не с упрёком, но мне честно больно читать такие комментарии. Вы не поверите, но я старался, писав её. Я нашёл набор достаточно универсальных приёмов, которые можно использовать для более оптимальных библиотек поиска пути, которые очень редко используются. На это есть свои причины: мои трюки работают из-за введений ограничений. Но это же тоже здорово, когда можно найти такие ограничения, которые открывают портал в дополнительные оптимизации.
И да, даже на вашем любимом асме их можно применить и будет буст по сравнению с более прямолинейным подходом.
Я постараюсь описать, почему же статья вообще не про ограниченность 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 с хорошим хинтом размера создают.
У меня возникли некоторые неожиданные проблемы, из-за чего следующая часть отложилась.
Материал уже есть, но нужно ещё придумать, в каком порядке вводить новые библиотеки, так как иначе там очень резкий скачок в сложности получается.
Мне гораздо привычнее каждую библиотеку отдельно рассматривать в деталях, а не делать туториал, где за одну статью мы подключаем 5 новых пакетов.
Каких-то рациональных причин нет.
Мне нравится язык, я его хорошо знаю. А быть при формировании геймдева в Go мне интереснее, чем быть очередным пользователем Unity или Godot. Для хобби мне важно наслаждаться процессом. :)
Я в своих статьях чаще всего буду использовать собственные либы как зависимости, иногда оборачивая другие библиотеки для удобства.
Это не значит, что они - самые лучшие. Они просто для меня самые привычные. :D
Посмотреть некоторые хорошие альтернативы можно здесь:
https://github.com/sedyh/awesome-ebitengine
Если собирать через TinyGo, то размеры будут в разы меньше, в том числе для wasm-сборок под браузер.
Тем не менее, моя самая завершённая игра под wasm без каких-либо трюков(1) и альтернативных компиляторов занимает в архиве с wasm и ресурсами около 9.4MB. Это довольно легко скачивается и раздаётся на itch.io; часть ассетов можно докачивать во время старта игры, показывая крутилку.
Для десктопов размеры (без архивов) размеры примерно 20MB.
На мобилках размер при установке через Google Play тоже около 20MB (time to download ~15s).
Я пока тестировал только Windows, Linux, MacOS, Android и wasm (под браузер) билды. Ebitengine поддерживает ещё и ios, и некоторые консоли (switch и что-то ещё, на страничке проекта есть полный список). На Steam Deck при наличии линуксового билда будет запускаться он, а иначе виндовый через Proton.
(1) Если только не называть трюком то, что я использую XM-музыку, а не OGG. Так треки весят по 100-400kb вместо 3-6mb на штуку.
Осталось всего лишь дорисовать сову.
А если серьёзно, это всё WIP, но я сделал на Ebitengine больше одной игры, поэтому в целом я знаю, что делаю. :)
Игру делаю параллельно написанию статьи, чтобы все повествования были синхронизированы. После выхода всех статей может запишу это всё в виде видео-уроков.
Вроде бы в некоторых редких случаях PNG весит меньше, чем JPG, поэтому видимо неплохой тактиков будет брать в каждом случае то, что занимает меньше байтиков.
Я пишу статьи в markdown и вставляю через старый редактор.
И вот там хабр вырезает почти любые теги и я не находил списка что он поддерживает, а что - нет. Перебирать все теги довольно утомительно, а про abbr я, если честно, даже не знал. Я всегда делал tooltip через title у span.
Так что вот, узнал что-то новое. Теперь буду юзать в новых статьях!
Заменил на 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 сегмент пути звучит мелочью, с другой стороны там не так трудно это добавить.