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?

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.

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.

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

Powinieneś rzucić okiem na algorytm wyszukiwania ścieżek, taki jak algorytm Dijsktry lub algorytm A * . Oto twój problem: problem z grafem / ścieżką.

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

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.

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.

To problem ze znalezieniem ścieżki. Popularny algorytm można znaleźć na stronie http://wiki.gamedev.net/index.php/A* .

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.

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.

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

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

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

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.

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.

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.

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.

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

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ę!

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());
    }
}

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

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.

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.