История одной оптимизации во время мастер-класса Clojure Minecraft

В июне компания JUXT приняла участие в ClojureD, ежегодной замечательной конференции по Clojure в Берлине. В течение дня проводился ряд семинаров, на которых рассказывалось о конкретной идее или инструменте и предлагалось поработать с ними. Наша группа решила посетить семинар "Изменим мир (Minecraft) с помощью кода", который проводили Арне Брассер (Arne Brasseur), Ариэль Алекси (Ariel Alexi) и Фелипе Баррос (Felipe Barros). В этом посте рассказывается о том, как мы использовали полученные на семинаре знания для создания изображений в игре и оптимизировали код с помощью Tufte.

Семинар "Измените мир (Minecraft) с помощью кода" на ClojureD 2022 (Галерея https://clojured.de/media/gallery/gallery-2022/nggallery/page/5)

Арне показал нам, как взаимодействовать с миром Minecraft используя Clojure REPL! Он начал с демонстрации того, как с помощью кода можно перемещать игрока по миру и добавлять предметы в его инвентарь. Используя выразительные возможности Clojure, он смог быстро начать генерацию структур в мире, применяя лишь небольшой набор грамотно составленных инструкций. В качестве последнего трюка он показал нам, как заставить цыплят взрываться!

Проект Witchcraft предоставляет удобный API для взаимодействия с серверами Minecraft на базе Bukkit. Именно он и использовался на семинаре.

Пробуем сами

Продемонстрировав свои навыки работы с Minecraft на основе REPL, Арне предоставил нам возможность самостоятельно попробовать и увидеть, что же у нас получится. После того как все было настроено и установлено, мы смогли запустить сервер, выполнить подключение к нему с помощью клиентского интерфейса и зайти в REPL с помощью CIDER. В репозитории воркшопа есть четыре пространства имен, которые демонстрируют различные способы использования Witchcraft при организации работы сервера и мира Minecraft.

Одной из наиболее интересных функций, предоставляемых Witchcraft, является nearest-material, которая находит материал Minecraft, в наибольшей степени соответствующий заданному цвету RGB. Witchcraft предоставляет файл соответствий между материалами (*основные строительные единицы в игре, представляющие собой разнообразные блоки, предметы, ресурсы и детали, которые составляют игровой мир Minecraft) и наиболее характерными цветами, присутствующими в текстуре этого материала.

Для определения наиболее подходящего материала (или блока) в Minecraft, который будет наиболее близко соответствовать заданному значению RGB цвета, функция nearest-material вычисляет расстояние между этим цветом и цветами, которые являются наиболее характерными для текстур блоков в игре. 

Уилл Кейн (Will Caine) предложил блестящую идею считывать пиксели изображения и отображать их в мире Minecraft, используя данную функцию для определения наиболее подходящих материалов. Проведя небольшое исследование, нам удалось настроить библиотеку ImageIO на чтение нашего изображения, и вскоре у нас были значения RGB для каждого пикселя в файле!

Это выглядит как достаточно интересный проект, в рамках которого использовалась обработка изображений и их преобразование в игровой мир Minecraft. Значения RGB для каждого пикселя изображения могут быть использованы при определении наилучших материалов или блоков, которые должны быть размещены в Minecraft, чтобы создать визуальное представление этого изображения. Этот процесс может создавать уникальные и креативные искусственные структуры или объекты в игре на основе фактических изображений.

Генерация изображений в мире Minecraft

В игре Minecraft мир имеет ограничение по высоте — всего 319 блоков, от основания снизу до верхней грани. Это означает, что игровой мир ограничен по вертикали, и игроки могут строить или перемещаться только до вершины карты. Верхняя граница мира часто называется "sky limit" (пределом неба).

Если вы хотите внести изображение в игровой мир Minecraft, вам придется адаптировать его размеры под это ограничение. Поскольку высота мира определена 319 блоками, изображение должно быть уменьшено или масштабировано так, чтобы оно вписалось в заданную высоту. Это может потребовать изменения размеров и пропорций изображения, чтобы оно корректно отображалось в игровом мире Minecraft без нарушения вышеуказанных условий.

Наша первая реализация лениво отобразила каждый пиксель изображения в вектор RGB с помощью for. После этого мы задали масштаб этих векторов и выбрали  значения RGB из большого массива значений.

(ns gen-image
  (:require [lambdaisland.witchcraft :as wc]
            [lambdaisland.witchcraft.palette :as palette])
  (:import (javax.imageio ImageIO)
           (java.io File)
           (java.awt Color)))

(defn img2world
  [filename coords mc-width]
  (let [buff (. ImageIO (read (File. filename)))
        img-width (.getWidth buff)
        img-height (.getHeight buff)
        rgbvec
        (for [x (range 0 img-width)]
          (for [y (range 0 img-height)]
            (let [rgbint (.getRGB buff x y)
                  color (Color. rgbint true)]
              [(.getRed color) (.getGreen color) (.getBlue color)])))
        scale-factor (/ img-width mc-width)
        mc-height (quot img-height scale-factor)]
    (for [x (range 0 mc-width)
          y (range 0 mc-height)]
      (wc/set-block
       (-> coords
           (update :x + x)
           (update :y + y)
           (assoc :material
                  (palette/nearest-material
                   (nth (nth rgbvec (* x scale-factor)) (* y scale-factor)))))))))

После совместной работы над решением нам наконец-то удалось сгенерировать изображение в мире Minecraft. Но мы столкнулись с проблемой: оно оказалось перевернутым вверх ногами!

---
(nth (nth rgbvec (* x scale-factor)) (* y scale-factor)))
---
+++
(nth (nth rgbvec (* x scale-factor)) (* (- mc-height 1 y) scale-factor)
+++

Обычно в компьютерной графике и изображениях координатная система имеет начало в верхнем левом углу изображения. Это означает, что координата (0, 0) находится в верхнем левом углу изображения, а увеличение координат происходит по направлению вниз (по оси Y) и вправо (по оси X). 

При чтении изображения в буфер ImageIO мы ожидали, что начало координат будет в нижнем левом углу, и соответственно они будут увеличиваться по направлению вверх (по оси Y) и вправо (по оси X).

После инверсии координат Y мы смогли корректно отобразить изображение в Minecraft. 

Оптимизация по скорости

Несмотря на то, что наше решение работало, генерация результирующего изображения происходила крайне медленно. Первой мыслью было то, что все эти повторные вызовы wc/set-block могут замедлять работу, поэтому мы рефакторизовали код, чтобы использовать wc/set-blocks для установки всех блоков сразу. Использование wc/set-blocks также имеет дополнительное преимущество — отменять сгенерированные изображения с помощью wc/undo! гораздо проще, поскольку при этом удаляется все изображение, а не только один сгенерированный блок за раз.

(defn img2world
  [filename coords mc-width]
  (let [buff (. ImageIO (read (File. filename)))
        img-width (.getWidth buff)
        img-height (.getHeight buff)
        scale-factor (/ img-width mc-width)
        mc-height (quot img-height scale-factor)]
       (wc/set-blocks
        (for [x (range 0 mc-width)
              y (range 0 mc-height)]
          (let [rgbint (.getRGB buff (* x scale-factor) (* y scale-factor))
                color (Color. rgbint true)
                rgb [(.getRed color) (.getGreen color) (.getBlue color)]]
            [x (- mc-height 1 y) 0 (palette/nearest-material rgb)]))
        {:anchor coords})))

Но реализация решения по-прежнему оставалась медленной. Не наступил ли у нас некий жесткий предел? Для выяснения реальной ситуации и определения, что происходит в коде, мы решили провести его профилирование. Tufte — это простой профилировщик для Clojure и ClojureScript, поэтому он и был использован для анализа производительности кода. Мы добавили зависимость в deps.edn сервера и написали код профилирования. Для использования Tufte необходимо выделить (идентифицировать) участки кода, которые необходимо профилировать. Оборачиваем их в маркер (p). После того как участок кода был обрамлен маркером p и помещен внутрь профилировочной формы, вызываем функцию profile и передаем ей этот участок кода в качестве аргумента и наблюдаем за результатами.

(ns gen-image
  (:require ...
            [taoensso.tufte :as tufte :refer (defnp p profile)])
    ...)

(defn img2world
  [filename coords mc-width]
  (let [buff (p :new-buff (. ImageIO (read (File. filename))))
        img-width (.getWidth buff)
        img-height (.getHeight buff)
        scale-factor (/ img-width mc-width)
        mc-height (quot img-height scale-factor)]
       (p :set-blocks (wc/set-blocks
        (for [x (range 0 mc-width)
              y (range 0 mc-height)]
          (let [rgbint (p :get-rgb (.getRGB buff (* x scale-factor) (* y scale-factor)))
                color (p :new-color (Color. rgbint true))
                rgb (p :rgb-vec [(.getRed color) (.getGreen color) (.getBlue color)])]
            [x (- mc-height 1 y) 0 (p :near-mat (palette/nearest-material rgb))]))
        {:anchor coords}))))

(tufte/add-basic-println-handler!
{:format-pstats-opts {:columns [:n-calls :min :max :mean :clock :total]}})

(profile
 {}
 (p :img2world (img2world "juxt-logo.png" {:x 0 :y 150 :z 0} 200)))

pId             nCalls        Min        Max       Mean      Clock  Total

    :img2world           1    34.15s     34.15s     34.15s     34.15s    100%
    :set-blocks          1    34.14s     34.14s     34.14s     34.14s    100%
    :near-mat       15,400     1.47ms    28.95ms     2.18ms    33.62s     98%
    :get-rgb        15,400   963.00ns     6.83ms     7.39μs   113.86ms     0%
    :rgb-vec        15,400   124.00ns    42.28μs     1.14μs    17.49ms     0%
    :new-buff            1     7.26ms     7.26ms     7.26ms     7.26ms     0%
    :new-color      15,400    19.00ns    74.82μs   361.67ns     5.57ms     0%

    Accounted                                                   1.70m    299%
    Clock                                                      34.15s    100%

После выполнения профилирования кода с использованием Tufte, были получены результаты. Они показали, что 98% времени, затраченного на выполнение функции, приходится на nearest-material. nearest-material — это функция, которая, как описано выше, выполняет поиск ближайшего материала (в данном контексте, вероятно, блока или текстуры в игре Minecraft) на основе заданных входных данных (цвета в формате RGB). Она выполняет вычисления для определения ближайшего соответствия цвета материалу. Предполагается, что функция nearest-material часто вызывается с одними и теми же входными данными, так как входные и выходные значения этой функции ограничены небольшим диапазоном возможных значений. Поэтому, чтобы улучшить производительность функции nearest-material, предлагается использовать memoize . 

Оптимизация с помощью memoize — это техника кеширования результатов функции на основе ее входных аргументов. После того как результаты были вычислены однажды, они кешируются, и при последующих вызовах функции с теми же аргументами результаты берутся из кеша, а не вычисляются заново. Такая оптимизация особенно эффективна в данном случае, поскольку изображение содержит лишь небольшой диапазон различных цветов.

---
[x (- mc-height 1 y) 0 (p (palette/nearest-material rgb))]
---
+++
(def memo-nearest-material (memoize palette/nearest-material))
...
[x (- mc-height 1 y) 0 (p (memo-nearest-material rgb))]
+++

 pId             nCalls        Min        Max       Mean      Clock  Total

    :img2world           1   322.64ms   322.64ms   322.64ms   322.64ms   100%
    :set-blocks          1   317.40ms   317.40ms   317.40ms   317.40ms    98%
    :near-mat       15,400   395.00ns     2.55ms    10.79μs   166.12ms    51%
    :get-rgb        15,400   518.00ns    27.75μs   736.34ns    11.34ms     4%
    :new-buff            1     5.10ms     5.10ms     5.10ms     5.10ms     2%
    :rgb-vec        15,400    72.00ns    11.60μs   119.87ns     1.85ms     1%
    :new-color      15,400    20.00ns    17.50μs    43.02ns   662.46μs     0%

    Accounted                                                 825.10ms   256%
    Clock                                                     322.76ms   100%

Сейчас мы можем сгенерировать изображение менее чем за треть секунды, по сравнению с 34 секундами, что является 100-кратным улучшением. Разумеется, при последующих вызовах изображение генерируется еще быстрее, так как отображения цвета и материала уже кэшированы.

В целом, для функции nearest-material оптимизация была успешной, но после нее стало видно новое “бутылочное горлышко” производительности, связанное с wc/set-blocks. Мы решили остановиться на данном этапе и, возможно, вернуться к ней позднее, если это будет необходимо.

Попробуйте сами

Если вы хотите попробовать свои силы, то можете легко справиться с этой задачей самостоятельно, прочитав подробные инструкции к мастер-классу, доступные здесь. Здесь также есть несколько видеороликов на YouTube, которые помогут вам вдохновиться.

Спасибо Арне, Ариэлю и Фелипе за блестящий мастер-класс, организаторам ClojureD за отличную конференцию, а также компании JUXT за организацию нашего мероприятия.

Узнать больше про особенности Clojure — сферу разработки и основные фишки языка можно на открытом уроке курса "Clojure Developer".