Wyczerpujący przegląd nowoczesnych technik
Zaawansowane algorytmy sztucznej inteligencji
Realistyczne odwzorowywanie zjawisk fizycznych, efektów dźwiękowych i oświetlenia
Języki skryptowe i sterowanie danymi
Techniki zabezpieczania gier w wersji beta
Przemysł gier komputerowych jest jedną z najszybciej rozwijających się branż informatyki. Gry, które jeszcze niedawno zapierały dech w piersiach, dziś wydają się proste i mało realistyczne. Współczesne symulatory i 'strzelanki' to arcydzieła, których produkcja angażuje środki porównywalne z budżetami hollywoodzkich superprodukcji. Rosnące w ogromnym tempie możliwości komputerów i konsoli wpływają jednak nie tylko na jakość gier, ale także na proces ich tworzenia i wykorzystywane podczas niego narzędzia. Programiści tworzący gry implementują zaawansowane algorytmy sztucznej inteligencji, wykorzystują niezwykłe możliwości układów wyświetlających grafikę i skomplikowany aparat matematyczny.
Książka 'Perełki programowania gier. Vademecum profesjonalisty. Tom 6' to doskonałe kompendium wiedzy dla wszystkich, którzy tworzą gry komputerowe lub zamierzają to robić. W każdym rozdziale, napisanym przez cenionego eksperta z tej branży, znajdziesz niezbędne informacje dotyczące różnych aspektów pisania gier. Przeczytasz o sztucznej inteligencji, symulacji zjawisk fizycznych oraz odwzorowywaniu oświetlenia i dźwięków. Poznasz nowoczesne techniki programowania współbieżnego, optymalizacji kodu pod kątem maszyn wieloprocesorowych, stosowania języków skryptowych i wykorzystywania możliwości procesorów graficznych.
Programowanie pod kątem procesorów wielordzeniowych
Siatkowa reprezentacja obiektów gry
Testowanie pojedynczych modułów gry
Optymalizacja korzystania z zasobów
Rachunek wektorowy i macierzowy
Symulacja zachowania cieczy
Tworzenie algorytmów sztucznej inteligencji
Korzystanie z reguł logiki rozmytej
Programowanie skryptowe w językach Lua i Python
Optymalizacja wyświetlania obiektów gry
Wykorzystywanie możliwości procesorów graficznych
Generowanie efektów dźwiękowych w czasie rzeczywistym
Tworzenie gier sieciowych
Przeczytaj i stwórz grę, w którą zagrają miliony graczy.
Darmowy fragment publikacji:
Pere‡ki programowania gier.
Vademecum profesjonalisty.
Tom 6
Autor: Mike Dickheiser
T‡umaczenie: Andrzej Gra¿yæski (wstŒp, czŒ(cid:156)ci I-III,
VI-VII); Miko‡aj Szczepaniak (czŒ(cid:156)ci IV-V)
ISBN: 978-83-246-1087-7
Tytu‡ orygina‡u: Game Programming
Gems 6 (Book CD-ROM)
Format: B5, stron: oko‡o 700
oprawa twarda
Zawiera CD-ROM
Wyczerpuj„cy przegl„d nowoczesnych technik tworzenia gier komputerowych
(cid:149) Zaawansowane algorytmy sztucznej inteligencji
(cid:149) Realistyczne odwzorowywanie zjawisk fizycznych, efekt(cid:243)w d(cid:159)wiŒkowych i o(cid:156)wietlenia
(cid:149) JŒzyki skryptowe i sterowanie danymi
(cid:149) Techniki zabezpieczania gier w wersji beta
Przemys‡ gier komputerowych jest jedn„ z najszybciej rozwijaj„cych siŒ bran¿ informatyki. Gry,
kt(cid:243)re jeszcze niedawno zapiera‡y dech w piersiach, dzi(cid:156) wydaj„ siŒ proste i ma‡o realistyczne.
Wsp(cid:243)‡czesne symulatory i (cid:132)strzelanki(cid:148) to arcydzie‡a, kt(cid:243)rych produkcja anga¿uje (cid:156)rodki
por(cid:243)wnywalne z bud¿etami hollywoodzkich superprodukcji. Rosn„ce w ogromnym tempie
mo¿liwo(cid:156)ci komputer(cid:243)w i konsoli wp‡ywaj„ jednak nie tylko na jako(cid:156)(cid:230) gier, ale tak¿e na proces ich
tworzenia i wykorzystywane podczas niego narzŒdzia. Programi(cid:156)ci tworz„cy gry implementuj„
zaawansowane algorytmy sztucznej inteligencji, wykorzystuj„ niezwyk‡e mo¿liwo(cid:156)ci uk‡ad(cid:243)w
wy(cid:156)wietlaj„cych grafikŒ i skomplikowany aparat matematyczny.
Ksi„¿ka (cid:132)Pere‡ki programowania gier. Vademecum profesjonalisty. Tom 6(cid:148) to doskona‡e
kompendium wiedzy dla wszystkich, kt(cid:243)rzy tworz„ gry komputerowe lub zamierzaj„ to robi(cid:230).
W ka¿dym rozdziale, napisanym przez cenionego eksperta z tej bran¿y, znajdziesz niezbŒdne
informacje dotycz„ce r(cid:243)¿nych aspekt(cid:243)w pisania gier. Przeczytasz o sztucznej inteligencji,
symulacji zjawisk fizycznych oraz odwzorowywaniu o(cid:156)wietlenia i d(cid:159)wiŒk(cid:243)w. Poznasz nowoczesne
techniki programowania wsp(cid:243)‡bie¿nego, optymalizacji kodu pod k„tem maszyn
wieloprocesorowych, stosowania jŒzyk(cid:243)w skryptowych i wykorzystywania mo¿liwo(cid:156)ci procesor(cid:243)w
graficznych.
(cid:149) Programowanie pod k„tem procesor(cid:243)w wielordzeniowych
(cid:149) Siatkowa reprezentacja obiekt(cid:243)w gry
(cid:149) Testowanie pojedynczych modu‡(cid:243)w gry
(cid:149) Optymalizacja korzystania z zasob(cid:243)w
(cid:149) Rachunek wektorowy i macierzowy
(cid:149) Symulacja zachowania cieczy
(cid:149) Tworzenie algorytm(cid:243)w sztucznej inteligencji
(cid:149) Korzystanie z regu‡ logiki rozmytej
(cid:149) Programowanie skryptowe w jŒzykach Lua i Python
(cid:149) Optymalizacja wy(cid:156)wietlania obiekt(cid:243)w gry
(cid:149) Wykorzystywanie mo¿liwo(cid:156)ci procesor(cid:243)w graficznych
(cid:149) Generowanie efekt(cid:243)w d(cid:159)wiŒkowych w czasie rzeczywistym
(cid:149) Tworzenie gier sieciowych
Przeczytaj i stw(cid:243)rz grŒ, w kt(cid:243)r„ zagraj„ miliony graczy
Wydawnictwo Helion
ul. Ko(cid:156)ciuszki 1c
44-100 Gliwice
tel. 032 230 98 63
e-mail: helion@helion.pl
Spis treści
Przedmowa ........................................................................................ 13
Wstęp ................................................................................................. 17
O obrazku z okładki ......................................................................... 23
Biografie autorów ............................................................................. 25
Część I Programowanie w ogólności ............................................... 43
Wprowadzenie .................................................................................. 45
Rozdział 1.1 Algorytmy nieblokujące .................................................................. 47
„Porównaj i zamień” oraz inne prymitywy uniwersalne ............................................... 48
Parametryzowany stos nieblokujący .............................................................................. 50
Parametryzowana kolejka nieblokująca ......................................................................... 54
Nieblokująca parametryzowana lista wolnych bloków pamięci .................................... 57
Konkluzja ....................................................................................................................... 58
Literatura cytowana ....................................................................................................... 59
Zasoby ............................................................................................................................ 60
Rozdział 1.2 Wykorzystanie możliwości procesorów wielordzeniowych
przy użyciu OpenMP ........................................................................ 61
Przykład: system cząstek ............................................................................................... 62
Korzyści ......................................................................................................................... 62
Wydajność ..................................................................................................................... 63
Przykład: wykrywanie kolizji ........................................................................................ 64
Zespoły wątkowe ........................................................................................................... 65
Zrównoleglanie wykonywania funkcji .......................................................................... 65
Tak, ale… ...................................................................................................................... 67
Konkluzja ....................................................................................................................... 68
Literatura cytowana ....................................................................................................... 68
Zasoby ............................................................................................................................ 68
Rozdział 1.3 Widzenie komputerowe w grach
— programowanie z użyciem biblioteki OpenCV ........................ 69
Komputerowe widzenie w grach ................................................................................... 69
Biblioteka Open Computer Vision ................................................................................ 70
Przykład zastosowania ................................................................................................... 70
Co dalej? ........................................................................................................................ 79
Literatura cytowana ....................................................................................................... 79
4
Perełki programowania gier. Vademecum profesjonalisty. Tom 6
Rozdział 1.4
Rozdział 1.5
Siatkowa rejestracja obiektów gry ................................................. 81
Drzewa czwórkowe i ósemkowe ................................................................................... 82
Organizacja obiektów .................................................................................................... 84
Konkluzja ....................................................................................................................... 88
Literatura cytowana ....................................................................................................... 88
Techniki BSP ....................................................................................... 89
Czym jest BSP? Dlaczego BSP? ................................................................................... 89
Węzłowe BSP ................................................................................................................ 90
Renderowanie obiektów w węzłowym wariancie BSP ................................................. 93
Bezpodziałowy wariant węzłowego BSP ...................................................................... 94
Liściaste BSP i regiony wypukłe ................................................................................... 95
Generowanie portali między regionami wypukłymi ..................................................... 98
Generowanie zbiorów PVS .......................................................................................... 100
Kompresja wektora widzialności ................................................................................. 105
Obiekty krajobrazu w drzewie BSP ............................................................................. 107
Konkluzja ..................................................................................................................... 108
Literatura cytowana ..................................................................................................... 108
Rozdział 1.6 Dopasowywanie łańcuchów ......................................................... 109
Wyszukiwanie opierające się na identyfikatorach tekstowych .................................... 109
No to mamy problem… ............................................................................................... 110
Kilka znanych rozwiązań ............................................................................................. 110
Nasze rozwiązanie ....................................................................................................... 111
Zastosowanie rozwiązania ........................................................................................... 116
Konkluzja ..................................................................................................................... 117
Literatura cytowana ..................................................................................................... 117
Rozdział 1.7
Rozdział 1.8
Rozdział 1.9
Implementacja testowania modułów na bazie CppUnit ........... 119
Ogólnie o testowaniu modułów ................................................................................... 119
Ogólnie o pakiecie CppUnit ........................................................................................ 120
Uruchamianie klas mocujących ................................................................................... 122
Wykorzystanie pakietu CppUnit do testowania klasy zarządzającej modelami .......... 123
Testowanie modułowe funkcji prywatnych ................................................................. 129
Wykorzystywanie CppUnit do testowania niskopoziomowej funkcjonalności .......... 129
Konkluzja ..................................................................................................................... 134
Literatura cytowana ..................................................................................................... 134
Fingerprinting jako metoda ochrony wersji pre-release aplikacji ...135
Zniechęcanie ................................................................................................................ 135
Znaki wodne i odciski palców ..................................................................................... 136
Wykonywanie znakowania .......................................................................................... 137
Bezpieczeństwo gwarantowane przez znakowanie ..................................................... 137
Strategie znakowania ................................................................................................... 137
Atak porównawczy ...................................................................................................... 140
Konkluzja ..................................................................................................................... 140
Literatura cytowana ..................................................................................................... 141
Przyspieszanie ładowania zasobów
na podstawie statystyki korzystania z nich .................................. 143
Sformułowanie problemu ............................................................................................ 143
Optymalizowanie kolejności zasobów ........................................................................ 145
Czynniki wpływające na wynik pomiaru .................................................................... 146
Potencjalne zagrożenia ................................................................................................ 147
Powszechne praktyki optymalizacyjne ........................................................................ 147
Spis treści
5
Konkluzja ..................................................................................................................... 148
Literatura cytowana ..................................................................................................... 148
Rozdział 1.10 Pozostań w grze:
podmiana modyfikowanych zasobów „na gorąco” ................. 149
Jak to działa? ................................................................................................................ 149
Anatomia procesu ........................................................................................................ 151
Uwarunkowania praktyczne ........................................................................................ 155
Przykładowy program .................................................................................................. 156
Konkluzja ..................................................................................................................... 156
Literatura uzupełniająca ............................................................................................... 156
Część II Matematyka i fizyka .......................................................... 157
Wprowadzenie ................................................................................ 159
Rozdział 2.1 Osobliwości arytmetyki zmiennopozycyjnej ............................... 161
Format reprezentacji zmiennopozycyjnej .................................................................... 162
Projektowanie programów i funkcji ............................................................................ 167
Konkluzja ..................................................................................................................... 179
Literatura cytowana ..................................................................................................... 180
Rozdział 2.2 Obliczenia w przestrzeniach rzutowych
z użyciem współrzędnych jednorodnych .................................... 181
Podstawy matematyczne .............................................................................................. 182
Obliczenia z użyciem współrzędnych jednorodnych ................................................... 184
Przecinanie linii z obiektami ....................................................................................... 187
Konkluzja ..................................................................................................................... 189
Dodatek A .................................................................................................................... 190
Dodatek B .................................................................................................................... 190
Podziękowania ............................................................................................................. 191
Literatura cytowana ..................................................................................................... 191
Zastosowanie iloczynu wektorowego
do rozwiązywania układów równań liniowych ........................... 193
Wprowadzenie ............................................................................................................. 193
Linie proste .................................................................................................................. 196
Efektywna interpolacja bilinearna ............................................................................... 198
Rozwiązywanie układu równań z trzema niewiadomymi ........................................... 201
Konkluzja ..................................................................................................................... 203
Podziękowania ............................................................................................................. 203
Literatura cytowana i zalecana .................................................................................... 203
Indeksowanie sekwencyjne w programowaniu gier ................. 205
Terminologia ................................................................................................................ 205
Sekwencje .................................................................................................................... 206
Sekwencje dziedzinowe ............................................................................................... 207
Sekwencje permutacyjne ............................................................................................. 210
Sekwencje kombinacyjne ............................................................................................ 214
Konkluzja ..................................................................................................................... 217
Literatura cytowana ..................................................................................................... 218
Pływalność brył wielościennych ................................................... 219
Pływalność ................................................................................................................... 220
Pole wielokąta .............................................................................................................. 221
Rozdział 2.3
Rozdział 2.4
Rozdział 2.5
6
Perełki programowania gier. Vademecum profesjonalisty. Tom 6
Objętość wielościanu ................................................................................................... 223
Częściowe zanurzenie .................................................................................................. 224
Dokładność obliczeń .................................................................................................... 227
Siły oporu ..................................................................................................................... 229
Kod źródłowy .............................................................................................................. 230
Konkluzja ..................................................................................................................... 230
Podziękowanie ............................................................................................................. 230
Literatura cytowana ..................................................................................................... 231
Rozdział 2.6 Cząsteczkowa symulacja w czasie rzeczywistym
oddziaływania cieczy z bryłami sztywnymi ................................. 233
Symulacja przepływów cieczy a SPH ......................................................................... 233
Rozszerzenie metody SPH na oddziaływania cieczy z bryłami sztywnymi ................ 238
Oddziaływanie z obiektami dynamicznymi — krokowa aktualizacja własności cząstek ...242
Szczegóły implementacji ............................................................................................. 243
Optymalizacje .............................................................................................................. 247
Konkluzja ..................................................................................................................... 248
Literatura cytowana ..................................................................................................... 248
Część III Sztuczna inteligencja ........................................................ 249
Wprowadzenie ................................................................................ 251
Rozdział 3.1
Zastosowanie modelowanego podejścia do implementacji AI
na przykładzie Locust AI Engine w QA3 ....................................... 253
Wprowadzenie ............................................................................................................. 254
Stan obecny — zbiory reguł deterministycznych ........................................................ 255
Problemy związane z regułami .................................................................................... 257
Modelowane podejście do implementacji AI .............................................................. 259
Interfejs ........................................................................................................................ 260
Zalety i korzyści dla projektantów .............................................................................. 261
Locust AI Engine w Quake III Arena .......................................................................... 263
Soar .............................................................................................................................. 264
Konkluzja ..................................................................................................................... 265
Literatura cytowana ..................................................................................................... 265
Rozdział 3.2 Koordynacja działań autonomicznych BN .................................. 267
Możliwe rozwiązania ................................................................................................... 268
Struktura BN ................................................................................................................ 269
Mechanizmy koordynacji ............................................................................................ 270
Przykład. Skoordynowane tropienie gracza ................................................................. 277
Konkluzja ..................................................................................................................... 278
Literatura cytowana ..................................................................................................... 279
Rozdział 3.3
Zastosowanie behawioralnych architektur robotycznych
w tworzeniu gier .............................................................................. 281
Architektura subsumpcyjna ......................................................................................... 282
Rozszerzone sieci behawioralne .................................................................................. 285
Dyskusja ...................................................................................................................... 289
Konkluzja ..................................................................................................................... 289
Literatura cytowana ..................................................................................................... 290
Spis treści
7
Rozdział 3.4 Konstruowanie sterowanego celem robota gry Unreal
Tournament przy użyciu czujników rozmytych, maszyn
skończenie stanowych i rozszerzonych sieci behawioralnych ..... 291
Projektowanie rozszerzonej sieci behawioralnej ......................................................... 292
Hierarchiczne czujniki rozmyte ................................................................................... 298
Moduły behawioralne jako maszyny skończenie stanowe .......................................... 301
Konkluzja ..................................................................................................................... 303
Literatura cytowana ..................................................................................................... 303
Rozdział 3.5 Robot sterowany celem:
projektowanie zachowań i cech osobowości agenta gry
przy użyciu rozszerzonych sieci behawioralnych ....................... 305
Rozszerzone sieci behawioralne .................................................................................. 306
Jakość wyboru akcji ..................................................................................................... 311
Projektowanie cech osobowości .................................................................................. 314
Konkluzja ..................................................................................................................... 317
Literatura zalecana ....................................................................................................... 318
Rozdział 3.6 Modelowanie pamięci krótkotrwałej
Rozdział 3.7
Rozdział 3.8
Rozdział 3.9
przy użyciu maszyny wektorów wspierających ........................... 319
Maszyny wektorów wspierających .............................................................................. 319
Modelowanie pamięci krótkotrwałej ........................................................................... 325
Limitowanie obciążenia procesorów ........................................................................... 326
Konkluzja ..................................................................................................................... 326
Literatura cytowana ..................................................................................................... 327
Zastosowanie modelu oceny kwantytatywnej
do analizy konfliktów zbrojnych ................................................... 329
Formuła podstawowa ................................................................................................... 330
Obliczanie siły ognia ................................................................................................... 330
Obliczanie potencjału bojowego .................................................................................. 331
Szacowanie efektywności użycia broni ....................................................................... 332
Teoretyczne przewidywanie wyniku konfliktu ............................................................ 333
A co z efektywnością wykorzystania broni? ............................................................... 334
Przykład systemu QJM ................................................................................................ 334
Ograniczenia ................................................................................................................ 335
Konkluzja ..................................................................................................................... 335
Literatura cytowana ..................................................................................................... 336
Projektowanie wielowarstwowego, przyłączalnego silnika AI .. 337
Rozwiązania pokrewne ................................................................................................ 338
Architektura silnika AI ................................................................................................ 339
Klasy i właściwości systemu sterowanego danymi ..................................................... 340
Priorytetowy zarządca zadań ....................................................................................... 345
Wydajność i techniki optymalizacyjne ........................................................................ 346
Narzędzia ..................................................................................................................... 348
Konkluzja ..................................................................................................................... 350
Literatura cytowana ..................................................................................................... 351
Zarządzanie złożonością scenerii na bazie reguł logiki rozmytej .. 353
Koncepcja .................................................................................................................... 353
Regulacja rozmyta ....................................................................................................... 354
Narzędzia ..................................................................................................................... 354
Projekt systemu ............................................................................................................ 357
Zastosowanie do gier ................................................................................................... 358
8
Perełki programowania gier. Vademecum profesjonalisty. Tom 6
Założenia ...................................................................................................................... 359
Uwagi implementacyjne .............................................................................................. 360
Testy i ich rezultat ....................................................................................................... 360
Konkluzja ..................................................................................................................... 362
Podziękowanie ............................................................................................................. 362
Literatura cytowana ..................................................................................................... 363
Część IV Skrypty i systemy sterowane danymi ............................. 365
Wprowadzenie ................................................................................ 367
Rozdział 4.1
Przegląd języków skryptowych ..................................................... 371
Po co w ogóle stosować języki skryptowe? ................................................................. 371
Wprowadzenie ............................................................................................................. 371
Sposób kodowania ....................................................................................................... 372
Integracja z językami C/C++ ....................................................................................... 377
Wydajność ................................................................................................................... 384
Metody wspierania procesów wytwarzania ................................................................. 387
Konkluzja ..................................................................................................................... 390
Literatura ...................................................................................................................... 390
Rozdział 4.2 Wiązanie obiektów C/C++ ze skryptami języka Lua .................. 391
Funkcje wiążące ........................................................................................................... 392
Wiązanie właściwych obiektów z wartościami języka Lua ......................................... 394
Wiązanie obiektów środowiska nadrzędnego z obiektami języka Lua ....................... 397
Wiązanie właściwych obiektów z tabelami języka Lua .............................................. 402
Konkluzja ..................................................................................................................... 403
Literatura ...................................................................................................................... 406
Rozdział 4.3
Rozdział 4.4
Programowanie zaawansowanych mechanizmów sterujących
z wykorzystaniem współprogramów języka Lua ......................... 407
Współprogramy Lua .................................................................................................... 408
Filtry ............................................................................................................................ 409
Iteratory ........................................................................................................................ 411
Mechanizmy szeregowania zadań ............................................................................... 414
Wielozadaniowość równoległa .................................................................................... 415
Konkluzja ..................................................................................................................... 419
Literatura ...................................................................................................................... 419
Zarządzanie wykonywaniem skryptów wysokopoziomowych
w ramach środowisk wielowątkowych ........................................ 421
Oprogramowanie komponentowe i interpreter skryptu ............................................... 422
Współprogramy i mikrowątki ...................................................................................... 422
Menedżer mikrowątków .............................................................................................. 423
Osadzanie kodu języka Python .................................................................................... 426
Eksperymenty i wyniki ................................................................................................ 429
Konkluzja ..................................................................................................................... 431
Literatura ...................................................................................................................... 432
Rozdział 4.5 Udostępnianie właściwości aktorów
z wykorzystaniem nieinwazyjnych pośredników ........................ 433
Aktorzy, pośrednicy i właściwości. Mój Boże! ........................................................... 433
Nieinwazyjna i dynamiczna architektura ..................................................................... 435
Właściwości aktora ...................................................................................................... 436
Pośrednicy aktorów ..................................................................................................... 440
Spis treści
9
Rozdział 4.6
Od teorii do praktyki .................................................................................................... 442
Konkluzja ..................................................................................................................... 443
Literatura ...................................................................................................................... 443
System komponentowy obiektów gry .......................................... 445
Obiekty gry .................................................................................................................. 445
Komponenty bazowe obiektów gry ............................................................................. 447
Zarządzanie komponentami z poziomu obiektów gry ................................................. 448
Komunikacja pomiędzy komponentami ...................................................................... 450
Szablony komponentów gry ........................................................................................ 451
Szablony obiektów gry ................................................................................................ 454
Tworzenie obiektu gry sterowanego danymi ............................................................... 455
Konkluzja ..................................................................................................................... 455
Część V Grafika ................................................................................ 457
Wprowadzenie ................................................................................ 459
Rozdział 5.1
Synteza realistycznych ruchów nieaktywnych postaci w grze . 461
Wprowadzenie ............................................................................................................. 462
Główne składowe animacji ciała ludzkiego ................................................................. 463
Zmiany postaw ............................................................................................................. 465
Ciągłe, drobne zmiany postaw ..................................................................................... 469
Konkluzja ..................................................................................................................... 474
Literatura ...................................................................................................................... 474
Rozdział 5.2 Dzielenie przestrzeni
z wykorzystaniem adaptacyjnego drzewa binarnego .............. 477
Budowa adaptacyjnego drzewa binarnego .................................................................. 477
Szczegółowa implementacja drzewa ABT .................................................................. 479
Poszukiwanie odpowiednich płaszczyzn dzielących ................................................... 483
Stosowanie drzew ABT dla scen dynamicznych ......................................................... 486
Wizualizacja drzewa ABT ........................................................................................... 487
Konkluzja ..................................................................................................................... 489
Podziękowania ............................................................................................................. 489
Literatura ...................................................................................................................... 489
Rozdział 5.3 Rozszerzony mechanizm eliminowania obiektów z wykorzystaniem
(niemal) całkowicie ukierunkowanych ramek ograniczających ...491
Przegląd znanych metod .............................................................................................. 492
Techniki tradycyjne ..................................................................................................... 493
Efektywne rozwiązanie dla dwóch wymiarów ............................................................ 494
Udoskonalenia technik tradycyjnych ........................................................................... 496
Eliminowanie obiektów według ramki ograniczającej ................................................ 500
Dalsze usprawnienia .................................................................................................... 501
Konkluzja ..................................................................................................................... 502
Literatura ...................................................................................................................... 503
Podział powierzchni z myślą o optymalizacji renderingu .......... 505
Wprowadzenie ............................................................................................................. 505
Koncepcje podziału ..................................................................................................... 506
Heurystyka podziału wag ............................................................................................ 508
Heurystyka palety kości ............................................................................................... 508
Szczegółowe omówienie heurystyki ............................................................................ 511
Konkluzja ..................................................................................................................... 515
Rozdział 5.4
10
Perełki programowania gier. Vademecum profesjonalisty. Tom 6
Rozdział 5.5 Rendering terenu na poziomie procesora GPU .......................... 517
Prosty algorytm ............................................................................................................ 518
Poziom szczegółowości ............................................................................................... 519
Eliminowanie szczelin ................................................................................................. 521
Odrzucanie obiektów spoza ostrosłupa widoczności ................................................... 523
Wyznaczanie normalnych ............................................................................................ 523
Unikanie kolizji ........................................................................................................... 525
Problemy implementacyjne ......................................................................................... 526
Wyniki ......................................................................................................................... 527
Konkluzja ..................................................................................................................... 528
Literatura ...................................................................................................................... 528
Rozdział 5.6
Rozdział 5.7
Interaktywna dynamika cieczy i rendering na poziomie GPU .. 529
Podstawy matematyczne .............................................................................................. 530
Implementacja na poziomie GPU ................................................................................ 534
Interakcja z cieczą ........................................................................................................ 540
Materiały dodatkowe ................................................................................................... 542
Konkluzja ..................................................................................................................... 542
Literatura ...................................................................................................................... 543
Szybkie oświetlanie poszczególnych pikseli
w środowisku z wieloma źródłami światła ................................... 545
Rozwiązanie polegające na odkładaniu efektów oświetlenia na później .................... 546
Implementacja odłożonego cieniowania dla najnowszych kart graficznych ............... 547
Podstawowe techniki optymalizacji składowania danych ........................................... 549
Optymalizacja shaderów i ograniczenia sprzętowe ..................................................... 552
Rozszerzanie efektów przetwarzania końcowego przestrzeni obrazu ......................... 555
Konkluzja ..................................................................................................................... 556
Literatura ...................................................................................................................... 556
Rozdział 5.8 Rendering ostrych znaków drogowych ....................................... 557
Wygładzanie krawędzi tekstur progowanych .............................................................. 559
Optymalne tekstury dla techniki progowania .............................................................. 564
Aplikacja autorska ....................................................................................................... 568
Konkluzja i perspektywa rozwoju ............................................................................... 571
Literatura ...................................................................................................................... 572
Rozdział 5.9
Praktyczny rendering nieba na potrzeby gier komputerowych ......573
Czego chcemy, a co mamy? ........................................................................................ 573
Co właściwie powinno się znaleźć na niebie? ............................................................. 575
Wąskie gardła .............................................................................................................. 576
Wprowadzenie sześciennej mapy nieba ...................................................................... 579
Skalowanie czasu ......................................................................................................... 580
Analiza aplikacji demonstracyjnej ............................................................................... 581
Kierunki rozwoju ......................................................................................................... 582
Konkluzja ..................................................................................................................... 583
Literatura ...................................................................................................................... 584
Rozdział 5.10 Rendering rozszerzonego zakresu jasności (HDR)
z wykorzystaniem obiektów bufora klatek biblioteki OpenGL .. 585
Wprowadzenie do obiektów bufora klatek .................................................................. 585
Konstruowanie obiektów bufora klatek ....................................................................... 587
Rendering rozszerzonego zakresu jasności (HDR) za pomocą obiektów bufora klatek ......590
Konkluzja ..................................................................................................................... 592
Informacje dodatkowe ................................................................................................. 593
Literatura dodatkowa ................................................................................................... 593
Spis treści
11
Część VI Audio ................................................................................. 595
Wprowadzenie ................................................................................ 597
Rozdział 6.1 Generowanie dźwięku w czasie rzeczywistym
poprzez deformację siatkową brył sztywnych ............................ 599
Retrospekcja ................................................................................................................ 599
Ogólne zasady .............................................................................................................. 600
Podstawy analizy modalnej ......................................................................................... 601
Ograniczenia ................................................................................................................ 603
Od deformacji do dźwięku ........................................................................................... 604
Konkluzja ..................................................................................................................... 605
Literatura zalecana ....................................................................................................... 605
Literatura cytowana ..................................................................................................... 606
Prosty generator efektów dźwiękowych czasu rzeczywistego . 607
Silnik akustyki otoczeniowej ....................................................................................... 607
Synteza dźwięku .......................................................................................................... 608
Przykłady ze świata rzeczywistego .............................................................................. 610
Konkluzja ..................................................................................................................... 612
Demo ............................................................................................................................ 613
Literatura cytowana ..................................................................................................... 613
Rozdział 6.2
Rozdział 6.3 Miksowanie dźwięku w czasie rzeczywistym .............................. 615
Niby nic, a jednak… .................................................................................................... 615
Implementacja łańcucha magistral ............................................................................... 617
Miara głośności — stosunek natężeń albo decybele ................................................... 619
Zapobieganie nieefektywności .................................................................................... 620
Inne usprawnienie ........................................................................................................ 620
Konkluzja ..................................................................................................................... 620
Literatura cytowana ..................................................................................................... 621
Rozdział 6.4
Rozdział 6.5
Rozdział 6.6
Zbiór potencjalnej słyszalności ..................................................... 623
PVS — podstawy ......................................................................................................... 623
PAS — algorytm podstawowy .................................................................................... 625
Bezpośrednie ścieżki dźwiękowe ................................................................................ 625
Rozszerzenie na falę przechodzącą .............................................................................. 630
Rozszerzenie na falę odbitą ......................................................................................... 631
Konkluzja ..................................................................................................................... 632
Literatura cytowana ..................................................................................................... 632
Tani efekt Dopplera ........................................................................ 633
Zjawisko Dopplera ....................................................................................................... 633
Programowanie efektu Dopplera ................................................................................. 636
Zmienna prędkość ........................................................................................................ 639
Aliasowanie ................................................................................................................. 640
Implementacja .............................................................................................................. 641
Konkluzja ..................................................................................................................... 641
Zasoby .......................................................................................................................... 641
Preparowanie efektów specjalnych ............................................ 643
Preparacja .................................................................................................................... 643
Przykład: radio grające w pokoju ................................................................................ 644
Krzywe stałej głośności ............................................................................................... 645
Zaawansowane sterowanie głośnością ......................................................................... 646
12
Perełki programowania gier. Vademecum profesjonalisty. Tom 6
Pliki wielościeżkowe i DirectSound ............................................................................ 646
Koszty i korzyści ......................................................................................................... 647
Konkluzja ..................................................................................................................... 647
Podziękowania ............................................................................................................. 647
Część VII Sieć i gry wielodostępne ................................................ 649
Wprowadzenie ................................................................................ 651
Rozdział 7.1 Dynamicznie adaptowalne strumieniowanie danych 3D
dla animowanych postaci ............................................................. 653
Wprowadzenie ............................................................................................................. 653
Podstawy i zagadnienia pokrewne ............................................................................... 654
Przygotowywanie i tworzenie skalowalnych danych 3D ............................................ 655
Sterowana kontekstem adaptacja wysyłanego strumienia ........................................... 662
Konkluzja ..................................................................................................................... 664
Literatura cytowana ..................................................................................................... 665
Rozdział 7.2 Wysokopoziomowa architektura systemowa
dla masywnych gier online ........................................................... 667
Systemy złożone i ich zachowanie wzbogacające ....................................................... 668
Architektura wielowarstwowa ..................................................................................... 668
Sprzężenie zwrotne w systemach decyzyjnych ........................................................... 680
Konkluzja ..................................................................................................................... 681
Literatura cytowana ..................................................................................................... 681
Rozdział 7.3 Generowanie unikalnych identyfikatorów globalnych
Rozdział 7.4
Rozdział 7.5
dla obiektów gier ........................................................................... 683
Wymagania dla identyfikatorów GUID ....................................................................... 683
Generowanie GUID ..................................................................................................... 685
Sytuacje wyjątkowe i ich obsługa ................................................................................ 687
Konkluzja ..................................................................................................................... 688
Literatura cytowana ..................................................................................................... 688
jako narzędzie prototypowania gier MMOG .......... 689
Second Life
Wstęp ........................................................................................................................... 689
Dlaczego Second Life? ................................................................................................ 689
Second Life — zaczynamy! ......................................................................................... 693
Second Life jako narzędzie projektanta ....................................................................... 693
Opracowywanie prototypu ........................................................................................... 695
Tringo — historia sukcesu ........................................................................................... 698
Konkluzja ..................................................................................................................... 698
Literatura cytowana ..................................................................................................... 699
Niezawodne połączenia TCP peer-to-peer
w warunkach translacji NAT .......................................................... 701
Problem ........................................................................................................................ 701
Rozwiązania ................................................................................................................. 703
Realizacja ..................................................................................................................... 703
Zastosowania ............................................................................................................... 708
Ograniczenia ................................................................................................................ 709
Konkluzja ..................................................................................................................... 709
Literatura cytowana ..................................................................................................... 710
Skorowidz ........................................................................................ 711
Rozdział 3.1
Zastosowanie
modelowanego podejścia
do implementacji AI
na przykładzie
Locust AI Engine w QA3
Armand Prieditis, Lookahead Decisions Inc.
prieditis@lookaheaddecisions.com
Mukesh Dalal, Lookahead Decisions Inc.
mukesh@lookaheaddecisions.com
Tworzenie dobrych gier w oparciu o AI jest naprawdę trudną sztuką. Tradycyjna filozo-
fia tej sztuki opera się na regułach (ang. rules), które — niestety — są często nieprecy-
zyjne, a ich definiowanie, implementowanie, debugowanie i modyfikowanie — dość
kosztowne. W dodatku często bywa i tak, iż ostateczny rezultat zastosowania owych re-
guł zdaje się mieć z jakąkolwiek inteligencją niewiele wspólnego. W niniejszym arty-
kule opisujemy alternatywne podejście do sztucznej inteligencji — podejście oparte na
modelowaniu realnego świata, w którym rozgrywa się scenariusz, czyli świata akcji, ich
efektów i obserwacji. Jest to podejście bardziej niezawodne, elastyczne i skutkujące in-
teligentniejszym zachowaniem aktorów gry; w charakterze przykładu przedstawimy
dotychczasowe rezultaty jego zastosowania w postaci silnika Locust AI Engine na po-
trzeby gry Quake III. Skoncentrujemy się głównie na korzyściach, jakie użytkownik gry
zyskuje dzięki sztucznej inteligencji, i z tej perspektywy przedstawimy wizję przyszłych
jej zastosowań.
254
Część III Sztuczna inteligencja
Wprowadzenie
Z rysunku 3.1.1 wynika, że współczesne gry komputerowe osiągają swój realizm, czer-
piąc z trzech dziedzin wiedzy: grafiki, fizyki i sztucznej inteligencji. Co prawda, samo
pojęcie „realizmu” trudno jednoznacznie zdefiniować w sposób formalny, niemniej jed-
nak intuicyjnie przekłada się ono w pierwszym rzędzie na zaangażowanie, jakie staje się
udziałem gracza, i inteligencję przejawianą w zachowaniu tzw. bohaterów niezależnych
(BN, z angielskiego Non-Player Characters — NPC)1: wygląd i zachowanie obiektów
zbliżone jest mocno do rzeczywistości, a działania bohaterów niezależnych wydają się
racjonalne. Te właśnie względy są nawet ważniejsze niż kreowanie „niezwyciężonych”
przeciwników.
Rysunek 3.1.1.
Gry komputerowe
jako kombinacja
zastosowań
trzech technologii
Bo do tworzenia „niepokonanych” wcale nie jest konieczna sztuczna inteligencja —
często wystarcza zwyczajne oszustwo czy nieuczciwość. Nietrudno przecież stworzyć
BN, który bezbłędnie, natychmiast odnajduje kryjówkę przeciwnika (w którego wciela
się gracz); zachowaniem bardziej realistycznym (mimo iż, oczywiście, mniej skutecz-
nym) jest jednak przeszukiwanie terenu, budynku itp. przypominające racjonalne postę-
powanie. W ten oto sposób interes gracza postawiony zostaje ponad interesem jego
przeciwnika; tego właśnie gracze od nas oczekują i to powinno stanowić nasz cel, cel
projektantów.
W dwóch cytowanych na rysunku 3.1.1 dziedzinach — grafice komputerowej i oblicze-
niowych zastosowaniach fizyki —na przestrzeni kilku ostatnich lat poczyniono olbrzy-
mi postęp. Oszałamiające możliwości takich narzędzi jak Maya czy 3D Max są obecnie
raczej normą niż wyjątkiem, a pakiety fizyczne w rodzaju Havok ułatwiają programo-
wanie realistycznych scen. Z tego powodu ani grafika, ani realistyczne symulacje zja-
wisk fizycznych nie są już dziś tymi czynnikami, które decydują o powodzeniu gier
w kręgach ich użytkowników. Jeśli natomiast chodzi o sztuczną inteligencję, to daje ona
większą okazję do twórczej inwencji i nowatorstwa, bo nie był jej udziałem żywiołowy
rozwój, jakiego doświadczyli dwaj jej partnerzy. Pozostająca niejako w ich cieniu nie
doczekała się też (na razie) żadnego wsparcia sprzętowego, więc siłą rzeczy związane
z nią obliczenia obciążają bezpośrednio procesory centralne (CPU), co stawia przed
programistami nowe wyzwania, ale też daje im szerokie pole do popisu. Z drugiej jed-
Patrz http://pl.wikipedia.org/wiki/Bohater_niezale C5 BCny — przyp. tłum.
1
Rozdział 3.1 Zastosowanie modelowanego podejścia do implementacji AI
255
nak strony, powierzenie wielu skomplikowanych funkcji koprocesorom graficznym
zmniejsza obciążenie CPU, których moc przeznaczyć można tym samym w większym
stopniu na potrzeby AI. W niniejszym artykule przedstawimy kilka przykładów wyko-
rzystania tej sposobności.
Stan obecny — zbiory reguł deterministycznych
W większości współczesnych gier pierwiastek sztucznej inteligencji manifestuje się po-
przez reguły. Każda reguła jest parą o postaci „sytuacja → akcja” — gdy stwierdzone
zostanie wystąpienie (zaistnienie) określonej sytuacji, uruchamia się właściwą dla niej
akcję, którą może być pojedynczy ruch obiektu, sekwencja takich ruchów określona
przez skrypt czy też zachowanie bardziej złożone, reprezentowane przez klip wideo.
I tak np. widoczność wroga i słaba kondycja gracza to sytuacja nakazująca odwrót tego
ostatniego, podobnie jak stwierdzenie wyraźnej przewagi wroga pod względem uzbro-
jenia. Animacja prezentowana w związku z akcją może być wyświetlana przez ustalony
odcinek czasu bądź też do momentu kolejnego „dopasowania” aktualnej sytuacji do
jednej z reguł. „Sytuacja” (jako składnik reguły) może mieć niekiedy postać skompli-
kowanej formuły boole’owskiej — w przedstawionym przykładzie jest to alternatywa
niewyłączająca (OR) dwóch okoliczności.
Inną popularną regułą, związaną z poszukiwaniem ścieżek, jest wybór przez BN naj-
krótszej drogi prowadzącej do określonego celu. Przy braku dynamicznych przeszkód
i innych agentów AI reguła ta sprawdza się całkiem dobrze.
Sposoby dopasowywania aktualnej sytuacji do konkretnej reguły mogą być zróżnico-
wane. Niekiedy proces dopasowywania może być sterowany za pomocą drzewa decy-
zyjnego, czego przykład przedstawiliśmy na rysunku 3.1.2: węzły drzewa reprezentują
wówczas pewne zdefiniowane a priori okoliczności elementarne, zaś każdy z liści —
jedną ze zdefiniowanych akcji. Na wspomnianym rysunku wszystko zaczyna się od
sprawdzenia, czy BN ma sprawną broń; jeśli tak, sprawdza się, czy znajduje się on do-
statecznie blisko przeciwnika. Spełnienie obu tych reguł wyzwala akcję, którą jest atak;
jak łatwo zauważyć, atak może być również podjęty w jeszcze jednej sytuacji — BN nie
ma broni, ale stwierdza, że przeciwnik, jako niższy wzrostem, jest słabszy fizycznie
i można go pokonać w walce wręcz.
Każda ze ścieżek, prowadząca w drzewie decyzyjnym od jego korzenia do jednego z li-
ści, reprezentuje więc pojedynczą regułę „sytuacja → akcja”, przy czym „sytuacja” zde-
finiowana jest przez ciąg odwiedzanych po drodze węzłów, zaś „akcja” reprezentowana
jest przez liść kończący ścieżkę. Mimo iż drzewo decyzyjne stanowi bardzo oszczędną
formę kodowania reguł, to pod względem zawartości informacyjnej jest ono równoważne
klasycznemu zbiorowi par „sytuacja → akcja”.
Innym środkiem kodowania reguł są maszyny skończenie stanowe (ang. Finite State
Machines — FSM). Maszyna taka składa się ze zbioru (zdefiniowanych a priori) stanów2,
z których każdy odpowiada określonej akcji oraz (reprezentowanych w formie łuków)
Z wyróżnionym stanem początkowym — przyp. tłum.
2
256
Część III Sztuczna inteligencja
przejść między stanami, odpowiadających testowaniu sytuacji [Rabin02]. W maszynie
FSM widocznej na rysunku 3.1.3 stanem początkowym może być BEZCZYNNOŚĆ, odpo-
wiadająca bezczynności BN, aż do momentu ujrzenia wroga, ki
Pobierz darmowy fragment (pdf)
