Algorytmy proceduralnego generowania.pdf

(1056 KB) Pobierz
Grzegorz Michalak
Algorytmy proceduralnego
generowania rzeczywistości
na przykładzie dwuwymiarowej
gry cRPG
Praca magisterska
wykonana pod kierunkiem
dr. Tomasza Gwizdałły
Uniwersytet Łódzki
Wydział Fizyki i Informatyki Stosowanej
Łódź, 2012
Spis treści
1. Wstęp................................................................................................................................. 4
1.1 Proceduralność oraz losowość..............................................................................................4
1.2 Zastosowania generatorów proceduralnych..........................................................................5
2. Cel...................................................................................................................................... 7
2.1 Implementacja algorytmów....................................................................................................7
2.2 Wybrane środowisko programistyczne..................................................................................8
2.2.1 Język programowania....................................................................................................8
2.2.2 Kompilator......................................................................................................................8
2.2.3 Biblioteka graficzna........................................................................................................8
3. Mapa świata....................................................................................................................... 9
3.1 Elewacja................................................................................................................................9
3.1.1 Automat komórkowy......................................................................................................9
3.1.2 Szum Perlina................................................................................................................10
3.2 Biomy...................................................................................................................................11
3.2.1 Korekta biomów...........................................................................................................12
3.3 Ukształtowanie terenu.........................................................................................................13
3.3.1 Rzeki............................................................................................................................13
3.3.2 Góry.............................................................................................................................14
3.3.3 Lasy.............................................................................................................................14
3.4 Infrastruktura........................................................................................................................15
3.5 Analiza kształtów.................................................................................................................17
4. Miasto............................................................................................................................... 22
4.1 Plan dróg.............................................................................................................................22
4.2 Przygotowanie listy budynków ............................................................................................23
4.3 Gospodarowanie przestrzenią.............................................................................................24
4.4 Generowanie budynków......................................................................................................24
4.5 Aranżacje pokojów...............................................................................................................27
5. Labirynt............................................................................................................................ 28
5.1 Zastosowanie algorytmu......................................................................................................28
5.2 Hunt&Kill..............................................................................................................................28
5.3 Mapa oświetlenia.................................................................................................................29
6. Postacie........................................................................................................................... 31
6.1 Statystyki postaci.................................................................................................................31
6.1.1 Zawody........................................................................................................................31
6.1.2 Cechy indywidualne.....................................................................................................32
6.1.3 Modyfikacje cech.........................................................................................................32
6.2 Animacja szkieletowa...........................................................................................................35
6.2.1 Budowa modelu szkieletowego...................................................................................35
6.2.2 Animacja......................................................................................................................36
7. Nazwy............................................................................................................................... 38
7.1 Technika generowania.........................................................................................................38
7.1.1 Łańcuch Markowa........................................................................................................38
7.2 Imiona postaci......................................................................................................................41
2
7.2.1 Imiona nordyckie..........................................................................................................41
7.2.2 Imiona europejskie.......................................................................................................41
7.2.3 Imiona afrykańskie.......................................................................................................42
7.3 Nazwy miast........................................................................................................................42
7.4 Tytuł gry...............................................................................................................................42
8. Efekty specjalne i czcionka............................................................................................44
8.1 Zastosowanie w praktyce....................................................................................................44
8.2 Płomień................................................................................................................................44
8.3 Zjawiska pogodowe.............................................................................................................45
8.4 Czcionka..............................................................................................................................45
8.4.1 Parametryzacja............................................................................................................46
9. Zagadnienia fabularne....................................................................................................47
9.1 Przedmioty...........................................................................................................................47
9.1.1 Inwentarz.....................................................................................................................47
9.1.2 Interakcja z przedmiotami............................................................................................48
9.2 Fabuła..................................................................................................................................49
9.2.1 Implementacja zadań...................................................................................................50
9.2.2 Przykładowe zadanie...................................................................................................50
10. Optymalizacja aplikacji.................................................................................................52
10.1 Rozmiar aplikacji................................................................................................................52
10.1.1 Dane wewnętrzne......................................................................................................52
10.1.2 Komponenty pliku wynikowego..................................................................................53
10.1.3 Zewnętrzna kompresja pliku......................................................................................53
10.2 Zużycie pamięci.................................................................................................................54
10.3 Zużycie czasu procesora...................................................................................................55
10.4 Wieloplatformowość...........................................................................................................55
10.5 Optymalizacja kodu programu...........................................................................................56
11. Wnioski........................................................................................................................... 58
3
1. Wstęp
Generowanie proceduralne jest dziedziną szeroko wykorzystywaną w produkcji mediów
cyfrowych. Algorytmy tworzenia zasobów stosuje się głównie w programach
przeznaczonych do manipulacji obrazem, jak również grach wideo. W pracy opisany został
sposób generowania wszystkich istotnych elementów gier komputerowych wraz z użytymi
w tym celu algorytmami.
1.1 Proceduralność oraz losowość
Element nazywany jest wygenerowanym proceduralnie jeżeli został stworzony
automatycznie przez algorytmy komputerowe. Jako prosty przykład można przyjąć funkcję
rysującą prostokąt o wymiarach
20x10px
w lewym górnym rogu ekranu. Prostokąt
niegenerowany proceduralnie będzie najczęściej grafiką wczytywaną z pliku
(np.
draw_image("prostokat.bmp"))
o wymiarach
20x10px,
natomiast prostokąt
generowany proceduralnie będzie funkcją rysującą cztery połączone ze sobą pod kątem
prostym linie (np.
draw_rectangle(0,0,20,10)).
Podejście proceduralne umożliwia swobodną modyfikację parametrów procedur.
Korzystanie w takim przypadku z generatorów liczb losowych jest bardzo intuicyjne.
Nawiązując do powyższego przykładu, nie jest problemem wygenerowanie prostokąta
o losowej szerokości. Jeżeli przyjmiemy, że funkcja
random(x,y)
zwraca liczbę całkowitą
z przedziału
<x,y>,
to można ją wykorzystać do wywołania funkcji w postaci
np.
draw_rectangle(0,0,random(10,30),10).
Użytym w grze generatorem liczb pseudolosowych jest funkcja
rand()
należąca
do standardowej biblioteki języka C++. Zwraca ona całkowitą liczbę z przedziału
<0,RAND_MAX>. RAND_MAX
jest stałą zdefiniowaną w
<cstdlib>.
Jej wartość domyślna
zależna jest od implementacji lecz nie może być mniejsza niż
32767.
Algorytm korzysta z ziarna losowości, które powinno być inicjalizowane określoną
wartością poprzez funkcję
srand(int).
Dla każdej różnej wartości ziarna, generator liczb
pseudolosowych tworzy inne sekwencje liczb przy wywołaniu funkcji
rand().
Dwie różne
inicjalizacje
srand()
z podaną tą samą wartością ziarna losowości zapewniają uzyskanie
tych samych sekwencji liczb przy kolejnych wywołaniach
rand().
Dlatego każdy obiekt
występujący w grze przechowuje swoje ziarno by móc zostać tak samo odwzorowanym
graficznie przy ponownym pojawieniu się na ekranie.
4
1.2 Zastosowania generatorów proceduralnych
Najczęściej spotykanymi elementami wygenerowanymi proceduralnie są:
•
tekstury
– efekty wizualne, takie jak szum Perlina
1
, są szeroko wykorzystywane
w produkcji filmów z efektami specjalnymi (pierwsze zastosowanie w filmie Tron
z 1982 roku) oraz w dziedzinie gier komputerowych,
•
siatki modeli 3D
– proceduralność pozwala na bardzo szybkie tworzenie
rozległych terenów i obszarów miejskich
2
,
•
dźwięk
– spotykany zarówno w syntezie mowy jak i komputerowej kompozycji
melodycznej
3
(Stephen Hawking korzysta z systemu generowania mowy, który
umożliwia mu komunikację),
•
fraktale
4
– wizualizacja odpowiednich wzorów matematycznych pozwala uzyskać
obrazy reprezentujące obiekty samo-podobne.
Wykorzystywanie generatorów w grach komputerowych jest zjawiskiem powszechnym.
Zwykle są to zasoby takie jak:
•
struktura poziomów
- tworzenie labiryntów dla produkcji typu hack and slash
(Diablo
II
5
wydana w 2000 roku ma swoich aktywnych fanów po dziś dzień,
natomiast
Minecraft
6
, z tworzonym pseudolosowo światem, zdobył ponad milion
nabywców w przeciągu kilku miesięcy),
•
elementy fabuły
- głównie spotykane w grach typu cRPG (począwszy
od
The Elder Scrolls II: Daggerfall
7
),
•
animacja postaci
- system automatycznego tworzenia animacji stworów w
Spore
8
,
•
fauna i flora
- popularny system
SpeedTree
pozwala wygenerować losowe,
niepowtarzające się drzewa (z aplikacji tej korzystają zarówno czołowi producenci
gier komputerowych na świecie jak i przemysł filmowy, np. James Cameron w filmie
Avatar),
•
rozmieszczenie przedmiotów
-
Borderlands
- losowe generowanie znajdywanych
broni i przedmiotów
9
,
•
liczba przeciwników
- innowacyjny moduł AI Director
10
na podstawie osiągnięć
gracza automatycznie dopasowuje do niego poziom trudności gry (Left
4 Dead),
•
efekty pogodowe
- animacja fal na wodzie, śladów na śniegu, bądź spadających
kropli deszczu również przebiega proceduralnie
11
(The
Elder Scrolls III: Morrowind
korzysta z systemu “Water Interaction” promowanego swego czasu przez NVIDIA).
Osobnym, lecz bardzo mało popularnym, gatunkiem gier komputerowych są produkcje
generowane w całości proceduralnie. Sztandarowym dziełem owej dziedziny jest
.kkrieger
12
[1] http://www.noisemachine.com/talk1/
[2] http://www.procedural.com/, http://www.planetside.co.uk/
[3] http://www.animenewsnetwork.com/feature/2011-07-15/
[4] http://chaospro.de
[5] http://diablo2.diablowiki.net/Diablo_Levels
[6] http://notch.tumblr.com/post/3746989361/terrain-generation-part-1
[7] http://www.uesp.net/wiki/Daggerfall:Quest_hacking_guide
[8] http://www.chrishecker.com/Real-time_Motion_Retargeting_to_Highly_Varied_User-Created_Morphologies
[9] http://borderlands.wikia.com/wiki/Lootable_object
[10] http://left4dead.wikia.com/wiki/The_Director
[11] http://exoed.com/source-engine-daynight-cycle-dynamic-weather/1330/
[12] http://www.theprodukkt.com/kkrieger
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin