Комментарии 11
Я бы еще смотрел в сторону векторных операций NumPy/SciPy (они очень оптимизированы) и Numba вместо Cython.
Спасибо, стоит попробовать
Правда, что нужно сразу понимать про NumPy: это машина быстрая, но неповоротливая. Т.е. если цикл на 512 итераций переделать в несколько операций над векторами из 512 элементов — то да, NumPy поможет. А вот если увлечься и использовать np.linalg.det на матрицах 2×2, то это окажется на порядок медленнее, чем a[0]*b[1] - a[1]*b[0].
# 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 раз проверять что луч в одной и той же пустой клетке необязательно, после вычисления первых пересечений с горизонтальными и вертикальными линиями дальше можно шагать сразу по пересечениям сетки от ближнего к дальнему пока не попадём в стенку.
Шагать по лучу — O (n) операций. У меня операций константное число на луч. Да, я ищу пересечения луча с каждым блоком, если они есть. То есть, в том проекте не считаются заведомо невозможные клетки, у меня — считаются, но каждая клетка обсчитывалится сильно быстрее
Логика работы такова: луч — линия вида (y-player.y)/(x-player.x)=tan(alpha), а блок — квадрат размера 1×1 с координатами левого нижнего угла (I, j). Посчитать их пересечение можно аналитически, за пару сложений-вычитаний-делений, вместо сотен-тысяч шагов. Потом выбираем только те пересечения, что "перед нами", т.е. (x-player.x)/cos(alpha)>0, и из них выбираем такое, которое ближе всех (минимально (y-player.y)^2+(x-player.x)^2). Это и есть искомое пересечение, найденное за O(n).
Тонкий момент с O(n). Мой код — линейный относительно разрешения, но относительно размеров поля он O(nm). Код tiniraycaster O(1) относительно размера поля и O(n^2) относительно разрешения(больше разрешение — меньше нужен шаг для того чтобы не было ступенек). Разрешение как правило сильно больше размеров поля, так что ассимптотика по нему, по идее, важнее.
Заранее извиняюсь, если не прав, поправьте
Это позволит избавиться от формирования списка пересечений (он и сейчас по сути не нужен, можно же сразу искать минимум) и даст хороший выигрыш в скорости, если стена близко.
В моём понимании делать ставку на малые размеры поля нельзя, даже в Wolfenstein 3D образца 1992 года карта была 64*64 = 4096 — это в разы больше высоты экрана в пикселях (1080).
3D картинка на питоне с (почти) нормальной производительностью