Pacman: w jaki sposób oczy wracają do dziury potworów?

321

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?

RoflcoptrException
źródło
11
Czy jesteś pewien, że twarde kodowanie w rogu jest wystarczająco dobre? To nie gwarantuje najlepszej trasy. Wyobraź sobie, że duch stoi przed długim, wąskim przejściem. Według twojego algorytmu musiałby zejść całym korytarzem, dotrzeć do rogu, a następnie wybrać najszybszą trasę. Jeśli na każdym kwadracie zostałeś zakodowany na stałe, w którym kierunku pójść, może wiedzieć, że najpierw się odwróci.
Mark Peters
3
@ Mark, zależy od twojej definicji w rogu. Jeśli jest to połączenie typu T, nawet jeśli przejdziesz prosto do górnej linii, jest w porządku.
Thorbjørn Ravn Andersen
1
@ Thorbjørn: Nie mówię nawet o skrzyżowaniach. Spójrz na tę tablicę: en.wikipedia.org/wiki/File:Pac-man.png . Gdyby duch poruszał się w prawo i znajdował się w drugiej kropce od lewego dolnego rogu, przez chwilę nie spotkałby się z żadnym przecięciem. Spowoduje to, że przemieści się on o 10 kwadratów dalej, niż gdyby obrócił się do tyłu (w lewo) i wybrał najkrótszą drogę.
Mark Peters
6
twoje rozwiązanie wykorzystuje punkty trasy (lub bułkę tartą) i myślę, że jest to powszechnie stosowana technika przyspieszania algorytmów wyszukiwania ścieżek.
Nick Dandoulakis
1
dzięki za wszystkie odpowiedzi! Po prostu trzymałem się mojego poprzedniego rozwiązania i na każdym rogu zakodowałem na stałe wskazówki. Aby to zrobić ogólnie, wymagane jest, aby plik leveldesigner / a level również zdefiniował te informacje w definicji poziomu.
RoflcoptrException

Odpowiedzi:

152

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:

  • kontynuuj poruszanie się w kierunku następnego skrzyżowania (chociaż jest to w zasadzie szczególny przypadek „gdy masz wybór, wybierz kierunek, który nie wymaga zmiany kierunku, jak widać w następnym kroku);
  • na skrzyżowaniu spójrz na sąsiednie kwadraty wyjściowe, z wyjątkiem tego, z którego właśnie przyszedłeś;
  • wybierając taki, który jest najbliżej celu. Jeśli więcej niż jeden jest równo w pobliżu bramki, wybierz pierwszy prawidłowy kierunek w tej kolejności: w górę, w lewo, w dół, w prawo.
Kylotan
źródło
16
Myślę, że ma na myśli, że możesz go obliczyć w czasie wykonywania (gdy poziom jest załadowany, ale zanim zaczniesz w niego grać), ale tylko raz. To nie jest trudne do utrzymania.
Mark Peters
3
Tak, lub jeśli istnieje narzędzie do tworzenia map, w ramach tego.
Kylotan
6
Nie ma nic złego w wstępnym obliczeniu ścieżek powrotnych. Wymieniasz miejsce (ścieżki) na wydajność środowiska wykonawczego.
Steve Kuo,
6
Dzięki. Myślę, że będę trzymać się tego rozwiązania. Czy ktoś wie, jak to zrobiono w oryginalnym Pacmanie?
RoflcoptrException
4
Nie ja nie. W pierwotnym pytaniu użyto tego terminu, ale nie jest on prawnie wiążący.
Kylotan
85

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.

Erich Kitzmueller
źródło
15
Tak. Floodfill jest bardzo dobry do wyszukiwania ścieżek w każdej sytuacji, w której świat nie jest zbyt duży, aby był opłacalny. Sądzę, że można by go zastosować nawet w dużych światach poprzez narzucenie grubszej siatki, której łączność została wstępnie obliczona. Sprawiłoby to, że sprawy trochę się zepsuły, ale byłoby to lepsze niż korki, które widziałem w takich grach.
Loren Pechtel
1
Aby zaoszczędzić miejsce (w przypadku większych światów lub systemów z ograniczeniami), możesz zapisać kierunek podróży na każdym skrzyżowaniu, zamiast zapisywać wartość dla każdej płytki. Właśnie to sugerował PO.
BlueRaja - Danny Pflughoeft,
BlueRaja: Jasne, ale jest to bardziej skomplikowane, a wynik nie jest tak optymalny - duch zostaje zjedzony między dwoma skrzyżowaniami, więc może przez jakiś czas wybiec w złym kierunku. Moje rozwiązanie działało dobrze na en.wikipedia.org/wiki/HP_200LX, więc o ile bardziej mogłoby być ograniczone?
Erich Kitzmueller,
5
(Jestem spóźniony ...) Tak, wypełnienie powodziowe jest dobre, jednak tak naprawdę nie potrzebujesz pełnej liczby, tylko kierunek (dwa bity) w każdym kwadracie, aby wskazać następny kwadrat do użycia.
Matthieu M.
Matthieu: Tak, to byłaby możliwa optymalizacja.
Erich Kitzmueller
42

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 ...

Dan Vinton
źródło
2
to będzie moja odpowiedź. Zasadniczo jest taki sam, jak amunicja, ale zawsze pamiętam o zapachu pacmana :)
Luke Schafer
Wygląda na to, że artykuł w Wikipedii jest martwy / usunięty. Najlepszy wynik w Google to ten wątek, ale myślę, że to się zbliża.
David
2
Przez sekundę byłem zdezorientowany, ale natychmiast zrozumiałem, co oznacza „zapach”. To świetny sposób na opisanie tych rzeczy z pola skalarnego!
Steven Lu
18

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 ...

Stephen C.
źródło
Tak, działa. Chciałbym jednak napisać dobry kod, a nie tylko kod. Dodatkowo dodałem ostatnie zdanie do mojego pytania, więc jeśli to możliwe, algorytm powinien być nie tylko dla jednego labiryntu, ale dla kilku.
RoflcoptrException
labirynty mogą być również generowane (mam algorytm, który generuje ładnie wyglądające labirynty Pacmana), więc droga do automatyzacji to droga
Erich Kitzmueller
„… lub użytkownicy mogą je zaprojektować”. W takim przypadku masz labirynt bazillionowy.
phuzion
@ phuzion - jestem tego świadomy. Istnieje jednak różnica między tymi dwoma przypadkami. Jeśli to OP tworzy labirynt bazzilion, niedogodnością jest ręczne tworzenie tras. Jeśli jest to użytkownik końcowy ... oznacza to, że OP musi pisać dokumentację, niekończące się rozwiązywanie problemów z labiryntami użytkowników końcowych, niekończące się skargi na temat tego, jak nieprzyjazny jest itp. Innymi słowy powody wdrożenia automatycznego generowania trasy są różne .
Stephen C
14

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.

Ivo Wetzel
źródło
Naprawdę podoba mi się to podejście i spróbuję również tego
RoflcoptrException
5
To nie jest poprawne; gdyby wszyscy postępowali zgodnie z tym algorytmem, goniliby go za jednym plikiem. Zachowanie każdego ducha jest inne; więcej informacji można znaleźć w artykule w Wikipedii.
dzielnik
5

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.

John Gardeniers
źródło
tak, mam już logikę, żeby ścigać Pacmana, ale już nie jestem z tego zadowolony;)
RoflcoptrException
Z mojego doświadczenia (uwielbiam pisać wersje Pacmana tylko dla zabawy), może to spowodować, że oczy utkną na zewnątrz przez długi czas. Wynika to z faktu, że algorytm ścigania zwykle przebiega w stylu „jeśli Pacman jest na północy, idź na północ”, ale labirynt może zawierać „pułapki”, w których oczy musiałyby najpierw skierować się na południe. Ponieważ Pacman się porusza, duch prędzej czy później ucieknie, ale dziura jest stałym celem. (Uwaga: mówię o wygenerowanych labiryntach)
Erich Kitzmueller
3

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.

mvbl fst
źródło
Chciałem to zasugerować. Zewnętrzne wypełnienie zalewowe rozpoczynające się od „potwornej dziury”. Myślę, że twoja odpowiedź przydałaby się ze zdjęcia.
AjahnCharles,
3

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.

Midpipps
źródło
2

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 =)

Hernán Eche
źródło
2
Aby dodać jeszcze więcej realizmu, pozwól, aby same duchy mogły poruszać się przez ściany: D
Thomas Eding
3
Są to nieprzezroczyste ściany ducha, ale duchy drugiego rzędu (duch ducha) są bardziej przezroczyste. (można znaleźć wiele instrukcji obsługi z błędami przekształconymi w funkcje)
Hernán Eche
1
+1 za „duchy drugiego rzędu” - och tak, pochodna ducha z pewnością musi wykraczać poza zwykłe przedmioty pierwszego rzędu, takie jak ściany ... :)
Assad Ebrahim
2

Oto analogowy i pseudokod pomysłu na wypełnienie amunicji.

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

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).

Mark Peters
źródło
2

Nie wiem wiele o tym, jak zaimplementowałeś swoją grę, ale możesz wykonać następujące czynności:

  1. Określ położenie oczu względem położenia względem bramy. tj. czy pozostało powyżej? Tuż pod?
  2. Następnie przesuń oczy przeciwne do jednego z dwóch kierunków (na przykład skieruj je w lewo, jeśli znajduje się na prawo od bramy i poniżej bramy) i sprawdź, czy istnieją przeszkody i ściany, które to uniemożliwiają.
  3. Jeśli istnieją przeszkody, aby to zrobić, przesuń go w przeciwnym kierunku (na przykład, jeśli współrzędne oczu w stosunku do szpilki znajdują się na północ i aktualnie poruszają się w lewo, ale jest ściana po drodze idź na południe.
  4. Pamiętaj, aby za każdym razem sprawdzać ruch, aby sprawdzać, gdzie znajdują się oczy w stosunku do bramy i sprawdzać, czy nie ma współrzędnych wzdłużnych. tzn. jest tylko nad bramą.
  5. W przypadku, gdy jest tylko nad bramą, zejdź w dół, jeśli jest ściana, przesuń się w lewo lub w prawo i wykonuj tę liczbę od 1 do 4, aż oczy znajdą się w jaskini.
  6. Nigdy nie widziałem ślepego zaułka w Pacmanie, ten kod nie uwzględnia ślepych zaułków.
  7. Dodałem również rozwiązanie, kiedy oczy „chwieją się” między ścianą rozciągającą się na początku w moim pseudokodzie.

Niektóre pseudokod:

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile

źródło
2

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.

imoatama
źródło
2

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.

dwidel
źródło
2

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.

Fischer Ludrian
źródło
2
ta ścieżka najprawdopodobniej będzie za długa
Ahmad Y. Saleh
Za każdym razem, gdy ponownie odwiedzasz węzeł, możesz wyeliminować pętlę z historii. To uczyniłoby to nieco bardziej bezpośrednim. Może być bardziej interesujący niż zawsze podążanie tą samą bezpośrednią ścieżką, ale dość często będzie zawierał pewne dość głupie prawie pętle (np. 3 boki kwadratu).
AjahnCharles
1

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.

Incognito
źródło
1

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ą.

cokół
źródło
1
  1. Przed rozpoczęciem gry zapisz węzły (skrzyżowania) na mapie
  2. Kiedy potwór umrze, weź punkt (współrzędne) i znajdź najbliższy węzeł na liście węzłów
  3. Oblicz wszystkie ścieżki zaczynające się od tego węzła do otworu
  4. Wybierz najkrótszą drogę według długości
  5. Dodaj długość odstępu między punktem a najbliższym węzłem
  6. Rysuj i poruszaj się po ścieżce

Cieszyć się!

GingerHead
źródło
1

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:

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

Wypełnij powódź z legowiska

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:

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

Przykład w pełni oznakowany

Pełna mapa

AjahnCharles
źródło
0

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 crossroadsą puste (domyślnie), a gdy duchy zaczną badać labirynt, będą crossroad path home informationsię aktualizować za każdym razem, gdy napotkają „nowe” skrzyżowanie lub inną ścieżkę potkną się ponownie na znanym skrzyżowaniu.

iNyuu
źródło
-2

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.

użytkownik4664601
źródło
tak, użył trochę sztucznej inteligencji. I tak Blinky podąża za Pacmanem, gdy jest w trybie pościgowym (od czasu do czasu przełącza się na niego), więc wszystko w porządku
Jean-François Fabre