infected

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[english, russian]{babel}
\usepackage{pgfplots}

\begin{document}
    %Титульный лист
    \begin{titlepage}
        \centering
        {\scshape\LARGE СУНЦ МГУ \par}
        \vspace{1cm}
        {\scshape\Large Проектная работа\par}
        \vspace{1.5cm}
        {\huge\bfseries Игра "Infection"\par}
        \vspace{2cm}
        {\Large\itshape Искандаров Лев\par}
        \vfill

        {\large Москва, 2018 г.\par}
    \end{titlepage}

    %Содержание
    \tableofcontents
    \newpage

    %Контент
    \section{Постановка задачи}

    \subsection{Общее описание}

    \paragraph{Задача} Создать многопользовательскую браузерную игру в стиле RTS-платформера.

    \paragraph{Цель игры} Две команды с помощью различных построек и улучшений должны уничтожить друг друга. Выигрывает выжившая сторона.

    \paragraph{Правила игры} Каждый игрок, может изменять мир и строить различные постройки, дающие ему ресурсы или наносящие другой стороне урон.

    \paragraph{Требования к реализации} Игра должна быть реализована на языке JavaScript с использованием библиотек по необходимости.

    \subsection{Описание игровых процессов}

    Необходимые реализации:
    \begin{itemize}
    \item Клиент-серверная архитектура
    \item Физический движок
    \item Оптимизированное хранение и передача игрового мира
    \item Случайный генератор мира
    \item Сторона людей
    \item Сторона вируса
    \item Пользовательский интерфейс
    \end{itemize}

    \subsection{Описание действий, выполняемых игроком}

    \begin{itemize}
    \item Сначала, игроку следует зарегистрироваться, войти в комнату, выбрать сторону и нажать "готов" и ждать начала игры
    \item Далее, игрок может перемещаться по миру, ставить и удалять блоки
    \end{itemize}

    \section{Используемые модели и технологии}

    \subsection{Используемые технологии}

    \begin{itemize}
    \item \textbf{Node.js} --- программная платформа для сервера
    \item \textbf{PixiJS} --- графическая библиотека для отрисовки
    \item \textbf{Socket.IO} --- библиотека для клиент-серверного общения
    \item \textbf{Bootstrap} --- библиотека для упрощения работы с HTML и создания GUI
    \item \textbf{JSON Web Token} --- библиотека для создания зашифрованного ключа-идентификатора пользователя
    \item Несколько вспомогательных библиотек
    \end{itemize}

    \subsection{Используемые модели}

    Сервер использует собственный физический движок (\ref{section:physics}), генерацию мира с помощью шумов (\ref{section:worldgen}). Так же, используются методы оптимизации и реализована клиент-серверная архитектура: например разбиение мира на чанки для ускорения рендера и передачи данных (\ref{section:optimize}).

    \subsubsection{Физический движок}
    \label{section:physics}

    \paragraph*{Два объекта.}
    Допустим, есть два физических объекта $a$ и $b$ и время между двумя игровыми тиками $dt$. Мы хотим понять, столкнутся ли они за это время, и если да, что-то с этим сделать.

    Для начала, определим объект как прямоугольник, со сторонами, параллельными координатной сеткой, заданный левой верхней точкой и его размерами, а так же скоростью.

    Возвращать наша функция будет время, через которое два объекта столкнутся (или $dt + 1$, если за время $dt$ они не столкнутся) и нормаль ко второму объекту, которая характеризует ту сторону, с которой произошло столкновение.

    Воспользуемся теоремой о разделяющей оси, упрощенной для нашего случая: найдем минимальную и максимальную проекцию на координатные оси для каждого объекта. Если по хотя бы одной из осей мы можем найти точку, которая лежит между двумя объектами, то в данный момент столкновения нет. Иначе, объект находится внутри другого.

    Но это лишь проверка на пересечение. Усовершенствуем алгоритм: найдем расстояние между этими крайними точками, поделим на проекцию скорости на данную ось и получим время, через которое объекты столкнутся по данной оси. Выберем из двух времен максимум и это будет время столкновения. Нужно лишь проверить, что по другой оси в это время мы все еще пересекаемся, а не вышли за объект. Время найдено, а нормаль к стороне определяется довольно просто исходя из знаков скорости и оси, по которой происходит столкновение.

    Остается только реакция на столкновение. Подвинем объект на то время, которое вернула данная функция. Если столкновение было, то изменилась скорость, а именно по той оси, по которой произошло столкновение она стала равна 0 - эта ось задается вектором нормали. Изменим скорость и подвинем объект на оставшееся время.

    \paragraph*{Обработка одного объекта с массивом преград.}
    Мы хотим за линейное время обработать один подвижный объект и массив неподвижных преград (например, игрок и объекты игрового мира).

    Пройдемся по всем объектам и найдем первый объект, с которым произойдет столкновение. Произведем обычную реакцию, за исключением того, что двигать на оставшееся время просто так не будем. У нас изменилась скорость, изменилось время, но задача осталась та же самая. Теперь, будем делать тоже самое, пока скорость и оставшееся время не будет равно 0.

    Заметим, что если при столкновении объектов скорость никак не изменяется извне (например, подъем игрока, если он столкнулся с шипами), то данный алгоритм будет проходится не более 2-х раз: если столкновений нет, то мы просто двигаем объект все оставшееся время. Иначе, после каждого из столкновений, по одной из осей скорость становится равной 0. Так как по этой же оси мы уже не сможем столкнуться еще раз, так как мы никуда не двигаемся, то остается только движение по второй оси, и, либо мы просто движемся оставшееся время, либо мы сталкиваемся по ней, и скорость равна 0, т.е. алгоритм прекращает свою работу.

    \subsubsection{Генерация мира с помощью шумов}
    \label{section:worldgen}

    \paragraph*{Шум Перлина.}
    По сути, мы хотим сгенерировать сглаженный набор случайных величин. Для это воспользуемся алгоритмом Перлина. Рассмотрим его двумерную реализацию.

    Создадим двумерную сетку с целыми координатами. В узлы сетки запишем единичный вектор случайного направления.

    Теперь, есть точка с координатами $(x, y)$ и мы хотим получить для нее значение шума $\left[-1, 1\right]$. Найдем единичный квадрат (границы сетки), в котором лежит наша точка (т.е. по сути, отбросим дробную часть координат). Найдем векторы из вершин этого квадрата в нашу точку. Теперь, есть 4 пары по два вектора: для каждой вершины есть два вектора: записанный в вершине и вектор до точки. Найдем для каждой вершины скалярное произведение этих двух векторов. Получим 4 числа.

    Далее, линейно интерполируем попарно, например, верхние и нижние числа, а затем получившиеся два. Это и будет результат функции шума.

    \paragraph*{Дополнения.}

    \begin{itemize}
        \item Вместо генерации случайной сетки заведем 256 векторов случайного направления, создадим массив перестановки из 256 элементов, с помощью математических преобразований будем получать для каждой вершины псевдослучайный элемент этой перестановки, т.е. случайный вектор.
        \item Вместо 256 случайных векторов возьмем 12, описанных Перлином (в каждой плоскости вектор в углы плоскости).
        \item После подсчета каждого скалярного произведения, возьмем от него функцию сглаживания: например, smootherstep $= 6x^5-15x^4+10x^3$. Это примерно прямая, которая в окрестности 0 ближе к 0, а в окрестности 1 ближе к 1.
    \end{itemize}

    \begin{tikzpicture}
    \begin{axis}[
    xlabel=$x$,
    ylabel={$smootherstep$}
    ]
    \addplot [draw=blue][domain=0:1]{x};
    \addplot [domain=0:1]{6*x^5-15*x^4+10*x^3};
    \end{axis}
    \end{tikzpicture}

    \paragraph*{Генерация мира}
    Используя функцию от трех координат, где последняя (и, если нужно 1 измерение - последние две) является зерном можно сгенерировать карту.

    Сначала, генерируется карта высот (одномерный случай): простой проход по всем столбцам и генерация для них функции шума, которая будет высотой в данной точке.

    Затем, в этих высотах я ставлю блок травы, и под ним случайное (2-4) блока земли. Так же, случайно расставляю блоки травы поверх блока травы.

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

    В конце происходит добавление деревьев: заводится переменная "сколько блоков назад было дерево", и, если текущее случайное число меньше этой переменной, то поверх блока травы устанавливается блок дерева.

    \subsubsection{Оптимизации и клиент-серверная архитектура}
    \label{section:optimize}

    \paragraph*{Деление мира на чанки}
    В идее моей игры нет необходимости хранить бесконечный мир - по задумке, мир должен быть ограниченным, но большим. Хранить в памяти придется весь мир, но передавать и выводить на экран стоит только то, что игрок может видеть. Для этого, весь мир делится на чанки: области $8*8$ блоков. Таким образом, на клиентской стороне выводится на экран только то, что должно выводится, а так же сервер может отправить каждому игроку информацию только о той части карты, в которой он может находится.

    \paragraph*{Защита от читеров}
    Т.к. игра по сети Интернет, то нужно было реализовать защиту от читеров. Единственный способ: обсчитывать всю информацию на сервере, а клиент только отправляет ввод и получает информацию, необходимую для вывода.

    \paragraph*{Переподключение}
    Во время игры могут быть проблемы с соединением, а так же перезагрузка страницы браузера. Нужно сохранять информацию об игроке, чтобы можно было сразу вернуть его в игру. Для этого, каждого игрока нужно идентифицировать: проблема заключается в том, что о клиенте мы знаем только его ip-адрес, никнейм и номер подключения socket.io.

    Для решения данной проблемы используется библиотека JSON Web Token. Создается зашифрованный токен с информацией об игроке - никнейм и номер подключения. После этого, этот токен отсылается клиенту, который должен сохранить его (в cookie). Далее, любое действие игрока требует от него токен, по которому он и идентифицируется. Так как стандартный браузер должен сохранять cookie между сессиями, то после потери соединения клиент снова отсылает токен, и сервер понимает, что этот игрок уже зарегистрирован и подключает его обратно.

    Раз в 30 минут сервер удаляет всех игроков, которые покинули сервер более 30 минут назад.

    \subsection{Планы на будущее}

    Доделать геймплей:

    \begin{itemize}
    \item Возможность строить здания
    \item Здания генераторов ресурсов
    \item Здания поля, наносящего урон
    \item Здания, создающие юнитов
    \end{itemize}

    \section{Руководство программиста}
    \subsection{Сервер}
    \subsubsection{Сетевая часть}
    \paragraph*{Подключение}
    Основные функции, связанные с сетевой частью описаны в событии \textbf{connection}.

    \paragraph*{Запрос токена}
    При подключении нового клиента с серверу, сервер просит клиента отослать ему токен. Если клиент отсылает его, то сервер проверяет актуальность и корректность токена, и если все хорошо, возвращает в сессию.

    \paragraph*{Регистрация}
    Данное событие отвечает на запрос регистрирования нового клиента. Если данное подключение уже зарегистрировано, игнорирует запрос, иначе создает новую запись и отсылает клиенту его токен.

   \paragraph*{Операции с комнатами}
   События \textbf{joinRoom}, \textbf{leaveRoom}, \textbf{joinSide}, \textbf{ready} отвечают за перемещение по комнатам, смену сторон и кнопки "готов". Клиент должен отсылать его токен вместе с остальной информацией, иначе запрос будет проигнорирован.

   \paragraph*{Запрос комнат}
   Событие \textbf{requestRooms} отсылает клиенту, который отправил данный запрос, список комнат на сервере.

   \paragraph*{Отключение}
   При отключении клиента сервер помечает игрока как покинувшего и записывает время. Так же, если игра не началась, а клиент в комнате, удаляет его из комнаты.

   \subsubsection{Сетевая часть игры}
   \paragraph*{Ввод}
   События \textbf{keyboard} и \textbf{mouse} обрабатывают ввод игрока.

   \paragraph*{Запрос карты}
   Событие \textbf{requestChunk} отсылает клиенту, который отправил данный запрос, чанк, только если клиент может этот чанк увидеть.

   \paragraph*{Передача игровых данных клиенту}
   Передача данных клиенту происходит в функции \textbf{updateGame} класса \textbf{Room}

   \subsubsection{Игровая часть}
   Описание основных классов игры

   \paragraph*{Vector2}
   Класс физического двумерного вектора

   \paragraph*{NetworkPrimitive}
   Класс, ответственный за все сетевое взаимодействие. Хранит всю необходимую о клиенте информацию.

   \paragraph*{PhysicsPrimitive}
   Физический объект, заданный прямоугольником со скоростью. Имеет функции коллизии.

   \paragraph*{Player}
   Класс, ответственный за сторону людей. Основная функция \textbf{tickUpdate} обновляет все внутренние состояния игрока.

   \paragraph*{Virus}
   Класс, ответственный за сторону вируса. Основная функция \textbf{tickUpdate} обновляет все внутренние состояния вируса.

   \paragraph*{Block}
   Класс, ответственный за хранение информации о игровом блоке. Функция \textbf{update} обновляет блок (разрушение блока). Функция \textbf{updateMultiTexture} обновляет информацию о том, какую текстуру следует поставить для блоков, у которых есть несколько спрайтов.

   \paragraph*{Chunk}
   Класс-контейнер, в основном служит как промежуточный слой между картой и блоком.

   \paragraph*{GameMap}
   Класс, хранящий игровую карту, а так же интерфейс, через который следует работать с игровым миром.

   \paragraph*{Room}
   Класс, ответственный за отдельную сессию. Каждая комната должна иметь свой объект данного класса. Имеет две стадии: \textbf{preGame} и \textbf{game} - лобби и игровая стадия соответственно. Функции \textbf{update} нужной стадии обновляют состояние комнаты. \newline

   Описание основных функций

   \paragraph*{loadFiles}
   Перед стартом основных функций, сервер должен загрузить некоторые файлы: информацию о блоках.

   \paragraph*{setup}
   Запускает сервер: создает комнаты, запускает главный цикл.

   \paragraph*{tick}
   Вызывает функцию обновления для каждой комнаты.

   \subsection{Клиент}
   \subsubsection{Серверная часть}

   Описана в файле client.js

   \paragraph*{Ошибка регистрации}
   Событие происходит, когда веденный никнейм или отправленный токен некорректные.

   \paragraph*{Удачная регистрация}
   Если клиент успешно зарегистрировался, то нужно поменять формы GUI.

   \paragraph*{Комнаты}
   Сервер прислал список комнат, следует обновить их.

   \paragraph*{Обновление}
   Информация о игровом состоянии

   \paragraph*{Обновление вируса}
   Информация о игровом состоянии для стороны вируса

   \paragraph*{Карта}
   Сервер прислал чанк карты

   \paragraph*{Обновление лобби}
   Находясь в лобби, произошло обновление

   \paragraph*{Начало игры}
   Началась игра, следует убрать все GUI, связанные с лобби, включить рендер игры и показать инвентарь

   \paragraph*{Конец игры}
   Игра закончилась, следует показать все GUI и убрать рендер игры.

   \subsubsection{Игровая часть}

   Основные классы остаются те же, но некоторые функции убраны, т.к. не используются.
   Появился один новый класс

   \paragraph*{GraphicsPrimitive}
   Класс, упрощающий работу с графическим движком. \newline

   Описание основных функций

   \paragraph*{setup}
   Функция, инициализирующая графический движок

   \paragraph*{frame}
   Функция, отвечающая за показ одного игрового кадра. Так же обновляет игровые данные.

   \paragraph*{keyboard}
   Функция, отвечающая за обработку нажатия одной клавиши.

   \section{Руководство пользователя}
   \subsection{Возможности}
   При заходе на сайт игроку следует зарегистрироваться, выбрать комнату, нажать кнопку "Готов". Далее, игрок может перемещаться по миру с помощью кнопок WASD, ломать блоки в пределах своей досягаемости на ЛКМ и ставить на ПКМ. При уничтожении блоков игроку даются ресурсы, при установке - тратятся.

   \subsection{Описание ресурсов}
   \paragraph*{Рабочие}
   Для любого действия у игрока должен быть свободен хотя бы 1 рабочий, который ставится на данную задачу.

   \paragraph*{Энергия}
   Аналогично, для любого действия у игрока должна быть энергия, чтобы его совершить.

   \paragraph*{Камень}
   Основной ресурс для построек. Является дешевым, нужен для низкоуровневых построек.

   \paragraph*{Железо}
   Дополнительный ресурс для построек. Является дорогим, нужен для высокоуровневых построек и улучшений.

   \subsection{Сторона людей}
   Весь геймплей строится вокруг персонажа игрока. С помощью клавиш, игрок может перемещать своего персонажа по миру. Область досягаемости определяется как небольшая зона вокруг персонажа.

   \subsection{Сторона вируса}
   Весь геймплей строится вокруг ядра и организма под землей. У каждого игрока есть свой центральный блок - блок ядра. При его уничтожении, игрок проигрывает. Камера может перемещаться в такой области, что недалеко от центра экрана был бы хотя бы один блок вируса. Область досягаемости определяется как все блоки вируса и соседние с ними.

    \begin{thebibliography}{9}

    \bibitem{1}
   Англоязычная документация PIXI.js
\\\texttt{http://pixijs.download/dev/docs/PIXI.html}

    \bibitem{2}
    Learning PIXI: A step-by-step introduction to making games and interactive
media with the Pixi rendering engine.
\\\texttt{https://github.com/kittykatattack/learningPixi}

    \bibitem{3}
    Англоязычная документация по socket.io
    \\\texttt{https://socket.io/docs/}

    \bibitem{4}
    Шум Перлина / Хабрахабр
    \\\texttt{https://habrahabr.ru/post/342906/}

    \bibitem{5}
    Perlin Noise / Scratchapixel
    \\\texttt{https://www.gamedev.net/articles/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/}

    \bibitem{6}
    Swept AABB Collision Detection and Response
    \\\texttt{https://www.gamedev.net/articles/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/}

   \end{thebibliography}

\end{document}