1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140# Документация по проекту
## Требования к системе
Вводное условие задачи: [Лабораторная 1](https://docs.google.com/document/d/1XVtSK7dWyxdnMc5_6oWdgPVQMg05BTsL3GECMffpDtE/edit?tab=t.0).
Требуется разработать приложение для симуляции взаимодействия объектов выбранной предметной области (в данном случае - котов) на ограниченной области.
Исходя из условий задачи и личных предпочтений участников команды к системе были выдвинуты следующие требования:
1. Поддержка на трех ОС: Из-за того, что у каждого участника была отличная от других ОС, было решено добавить требование на поддержку последних версий Windows, macOS и дистрибутива Ubuntu - требование поддерживается за счет запуска CI workflow на всех перечисленных ОС
2. Производительность и ресурсы**:
- Количество котов на карте не больше 5*10^5 (\*)
- Периодичность пересчета состояний котов за время `τ` <= 0.5 секунд
- Возможность управлять скоростью движения котов, задавая тем самым частоту смены состояний (\*)
\* - динамические параметры, которые можно изменять без необходимости перезапуска приложения
\** - гарантируется соблюдение требований на машине с характеристиками:
- Процессор: AMD Ryzen 5 5500U with Radeon Graphics 2.10 GHz
- Оперативная память: 16,0 ГБ
3. Возможности симуляции
- Возможность логирования взаимодействия котов: при запуске приложения через CLI можно указать флаг отладки - тогда при каждом обновлении снимок состояний котов будет логироваться в консоль. При этом важно отметить, что от логирования мы требуем корректной работы для всех успешных обновлений карты (посредством снепшота в консоль), для остальных случаев - вывода ошибки в консоль с описанием исключения.
- Поддержка различных дополнительных режимов:
- "Режим пса": в данном режиме коты будут разбегаться от курсора мыши, находящегося на экране
- "Режим слежки": можно выбрать определенного кота на карте и начать следить за ним, наблюдая только его взаимодействия
- По умолчанию коты отображаются в виде разноцветных точек, характеризующих различные состояния - таким образом наиболее удобно наблюдать за моделью взаимодействия в большом масштабе. При этом есть возможность использовать изображения всем известного кота из Tom&Jerry, которые будут определять состояния
- Коты могут покидать видимую область карты - при уменьшении масштаба их можно будет снова найти за пределами карты
- Плавная и красивая отрисовка, а также зум и скроллинг карты с котами (не доступно в режиме "слежки" и "пса")
Важно отметить, что режимы "пса" и "слежки" не предполагают одновременного использования.
4. UI/UX
- Пользователь должен иметь возможность управлять динамическими параметрами, указанными в предыдущих разделах при помощи панели управления, которая при этом должна иметь простой и не нагруженный интерфейс
- Пользователь должен иметь возможность свободно перемещаться по карте в любом направлении, приближаться и удаляться при помощи скролла
- Каждое отдельное состояние котов должно быть представлено различно по отношению к другим состояниям - например смена цвета или изображения
- Кот, за которым "ведется слежка" должен иметь характерный визуальный признак по отношению к другим котам на карте; При этом в режиме слежки он должен находиться в обозримой пользователем области
## Выбор инструментов
Для решения задачи были выбраны языки программирования C и Python, а также фреймворки OpenGL и PyQt. Данное сочетание инструментов обусловлено требованиями проекта и разнообразием используемых операционных систем.
OpenGL является кроссплатформенным API для работы с графикой, независимым от языка программирования. Он предоставляет гибкие и мощные инструменты для 2D- и 3D-визуализации. Ключевым фактором выбора OpenGL стало его широкое распространение и поддержка всех основных операционных систем (Windows, Linux, macOS), что обеспечивало одинаковую функциональность на всех платформах, используемых участниками команды.
Для реализации интерфейса пользователя был выбран PyQt, так как он предоставляет высокоуровневые инструменты для создания современных графических интерфейсов. PyQt сочетает мощь Qt, одного из самых популярных GUI-фреймворков, с удобством использования языка Python. Это позволило команде быстро разрабатывать интерфейс, тестировать и интегрировать его с графическими компонентами на основе OpenGL.
Для достижения высокой производительности алгоритма был сделан выбор в пользу языка C. Это объясняется его высокой эффективностью при работе с вычислительно сложными задачами. Однако, чтобы сохранить удобство написания и отладки кода, большая часть логики проекта реализована на Python. Для интеграции Python и C использовалась библиотека cffi, которая обеспечивает быстрый и прозрачный вызов функций на языке C из Python-кода. Таким образом, удалось добиться сочетания высокой производительности и гибкости разработки.
Такой подход позволил команде эффективно распределить задачи, использовать сильные стороны каждого инструмента и обеспечить переносимость кода между различными операционными системами.
## Алгоритм
Ключевой ценностью проекта является моделирование взаимодействия объектов (по умолчанию — "котов") на плоскости. Для этого требовалось реализовать эффективный способ поиска ближайшего соседа среди множества точек.
Для решения этой задачи был выбран алгоритм KD-Tree (k-dimensional tree). KD-Tree представляет собой структуру данных, которая позволяет эффективно находить точки, ближайшие к заданной. Это особенно важно при работе с большим количеством объектов, так как алгоритм обеспечивает хорошую производительность даже на больших объемах данных (поиск ближайшего соседа имеет сложность (`O(log n)`) в среднем случае).
Вместо написания алгоритма с нуля была использована готовая реализация на языке C. Это решение позволило избежать ошибок при реализации и сосредоточиться на интеграции алгоритма в проект. Реализация KD-Tree была интегрирована в Python с использованием библиотеки `cffi`, что обеспечило высокую производительность и удобство использования.
## Архитектура проекта
Проект был разделен на два основных модуля: frontend и backend, что обеспечило четкое разделение ответственности и упростило поддержку кода.
Основной файл для запуска `main.py`вызывает класс `Core` из фронтендской части, который в свою очередь служит точкой входа в приложение.
### Backend
Весь бекенд реализован на языке C и отвечает за главную логику взаимодействия котов
- ```third-party/kdtree``` — реализация библиотеки для работы с kd-деревьями.
- ```utils-opengl.c``` — содержит функцию, преобразующую позиции котов из системы координат OpenGL в упрощённые одномерные координаты. Каждая точка _{x, y}_ из OpenGL переводится в пиксельные координаты с учётом масштаба.
- ```utils-random.c``` — содержит функцию, генерирующую случайное значение типа double в диапазоне _\[0.0, 1.0\]_.
- ```library.c``` — библиотека, моделирующая поведение "пьяных котов" с использованием kd деревьев.
- ```drunk_cats_configure()``` настраивает глобальные радиусы взаимодействия (драки и шипения).
- ```drunk_cats_calculate_states()``` функция, вычисляющая состояния котов на основе их позиций.
- ```drunk_cats_free_states()``` освобождает память, выделенную для массива состояний.
### Frontend
Frontend делится на две логические части — ```Core``` и ```UI```, а ```constants.py``` содержит настройки для рендеринга
#### Core
Данный модуль управляет визуализацией движения "пьяных котов" с интеграцией бекенда, реализованным на C.
- Инициализируется глобальный логгер
- ```Backend``` описывает интерфейс функций, предоставляемых бекендом:
- ```drunk_cats_configure``` задаёт радиусы взаимодействия для драки и шипения.
- ``` drunk_cats_calculate_states``` рассчитывает состояния котов на основе их позиций.
- ```drunk_cats_free_states``` освобождает память, выделенную для массива состояний.
- ```ArgumentParser``` предоставляет аргументы командной строки.
- ```Core``` основной класс приложения, непосредственно обеспечивающий интеграцию бекенда на C и предоставляющий графический интерфейс.
#### UI
Данный модуль предоставляет взаимодействием с пользовательским интерфейсом, обновляет состояния объектов и рендерит их на экране
- `InputHandler` обрабатывает события ввода пользователя, такие как движение мыши и прокрутка колесика
- `RenderState` содержит состояния рендеринга (points, states, zoom_factor) и т.д
- `PointRenderer` настраивает шейдеры и управляет отображением точек
- `Core` интерфейс, описывает метод `update_states`, который обновляет состояния точек на основе их позиций и размеров окна.
- `UpdateStatesWorker` асинхронно обновляет состояния точек.
- `CanvasState` хранит состояние канваса (zoom_factor, speed_factor и т.д)
## Тестирование
### План тестирования
1. Объект тестирования:
- `drunk_cats_calculate_states` в `backend\library`: единственная доступная извне функция, содержащая в себе логику вычисления состояний котов на основе их позицией на карте. KD-деревья являются сторонним решением и поэтому не нуждаются в тестировании, а остальные функции бэкенда являются инфраструктурными и не содержат в себе бизнес логики
- некоторые функции в `Core`: функции, которые содержат в себе ядро бизнес логики приложения: генерация точек, изменения точек и работа с состояниями
- класс `CanvasState`, инкапсулирующий в себе состояние доски: важен для тестирования, поскольку именно он определяет состояние карты в момент времени
- вся система целиком: тестирование на предмет производительности и отказоустойчивости
2. Цель тестирования
Обеспечить выполнение функциональных требований из первого раздела. Однако из-за нетривиальной архитектуры системы, обусловленной инструментами frontend части, почти не представлялось возможным протестировать все компоненты, поскольку в таком случае стоимость тестирования превысила бы стоимость создания приложения. Поэтому для тестирования были выбраны наиболее критические части и части не содержащие большого количества контекста.
3. Уровни тестирования
Юнит-тестирование, стресс-тесты, приемочное тестирование
4. Критерии тестирования
Тестами покрыты описанные в разделе 1. объекты
### Результаты
Протестированы все объекты из плана тестирования, а сами тесты можно найти в директории `tests/`.
1. `drunk_cats_calculate_states`
Были покрыты все кейсы взаимодействия: один кот (ожидаем, что будет в состоянии покоя), два кота на расстоянии < r0 - ожидаем драку, два кота на расстоянии r0 < r < R0 - ожидаем шипение, три кота - два на расстоянии r < r0 и третий на расстоянии r0 < r R0 от второго - ожидаем драку 1-го и 2-го и шипение 3-го. Также тест для 4 котов, которые разбиты по парам на расстоянии r < r0 (но расстояние между условными компонентами > R0) - ожидаем драку всех 4ых.
Отдельно стоит упомянуть про тестирование шипения: если расстояние между котами r0 <= r < R0, то они должны шипеть с "вероятностью обратно пропорциональной квадрату расстояния между ними". Чтобы предсказуемо протестировать алгоритм, в рамках теста мы всегда считаем такую вероятность равной 1. Для поддержки такого состояния в тестах используется отдельная сборка, которая компилируется с доп флагом `-DTEST` — в алгоритме он как раз определяет "тестовый режим".
Любые другие варианты взаимодействия выводятся из описанных выше.
2. `frontend.core`
Протестированы все ключевые функцию для обновления координат котов. При этом поскольку методы `generate_points` и `generate_deltas` являются статическими, их тестирование оказалось тривиальным. Однако для тестирования функции `update_states` пришлось мокать множество дополнительны полей `Core` - тестировалось также взаимодействие с ними.
Соблюдение большинства требований проверялось в ручном режиме на мшине с описанными выше характеристиками. Для этого приложение предварительно было изолировано посредством того что было единственным работающим в системе. Также машина находилась в "горячем состоянии" для воспроизводимости в реальных условиях.
Каждое тестируемое требование проверялось сначала в изоляции (то есть с параметрами по умолчанию для системы). Затем был сделан один общий ручной тест, проверяющий работу всех требований вместе - а точнее будет сказать, что два теста для режимов "пса" и "слежки", поскольку, как отмечалось ранее, они не совместимы между собой. Отдельное внимание стоит уделить тестированию логгирования - при ручном тестировании не было обнаружено краша системы, поэтому нельзя было проверить тот факт, что при краше фиксируется ошибка. Однако когда обновление успешно выполнялось, мы наблюдали снимок состояния системы в консоли (тестировали при маленьком количестве котов для четкой фиксации этих снимков и на большом чтобы гарантировать, что снимки выполняются)