[Bastion-cvs] bastion/doc Licencjat.tex,NONE,1.1

[Jacek K. <jac...@us...>]

Update of /cvsroot/bastion/bastion/doc
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv4551

Added Files:
	Licencjat.tex 
Log Message:
- dodanie pliku Licencjat.tex - dokument w wersji przesylanej mailem przez Darka. 


--- NEW FILE: Licencjat.tex ---
%& --translate-file=il2-pl


\documentclass[licencjacka]{pracamgr}

\usepackage{polski}

% Je¿eli Twój TeX nie reaguje na komentarz w~pierwszej linijce,
% i~psuje polskie znaki, uaktywnij poni¿sz± deklaracjê:
%\usepackage[latin2]{inputenc}

% Dane magistranta:

\author{Dariusz Ku¶mierek}

\nralbumu{197885}

\title{Implementacja gry strategicznej czasu rzeczywistego -- projekt~,,{\bf Bastion}''}

\kierunek{Informatyka}

% Praca wykonana pod kierunkiem:
% (podaæ tytu³/stopieñ imiê i nazwisko opiekuna
% Instytut 
% ew. Wydzia³ ew. Uczelnia (je¿eli nie MIM UW))
\opiekun{mgr. Krzysztofa Ciebiery\\ 
  Zak³ad Analizy Algorytmów\\
  Instytut Informatyki\\
  }

% miesi±c i~rok:
\date{Lipiec 2004}

% Podaæ klasyfikacjê tematyczn± wed³ug AMS MSC 2000 lub ACM CCS:
\klasyfikacja{
K. Computing Milieux \\
K.8 Personal Computing\\
K.8.0 General\\
Subject Descriptor: Games\\
}

% S³owa kluczowe:
\keywords{gra strategiczna czasu rzeczywistego, informacja, sztuczna inteligencja}

% Tu jest dobre miejsce na Twoje w³asne makra i~¶rodowiska:
\newtheorem{defi}{Definicja}[subsection]

% koniec definicji

\begin{document}
\maketitle

\begin{abstract}
  W~pracy przedstawiono implementacjê gry~strategicznej czasu rzeczywistego rozgrywaj±cej siê w~trójwymiarowym ¶wiecie. 
  Rozwój sprzêtu komputerowego, w szczególno¶ci za¶ akceleratorów grafiki trójwymiarowej, pozwoli³ na~stworzenie 
  rozbudowanego modelu ¶wiata gry oraz jego jednoczesn±, precyzyjn± prezentacjê. 
  Nacisk po³o¿ony na~hermetyczno¶æ systemu przekazu informacji i poleceñ, pozwoli³ na~niezwykle realistyczne oddanie sytuacji dowódcy wojsk w~czasie kampanii.
\end{abstract}

\tableofcontents
%\listoffigures
%\listoftables

\newpage
\section*{Wprowadzenie}
\addcontentsline{toc}{section}{Wprowadzenie}

Niniejsza praca stanowi podsumowanie projektu znanego jako ,,{\bf Bastion}'', polegaj±cego na implementacji gry strategicznej czasu rzeczywistego, w~której gracz
dowodzi armi± jednostek uformowanych w oddzia³y, zdolnych do~wykonywania rozmaitych rozkazów. Projekt~,,{\bf Bastion}'' zrealizowany zosta³ przez zespó³ 
w~sk³adzie (w~kolejno¶ci alfabetycznej):
\begin{itemize}
\item   Pawe³ Kêpka
\item   Jacek Ko³odziej -- kierownik zespo³u
\item   Dariusz Ku¶mierek
\item   Micha³ S³apa
\end{itemize}

Niniejsza praca sk³ada siê z~2~rozdzia³ów. 

Rozdzia³~1 stanowi ca³o¶ciowy opis projektu. Przypominamy w nim podstawowe pojêcia wi±¿±ce siê z grami strategicznymi czasu rzeczywistego, 
nastêpnie przedstawiamy regu³y, jakimi rz±dzi siê ¶wiat przez nas modelowany oraz za³o¿enia, jakimi kierowali¶my siê~podczas realizacji gry,
by ostatecznie po¶wiêciæ kilka zdañ technikaliom wi±¿±cym ~siê ze~¶rodowiskiem programistycznym, w~jakim powstawa³ ,,{\bf Bastion}'' oraz
bibliotekom wykorzystanym do~jego implementacji.

Rozdzia³~2 zawiera podsumowanie wk³adu, jaki przedk³adaj±cy niniejsz± pracê w³o¿y³ w~realizacjê projektu~,,{\bf Bastion}''. 

\chapter{Opis projektu~,,{\bf Bastion}''}\label{r:opis}
\section{Podstawowe pojêcia}\label{r:pojecia}
\subsection{Gra strategiczna czasu rzeczywistego}

Gry strategiczne czasu rzeczywistego  (ang. {\it RTS -- Real Time Strategy}) pozwalaj± graczom na~wziêcie udzia³u w~rozgrywce, podczas której akcje 
podejmowane przez przeciwnika oraz przez gracza i~jego jednostki odbywaj± siê~jednocze¶nie. Takie uporz±dkowanie rozgrywki wymusza wykonywanie 
wszelkich obliczeñ na~bie¿±co, co~niesie za sob± konieczno¶æ zastosowania efektywnych, czêsto przybli¿onych algorytmów.


\subsection{Informacje i mg³y wojny}

Genera³ Sun Tzu Wu (500 r. p. n. e.) tak pisa³ w~ostatnim rozdziale swej s³ynnej ,,{\it Sztuki~wojny}'':
\begin{quote}

    Tak wiêc ¶wiat³y w³adca i~rozs±dny genera³ zawsze wygrywaj±; 
osi±gaj±~to, czego pospolity cz³owiek osi±gn±æ nie~potrafi - a~wszystko~to dziêki temu, ¿e~wiedz± wcze¶niej.
Wiedzy takiej nie~mo¿na otrzymaæ od~bogów, nie~mo¿na jej~zdobyæ przez obserwacjê rzeczywisto¶ci, nie~mo¿na jej~te¿~wyczytaæ z~gwiazd. 
Jedynym sposobem, aby~poznaæ wroga, to~zdobyæ wiadomo¶ci o~nim od~kogo¶ innego.

\raggedleft\slshape t³um. z~chiñskiego Jaros³aw Zawadzki
\end{quote}

Genera³ zwraca w~powy¿szym fragmencie uwagê czytelnika na~kluczowe znaczenie informacji w~rozwoju kampanii wojennej.

Twórcy gier strategicznych dla~dodania swym produkcjom realizmu od~lat stosuj± metodê ukrywania przed graczem informacji na~temat 
nie~widocznego w~danym momencie terenu (najwa¿niejsz± -- i~zazwyczaj jedyn± -- ukrywan± w~ten sposób informacj± jest obecno¶æ wrogich jednostek).
Technika ta~nazywana jest powszechnie mg³ami wojny (ang. {\it Fog of war}).





\section{Rzeczywisto¶æ modelowana w~projekcie ,,{\bf Bastion}'' }\label{r:rzeczywisto¶æ} 
\subsection{Cel gry}

W~,,{\bf Bastionie}'' gracz wciela siê~w~rolê genera³a dowodz±cego wojskami szturmuj±cymi zamek. 
Na~planszy (wewn±trz oraz na~zewn±trz zamku) znajduj±~siê tak¿e jednostki wojsk przeciwnych, z~którymi armia genera³a musi siê~zmierzyæ.

Celem gracza jest doprowadzenie do zdobycia zamku. Gra koñczy~siê klêsk± w~momencie ¶mierci genera³a.

\subsection{Informacje i rozkazy}
Gracz obserwuje ¶wiat z~perspektywy genera³a. 
Przyjêli¶my za³o¿enie, i¿~zarówno kszta³t jak i rodzaj terenu na ca³ej planszy jest znany, nieznane pozostaje po³o¿enie oraz liczno¶æ wojsk zarówno przeciwnych jak i~podleg³ych genera³owi.
Gracz obserwowaæ mo¿e w~trakcie gry bezpo¶rednie po³o¿enie jednostek widocznych dla genera³a; dla jednostek, które opu¶ci³y pole widzenia dowódcy wy¶wietlana jest ostania pozycja, 
w~której by³y widziane. Do takiej pozycji bêdziemy siê~odnosiæ jako do {\it ostatniej zaobserwowanej pozycji} jednostki.

Ostatnia zaobserwowana pozycja zostaje zaktualizowana w~momencie, w~którym dowódca dostrze¿e rzeczon± jednostkê w~innej lokalizacji. 
Aktualizacja ostatniej zaobserwowanej pozycji ma~tak¿e miejsce, gdy do dowódcy dotrze pos³aniec wys³any przez który¶ z oddzia³ów.  
Pos³aniec przekazuje dowódcy informacje na~temat zaobserwowanego po³o¿enia jednostek. 
Je¿eli pos³aniec posiada ¶wie¿sze od genera³a informacje odno¶nie lokalizacji danej jednostki, wówczas ostatnia zaobserwowana pozycja tej¿e jednostki zostaje zaktualizowana.

Podobnie jak~w~wiêkszo¶ci gier strategicznych, równie¿ w~,,{\bf Bastionie}'' kluczowym dla~rozgrywki jest wykonywanie rozkazów dowódcy przez oddzia³y jemu podlegaj±ce. 
Ze wzglêdu na za³o¿enie o~jak najwy¿szym stopniu realizmu rozgrywki, w~,,{\bf Bastionie}'' rozkaz, zanim zostanie wykonany przez oddzia³, musi zostaæ do~niego dostarczony przez pos³añca. 

Pos³añcy s± zwyk³ymi jednostkami przemieszczaj±cymi siê pomiêdzy oddzia³em dowódcy a pozosta³ymi; tak samo jak~wszystkie inne jednostki, pos³añcy mog± zostaæ zabici przez przeciwnika.
P³ynie z~tego wa¿ki wniosek, i¿~rozkaz wydany przez dowódcê mo¿e nie~dotrzeæ do~celu, a~zatem nigdy nie zostaæ wykonanym, w~najlepszym za¶~razie zostanie wykonany z~opó¼nieniem,
równym czasowi podró¿y pos³añca pomiêdzy dowódc± a oddzia³em (na~pos³añca wybierana jest najszybsza jednostka w~oddziale dowódcy).

\subsubsection{Rozkazy z³o¿one}
Ze~wzglêdu na~omówione powy¿ej ograniczenia stoj±ce przed dowódc±, zrodzi³a~siê potrzeba rozbudowania mechanizmu definiowania rozkazów.

W~,,{\bf Bastionie}'' gracz definiuje drzewo rozkazu z~rozkazów podstawowych takich jak: przemieszczenie~siê do~zadanej pozycji (opcjonalne przemieszczanie siê w~lesie, lub z~dala od zamku), 
oczekiwanie na~up³yniêcie pewnego czasu, 
lub na~nadej¶cie sygna³u rogu (pozwala na~synchronizacjê dzia³añ kilku oddzia³ów), 
atakowanie muru (stawianie drabin pod~murem), b±d¼ podzielenie oddzia³u.

W ramach definicji rozkazu, gracz wyspecyfikowaæ mo¿e stopieñ waleczno¶ci ¿o³nierzy (atakowanie ka¿dego przeciwnika, unikanie walki, atakowanie tylko mniej licznych oddzia³ów).

Wspomnieli¶my, i¿~rozkaz z³o¿ony ma~strukturê drzewiast±. Ka¿dy rozkaz podstawowy zakoñczyæ siê~mo¿e sukcesem~lub~pora¿k±. Gracz ma mo¿liwo¶æ wyspecyfikowania, jakie akcje
zostan± przez oddzia³ wykonane w~zale¿no¶ci od~wyniku danej akcji.

\subsection{Jednostki}
W~,,{\bf Bastionie}'' wystêpuj± trzy rodzaje jednostek
\begin{itemize}
\item [--] Piechota - standardowa jednostka bojowa
\item [--] £ucznicy - standardowa jednostka zdolna do~ataku na~odleg³o¶æ
\item [--] Konnica - szybsza i~potê¿niejsza jednostka, nie~zdolna jednak do~wspinania~siê po~drabinie i~zdobywania murów. W~czasie ataku na~mur, konnica od³±czana jest od~oddzia³u.
\end{itemize}

\subsection{Oddzia³y}
Jednostki uformowane s± w~oddzia³y. Oddzia³ zarz±dza po³o¿eniem poszczególnych jednostek, dbaj±c o~to, aby~jednostki poszczególnych rodzajów porusza³y~siê razem (w~pododdzia³ach). 

W ramach oddzia³u wykonywane s±~modyfikacje formacji, konieczne na~przyk³ad w~sytuacji, gdy na drodze oddzia³u znajduje siê~w±ski w±wóz.

Oddzia³ tak¿e, poprzez dostosowanie 
po³o¿enia, do~którego d±¿± poszczególne jednostki, mo¿e czekaæ na~maruderów, czyli jednostki, które nie~dotar³y do wyznaczonych im~pozycji (jednostki takie zwiêkszaj± swoj± prêdko¶æ
na~krótkim dystansie, celem zniwelowania opó¼nienia).

\subsection{Plansza i teren}
Jednostki poruszaj±~siê po~planszy, która podzielona jest na~pola. Chocia¿ w~ramach jednego pola znajdowaæ siê~mo¿e tylko jedna jednostka (co~wymaga rozstrzygania 
konfliktów pomiêdzy jednostkami), to jednostka ta~znajdowaæ siê mo¿e w dowolnym miejscu swojego pola (po³o¿enie jednostki opisane jest przez trzy wspó³rzêdne rzeczywiste), oraz 
mo¿e przemieszczaæ~siê w~dowolnym kierunku.

Na planszy znajdowaæ siê mog± trzy rodzaje terenu:
\begin{itemize}
\item [--] Pole -- standardowy teren
\item [--] Las -- teren, który utrudnia poruszanie~siê jednostek oraz ogranicza widoczno¶æ w~sposób niesymetryczny (pozwala na~ukrywanie siê~jednostek)
\item [--] Ska³y -- teren niedostêpny dla jednostek
\end{itemize}

Na polu mo¿e (ale~nie~musi) znajdowaæ~siê budynek jednego z~czterech rodzajów:
\begin{itemize}
\item [--] Mur -- po~którym mog± przemieszczaæ~siê jednostki
\item [--] Wie¿a -- na~której jednostki nie~mog± siê~znajdowaæ
\item [--] Drabina -- po~której wszystkie jednostki poza konnic± mog± dostaæ~siê na~mur, oraz z~niego zej¶æ
\item [--] Brama
\end{itemize}



\section{Technikalia i~opis implementacji}\label{r:technikalia}
W tej czê¶ci wymienimy dane techniczne dotycz±ce ¶rodowiska w~jakim projekt~,,{\bf Bastion}' powsta³ oraz w~jakim mo¿e byæ uruchomiony.

\subsection{¦rodowisko u¿ytkownika}
\subsubsection{System operacyjny}
Projekt~,,{\bf Bastion}'' funkcjonuje jedynie jako aplikacja systemu operacyjnego {\bf Linux}.
\subsubsection{Wymagania techniczne}
Ze wzglêdu na~wysokiej jako¶ci grafikê stworzon± na~potrzeby gry, do~jej~funkcjonowania wymagana jest sprzêtowa akceleracja 3D oraz poprawnie zainstalowany OpenGL.


\subsection{¦rodowisko programistyczne}

\subsubsection{Jêzyk}
Projekt~,,{\bf Bastion}'' zrealizowany zosta³ ca³kowicie w~jêzyku {\bf C++}.

\subsubsection{Biblioteki}
Na potrzeby realizacji projektu wykorzystane zosta³y nastêpuj±ce biblioteki:
\begin{itemize}
\item [--] Glut -- dla~obs³ugi trybu graficznego oraz zdarzeñ kontrolnych (mysz, klawiatura)
\item [--] Plib -- dla~stworzenia zaawansowanego i~wygodnego interfejsu u¿ytkownika  (ang. {\it GUI -- Graphical User Interface}) 
\item [--] Demeter -- dla~wygenerowania realistycznego trójwymiarowego pod³o¿a 
\end{itemize}

\subsubsection{Narzêdzia}
W~tworzeniu i dokumentacji projektu pomocne okaza³y siê narzêdzia:
\begin{itemize}
\item [--] cvs.sf.net -- na potrzeby wygodnej i~wydajnej pracy zespo³owej
\item [--] Doxygen -- na potrzeby automatycznej dokumentacji kodu
\end{itemize}


\chapter{Funkcjonalno¶ci zrealizowane przez przedk³adaj±cego pracê licencjack±}\label{r:funkcjonalnosci}
\begin{enumerate}
	\item  Reprezentacja mapy 
	\begin{enumerate}
		\item  Teren: las, pole, ska³y
		\item  Budynki: mur, wie¿a, drabina, brama
		\item  Wykonywanie polecenia przemieszczenia jednostki 
		\begin{enumerate}
			\item  Prêdko¶æ zale¿na od~nachylenia i~rodzaju terenu
			\item  Rozstrzyganie konfliktów pomiêdzy jednostkami
		\end{enumerate}
	\end{enumerate}
	\item  Uproszczone rozstrzyganie widoczno¶ci 
	\begin{enumerate}
		\item  Generowanie zbioru jednostek i~budynków widzianych przez dowódcê oddzia³u
		\item  Widoczno¶æ zale¿na od~rodzaju i~kszta³tu terenu
	\end{enumerate}
	\item  System wyszukiwania ¶cie¿ek
	\begin{enumerate}
		\item  Tworzenie i~aktualizowanie map spójnych sk³adowych pozwalaj±cych na~szybkie rozstrzygniêcie, czy~¶cie¿ka pomiêdzy zadanymi punktami istnieje.
		\item  Wyszukiwanie, je¶li istnieje, ¶cie¿ki na~wprost
		\item  W przeciwnym wypadku u¿ycie algorytmu A* dla wyszukania ¶cie¿ki
		\begin{enumerate}
			\item  Heurystyka przyspieszaj±ca wyszukiwanie kosztem nie~zawsze optymalnej ¶cie¿ki (heurystyka przeszacowana)
			\item  Dodatkowe, opcjonalne heurystyki pozwalaj±ce~na:
			\begin{enumerate}
				\item  Wyszukiwanie ¶cie¿ek omijaj±cych zamek
				\item  Wyszukiwanie ¶cie¿ek ukrytych w~lesie (w~jak~najwy¿szym stopniu)
				\item  Wyszukiwanie ¶cie¿ek omijaj±cych ska³y
			\end{enumerate}
			\item  Badanie szeroko¶ci ¶cie¿ki na~potrzeby zmiany formacji oddzia³u (np.~zwê¿enie formacji podczas przej¶cia przez ska³y)
		\end{enumerate}
	\end{enumerate}
\end{enumerate}





\begin{thebibliography}{99}
\addcontentsline{toc}{section}{Bibliografia}
  
\bibitem[Str97]{stroustrup} Bjarne Stroustrup, \textit{Jêzyk C++}, Wydawnictwa Naukowo--Techniczne, 1997
  

\end{thebibliography}

\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% coding: latin-2
%%% End: