1 wykonał Jarosław Orski promotor pracy: mgr Szymon Smaga“Analiza i implementacja wybranych algorytmów sztucznej inteligencji w grze komputerowej” wykonał Jarosław Orski promotor pracy: mgr Szymon Smaga

2 Agenda Cele pracy Założenia gry, wymagania dla AIWybrane algorytmy i ich warianty A*, metody podziału przestrzeni poszukiwań FSM i NFA Implementacja Engine graficzny Implementacja algorytmów Możliwy rozwój projektu Prezentacja aplikacji

3 Cele Pracy Zbadanie i zaimplementowanie wybranych algorytmów AI w grze komputerowej Zbadanie współpracy platformy .NET i języka C# z otwartą bilblioteką OpenGL (Tao) Zbadanie wydajności C# jako narzędzia do tworzenia trójwymiarowych gier komputerowych

4 Założenia gry Pojedynek dwóch czołgów na wirtualnym polu walkiKażdy posiada pewną prędkość poruszania się, ostrzału i poziom energii Trafienie przeciwnika zmniejsza poziom energii Jej poziom można odnowić wracając do bazy własnej W sytuacji awarynej można użyć dopalacza Zwycięża czołg, który pozbawi przeciwnika całej energii

5 Wymagania dla AI Poruszanie się po planszy gry Omijanie przeszkódMożliwość badania otoczenia Reakcja na zmianę warunków Podejmowanie decyzji na podstawie odbieranych sygnałów Wybrane algorytmy: A*, FSM

6 Wybrane algorytmy: A* Popularny algorytm wyszukiwania ścieżkiPrzeszukuje przestrzeń stanów i wybiera optymalny z uwagi na koszt ruchu Koszt całkowity = koszt dotychczasowy + estymacja kosztu do celu Szybkość działania, wybór stanu sąsiedniego, estymacja kosztu docelowego zależą od sposobu podziału przestrzeni

7 A*: siatka prostokątnaObszar gry podzielony równomiernie w kierunku x i y Sąsiad = węzeł o indeksie różnym o 1 Estymacja kosztu do celu metodą Manhattan + Naturalność podziału + Łatwość analizy i wykrywania błędów - Liczne stany nadmiarowe - Trudność doboru rozmiaru siatki - Konieczność oznaczenia stanów zabronionych

8 A*: punkty widocznościWęzły wyznaczone przez wypukłe wierzchołki przeszkód (+ margines na obrót obiektu) Sąsiad wyznaczony przez linię widoczności Estymacja kosztu docelowego przez różnicę współrzędnych + Zmniejszona ilość węzłów, krótszy czas przeszukiwania + Niezależność od wielkości obiektów - Trudniesze wyznaczenie sąsiednich węzłów - Trudniejsze pozycjonowanie węzłów - Trudniejsza analiza

9 Automat skończony Dokładniej: Automat o skończonej liczbie stanówAlgorytm podejmowania decyzji na podstawie dostępnych informacji Zmiana stanu obiketu na podstwie docierającego sygnału i bieżącego stanu

10 FSM – automat deterministycznyStałe przejście na podstawie danego sygnału + Zwarty zapis (w postaci tablicy) + Duża szybkość - Przewidywalność “zachowań” - Mała elastyczność (brak mechanizmów uczenia się)

11 NFA – automat niedeterministycznyZ danym sygnałem związane drzewo przejść Wybór danej gąłęzi losowy +Nieprzewidywalność “zachowań” - Złożony zapis - Trudniejsza analiza

12 Implementacja Silnik graficzny: Detekcja kolizjiOparty na OpenGL (Tao) i C# Ładowanie modeli w formacie 3DS Prosty system cząsteczkowy Podstawowy pomiar wydajności: fps Możliwość modyfikacji niektórych parametrów renderingu (przezroczystość, oświetlenie) w trakcie pracy aplikacji Detekcja kolizji Oparta na OBB

13 Implementacja AI Podsystem AIMożliwość wyboru trybu pracy (wariantu) zaimplementowanych algorytmów Wizualizacja pracy Sygnały przekazywane z wykorzystaniem mechanizmu zdarzeń

14 Sharp Tankz W pełni obiektowa (C#) Główne klasy:SharpGLEngine – silnik graficzny SharpAIEngine – implementacja AI Agent – obiekt widoczny na ekranie

15 Podsumowanie Cele osiągniętoA* jest skutecznym algorytmem w zadanych warunkach prawidłowo wyznacza optymalną drogę duża szybkość wyszukiwania (szczególnie dla podziału punktami widoczności) FSM sprawdzają się w kontroli agenta szybkość działania, różnorodnośc zachowań, nieprzewidywalność (NFA) C# dobrze współpracuje z OpenGL wystarczająca wydajność (ok. 200 fps, GF4200) brak problemów z kompatybilnością

16 Możliwości rozwoju projektuRozwój systemu AI – algorytmy samouczące się (sieci neuronowe) Rozwój silnika graficznego – uszczegółowienie modeli, opracowanie tekstur, dodatkowe efekty Rozwój pozostałych podsystemów – dodanie obsługi dźwięku, gra wieloosobowa przez LAN Prezentacja: Sharp Tankz