1 Promotor: dr inż. Leszek Koszałka Autor: Markuszewski Kamil 171016Analiza porównawcza wybranych metod sztucznej inteligencji w komputerowych grach strategicznych Comparative analysis of artificial iteligece methods applied to strategy games Promotor: dr inż. Leszek Koszałka Autor: Markuszewski Kamil

2 Cele Wybór problemów do analizy Implementacja rozwiązańPropozycja własnych modyfikacji Porównanie rozwiązań, efektywności algorytmów Stworzenie prostej gry strategicznej

3 Sztuczna inteligencjaCo postanowiłem poruszyć: Ograniczony stan wiedzy Uwzględnienie w grafach ograniczonej wiedzy Szukanie ścieżki Przekształcanie siatki na graf (różne metody) Algorytm A* i jego modyfikacje Najkrótsza droga (różna wydajność) Logika rozmyta i Automaty stanów skończonych Cele i ocena stanu „agentów” Nasłuchiwanie, a komunikaty

4 Kryteria analizy rozwiązańCzas działania Wpływ na skomplikowanie gry Wpływ na realizm

5 Plansza gry Rozgrywka na w 2 wymiarowej przestrzeni, na kwadratowej siatce Siatka jest rozmiaru 40x40 pól W celu przeszukiwania drogi siatka odwzorowywana jest na graf

6 Ograniczony stan wiedzyGracz i SI widzi tylko określoną część mapy - realizm Pozostała część mapy pokryta jest tak zwaną „mgłą wojny” Wpływ na przeszukiwanie drogie: Częste generowanie grafu Częste dodawanie wierzchołków Mniejszy graf – prostsze przeszukiwanie

7 Reprezentacja poprzez grafOperacje na siatce Brak oddzielnych algorytmów generowania grafu! Spójne obliczenia Nieefektywne przeszukiwanie drogi Macierz sąsiedzctwa Tablica (V-1)x(V-1) (opisuje relacje wszystkich wierzchołków) Dużo pamięci Łatwe dodawanie i usuwanie krawędzi Lista sąsiedzctwa Przetrzymuje wszystkie krawędzie Nieefektywne w przypadku grafu z wieloma krawędziami

8 Reprezentacja poprzez graf

9 Algorytmy wyszukiwania drogiAlgorytm Bellmana-Forda i Algorytm Dijkstry Przeszukują cały graf Nie uwzględniają kierunku Dobre dla nieregularnych grafów Algorytm A* Uwzględnia kierunek! Bardzo dobry dla regularnych grafów (np. siatki) Opiera się na heurystycznym Algorytm A* z modyfikacjami Wygładzanie drogi

10 Pierwsze wyniki pomiarów„Rzadki” graf – mało połączeń „Gęsty” graf – dużo połączeń

11 Logika rozmyta gracza SIGracz sterowany przez SI określa swoje cele przez logikę rozmytą Stany zmieniane są przez nasłuchiwanie o zmianach lub komunikaty Obiekty należące do gracza posiadają osobny zestaw stanów Implementacja kolejki komunikatów Przy nasłuchiwaniu co klatkę widoczne opóźnienia

12 Podsumowanie metod Metoda Czas działania Wpływ na realizmWpływ na skomplikowanie Trudność implementacji Mgła wojny Ma wady i zalety Duży Średna Operacje na siatce Długi Brak Łatwa Macierz sąsiedzctwa Krótki Lista sąsiedzctwa Algorytm A* Trudna Algorytm Bellmana-Forda Mały Algorytm Djikstry Logika oparta na nasłuchiwaniu Logika oparta na komunikatach

13 Bibliografia: SI w grachPerełki programowania gier. Vademecum profesjonalisty. Dante Treglia, Mark DeLoura. Tom 1. Forum, artykuły, gotowe rozwiązania (ang.) Lista dyskusyjna, zbiór publikacji (ang.) Grafy, drzewa, algorytmy genetyczne Algorytmy i struktury danych - Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman

14 Bibliografia: Unity 3d Unity 3D Game Development by Example Beginner's Guide - Ryan Creighton (ang.) Unity Game Development Essentials - Will Goldstone (ang.) unity3d.com/ Unity: Game Development Tool (ang.) unity3d.com/support/documentation/ScriptReference/index.html (ang.) unity3d.com/support/documentation/Manual/index.html (ang.)