Skip to content

doc.md

Latest commit

 

History

History
66 lines (51 loc) · 5.92 KB

doc.md

File metadata and controls

66 lines (51 loc) · 5.92 KB

Техническая документация

Инструменты

  • Для реализации алгоритма и визуализации симуляции использовалась библиотека taichi
    • Позволяет компилировать python-подобный код в нативный
    • Автоматически поддерживает fork–join параллелизм (все внешние циклы for параллелятся)
    • Предоставляет из коробки инструменты для визуализации
  • Для управления зависимостями использовался пакетный менеджер rye

Описание архитектуры

Библиотека taichi накладывает ряд ограничений, из-за которых было удобно воспринимать один модуль-файл, как один класс. Кроме того, для ускорения работы алгоритма, вся динамическая память выделяется заранее на этапе конфигурации и потом переиспользуется.

  • __main__.py -- это основной файл для запуска.
    • тут выделяется массив "котов", который используется потом в алгоритме и при отрисовке
      cats = Cat.field(shape=(cfg.CATS_N,))
  • cat.py -- содержит в себе, dataclass Cat. Он описывает передвижение, а также изменение состояния одного "кота".
    • перед использованием надо вызвать init_cat_env(), для инициализации модуля
  • grid.py -- здесь представлен сам алгоритм
    • перед использованием надо вызвать setup_grid(), для инициализации модуля
  • config.py -- это конфигурация запуска (из-за отсутствия интерактивного UI изменять параметры запуска можно только при перезагрузке всего приложения)

Сама архитектура довольно проста:

  • В __main__.py происходит вся инициализация (алгоритма и "котов"), а также исполнение основного цикла:
    • move_cats(cats) -- передвижение котов
    • update_statuses(cats) -- пересчет состояний (запуск алгоритма)
    • GUI.circles(cats) -- отрисовка "котов" (в виде окружностей)
    • GUI.show() -- отображение одного кадра

cats -- заранее выделенный массив "котов"

Описание алгоритма

Алгоритм основывается на том, что все пространство разбивается на равные ячейки.

  • На каждой итерации после перемещения "котов" на новые позиции происходит вызов функции update_statuses, которая проходится по всем "котам" (окружностям) и обновляет их состояние.
  • Алгоритм смотрит в какую ячейку попадает рассматриваемый "кот". И проверяет расстояние до всех "котов" расположенных в соседних ячейках (т.е. рассматривается 9 ячеек).
  • Этого достаточно, потому что высота и ширина ячейки равняется 2*RADIUS_1.

Важно заметить, что в худшем случае, когда RADIUS_1 будет достаточно большим, весь алгоритм будет работать за O(n^2), что обусловлено нахождением всех "котов" в одной ячейке (приходится рассматривать всех со всеми)

Алгоритм решения вдохновлен этой статьей.

Тестирование

  • Тестирование алгоритма ячеек проводилось путем сравнения его результатов с "наивным" решением, основанным на методе полного перебора. "Наивное" решение подразумевает исчерпывающий поиск соседних узлов ("котов") для каждого элемента набора данных путем последовательного обхода всех имеющихся узлов ("котов").

primitive_update_states() наивное решение

  • В качестве тестовых данных использовались наборы, сгенерированные с применением различных конфигурационных параметров. Координаты узлов в рамках каждого тестового набора определялись посредством генератора псевдослучайных чисел, что обеспечивало репрезентативность и вариативность условий эксперимента.

  • Также проведено юнит-тестирование функций перемещения: протестировано, что функции не нарушают допустимый радиус перемещения.