\documentclass[]{article}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage[polish]{babel}
\usepackage[margin=1.25in]{geometry}
\usepackage{titling}
\usepackage{pdfpages}
\usepackage{float}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage{enumerate}
\usepackage{lmodern}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{wrapfig}
\usepackage{braket}
\usepackage{subcaption}
\usepackage{multirow}
\usepackage{etoolbox}
\usepackage{color}
\usepackage{pgfkeys}
\usepackage{siunitx}

\pgfplotsset{compat=1.15}
\usepgfplotslibrary{groupplots}
\usepgfplotslibrary{external} 

\usetikzlibrary{decorations.pathmorphing, arrows.meta, positioning}
\usetikzlibrary{shapes.geometric, arrows, intersections}

\newcommand{\areyousure}[1]{{\color{red}\textbf{???} #1 \textbf{???}}}
\newcommand{\todo}[1]{{\color{blue}\textbf{TODO:} #1}}

\makeatletter

\newenvironment{packet}{%
    \def\byte{*8mm}%

    \newrobustcmd{\member}[3][]{%
        \node[packet, minimum width=##3\byte] (##2) {##2};
        \node[below=of ##2] {##3};
        \node[above=of ##2.north, text depth=0pt] {##1};
        
        \tikzstyle{packet}+=[right=of ##2];
    }%

    \newrobustcmd{\preamble}[1][15]{%
        \node[packet, minimum width=2\byte, dashed] (Preamble) {$\cdots$};
        \node[below=of Preamble] {##1};
        \node[above=of Preamble.north] {Preambuła};
        
        \tikzstyle{packet}+=[right=of Preamble];
    }%

    \begin{tikzpicture}[%
        packet/.style={draw, auto, align=center, minimum height=7mm, font=\ttfamily, right=of start},
        optional/.style={dotted},
        every node/.style={text depth=0pt},
        node distance=0,
        x=8mm, y=1.5cm
    ]%
    \node (start) {};
}{%
    \end{tikzpicture}%
    \let\byte\undefined
    \let\member\undefined
    \let\preamble\undefined
}

\makeatother

% opening
\title{Przetwarzanie Rozproszone - Projekt}
\author{\protect\begin{tabular}{ll|l}
    Weronika Czarnecka   & \textit{165600} & \multirow{4}{*}{\shortstack[l]{Informatyka 2016/2017 \\ Semestr IV, gr. 1}} \tabularnewline
    Anna Piliczewska     & \textit{165436} & \tabularnewline
    Maciej Borzyszkowski & \textit{165407} & \tabularnewline
    Kacper Donat         & \textit{165581} & %
\protect\end{tabular}}

\floatname{algorithm}{Program}

\begin{document}

\maketitle

\section{Zasady rozgrywki}
Gracze poruszają się po wspólnej planszy czołgami strzelając do siebie i starając się zniszczyć. Każdy gracz kontroluje
tylko i wyłącznie swój czołg.

\subsection{Przechowywany stan}
Aktualny stan rozgrywki $S$ jest determinowany przez aktualne obiekty na mapie. Każda aktualizacja ze strony klienta,
wpływająca na stan $S$ powoduje zwiększenie licznika stanu o 1. Ze względu na trudność synchronizacji kolejności
aktualizacji (np. stan 2 klienta A może być stanem 3 dla klienta B i odwrotnie) zdecydowano się, że każdy klient
przechowuje ilość odebranych aktualizacji stanu od każdego klienta osobno.

Dodatkowo, każdy obiekt na mapie zawiera swój własny stan, zależny od typu obiektu. Przykładowo dla czołgu może to być
pozycja (\texttt{vec2}), kąt (\texttt{double}) oraz ich pierwsza oraz druga pochodna (w celach predykcji). 

\section{Wykorzystane technologie}
\begin{itemize}
    \item SFML.net           - obsługa grafiki oraz wejścia od użytkownika 
    \item System.Threading   - wątki 
    \item System.Net.Sockets - obsługa sieci
\end{itemize}

\section{Proponowana Architektura}
Z założenia, rozgrywka ma odbywać się w czasie rzeczywistym zatem wykorzystanie protokołu TCP mogłoby
wprowadzać niepotrzebne opóźnienia, wynikające z niepotrzebnych retransmisji pakietów. 

Komunikacja będzie odbywała się zatem za pomocą datagramów UDP, które pozwalają na szybszą - acz mniej dokładną
transmisję informacji pomiędzy klientami. W wypadku normalnej gry jednak strata części pakietów jest jak
najbardziej akceptowalna i nie wpłynie na rozgrywkę w znaczący sposób.

W projekcie przyjęto architekturę klient-klient, tj. nie występuje żaden serwer stanowiący źródło prawdy dla rozgrywki.
Zamiast tego jeden z klientów zawsze będzie miał status \textit{mastera}. Poprawnym stanem rozgrywki z definicji jest
stan symulacji \textit{mastera}. \textit{Masterem} zawsze jest klient o najmniejszym \texttt{ClientId}, tj. klient,
który podłączył się najwcześniej. Takie podejście zapewnia rozwiązanie sytuacji, w której aktualny \textit{master} się
rozłączy bez konieczności przeprowadzania negocjacji.

\begin{figure}[H]
    \centering

    \begin{tikzpicture}[
        client/.style = { circle, draw },
        master/.style = { very thick },
        node distance=2cm
     ]
        \node[client, master] (C1) {$C_1$};
        \node[client, right=of C1] (C2) {$C_2$};
        \node[client, below=of C2] (C3) {$C_3$};
        \node[client, left=of C3] (C4) {$C_4$};

        \foreach \u/\v in {C1/C2,C1/C3,C1/C4,C2/C3,C2/C4,C3/C4} \draw[<->] (\u) -- (\v); 
    \end{tikzpicture}

    \caption{Proponowana architektura sieciowa}
\end{figure}

Dodatkowo, przyjmuje się zasadę, że każdy klient jest odpowiedzialny za swoją część symulacji, dla której stanowi źródło
prawdy. W praktyce oznacza to, że każdy gracz wysyła tylko i wyłącznie informacje o zmianach rzeczy, na które on ma
wpływ - np.  pozycję własnego czołgu, czy wystrzelenie pocisku. W gestii innych klientów jest przetworzyć te informacje
i zsynchronizować się. Przewidziano również obiekty o zachowaniu deterministycznym, które każdy klient może aktualizować
samodzielnie w ramach swojej symulacji.

Takie podejście zapewnia brak konfliktu o zasoby, ponieważ każdy obiekt jest modyfikowany wyłącznie przez jedną osobę,
zatem nigdy nie nastąpi konflikt. Nie występuje również problem odczytywania zmienionych danych ponieważ wyświetlanie
oraz aktualizacja stanu gry odbywają się w ramach jednego wątku.

Ze względu na możliwość zgubienia niektórych pakietów, oraz chęć uniknięcia skokowej aktualizacji rozgrywki po stronie
każdego klienta następuje predykcja zachowań innych graczy. W wypadku otrzymania pakietu aktualizującego stan gracza,
predykcja jest odrzucana i wykorzystane są otrzymane dane.

Ze względu na niedoskonałość mechanizmu predykcji, predykcje nie mogą modyfikować stanu gry w sposób nieodwracalny, tj
np. predykcja nie może usunąć obiektu z mapy - może go natomiast oznaczyć jako prawdopodobnie usunięty, co za tym idzie
nie będzie on wyświetlany ani predykowany dalej (z punktu widzenia gracza zostanie usunięty) - w takiej sytuacji
przywrócenie obiektu w wypadku błędnej predykcji wciąż będzie możliwe.

Każdy klient będzie obsługiwany przez 4 osobne wątki, których kompetencje nie kolidują ze sobą:
\begin{enumerate}
    \item Aktualizacja, predykcja oraz renderowanie stanu symulacji  \label{thread:render}
    \item Input z sieci (obiór pakietów, kolejkowanie) \label{input:net}
    \item Input użytkownika (odczyt klawiatury itd.)   \label{input:user}
    \item Output sieciowy (wysyłanie pakietów, retransmisje) \label{output:net}
\end{enumerate}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=1cm]
        \node[label=below:{Wątek \ref{thread:render}}] (thread-render) {
            \begin{tikzpicture}[every node/.style={align=center}, node distance=1cm]
                \node[draw] (predict) {Przewidywania};
                \node[draw, below=of predict] (update)  {Aktualizacja};
                \node[draw, below=of update] (render)  {Wyświetlanie};
                \draw[->] (predict.west) edge [bend right] (update.west) 
                    (update.west) edge [bend right] (render.west)
                    (render.east) edge [bend right] (predict.east);
            \end{tikzpicture}
        };

        \node[label=below:{Wątek \ref{input:net} i \ref{input:user}}, right=of thread-render] (thread-input) {
            \begin{tikzpicture}[every node/.style={align=center}, node distance=1cm]
                \node[draw] (udp) {Nasłuchiwanie UDP};
                \draw[->] (udp) edge [loop above] (udp);

                \node[draw, below=of udp] (user) {Nasłuchiwanie HID};
                \draw[->] (user) edge [loop above] (user);
            \end{tikzpicture}
        };

        \node[label=below:{Wątek \ref{output:net}}, left=of thread-render] (thread-output) {
            \begin{tikzpicture}[every node/.style={align=center}, node distance=1cm]
                \node[draw] (listen) {Wysyłka pakietów};
                \draw[->] (listen) edge [loop above] (listen);
            \end{tikzpicture}
        };

        \node[below=of thread-render] (queue-actions) {Kolejka akcji};
        \node[above=of thread-render] (queue-output) {Kolejka wysyłki};

        \draw[<->, double] (thread-render) edge (queue-actions)
                   (thread-input) edge (queue-actions);

        \draw[<->, double] 
            (thread-output) edge (queue-output)
            (thread-input) edge (queue-output);
    \end{tikzpicture}

\end{figure}

Wątki \ref{input:net} oraz \ref{input:user} będą umieszczały akcje do wykonania w jednej kolejce akcji, zatem kolejka ta
musi być \textit{thread-safe} i udostępniać atomowe metody \texttt{enqueue} i \texttt{dequeue}, gwarantujące że stan
kolejki nie zostanie uszkodzony, tj. żadna akcja nie zostanie wykonana 2-krotnie ani żadna nie zostanie zgubiona.
Zostanie to osiągnięte poprzez ustawienie Mutexa\footnote{https://msdn.microsoft.com/en-us/library/system.threading.mutex(v=vs.110).aspx}
w metodach.

Zakładamy, że akcje użytkownika muszą zostać umieszczone na kolejce akcji natychmiastowo, zatem nie ma potrzeby
synchronizacji z siecią. Co za tym idzie, dostęp do kolejki pakietów (potrzebnej ze względu na możliwość otrzymania
pakietów w nieodpowiedniej kolejności) i jej obsługa będzie w całości po stronie wątku \ref{input:net} - czyli problem
wyścigów nie następuje. 

Poprzez identyczną kolejkę będzie obsługiwana wysyłka pakietów, stworzona w celu skomunikowania wątków \ref{input:user}
oraz \ref{output:net}. Dodatkowo w wątku \ref{output:net} będzie działać samodzielna kolejka odpowiadająca za
retransmisję pakietów.

Niektóre pakiety zmieniają stan rozgrywki (np. śmierć, wystrzelenie pocisku), a co za tym idzie muszą zostać
przetworzone przez wszystkich klientów w zbliżonej kolejności i w miarę jednakowym czasie (nie ma możliwości
zagwarantowania idealnej synchronizacji). W tym celu wprowadzony zostanie system numerowania kolejnych pakietów, a każdy
pakiet będzie zawierał informację na temat stanu od którego ,,zależy'' - tj. numeru ostatniej aktualizacji.

\subsection{Protokół}
Protokół opiera się o wysyłanie datagramów UDP między wszystkimi klientami. Ze względu na specyfikę UDP (brak gwarancji
dotarcia pakietów, brak gwarancji kolejności, brak gwarancji poprawności) przyjmuje się następujące założenia:
\begin{itemize}
    \item nie wszystkie pakiety są ważne, niektóre można pominąć
    \item wszystkie pakiety aby zostać przetworzone muszą dojść w całości poprawnie
    \item pakiety są numerowane
    \item pakiety mogą wymagać konkretnego poziomu stanu gry
\end{itemize}

Ze względu na konieczność szybkiego przesyłania informacji pomiędzy klientami, zaprojektowany protokół jest protokołem
binarnym, o konstrukcji pakietu widocznej poniżej.

\begin{figure}[H]
    \center
    \begin{packet}
        \member{CRC16$_p$}{2}
        \member{Type}{1}
        \member{Size}{2}
        \member{ClientId}{2}
        \member{State}{4}
        \member{PacketId}{4}
        \node[packet, dashed, right=of PacketId, text width=15mm] {CRC16$_d$};
    \end{packet}

    \caption{Preambuła pakietu} 
\end{figure}

\begin{table}[H]
    \centering
    \begin{tabular}{l|l|l}
        \textbf{Właściwość} & \textbf{Typ} & \textbf{Opis} \\ \hline
        \texttt{CRC16$_p$} & \texttt{int16} & Suma kontrolna danych w preambule \\
        \texttt{Type} & \texttt{uint8}  & Rodzaj wysyłanego pakietu \\ 
        \texttt{Size} & \texttt{uint16} & Rozmiar wysłanych danych, razem z pierwszym bajtem \\
        \texttt{ClientId} & \texttt{uint16} & Identyfikator klienta \\
        \texttt{State} & \texttt{uint32} & Wymagany stan gry do przetworzenia pakietu \\
        \texttt{PacketId} & \texttt{uint32} & Timestamp oryginalnego wysłania pakietu \\ \hline
        \texttt{CRC16$_d$} & \texttt{int16} & Suma kontrolna danych pakietu (o ile jakieś są) \\
    \end{tabular}
\end{table}

Dla ułatwienia implementacji przyjmuje się, że dla pakietów, których najstarszy bit typu (\texttt{Type \& 0x80}) jest
ustawiony na 1 nie zachodzi potrzeba retransmisji - czyli są to pakiety mało istotne bądź szybko przedawniające się.
Przykładem takiego pakietu może być aktualizacja pozycji gracza - nie ma potrzeby retransmisji ponieważ prawdopodobnie i
tak w drodze jest następny pakiet z nowszą pozycją.

W celu zapewnienia poprawności transmisji, każdy pakiet poprzedzany jest 16-bitową sumą kontrolną \texttt{CRC16},
pozwalającą upewnić się, że dane zostały odebrane poprawnie. Suma kontrolna liczona jest ze wszystkich składowych
pakietu poczynając od \texttt{Type} włącznie. Dodatkowo, jeżeli pakiet potrzebuje dodatkowych danych prócz preambuły to
dane te zawierają własną sumę kontrolną \texttt{CRC16}. Rozgraniczenie to wprowadzono, aby uniknąć sytuacji, w której w
preambule zostałoby uszkodzone pole \texttt{Size} uniemożliwiając pobranie całego pakietu poprawnie.

W wypadku niezgodności przesłanej sumy kontrolnej z sumą wyliczoną po stronie odbierającego, odbierający wysyła pakiet
\texttt{RET = 0x81}. Dla pakietów mało ważnych nie zachodzi potrzeba retransmisji. 

Aby upewnić się, że transmisja ważnego pakietu się powiodła, każdy klient musi odpowiedzieć pakietem \texttt{ACK}
(\texttt{Type = 0x80}). W wypadku, gdyby odpowiedź \texttt{ACK} nie dotarła w ciągu $t\ \si{ms}$ pakiet zostaje
wysłany ponownie. 

W przypadku wielokrotnego otrzymania pakietu o tym samym \texttt{PacketId} (np. w wypadku automatycznej retransmisji),
każdorazowo należy potwierdzić jego otrzymanie odpowiedzią \texttt{ACK} jednak akcja związana z tym pakietem powinna
zostać wykonana tylko raz. 

Pakiety \texttt{ACK} oraz \texttt{RET} w polu \texttt{PacketId} zawierają id pakietu, którego dotyczą. Dodatkowo ze 
wzgledu na to, że \texttt{ACK} nie jest bezpośrednio związany z rozgrywką, wymagany stan (\texttt{Sate}) zawsze wynosi 
0.

\begin{figure}[H]
    \center
    \begin{packet}
        \member{CRC16$_p$}{2}
        \member[Type]{0x80}{1}
        \member[Size]{15}{2}
        \member{ClientId}{2}
        \member[State]{0}{4}
        \member{PacketId}{4}
    \end{packet}

    \caption{Pakiet \texttt{ACK}} 
\end{figure}

W momencie kiedy po $n$-tej retransmisji pakietu z rzędu nie otrzymamy potwierdzenia \texttt{ACK} uznajemy, że nastąpiło
zerwanie połączenia ze strony tego gracza - dodatkowo, jeżeli jakimś cudem wszyscy pozostali gracze stracili połączenie
zakładamy, że to problem jest po naszej stronie.

W celu sprawdzenia poprawności połączenia z danym graczem można również wysłać pakiet \texttt{PING = 0x00}, za poprawny
\textit{pong} uznajemy pakiet \texttt{ACK}.

\subsection{Zestawienie połączeń}
Ze względu na to, że port na którym nasłuchują klienci nie jest deterministyczny istnieje konieczność wprowadzania
scentralizowanego \textit{lobby} pozwalającego na wymianę tych informacji pomiędzy klientami. Jedynym zadaniem
\textit{lobby} jest przechowywanie informacji o graczach chcących wspólnie zagrać, zatem nie zachodzi potrzeba szybkiego
działania. 

Stąd przyjęto, że do realizacji lobby zostanie wykorzystany protokół TCP. Ze względu na to, że lobby stanowi jedynie
pośrednika do zestawiania połączeń, dokładny opis działania zdecydowano się pominąć.

Ponieważ protokół UDP nie zapewnia obsługi połączeń, każdy klient musi wysłać do wszystkich innych pakiet
\texttt{CONNECT = 0x01}, którego odebranie zgodnie z opisem powyżej (najstarszy bit = 0) musi zostać potwierdzone.
Po udanym nawiązaniu połączenia ze wszystkimi klientami, zostaje utworzony czołg gracza, a informacja o tym zostaje
przesłana do pozostałych graczy.

Dokładny opis pakietów służących do aktualizacji stanu rozgrywki (np. aktualizacja pozycji gracza) pomijamy, ponieważ
nie ma związku z problemem synchronizacji klientów.

\section{Potencjalne zmiany}
Założono, że pakiety będą dochodziły \textit{wystarczająco szybko} aby desynchronizacja związana z opóźnieniem w ruchu
sieciowym nie stanowiła problemu. Jednak należy przeprowadzić testy, czy faktycznie jest to dobre założenie. W wypadku,
gdyby jednak desynchronizacja związana z opóźnieniami stanowiła problem należy wprowadzić system pozwalający uwzględniać
opóźnienia odebrania pakietu względem przesłania - np. poprzez wprowadzenie wspólnego, synchronizowanego zegara gry.

Synchronizację zegara można zapewnić w sposób analogiczny do działania protokołu
SNTP\footnote{https://en.wikipedia.org/wiki/Network\_Time\_Protocol}, przy czym synchronizacja następowałaby do zegara
\textit{mastera}. W takim wypadku do pakietów moglibyśmy dołączyć informację na temat momentu w rozgrywce, w którym
pakiet został wysłany i odpowiednio uwzględniać opóźnienie (np. przesuwając obiekt o odpowiednią odległość względem
opóźnienia i dostępnych wektorów prędkości oraz przyspieszenia).


\end{document}