\chapter{Centrale valg}\label{chap:centralevalg}
I dette afsnit bliver der redegjort for hvilke overordnede valg der har formet udviklingen af Blaster.

\section{Visualisering}
Der er mange fremgangsmåder til at visualisere et spil på. Først er det vigtigt at identificere de forskellige typer af elementer der skal tegnes i Blaster. Elementer som rumskibe og skud er ofte ret små i forhold til størrelsen på skærmen eller vinduet som spillet tegnes i. Omvendt er den verden som spilleren bevæger sig i, ofte større end skærmen, således at spilleren kun ser et lille udsnit af banen på et givet tidspunkt. Yderligere kan der være visse oplysninger som spilleren er interesseret i at se på skærmen: brændstof, antallet af points og så videre.

De to mest relevante visualiseringsmetoder i dette tilfælde er bitmaps og sprites, samt polygonbaseret grafik. Tidlige computerspil brugte hovedsageligt bitmaps, mens nye computerspil overvejende benytter sig af polygoner til at visualisere sig selv.

\subsection{Bitmaps}
Vælges den bitmaporienterede fremgangsmåde betyder det, at små elementer på skærmen tegnes som \emph{sprites}, og større elementer på skærmen (verden) tegnes enten som et stort bitmap, eller som en række \emph{tiles}.

En \emph{sprite} er en lille rektangulær bitmap som har en størrelse, hvor hvert led er en andenpotens. Dette gør dem særligt hurtige at tegne for grafiksystemet. Selv om en sprite i sig selv er rektangulær, kan dele af den være defineret som gennemsigtige, således at en sprite kan fremstå runde eller hule. Dette vil ikke blive gennemgået nærmere.

En \emph{tile} er en sprite der er tegnet således at den kan placeres ved siden af sig selv eller en anden sprite, således at de to sprites har en naturlig overgang og fremstår som én. En skov kan f.eks. repræsenteres ved at have en lille sprite der viser nogle træer, og så tegne flere af disse sprites ved siden af hinanden. Fordelen ved tiles er, at det er muligt at opbygge et større billede ud af små byggeklodser. Dette bl.a. er en fordel både hvad angår hukommelsesforbrug.

En stor ulempe ved sprites er, at der kræves en ny sprite for hver retning som rumskibet kan bevæge sig, da man normalt ikke rotere sprites. Det betyder man enten skal begrænse de retninger, som rumskibet har mulighed for at bevæge, eller også må man vælge den sprite er tættest på  at repræsenterer den orientering som rumskibet har på det givne tidspunkt. Enten begrænses spillerens bevægelsesmuligheder, eller også accepteres det, at der godt kan være en uoverensstemmelse med den orientering, som skibets sprite repræsenterer i forhold til skibets egentlige orientering.

Grunden til at man undgår at rotere, eller på anden måde manipulere, sprites, er hastighed. Hvis man manipulere med en sprite før man tegner den, mister man en del af den hastighed man prøvede at vinde ved at bruge en sprite. 

Uanset hvor meget det er muligt at reducere kravet til mængden af sprites og tiles vil der altid være et minumumsantal, der skal tegnes. Eksempelvis er det næppe acceptabelt med mindre end 8 mulige orienteringer for rumskibet, selv om antallet af unikke sprites kan reduceres ved brug af spejling, og af hensyn til variation i banen skal der også være et par tiles at vælge imellem. Dette stiller krav til at disse rent faktisk skal tegnes.

Et andet potentielt problem ved bitmaps er, at det ikke er ligetil at bestemme, hvad der sker, hvis et rumskib kolliderer med banen. Grunden til dette er at man normalt ikke ønsker at kollidere med selve spriten, men dens grafiske repræsentation. Normalt vil man f.kes. ikke kollidere med gennemsigtige dele af spriten. Men hvordan finder man nemt hældningen på en del af en bitmap? Hvad hvis der kun er en enkelt løsstående pixel som kolliderer - hvilken retning skal skibet da afbøjes i? Derfor er sprites ikke gode kandidater til detaljeret kollision. 

\subsection{Polygoner}
Den anden metode er som nævnt at bruge polygoner til at repræsentere de forskellige elementer i banen. Når der arbejdes med polygoner er det forholdsvis nemt at beregne rumskibets nye bevægelsesretning, da siderne af en polygon består af veldefinerede linier. Ud fra disse er det let at beregne reflektionsvektoren ud fra det indkommende rumskibs hastighedsvektor.

Veldefinerede kollisioner er ikke den eneste fordel som polygoner har i forhold til bitmaps. Det er simpelt at rotere en polygon i en vilkårelig vinkel, da polygoner er defineret ud fra et antal punkter i et koordinatsystem, og disse kan transformeres.
 
Det er dog vigtigt at pointere, at det er lidt langsommere at rotere en polygons punkter og derefter tegne den, end at tegne en simpel sprite. Uden at gå for meget i detaljer, så tegnes en sprite ved at kopiere dens bitmap over i skærmens bitmap. For at tegne en polygon skal den først rasteriseres i et bitmap, og dette skal da kopieres ind i skærmens bitmap \cite{foley}.

%konklusion på visualisering
De væsentligeste grunde til at polygonbaseret grafik er at foretrække frem for bitmaps er altså, at brugen af polygoner garanterer at elementerne i spillet kan tegnes med samme orientering som i modellen, samt at kollisioner mellem to polygoner i bevægelse umiddelbart er mere veldefineret end mellem to sprites.

\section{Banen}
Når det er vedtaget at bruge polygoner til at repræsentere grafikken i banen, skal der findes en metode til at definere en bane i spillet.

En mulighed er at indlæse filer fra et eksisterende modelleringsværktøj, som Maya eller 3D StudioMax. Disse programmer er designet til at lave avancerede 3D modeller, ofte opbyggede af polygoner. Dog indeholder sådanne programmers filformater  overflødig data i forhold til de krav som Blaster stiller, og understøtter ikke nødvendigvis de egenskaber for polygoner som Blaster kræver. Desuden kan sådanne filformater være komplekse og udokumenterede. Derfor vurderes det at Blaster må have sit eget filformat til banerne.

Filformatet skal beskrive de polygoner der ligger i banen, såvel som de egenskaber polygonerne og banen måtte have. Dog bliver det nemt uoverskueligt at redigere en fil med mere end et par polygoner, hvorfor det vurderes at være nødvendigt at lave en lille editor der er i stand til at redigere baner med et grafisk interface.

\section{Netværket}
Et af målene for Blaster er som nævnt, at flere spillere skal kunne spille mod hinanden. Det betyder, at data skal sendes mellem spillere. Det præsenterer to problemer:  Hvilken netværksmodel skal bruges til at sende data mellem spillerne, og hvilket indhold skal der være i de data der transmitteres mellem spillerne.

\subsection{Netværksmodeller}
Netværksmodellen bestemmer hvordan information om spillets tilstand sendes rundt på netværket, samt hvem der er ansvarlig for at opdatere spillets tilstand.

\subsubsection{Peer to peer}

Den simpleste netværksmodel er \emph{peer to peer} modellen. I denne model har alle spillere forbindelse til samtlige andre spillere. Når en spiller vil opdatere spillets tilstand med dens information, skal den sende information om sig selv til samtlige andre spillere på netværket. En spiller er altså ansvarlig for at fortælle alle de andre spillere om sine handlinger.

\begin{figure}[h]
\begin{center}
    \begin{minipage}[t]{\textwidth}
        \begin{center}
	        \scalebox{0.6}{\includegraphics{gfx/p2p.pdf}}
            \caption{Peer to peer modellen}
            \label{fig:p2pmodel}
        \end{center}
    \end{minipage}
\end{center}
\end{figure}

Der er en enkelt fordel, men mange ulemper ved peer to peer netværksmodellen. Fordi hver spiller har direkte forbindelse til hinanden, skal netværksdataen kun igennem ét led, hvilket giver en lav forsinkelse fra dataen bliver sendt til den bliver modtaget. Desværre bruger denne model meget båndbredde, og forbruget stiger eksponentielt for hver ny spiller. Når hver spiller sender og modtager data fra samtlige andre spillere, kræver $n$ spillere $(n-1)!$ netværksforbindelser. Hvis en spiller antages at sende 100 bytes ti gange hvert sekund til hver spiller i et spil med 20 spillere, sendes altså $1000 \frac{bytes}{s} * (20-1)! = ~1.22 * 10^{17} \frac{bytes}{s}$. Der går nok mange år inden der findes netværk der kan håndtere en sådan belastning.

Fordi hver spiller fortæller de andre spillere om dens tilstand, er der potentiale for at snyde ved at sende falsk information omkring spilleren til de andre spillere. Der rejser sig også spørgsmål om hvad der sker hvis én spiller rammer en anden med skud: hvilken spiller er ansvarelig for at sørge for, at den ramte spiller bliver tildelt den skade den skal have? Hvordan forhindrer man at det bliver misbrugt? Hvis en spiller selv er ansvarlig for at håndtere skade, kan spilleren jo bare lade være med det. Omvendt, hvis andre spillere har ansvaret, hvad forhindrer så en spiller i at påstå at den pludselig har dræbt samtlige spillere i banen?

\subsubsection{Ringmodellen}

Ringmodellen er en forbedring af peer to peer modellen, som er opbygget efter samme princip som TokenRing netværk. Spillere organiseres i en ring, og hver spiller skiftes til at have lov til at ændre spillets tilstand. Mens en spiller venter på sin tur, gemmes input fra brugeren. Når det bliver spillerens tur, modtager den spillets tilstand fra den forrige spiller i ringen. Spilleren opdaterer spillets tilstand ud fra det input den har fået fra brugen, og giver turen videre til den næste spiller i ringen.

\begin{figure}[h]
\begin{center}
    \begin{minipage}[t]{\textwidth}
        \begin{center}
	        \scalebox{0.6}{\includegraphics{gfx/ring.pdf}}
            \caption{Ringmodellen}
            \label{fig:ringmodel}
        \end{center}
    \end{minipage}
\end{center}
\end{figure}

I forhold til peer to peer netværk er båndbreddeforbruget drastisk beskåret: på et givet tidspunkt er der kun to spillere der kommunikerer med hinanden. Desværre medfører ringmodellen en voldsom forsinkelse mellem hver gang en spiller har mulighed for at opdatere sin tilstand af spillet. Turen skal hele vejen rundt i ringen inden spilleren kan få sin tur igen. Forsinkelsen afhænger af antallet af spillere: hvis der er 19 andre spillere med i spillet, er spilleren nødt til at vente på at de 19 andre spillere opdaterer spillets tilstand. Hvis det antages, at spillet opdaterer lokalt 30 gange i sekundet hos hver spiller, tager det $0,033$ sekunder for en spiller at beregne en opdatering, hvilket inkluderer at læse fra og sende til netværket. En spiller skal altså vente $0.033 s * 19 = ~0.63 s$, eller lidt over et halvt sekund mellem hver opdatering af spillet. Spillerens oplysninger om de andre spillere vil altså kun blive opdateret hvert halve sekund. Ringmodellen egner sig altså ikke til spil med ret mange spillere.

Der er stadig mulighed for snyd i ringbaserede netværk. Der er ikke noget der forhindrer en spiller i at opdatere spillets tilstand som det nu engang passer spilleren.

\subsubsection{Klient-server modellen}

Opbygningen af klient-servermodel har form som en stjerne med serveren i midten, omgivet af klienter (spillere). En givet spiller har kun forbindelse til serveren, og serveren har forbindelse til alle spillere i spillet.

Klient-servermodellen har mange fordele i forhold til de to andre modeller, og få ulemper. Båndbreddekravene til serveren er større end for en klient: det kræves at serveren skal håndtere forbindelser til samtlige forbundne spillere. Båndbreddekravene for en klient er blot forbindelsen til serveren.

\begin{figure}[h]
\begin{center}
    \begin{minipage}[t]{\textwidth}
        \begin{center}
	        \scalebox{0.6}{\includegraphics{gfx/clientserver.pdf}}
            \caption{Klient-server modellen}
            \label{fig:clientservermodel}
        \end{center}
    \end{minipage}
\end{center}
\end{figure}

I en ideel klient-server situation behandler klienten ikke input fra brugeren, men sender det til serveren hvor det bliver behandlet. Serveren opdaterer spillets tilstand ud fra alle klienternes input, og sender visuel information om spillets nye tilstand til alle klienterne. Klienten fungerer altså stort set som en dum terminal hvor alle beregninger og opdateringer af spillets tilstand foregår på serveren, og klienten kun samler input og tegner spillet. Dette sætter automatisk en begrænsning på muligheden for at sende falsk data, da en klient i så fald kun vil kunne snyde sig til hændelser som spilleren alligevel havde mulighed for at foretage sig. En spiller kan således ikke længere påstå at hoppe til den anden ende af banen på et øjeblik, eller dræbe spillere som den ellers ikke havde mulighed for at ramme.

Forsinkelsen mellem input fra brugeren og visuel reaktion er større end ved peer to peer, men mindre end ved brug af ringmodellen: inputtet fra brugren skal først sendes til serveren hvor den behandles. Først når serveren har opdateret spiltilstanden sendes der data til klienten så den kan opdatere skærmen.

Antallet af spillere påvirker ikke forsinkelsen mellem en klient og en server, og påvirker kun båndbreddekravene lineært, da en spiller så skal modtage flere beskeder fra serveren jo flere spillere der er med i spillet.

Af de nævnte netværksmodeller er klient-server modellen den der har de bedste egenskaber til et multiplayer spil: modellen er skalerbar og begrænser mulighederne for at snyde.

\subsection{Protokollen}

Klient-server netværksmodellen lægger som nævnt op til, at klienten sender input til serveren og får en form for grafikbeskrivelse tilbage fra serveren, om det er i bitmap form eller mere abstrakte tegneinstruktioner. I praksis giver dette en mærkbar forsinkelse mellem input og reaktion hos brugeren hvis der blot er en lille forsinkelse mellem klienten og serveren. Problemet er at klientens input skal igennem serveren før klienten kan tegne en opdateret repræsentation af spillet hvor brugerens input har haft konsekvenser.

Forsinkelsen kan ikke fjernes, men den kan til en vis grad skjules hvis klienten sender og modtager information om rumskibenes position, oritentering og hastighed i stedet for simpel input. Således er klienten i stand til at gætte hvor de andre spillere er henne mellem opdateringer fra serveren, og serveren er i stand til at gætte klientens placering og orientering imellem opdateringer fra klienten. Når en ny opdatering kommer fra serveren, overskriver klienten blot de andre skibes positioner m.m, ligeledes når serveren modtager en klients opdaterede position.

Således har klienten en kopi af spillets tilstand liggende lokalt, som den bruger til at visualisere spillet. Når brugeren bevæger sit rumskib, sker det i den lokale kopi af spillets tilstand. Det lokale rumskibs placering m.m bliver sendt til serveren med korte mellemrum, præcis som serveren sender information om alle de andre spillere til klienten. Den lokale kopi af spillets tilstand vil næsten altid være i let uoverensstemmelse med serverens opfattelse af spillets tilstand, men hvis serveren får lov til at beholde autoriteten har det ikke nogen større betydning. En spiller vil aldrig se præcis samme tilstand som serveren ser, men en approksimeret tilstand som skulle afvige meget lidt. Det er ikke så kritisk hvis nogle af rumskibene hopper en lille smule af og til, hvis klientens eget fly bevæger sig i en glidende bevægelse og reagerer med det samme. 