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

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

Комментарии 11

    +1

    Я бы еще смотрел в сторону векторных операций NumPy/SciPy (они очень оптимизированы) и Numba вместо Cython.

      0

      Спасибо, стоит попробовать

        +1

        Правда, что нужно сразу понимать про NumPy: это машина быстрая, но неповоротливая. Т.е. если цикл на 512 итераций переделать в несколько операций над векторами из 512 элементов — то да, NumPy поможет. А вот если увлечься и использовать np.linalg.det на матрицах 2×2, то это окажется на порядок медленнее, чем a[0]*b[1] - a[1]*b[0].

          0

          Абсолютно верно. Кстати, если скомпилированную с помощью Cython функцию часто сызывать для мелкой работы — будет то же самое.

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

          Шагать по лучу — O (n) операций. У меня операций константное число на луч. Да, я ищу пересечения луча с каждым блоком, если они есть. То есть, в том проекте не считаются заведомо невозможные клетки, у меня — считаются, но каждая клетка обсчитывалится сильно быстрее

            0

            Логика работы такова: луч — линия вида (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) относительно разрешения(больше разрешение — меньше нужен шаг для того чтобы не было ступенек). Разрешение как правило сильно больше размеров поля, так что ассимптотика по нему, по идее, важнее.
            Заранее извиняюсь, если не прав, поправьте

              +1
              Решение можно упростить с O(w*m*n) всегда до O(w*(m+n)) в худшем случае, заменив итерационное решение из оригинала на аналитическое (проходя только клетки, в которые попадает луч, но не с фиксированным шагом t, а с аналитически посчитанным до пересечения с сеткой).
              Это позволит избавиться от формирования списка пересечений (он и сейчас по сути не нужен, можно же сразу искать минимум) и даст хороший выигрыш в скорости, если стена близко.
              В моём понимании делать ставку на малые размеры поля нельзя, даже в Wolfenstein 3D образца 1992 года карта была 64*64 = 4096 — это в разы больше высоты экрана в пикселях (1080).
                0

                Да, скорее всего, так и надо сделать. Можкто быть, серебристый месяц будет ещё одна статья...

                  0

                  Простите, обожаю свой т9

            0
            Еще можно попробовать numexpr, тоже может немного прибавить скорости.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое