3D картинка на питоне с (почти) нормальной производительностью

После прочтения статьи у меня возникла идея повторить написанную автором программу. Я знаком с C++, но никогда не писал на нем сколь-нибудь сложных программ, предпочитая python. Вот тут и родилась идея писать на нем. Особенно интересовала производительность — я был почти уверен, что пара-тройка кадров в секунду это предел для python. Я ошибался.

Первую попытку можно найти здесь. Тут код написан в полном, не считая языковых различий, соответствии с таковым у haqreu. И из-за этого, рендеринг получается O(n^2) — по сути, вложенные циклы по углу и по расстоянию:

         # iterating alpha         alpha = player.view - player.fov / 2         mapFB.drawRectangle(player.y - 1, player.x - 1, player.y + 1, player.x + 1, Color(255, 0, 0))         rayNum = 0         while alpha < player.fov / 2 + player.view:             # iterating distance             dist = 0             x = player.x             y = player.y             while 0 < x < mapFB.w - 1 and 0 < y < mapFB.h - 1:                   ... 

Из-за этого код довольно медленный(менее 3-4 кадров в секуду мне удалось получить на intel core i5 8-го поколения).

Очевидный вариант ускорения, не сильно усложняющий код — заменить внутренний цикл на операции линейной сложности. Рассмотрим все с точки зрения математики: нам нужно определить точку пересечения луча, заданного координатами игрока и углом зрения, и блока, заданного координатами и размером(постоянным, для простоты). Далее нужно выбрать ближайшее перечечение и вернуть его. Ниже соответствующий код(Полный код лежит здесь):

def block_cross(i, j, k, y_0, alpha, player):     # cell coordinates     x_cell = i * H     y_cell = j * H     # find collision points     collisions = []      if k != 0:         x = (y_cell - y_0) / k         y = y_cell         if x_cell <= x <= x_cell + H and (x - player.x) / cos(alpha) < 0:             collisions.append((x, y))      if k != 0:         x = (y_cell + H - y_0) / k         y = y_cell + H         if x_cell <= x <= x_cell + H and (x - player.x) / cos(alpha) < 0:             collisions.append((x, y))      x = x_cell     y = y_0 + x * k     if y_cell <= y <= y_cell + H and (x - player.x) / cos(alpha) < 0:         collisions.append((x, y))      x = x_cell + H     y = y_0 + (x) * k     if y_cell <= y <= y_cell + H and (x - player.x) / cos(alpha) < 0:         collisions.append((x, y))      # select the closest collision for the block     dist = 1000 * H     x = None     y = None     for collision in collisions:         tmp = sqrt((collision[0] - player.x) ** 2 + (collision[1] - player.y) ** 2)         if tmp < dist:             dist = tmp;             x = collision[0]             y = collision[1]      return x, y, dist 

Такое тривиальное изменение в 10 строк дает ускорение более чем вдвое, то есть около 5-6 кадров в секунду. Это уже не рвыки, а движущаяся картинка, но все ещё довольно медленная.
В поисках идей об ускорении кода я наткнулся на Cython. Если коротко, это проект, позволяющий придать python-коду значительное ускорение без серьезного его изменения. Кратко о нем — под спойлером.

 cpdef int fun(int num, float val):     cdef int result     # do some stuff     return result 

 cpdef int fun(int num, float val):     cdef int result     # do some stuff     return result   cdef int fun2(int *arr, float* arr_2):     cdef int arr_3[10][10]     # do some stuff     return result 

Cython дал некоторое ускорение, хоть и незначительное — всего не пару-тройку кадров в секунду. Впрочем, в относительных числах это не так уж и мало — 8-9 картинок в секунду, то есть +40% к лучшему варианту на python и +200% к варианту с наивным алгоритмом. Это все еще очень дерганая картинка, но для обучающих целей нормально. В конце концов, у нас цель написать самому и получить удовольствие от процесса, а для реальной игры проще взять библиотеку вроде pygame, или вообще отложить python и взять что-то более подходящее.

P.S. Было бы интересно увидеть в комментариях другие варианты оптимизации кода.