System poszukiwania trasy TRASER
System poszukiwania trasy TRASER powstał jako część mojej pracy dyplomowej.
Program składa się z dwu modułów - interfejsu użytkownika pozwalającego na wybór parametrów i rozpoczęcie procesu wyszukiwania trasy oraz modułu głównego, który dokonuje faktycznego obliczenia drogi pomiędzy dwoma punktami oraz zapewnia wizualizację procesu wyznaczania trasy.
Interfejs użytkownika został napisany w języku C++, z wykorzystaniem biblioteki Qt. Zapewnia to przenośność pomiędzy różnymi platformami. Moduł główny także powstał w C++, biblioteką graficzną jest SDL, co również zapewnia przenośność kodu na wiele różnych platform.
TRASER umożliwia wyszukiwanie drogi pomiędzy dwoma punktami (dowolnie wybranymi) na mapie prostokątnej opisanej siatką kwadratową. Rozmiar mapy jest ograniczony jedynie ilością dostępnej pamięci (oraz czasem potrzebnym na wykonanie obliczeń). Punkty opisujące przeszkody mogą być wczytane z pliku, jak również edytowane za pomocą prostego edytora jeszcze przed uruchomieniem procesu wyszukiwania trasy. W celach naukowych został także zaimplementowany generator losowych przeszkód.
System wyszukiwania trasy jest konfigurowalny i może pracować według algorytmów:
- heurystycznego zachłannego
- heurystycznego optymalnego - A*
- Dijkstry
Dla algorytmu zachłannego, który nie gwarantuje znalezienia optymalnego rozwiązania, zaimplementowałem dodatkowe przetwarzanie końcowe, pozwalające niewielkim nakładem obliczeniowym znacznie poprawić jakość rozwiązania. W tym celu rozwinąłem metodę punktów widoczności, tworząc wieloprzebiegową metodę punktów widoczności, z którą jak dotąd nie spotkałem się w literaturze.
Możliwe jest także użycie różnych metryk (do oszacowania kosztu trasy w algorytmach heurystycznych) - zaimplementowałem metryki miejskie (Manhattan dla 4 i 8 sąsiadów) oraz metrykę euklidesową.
Program można pobrać w następujących wersjach:
Linux 32-bit
Poniżej znajduje się zrzut ekranu po procesie wyznaczania trasy. Kolorem czarnym zaznaczona jest wyznaczona trasa, szarym punkty brane pod uwagę w procesie wyszukiwania trasy. Przeszkody oznaczone są kolorem czerwonym.
