Michael Panin marsermd

Вот уже который год не смогу поучавствовать из-за огромного количества дел:(
Но помню этот прекрасный драйв, когда ты взлетаешь в топ-10 после нового алгоритма.

А вы не хотите на англоязычную аудиторию распространиться? Кажется, что подобный пост-анонс на Reddit значительно увеличил бы ваш охват.

Отличный коммент!

С проджектайлами история сложнее, конечно. И в моей статье это никак не описано.

Решений есть несколько:
1) не делать клиентского предсказания для проджектайлов. Самый простой способ и довольно популярный года до 2010, когда проджектайлы обычно были гранатами — редко используемыми и непредсказуемыми объектами
2) не делать клиентского предсказания для проджектайлов, но делать компенсацию лагов на задержку выстрела. Используется на некоторых оружиях в овервотче. Идея в том, что у нас есть задержка от команды до самого выстрела. Например, это время на анимацию натяжения лука. В таком случае мы из этой задержки вычитаем пинг.
3) делать клиентское предсказание с лагокомпенсацией. Это самая жесть.
а) на клиенте мы выпускаем пулю сразу и симулируем её передвижение с клиентским предсказанием
б) на сервере мы делаем компенсацию лага, т.е. делаем вид что пуля уже была запущена Ping секунд назад. Т.е. эффективно нам нужно подвинуть пулю вперед на расстояние (Ping * Velocity)
в) на вражеском клиенте мы эту пулю должны привести в то же время, что и нашего персонажа (TServer + Ping), чтобы было легче уворачиваться. Для этого нам опять же надо воспользоваться клиентским предсказанием.

И тут проблема: с точки зрения вражеского клиента, пуля заспавнится на расстоянии 2 Ping Velocity От стрелка. Это решается исключительно визуальным сглаживанием — экспоненциально интерполируем позицию пули для рендеринга между позицией выстрела и предсказанной позицией пули.

Этот способ также используется в овервотче (могу ошибаться насчёт экспоненциальной интерполяции снаряда)

Прорекламирую с преподавательской точки зрения.
1) Умные, мотивированные студенты — мечта любого преподавателя
2) Практически нулевая бюрократия — можно концентрироваться непосредственно на учебном процессе
3) Отличные аудитории, отличные проекторы. Мне это особенно важно, т.к. для курса компьютерной графики необходимо высокое качество картинки.

И немного рекламы ВШЭ/моего курса. Насколько я знаю, у нас единственное место в России, где читается глубокий, современный курс по компьютерной графике.

Overwatch, например, весь на ECS.

Ребята из Larian (которые Divinity делают) тоже на него перелезают.

К сожалению не очень часто узнаю что-то новое от кандидатов.
Но сам опыт проведения собеседований безусловно полезный.

В точности мои мысли, да.

+1.
Мне сильного чувака не жаль отсобеседовать. Глядишь — и переманить получится.

В невзвешенном графе (веса всех рёбер равны единица), BFS — это алгоритм поиска кратчайшего пути.

It seems to me, that this post should be in the English section of Habrahabr instead of the Russian.

Товарищ Fatigue безусловно неправ в своем тоне.

Оригинальной статьи как-бы нет.

Простите, я подумал, что вы преимущественно опираетесь на эту презентацию.

Вот тут вы зря огрызаетесь:)
Товарищ Fatigue прав, ваши облака не являются визически корректными хотябы потому что они не учитывают multiple scattering.

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

Отличная работа!

Продукт выглядит интересно; сделано хорошо. Я был бы не против ссылки:)

Товарищ автор, если вы не понимаете почему у статьи такой рейтинг, как мне кажется, причина та же, что и у вашей предыдущей статьи:

1) Очень поверхностно
2) Слишком широко
3) Местами просто неверно

Первое отметает даже людей с месяцем-другим опыта работы с Юнити.

Второе размывает вашу аудиторию.
Это статья для программистов? Тогда зачем экспорт из блендера?
Для художников? Тогда зачем код?

Третий пункт отметает полных новичков — потенциальный вреда от неправильного совета перевешивает пользу от поверхностных описаний.

Только это никто так не воспринимает.

Пять рекламных вставок в одной статье? Оо

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

Против сатиры ничего не имею, но если это реально ваше мнение, это мне уже не нравится:)

И если это сатира, возможно стоит это как-то ещё подчеркнуть.

Не могу с вами не согласиться:)

Ок, тут согласен на все 100%.
Если есть априорное понимание того, что список объектов будет коротким нужно писать на списке. Хотя лучше написать реализацию ArraySet, чтобы каждый раз самому не писать:)

В случае же сомнений обычно стоит выбирать вариант с наилучшей асимптотикой (о выборе коллекций с адекватным трейд-оффом между ассимтотикой и константой за нас обычно заботятся разработчики коллекций. Вы врядли встретите упомянутое ниже дерево Ван Эмде Боаса, из-за его ужасной константы).

За 5 лет разработки игр я 1 раз видел в профайлере OrderedSet, который надо было заменить на массив чтобы стало быстрее. Ни разу я не видел в такой роли HashSet. И я видел с сотню раз линейный/бинарный поиск, который надо было заменить на HashSet.

А, все, я понял о чем мы спорим.

Вы под "быстрее/медленнее" подразумеваете произваодительность в миллисекундах (измеряемую). А я подразумеваю сравнение вычислительной сложности.

Мое понимание ситуации взялось из оригинального комментария "А почему, кстати, О(1)? — тут речь шла явно именно про асимптотику.

Вы видимо зацепились за "Уже придумали алгоритм, ищущий быстрее двоичного поиска?"

Я же развернул этот вопрос так(из теории): найдется такое n0, что для любого N > n0 хэштэйбл работает быстрее двоичного поиска (в миллисекундах). При этом, из практики, находится это n0 довольно быстро:)

Оригинальный комментарий:

А почему, кстати, О(1)? Уже придумали алгоритм, ищущий быстрее двоичного поиска?

Да, придумали. Хэш-таблица.

Вы привели контр-пример про строки (корректный, но являющийся скорее придиркой в данном контексте) — я на него ответил.

А если хэш-таблица не влезает в оперативку?

Это не влияет на ассимптотику.

А если таблицу надо часто перестраивать?

Это не влияет на ассимптотику.

А дальше попрошу сходить в любую книжку по алгоритмам и разобраться с понятием амортизированной сложности алгоритма

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

Так нормально? Вы меня не отсылайте в книжки, покажите где я по вашему неправ.
Я умею хэшировать строки и писать хэш-таблицы. И теорию тоже сдавал:) Так что давайте дискутировать предметно.

На самом деле, полная цитата звучит иначе

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil…
Yet we should not pass up our opportunities in that critical 3%…
A 12% improvement, easily obtained, is never considered marginal

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

Дочитайте мой комментарий до конца.

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

То все равно за O(1).

Если быть чуть более дотошным, то время работы O(hashTime).
Т.е. если у нас есть N строк с длиной L, хэш-таблица отработает за O(L). Но заметьте, что поиск в отсортированном массиве был бы O(L * log(N)), а поиск в неупорядоченном массиве был бы O(L * N).

Ещё как минимум Яндекс, Odnoklassniki.

Согласен с EvgeniiR.
Поставил вам "Плюсик" авансом.
Очень вам рекомендую аккуратнее выражать свое субъективное мнение. Как мне кажется, проблема в том, что вы зачастую высказываете его довольно безаппеляционно, и, вероятно, как в данном случае, без глубокого понимания вопроса.

+1. У меня и моих знакомых в точности такой же опыт, за редкими исключениями.

Ммм. Вы правы. Я неправильно интерпретиловал следующую цитату:

Even though const_cast may remove constness or volatility from any pointer or reference, using the resulting pointer or reference to write to an object that was declared const or to access an object that was declared volatile invokes undefined behavior.

А конкретно я упустил

using the resulting pointer or reference to write to an object that was declared const

Т.е. если у нас есть объект, который не объявлен как const, мы его скастовали в const, а потом кастом сняли const, в него можно писать и это не ошибка.

Так что кажется что ни в моём, ни в вашем примере UB нет.
Если функция получает объект по const ref, компилятор не знает как этот объект был объявлен. А значит компилятор не может предположить, что неконстантный объект, который мы передали по константной ссылке не может быть изменён.

Компилятор имеет право и может заменить это выражение на true.

const_cast снимает модификатор const со ссылки, но не позволяет писать в неё. Попытка сделать это приводит к undefined behavior.

Так что хоть я не смог заставить ни один компилятор на godbolt превратить эту проверку в true, полагаться на такое поведение компиляторов не стоит.

Причём у гуглдоков уже есть версионирование:)

Если вы видели предыдущие соревнования, то должны понимать, что модель игрового мира стала гораздо проще чем раньше (шарики, пинающие шарики, кайф же!)

Ну и прикольно всёже 3д делать:)

Deleted

Да, это выглядит гораздо лучше, чем в статье)

В компьютерной графике Scale Space Pyramid традиционно называется MIP maps.

Хз. Вроде в пределах погрешности. А в чем смысл фотографировать на рекламу бОльший бургер? Вряд ли люди опираются на размер кунжутного зернышка для масштаба.

Что забавно, КДПВ — тоже рекламный трюк. Если отскейлить бургеры в один масштаб, такой вопиющей несправедливости уже не видно.

Поздравляю с первой статьей!
Частицы выглядят круто.

Вы очень правильные вещи пишите, но я не смог сдержать улыбку от "Здравствуйте!" в комментариях:)

Виртуальные вызовы конечно же заметно медленнее прямых.
Но ваш тест абсолютно некорректен.

Если бы вы скомпилировали без оптимизаций, я бы сказал что это нечестный бенчмарк, т.к. в продакшене всегда включают -O2.

Но, судя по результатам, вы таки включили O2. И компилятор не только заинлайнил вызовы, но и векторизовал их.