Kilka pytań dotyczących odnajdywania ścieżek pacman

Question

Dowiedziałem się o A *, BFS, DFS i mogę je całkiem dobrze zastosować. Jednak niektóre problemy pojawiają się, gdy próbuję to zrobić, rozwiązując problem ze znalezieniem ścieżki pacmana. Przyjmijmy, że istnieją tylko dwa typy labiryntów: jeden ma pełne przedmioty, ponieważ w pustym polu wszystko jest albo pacmanem, albo przedmiotem do zebrania albo ścianą; a jeden ma tylko kilka przedmiotów (4 lub mniej).

1. Jak dokładnie są BFS i DFS realizowane, jeśli nie masz więcej niż jeden element, aby zbierać? W takim razie czy nadal dają optymalny wynik?

2. Jaki jest najlepszy algorytm/heurystyka dla mapy całego przedmiotu? To, co do tej pory wymyśliłem, jest czymś w rodzaju chciwej heurystyki, ale jest całkiem przypadkowe, ponieważ mapa ma zbyt wiele przedmiotów do zebrania i dlatego nie jest dobrym pomysłem na rozwiązanie tego labiryntu.

3. Korzystanie z A *, na mapie z kilkoma pozycjami, czy istnieje dobry sposób na określenie, który przedmiot powinien zostać pobrany jako pierwszy? Pomyślałem o próbie wykorzystania odległości Mahattan jako przybliżonej oceny, ale to nie brzmi dobrze, szczególnie w niektórych trudnych sytuacjach.

Answer 1

Algorytmy się nie zmieniają, jeśli dodasz więcej jedzenia. Jedyną zmianą jest przestrzeń stanu. Musisz wymyślić nowy sposób reprezentowania twojego problemu. Kiedy masz tylko jedno jedzenie, potrzebujesz tylko pozycji x, y pacmana. Kiedy na przykład masz 3 kropki do zjedzenia, musisz dodać te informacje do swojego modelu. Możesz dodać 3 zmienne binarne, aby wskazać, że pacman przeszedł kropkę. Teraz już przestrzeń stanów jest wykres z węzłów następujących typów:

((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food 
((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food 
((x,y),TRUE,TRUE,TRUE) -> this is the goal state 

Aby rozwiązać ten problem wystarczy uruchomić ten sam algorytm w swoim nowym modelu. BFS i A * zawsze zapewniają optymalne rozwiązanie. Problem polega na tym, że im więcej żywności wkładasz, tym wolniej znajdziesz rozwiązanie. Tak więc algorytmy te nie dadzą odpowiedzi w rozsądnym czasie. Wymyśliłeś nowy sposób robienia tego.

Answer 2

1) Problem związany z korzystaniem z BFS lub DFS w tej sytuacji jest taki, jak nieskuteczny, w szczególności w pełnym przykładzie mapy. Aby algorytm działał z wieloma celami, można albo zbudować wyszukiwanie, aby nie kończyło się po znalezieniu pierwszej ścieżki, ale to nadal nie dałoby "optymalnej" ścieżki dla każdego kawałka jedzenia na mapie albo możesz zrobić ścieżkę od pacmana do najbliższego jedzenia, tego jedzenia do najbliższego najbliższego itd., znaleźć te ścieżki, a następnie porównać je, aby znaleźć naprawdę optymalną ścieżkę, ale nie chcę myśleć o tym, jak długo to potrwa. brać.

2) Pewnie trzymałbym się z chciwym A *, który patrzy tylko na najbliższe jedzenie (w większości przypadków nie widzę problemu z odległością od manhattanu, ponieważ mapa dla pacmana jest już siatką; być nieoptymalnym dla przypadków krawędziowych, w których ściany powstrzymują Pacmana przed dostępem do najbliższego, ale jest to trudny problem do rozwiązania, Manhattan byłby przyzwoity, prawdopodobnie zmodyfikowany przez gęstość jedzenia zamiast odległości, coś w stylu: (odległość manhattan)/(całkowite jedzenie w 3 x 3 kwadracie jedzenia)

3) Krótki z wykorzystaniem odnajdywania ścieżki na każdym przedmiocie, a następnie wybór najkrótszego, myślę, że manhattan zrobiłoby się dobrze w scenariuszu z kilkoma pozycjami. Nie zawsze wybierze najlepszą, ale w 100% optymalna sztuczna inteligencja nie jest zwykle najlepszym celem w grach.

W tym przypadku chciałbym wypróbować chciwego A * z wagą faworyzującą skupiska przedmiotów jako proste, przyzwoicie szybkie rozwiązanie.

Bardziej skomplikowane rozwiązanie, które powinny powrócić bliżej optymalnych ścieżek dla Pacman śledzić byłoby użyć algorytmu znaleźć Minimum Spanning Tree http://en.wikipedia.org/wiki/Minimum_spanning_tree ale nie wiem, jak łatwo byłoby wdrożyć. Oto pytanie omawiające zalety dwóch algorytmów Minimum Spanning Tree: Kruskal vs Prim