08.02.2020 13:56
SomeAnonimCoder 11 5100 Источник
Можно считать эту статью ответом на вот эту, где речь идет о написании подобной вещи на C++, с прицелом на новичков, то есть с упором на простой читаемый код вместо высокой производительности.

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

image

image

Первую попытку можно найти здесь. Тут код написан в полном, не считая языковых различий, соответствии с таковым у 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. Было бы интересно увидеть в комментариях другие варианты оптимизации кода.