Znalazłem wiele odniesień do sztucznej inteligencji duchów w Pacmanie, ale żadne z nich nie wspomniało, w jaki sposób oczy wracają do centralnej dziury duchów po zjedzeniu ducha przez Pacmana.
W mojej implementacji wdrożyłem proste, ale okropne rozwiązanie. Po prostu zakodowałem na każdym rogu, który kierunek należy obrać.
Czy jest jakieś lepsze / lub najlepsze rozwiązanie? Może ogólny, który działa z różnymi projektami poziomów?
artificial-intelligence
path-finding
heuristics
pacman
RoflcoptrException
źródło
źródło
Odpowiedzi:
Właściwie powiedziałbym, że twoje podejście jest dość niesamowitym rozwiązaniem, przy prawie zerowym koszcie czasu pracy w porównaniu do dowolnego rodzaju poszukiwania ścieżki.
Jeśli potrzebujesz go do uogólnienia na dowolne mapy, możesz użyć dowolnego algorytmu wyszukiwania ścieżki - na przykład proste wyszukiwanie w pierwszej kolejności jest łatwe do zaimplementowania - i użyć go do obliczenia kierunków, które należy zakodować w każdym z rogów, przed uruchomieniem gry.
EDYCJA (11 sierpnia 2010 r.): Właśnie odniosłem się do bardzo szczegółowej strony w systemie Pacman: Dokumentacja Pac-Mana i ponieważ otrzymałem tutaj akceptowaną odpowiedź, czułem, że powinienem ją zaktualizować. Artykuł nie wydaje się wyraźnie opowiadać o powrocie do domu potworów, ale stwierdza, że bezpośrednie wyszukiwanie ścieżki w Pac-Manu jest następujące:
źródło
W ten sposób rozwiązałem ten problem dla ogólnych poziomów: Zanim zacznie się poziom, wykonuję jakieś „wypełnienie zalewowe” z otworu potwora; każda płytka labiryntu, która nie jest ścianą, otrzymuje liczbę określającą odległość od dziury. Kiedy więc oczy znajdują się na kafelku o odległości 68, patrzą, który z sąsiednich kafelków ma odległość 67; to jest właśnie droga.
źródło
Jako alternatywę dla bardziej tradycyjnych algorytmów wyszukiwania ścieżek, możesz rzucić okiem na (odpowiednio nazwany!) Wzór Anti-Object Scent Pac-Man Scent .
Podczas uruchamiania można było rozproszyć zapach potwornej dziury wokół labiryntu, a oczy podążyły za nim do domu.
Po skonfigurowaniu zapachu koszt działania jest bardzo niski.
Edytuj: niestety artykuł z Wikipedii został usunięty, więc WayBack Machine na ratunek ...
źródło
Powinieneś rzucić okiem na algorytm wyszukiwania ścieżek, taki jak algorytm Dijsktry lub algorytm A * . Oto twój problem: problem z grafem / ścieżką.
źródło
Każde proste rozwiązanie, które działa, jest łatwe w utrzymaniu, niezawodne i działa wystarczająco dobrze, jest dobrym rozwiązaniem. Wydaje mi się, że znalazłeś już dobre rozwiązanie ...
Rozwiązanie do poszukiwania ścieżki może być bardziej skomplikowane niż obecne rozwiązanie, a zatem może wymagać debugowania. Prawdopodobnie będzie też wolniejszy.
IMO, jeśli nie jest zepsute, nie naprawiaj tego.
EDYTOWAĆ
IMO, jeśli labirynt jest naprawiony, to twoje obecne rozwiązanie jest dobrym / eleganckim kodem. Nie popełniaj błędu, utożsamiając „dobry” lub „elegancki” z „sprytnym”. Prosty kod może być również „dobry” i „elegancki”.
Jeśli masz konfigurowalne poziomy labiryntu, być może powinieneś po prostu znaleźć ścieżkę przy początkowej konfiguracji labiryntów. Najprościej byłoby poprosić projektanta labiryntu, aby zrobił to ręcznie. Zaabsorbowałbym to automatyzacją tylko, jeśli masz bazillionowe labirynty ... lub użytkownicy mogą je zaprojektować.
(Poza tym: jeśli trasy są konfigurowane ręcznie, projektant labiryntu może uczynić poziom bardziej interesującym, używając tras nieoptymalnych ...
źródło
W oryginalnym Pacmanie Duch znalazł żółtego zjadacza pigułek po swoim „zapachu”, pozostawi ślad na mapie, duch wędruje losowo, dopóki nie znajdzie zapachu, a następnie po prostu podąży ścieżką zapachu, która prowadzi ich bezpośrednio do gracz. Za każdym razem, gdy Pacman się poruszał, „wartości zapachu” zmniejszały się o 1.
Teraz prostym sposobem na odwrócenie całego procesu byłoby posiadanie „piramidy zapachu ducha”, która ma najwyższy punkt na środku mapy, a następnie duch porusza się w kierunku tego zapachu.
źródło
Zakładając, że masz już logikę wymaganą do ścigania Pacmana, dlaczego nie użyć tego ponownie? Po prostu zmień cel. Wydaje się, że byłoby to o wiele mniej pracy niż próba stworzenia zupełnie nowej procedury przy użyciu tej samej logiki.
źródło
To problem ze znalezieniem ścieżki. Popularny algorytm można znaleźć na stronie http://wiki.gamedev.net/index.php/A* .
źródło
Co powiesz na każdy kwadrat mający wartość odległości od centrum? W ten sposób dla każdego kwadratu można uzyskać wartości kwadratów najbliższego sąsiada we wszystkich możliwych kierunkach. Wybierz kwadrat o najniższej wartości i przejdź do tego kwadratu.
Wartości zostaną wstępnie obliczone przy użyciu dowolnego dostępnego algorytmu.
źródło
To było najlepsze źródło, jakie mogłem znaleźć na temat tego, jak to naprawdę działa.
http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Gdy duchy zostaną zabite, ich bezcielesne oczy wracają do miejsca początkowego. Dokonuje się tego po prostu poprzez ustawienie płytki docelowej ducha w tym miejscu. Nawigacja wykorzystuje te same reguły.
To ma sens. Może nie jest to najbardziej wydajny na świecie, ale całkiem niezły sposób, aby nie martwić się o inny stan lub coś podobnego, zmieniając cel.
Uwaga dodatkowa: nie zdawałem sobie sprawy z tego, jak niesamowici byli programiści Pac-Mana, którzy w zasadzie stworzyli cały system komunikatów na bardzo małej przestrzeni z bardzo ograniczoną pamięcią ... to niesamowite.
źródło
Myślę, że twoje rozwiązanie jest odpowiednie dla problemu, prościej jest uczynić nową wersję bardziej „realistyczną”, w której oczy duchów mogą przechodzić przez ściany =)
źródło
Oto analogowy i pseudokod pomysłu na wypełnienie amunicji.
Chodzi o to, że jest to pierwsze wyszukiwanie szerokości, więc za każdym razem, gdy napotkasz nowe sąsiadujące kwadraty, najlepszą ścieżką jest p. Wierzę, że to O (N).
źródło
Nie wiem wiele o tym, jak zaimplementowałeś swoją grę, ale możesz wykonać następujące czynności:
Niektóre pseudokod:
źródło
Sugestia dtb23, by po prostu wybrać losowy kierunek na każdym rogu, a ostatecznie okaże się, że potwór brzmi okropnie nieskutecznie.
Możesz jednak skorzystać z jego nieefektywnego algorytmu powrotu do domu, aby uczynić grę przyjemniejszą, wprowadzając większą różnorodność trudności gry. Zrobiłbyś to, stosując jedno z powyższych podejść, takie jak punkty trasy lub wypełnienie powodziowe, ale robiąc to w sposób niedeterministyczny. Więc na każdym rogu możesz wygenerować losową liczbę, aby zdecydować, czy wybrać optymalną drogę, czy losowy kierunek.
W miarę postępów gracza zmniejszasz prawdopodobieństwo przyjęcia losowego kierunku. Dodałoby to kolejną dźwignię na ogólnym poziomie trudności oprócz prędkości poziomu, prędkości ducha, przerwy na zjadanie pigułek (itp.). Masz więcej czasu na relaks, podczas gdy duchy są po prostu nieszkodliwymi oczami, ale czas ten staje się coraz krótszy w miarę postępów.
źródło
Krótka odpowiedź, niezbyt dobrze. :) Jeśli zmienisz labirynt Pac-mana, oczy niekoniecznie wrócą. Niektóre z pływających hacków mają ten problem. To zależy od posiadania labiryntu kooperacyjnego.
źródło
Proponuję, aby duch przechował ścieżkę, którą wybrał z dołka do Pacmana. Gdy tylko duch umrze, może podążać zapisaną ścieżką w odwrotnym kierunku.
źródło
Wiedząc, że ścieżki Pacmana są nieprzypadkowe (tj. Każdy konkretny poziom 0-255, atramentowy, mrugający, różowawy i clyde będą działały dokładnie tak samo jak dla tego poziomu).
Zrozumiałbym to, a potem zgaduję, że istnieje kilka ścieżek mistrzowskich, które owijają się wokół całego labiryntu jako „ścieżka powrotna”, którą krąży obiekt gałki ocznej tam, gdzie jest, gdy pac man zjadł ducha.
źródło
Duchy w Pacman podążają za mniej lub bardziej przewidywalnymi wzorami, jeśli chodzi o próbę dopasowania najpierw na X lub Y, dopóki cel nie zostanie osiągnięty. Zawsze zakładałem, że to samo dotyczy oczu, które wracają.
źródło
Cieszyć się!
źródło
Moje podejście wymaga trochę pamięci (z perspektywy epoki Pacmana), ale wystarczy tylko raz obliczyć i działa na każdym poziomie projektowania (w tym skokach).
Oznacz węzły raz
Podczas pierwszego ładowania poziomu oznacz wszystkie węzły legowiska potworów 0 (reprezentujące odległość od legowiska). Kontynuuj etykietowanie na zewnątrz połączonych węzłów 1, połączonych z nimi węzłów 2 itd., Aż wszystkie węzły zostaną oznaczone. (uwaga: działa to nawet, jeśli legowisko ma wiele wejść)
Zakładam, że masz już obiekty reprezentujące każdy węzeł i połączenia z ich sąsiadami. Pseudo kod może wyglądać mniej więcej tak:
Oczy przenoszą się na sąsiada z etykietą najniższej odległości
Gdy wszystkie węzły zostaną oznaczone, przekierowanie oczu jest banalne ... wystarczy wybrać sąsiedni węzeł z etykietą o najniższej odległości (uwaga: jeśli wiele węzłów ma równą odległość, nie ma znaczenia, który zostanie wybrany). Pseudo kod:
Przykład w pełni oznakowany
źródło
Dla mojej gry PacMan stworzyłem nieco „
shortest multiple path home
” algorytm, który działa dla każdego labiryntu, który mu zapewniam (w ramach mojego zestawu zasad). Działa również w ich tunelach.Gdy poziom jest załadowany, wszystkie
path home data in every crossroad
są puste (domyślnie), a gdy duchy zaczną badać labirynt, będącrossroad path home information
się aktualizować za każdym razem, gdy napotkają „nowe” skrzyżowanie lub inną ścieżkę potkną się ponownie na znanym skrzyżowaniu.źródło
Pierwotny pac-man nie używał poszukiwania ścieżki ani wyszukanej sztucznej inteligencji. Właśnie sprawiło, że gracze uwierzyli, że jest w tym więcej głębi, niż było w rzeczywistości, ale w rzeczywistości była losowa. Jak stwierdzono w Artificial Intelligence for Games / Ian Millington, John Funge.
Nie jestem pewien, czy to prawda, czy nie, ale ma to dla mnie sens. Szczerze mówiąc, nie widzę tych zachowań, o których mówią ludzie. Red / Blinky na przykład przez cały czas nie śledzi gracza, jak mówią. Wydaje się, że nikt celowo nie konsekwentnie śledzi gracza. Szansa, że pójdą za tobą, wygląda dla mnie losowo. Bardzo kuszące jest obserwowanie losowości, szczególnie gdy szanse na ściganie są bardzo duże, z 4 wrogami i bardzo ograniczonymi opcjami skrętu na małej przestrzeni. Przynajmniej w początkowej implementacji gra była niezwykle prosta. Sprawdź książkę, jest w jednym z pierwszych rozdziałów.
źródło