Seminarium: Algorytmy wyszukiwania ścieżek

Język wykładowy Polski
Semestr Letni
Status W ofercie
Opiekun Jakub Kowalski
Liczba godzin 30 (sem.)
Rodzaj Seminarium
ECTS 3
Polecany dla I roku Nie
Egzamin Nie

Opis przedmiotu:

**Pathfinding algorithms** Seminarium ma na celu pokazanie, że problem wyszukiwania drogi na algorytmie A* się nie kończy, a dopiero zaczyna. A także, że jest to problem bardzo różnorodny, w praktyce występujący w wielu odmianach i często podlegający dodatkowym ograniczeniom. W tym celu chciałbym abyśmy opowiedzieli sobie m.in. o * niestandardowych funkcjach heurystycznych (rodzina ALT, ...) * hierarchicznych podejściach do przeszukiwania (HPA* i rozszerzenia) * asymetrycznych algorytmach dla grafów typu uniform grid (JPS, JPS+, ...) * wyszukiwaniu w czasie rzeczywistym (IDA*, DBA*, ...) * wyszukiwaniu przy dynamicznym środowisku (D*, D* Lite, ...) * równoczesne wyszukiwanie ścieżek dla wielu agentów * wyszukiwaniu w niestandardowych grafach (heksy, trójkąty) * tworzeniu (dobrze wyglądających) ścieżek w przestrzeni ciągłej * różnych niestandardowych zagadnieniach (np. przeszukiwanie zależne od zawartości ekwipunku postaci) Materiały przeglądowe: * [Pathfinding in Games,](http://drops.dagstuhl.de/opus/volltexte/2013/4333/pdf/4.pdf) Botea et al. * [A Comprehensive Study on Pathfinding Techniques for Robotics and Video Games](https://www.hindawi.com/journals/ijcgt/2015/736138/), Algfoor et al. * [Grid-Based Path Planning Competition](http://movingai.com/GPPC/), Sturtevant N.