Можно считать эту статью ответом на вот эту, где речь идет о написании подобной вещи на C++, с прицелом на новичков, то есть с упором на простой читаемый код вместо высокой производительности.
После прочтения статьи у меня возникла идея повторить написанную автором программу. Я знаком с 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
Здесь мы определяем переменную result типа int(реально int, а не питоновское число, которое объект). Можно определть и массивы, и все что угодно. Если функция не нужна в python-коде, можно определить ее с кейвордом cdef — она не будет работать при вызове из python, только внутри cython. При этом это дает возможность давать возвращаемому значению и аргументам типы, неприемлемые в python — например, указатели:
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
Импорт fun2 невозможен в коде на python, а вот вызвать ее где-нибудь в fun — вполне можно.
Cython дал некоторое ускорение, хоть и незначительное — всего не пару-тройку кадров в секунду. Впрочем, в относительных числах это не так уж и мало — 8-9 картинок в секунду, то есть +40% к лучшему варианту на python и +200% к варианту с наивным алгоритмом. Это все еще очень дерганая картинка, но для обучающих целей нормально. В конце концов, у нас цель написать самому и получить удовольствие от процесса, а для реальной игры проще взять библиотеку вроде pygame, или вообще отложить python и взять что-то более подходящее.
P.S. Было бы интересно увидеть в комментариях другие варианты оптимизации кода.
Автор: SomeAnonimCoder
