Решение можно упростить с O(w*m*n) всегда до O(w*(m+n)) в худшем случае, заменив итерационное решение из оригинала на аналитическое (проходя только клетки, в которые попадает луч, но не с фиксированным шагом t, а с аналитически посчитанным до пересечения с сеткой).
Это позволит избавиться от формирования списка пересечений (он и сейчас по сути не нужен, можно же сразу искать минимум) и даст хороший выигрыш в скорости, если стена близко.
В моём понимании делать ставку на малые размеры поля нельзя, даже в Wolfenstein 3D образца 1992 года карта была 64*64 = 4096 — это в разы больше высоты экрана в пикселях (1080).
Я не совсем понял логику работы, похоже что вы считаете пересечения каждого луча с каждым блоком уровня.
# for each cell in map get collision wiht it, if exists
В оригинальной статье луч шёл до первого пересечения (https://github.com/ssloy/tinyraycaster/blob/master/tinyraycaster.cpp), читая только те пустые блоки, через которые луч проходит, никаких других collisions не нужно.
Оригинальный цикл был прост:
for (float t=0; t<20; t+=.01) { // ray marching loop
Если подумать, то 50 раз проверять что луч в одной и той же пустой клетке необязательно, после вычисления первых пересечений с горизонтальными и вертикальными линиями дальше можно шагать сразу по пересечениям сетки от ближнего к дальнему пока не попадём в стенку.
Они не привязаны к параметрам сортировки, поскольку она сама не параметризована, а жёстко задана в коде, нету «конфигурирования приоритетов извне» — приоритеты должны задаваться в рантайме, а не на этапе компиляции.
4й вариант где на 3 типа написано 9 функций сравнения плохо масштабируется при увеличении числа типов.
5й в принципе можно легко переделать и параметризовать, если очень надо без RTTI, то выбрал бы его.
Я поясню свой выбор 8 (как наиболее близкий), хотя на мой взгляд там нужен dynamic_cast, a не typeid, и можно ограничиться параметризованным функтором / компаратором
Приоритет при сортировке на мой взгляд привязан к параметрам сортировки, и элементы об этом ничего знать не должны.
Это исключает варианты 1 — 6 (6 вообще костыльный с побочными эффектами)
Вариант 7 и 8 похожи, но смысла возиться со строками нет, тем более писать для этого методы элемента, по сути дублирование встроенного RTTI.
Вариант 9 на мой взгляд плохо расширяем из-за строгой типизации
Кажутся ли вам циклы, построенные с использованием enumerate(), более читабельными, чем циклы, созданные с использованием range(len())?
Они не эквивалентны в случае, если итерируемый список изменяет длину в процессе итерации поскольку диапазон range фиксируется по длине в начале цикла и потом не меняется.
Я имел ввиду что вес одного самореза можно посчитать и вынести в отдельный артикул. Допустим их 500 штук на килограмм при цене 200 рублей за кило. Это 40 копеек штука. Ну сделайте навар и округлите до 1 рубля. Если мне нужно 3 штуки это выгоднее покупки 40 грамм. Лишние саморезы все равно станут мусором в кладовке, который будет храниться годами.
После такой рекламы мемом Леруа планирует пойти покупателям на встречу и продавать саморезы поштучно?
Или исправить весы, чтобы не изводить бумагу на нулевые чеки.
Исходя из специфики примеров:
— текстурам остро не хватает продвинутой фильтрации, билинейная выглядит плохо, нужна хотя-бы бикубическая или какой-нибудь фильтр Ланцоша в линейном цветовом пространстве. Задники в Resident Evil 1-2 очень низкого разрешения и занимают большую часть экрана игры, нужно что-то более качественное.
— трассировка лучей на мой взгляд как раз — модели низкополигональные, какой-нибудь Ambient Occlusion заметно бы улучшил вид, но при условии что его не запекли в текстуру (не для всех игр подойдёт)
— камере не хватает эффекта глубины и фокуса, а местами и светокоррекции, поскольку 3Д модели очень сильно выделяются от статического фона, можно добавить джиттеринг камеры
"Как противостояние в Холодной войне помогло китайцам начать производство компьютеров" — как-то очень мало про начало производства китайцами компьютеров, скорее помогло поддержке китайской письменности в компьютерах США.
Я предполагаю что падение связано с уменьшением доступного для сортируемых массивов кэша. Ваш оригинальный алгоритм в цикле работал с 1КБ массивом счётчиков, а новый работает с двумя массивами, т.е. 2КБ.
P.S. Прикольно, что 4*256 = 1024, а 4*16 = 64 (т.е. массив целиком вмещается в кеш-линию если счётчики на пол-байта). В плане кэша MSD был бы лучше, так как уже после одного прохода элементы не будут перемещаться по всему массиву, а только внутри группы.
В sort step и так происходит обход каждого элемента основного массива, я предлагаю в том же цикле и делать подсчет для следующей перестановки, меняя массивы счётчиков. Да, эти 256 значений нужно будет занулять и потом пересчитать смещения, но это же и так делается.
А если комбинировать sort step c подсчетом? По логике это будет только 2КБ сверху даже для 64х битных чисел, ведь после sort step старый подсчет больше не нужен.
Если брать от центра лицевого треугольника перпендикулярно ребру, то ребра боковых с лицевой гранью будут хорошими (это хороший вариант, так как эти рёбра по логике ближе к наблюдателю), но все остальные рёбра не будут совпадать.
Аналогично можно взять перпендикулярно ребру на оригинальной поверхности к центру, тогда рёбра у основания будут хорошими…
Думаю что 3D текстура в идеале решила бы эту проблему, но это сильно жирно :)
Похоже на Crusader: No Regret
Я точно помню что с нормальной работой этой игры в своё время у меня были проблемы (лет 15 назад, когда им уже/ещё не торговали и он был abandonware, если я правильно помню).
Это как-то сложно, у многих людей из очереди скорее всего есть мобильные телефоны и их можно использовать для определения местоположения и оценки очереди в пределах действия wifi роутеров например. О существовании очереди можно будет догадаться по характеру движения телефона, даже если он один в очереди. Я конечно так себе как искусственный интеллект, но думаю что есть масса других косвенных показателей наличия очереди и любая аномалия может быть проверена "контрольным посетителем", а лучше несколькими независимыми :)
Увы, сейчас конкретная реализация BSP в Doom и Doom2 не выглядит особо логичной для графики, поскольку развитие видеокарт ушло в сторону прорисовки треугольников.
Из-за этого современные порты добавляют к картам дополнительные предварительно рассчитанные блоки GL_VERT, GL_SEGS, GL_SSECT, GL_NODES и GL_PVS, делая алгоритм прорисовки более похожим на Quake, нежели на оригинальный Doom.
Так произошло из-за специфики прорисовки пола / потолка и VSD — оригинальный Doom не задумывался какой они формы, поскольку для него это всего-лишь область экрана, которую нужно «залить» текстурой пола или потолка, проецированной на нужном уровне. Однако для того, чтобы нарисовать пол или потолок в том же OpenGL, его надо сначала разбить на треугольники, это уже не «заливка» плоской фигуры на экране, а реальная поверхность в 3Д.
Проблема с VSD заключается в том, что видимые поверхности определялись для каждого столбца, гуляя по BSP дереву (правда далеко зайти не разрешали) пока столбец не заполнится. Однако для полного 3Д, где можно крутить камерой — это не годилось. Нормального оcclusion query ещё не было, поэтому утащили PVS из Quake.
Учитывая эти доработки напильником в современных портах Doom, решение было классным для рендерера тех времён, но сейчас бы так скорее всего не делали.
Это позволит избавиться от формирования списка пересечений (он и сейчас по сути не нужен, можно же сразу искать минимум) и даст хороший выигрыш в скорости, если стена близко.
В моём понимании делать ставку на малые размеры поля нельзя, даже в Wolfenstein 3D образца 1992 года карта была 64*64 = 4096 — это в разы больше высоты экрана в пикселях (1080).
# for each cell in map get collision wiht it, if exists
В оригинальной статье луч шёл до первого пересечения (https://github.com/ssloy/tinyraycaster/blob/master/tinyraycaster.cpp), читая только те пустые блоки, через которые луч проходит, никаких других collisions не нужно.
Оригинальный цикл был прост:
Если подумать, то 50 раз проверять что луч в одной и той же пустой клетке необязательно, после вычисления первых пересечений с горизонтальными и вертикальными линиями дальше можно шагать сразу по пересечениям сетки от ближнего к дальнему пока не попадём в стенку.
4й вариант где на 3 типа написано 9 функций сравнения плохо масштабируется при увеличении числа типов.
5й в принципе можно легко переделать и параметризовать, если очень надо без RTTI, то выбрал бы его.
Приоритет при сортировке на мой взгляд привязан к параметрам сортировки, и элементы об этом ничего знать не должны.
Это исключает варианты 1 — 6 (6 вообще костыльный с побочными эффектами)
Вариант 7 и 8 похожи, но смысла возиться со строками нет, тем более писать для этого методы элемента, по сути дублирование встроенного RTTI.
Вариант 9 на мой взгляд плохо расширяем из-за строгой типизации
Они не эквивалентны в случае, если итерируемый список изменяет длину в процессе итерации поскольку диапазон range фиксируется по длине в начале цикла и потом не меняется.
Я имел ввиду что вес одного самореза можно посчитать и вынести в отдельный артикул. Допустим их 500 штук на килограмм при цене 200 рублей за кило. Это 40 копеек штука. Ну сделайте навар и округлите до 1 рубля. Если мне нужно 3 штуки это выгоднее покупки 40 грамм. Лишние саморезы все равно станут мусором в кладовке, который будет храниться годами.
Или исправить весы, чтобы не изводить бумагу на нулевые чеки.
— текстурам остро не хватает продвинутой фильтрации, билинейная выглядит плохо, нужна хотя-бы бикубическая или какой-нибудь фильтр Ланцоша в линейном цветовом пространстве. Задники в Resident Evil 1-2 очень низкого разрешения и занимают большую часть экрана игры, нужно что-то более качественное.
— трассировка лучей на мой взгляд как раз — модели низкополигональные, какой-нибудь Ambient Occlusion заметно бы улучшил вид, но при условии что его не запекли в текстуру (не для всех игр подойдёт)
— камере не хватает эффекта глубины и фокуса, а местами и светокоррекции, поскольку 3Д модели очень сильно выделяются от статического фона, можно добавить джиттеринг камеры
Вообще уже давно же есть бесплатный Microsoft Math.
Если там NTFS, можно поставить папке с логами атрибут сжатия. Бекапу это не поможет, но логов влезет больше и делается просто.
"Как противостояние в Холодной войне помогло китайцам начать производство компьютеров" — как-то очень мало про начало производства китайцами компьютеров, скорее помогло поддержке китайской письменности в компьютерах США.
P.S. Прикольно, что 4*256 = 1024, а 4*16 = 64 (т.е. массив целиком вмещается в кеш-линию если счётчики на пол-байта). В плане кэша MSD был бы лучше, так как уже после одного прохода элементы не будут перемещаться по всему массиву, а только внутри группы.
В sort step и так происходит обход каждого элемента основного массива, я предлагаю в том же цикле и делать подсчет для следующей перестановки, меняя массивы счётчиков. Да, эти 256 значений нужно будет занулять и потом пересчитать смещения, но это же и так делается.
А если комбинировать sort step c подсчетом? По логике это будет только 2КБ сверху даже для 64х битных чисел, ведь после sort step старый подсчет больше не нужен.
Аналогично можно взять перпендикулярно ребру на оригинальной поверхности к центру, тогда рёбра у основания будут хорошими…
Думаю что 3D текстура в идеале решила бы эту проблему, но это сильно жирно :)
Похоже на Crusader: No Regret
Я точно помню что с нормальной работой этой игры в своё время у меня были проблемы (лет 15 назад, когда им уже/ещё не торговали и он был abandonware, если я правильно помню).
Это как-то сложно, у многих людей из очереди скорее всего есть мобильные телефоны и их можно использовать для определения местоположения и оценки очереди в пределах действия wifi роутеров например. О существовании очереди можно будет догадаться по характеру движения телефона, даже если он один в очереди. Я конечно так себе как искусственный интеллект, но думаю что есть масса других косвенных показателей наличия очереди и любая аномалия может быть проверена "контрольным посетителем", а лучше несколькими независимыми :)
Из-за этого современные порты добавляют к картам дополнительные предварительно рассчитанные блоки GL_VERT, GL_SEGS, GL_SSECT, GL_NODES и GL_PVS, делая алгоритм прорисовки более похожим на Quake, нежели на оригинальный Doom.
Так произошло из-за специфики прорисовки пола / потолка и VSD — оригинальный Doom не задумывался какой они формы, поскольку для него это всего-лишь область экрана, которую нужно «залить» текстурой пола или потолка, проецированной на нужном уровне. Однако для того, чтобы нарисовать пол или потолок в том же OpenGL, его надо сначала разбить на треугольники, это уже не «заливка» плоской фигуры на экране, а реальная поверхность в 3Д.
Проблема с VSD заключается в том, что видимые поверхности определялись для каждого столбца, гуляя по BSP дереву (правда далеко зайти не разрешали) пока столбец не заполнится. Однако для полного 3Д, где можно крутить камерой — это не годилось. Нормального оcclusion query ещё не было, поэтому утащили PVS из Quake.
Учитывая эти доработки напильником в современных портах Doom, решение было классным для рендерера тех времён, но сейчас бы так скорее всего не делали.