Jak stworzyć losowy labirynt pacman

Question

Witam Pracowałem nad algorytmem generowania losowego labiryntu pacman. Widziałem kilka artykułów, ale nie mogłem złamać logiki. Używam najpierw algorytmu głębi algorytmu labiryntu, a potem lustruję labirynt, aby każdy labirynt był symetryczny. Zajmuję się problemami, takimi jak czyszczenie ślepych zaułków. Jeśli nie jest to możliwe, spróbuję zastosować inny algorytm, jeśli ktoś ma własną logikę do generowania losowego labiryntu. Każda pomoc jest doceniana. Dzięki

Answer 1

Proponuję zrobić losowy spacer przez dfs w czystym obszarze (bez ściany, w macierzy n * n 0), po czym wypełnić obszary, które nie są objęte przypadkowym spacerem (zrób to jak ściana), może to również spowodować niewykorzystanie przestrzeni, ale ta gwarancja długiego spaceru. możesz ustawić rozmiar spaceru dowolnie (np. kiedy twój rozmiar spaceru osiągnął (n^2)/2, możesz zatrzymać spacer).

Answer 2

Rozwiązałem mój problem i chciałem się nim podzielić. Na początek ustawiłem górny rząd, pierwszą kolumnę i ostatnią kolumnę jako przeszkodę na ścianie, a następnie ustawiłem ścieżkę na drugiej kolumnie, drugim do ostatniego rzędu i drugim rzędzie, tak aby otoczyła zewnętrzną ścianę. Pamiętaj też, że tworzę tylko 50% labiryntu, więc kiedy skończę, kopiuję labirynt, aby obie strony były równe. Potem stworzyłem środkową sekcję otoczoną murem dla obszaru, w którym odradzają się duchy. Następnie jakakolwiek część labiryntu, na którą nie spojrzałem, wygenerowałem ścieżki za pomocą pierwszego algorytmu wyszukiwania głębi. Po tym wszystkim wiem, że w labiryncie pacmana nie ma ślepych zaułków. To, co zrobiłem, to sprawdzenie każdej komórki, która jest częścią ścieżki, którą pacman może podróżować. Jeśli jakakolwiek komórka ma tylko jedną graniczącą komórkę, to jest ślepy zaułek. Jeśli jest to ślepy zaułek, sprawdź, czy można go podłączyć do innej ścieżki. Jeśli nie, ustaw ślepy zaułek jako ścianę i sprawdź labirynt w poszukiwaniu ślepych zaułków. Po wykonaniu tych kroków będziesz miał losowy labirynt bez ślepych zaułków, który przypomina typowy labirynt Pacmana.

Answer 3

Stworzyłem losowy generator labiryntu PacMan dawno temu na C = 64, wykorzystując najpierw głębokość i eliminując ślepy zaułek, ale ostatnio zostałem zakwestionowany przez mojego przyjaciela, aby zrobić to ponownie. Znalazłem lepszy sposób. Sprawdź to pod adresem: my site

Zasadniczo stworzyłem siatkę pokoi z każdym kierunkiem z otwartymi drzwiami (zamkniętymi na granicy z wyjątkiem miejsca, w którym przebiega tunel), a następnie zacznij zamykanie drzwi losowo zgodnie z zasadą, że nigdy nie powinno być być więcej niż 1 zamkniętymi drzwiami w sąsiednim pokoju, jeśli 2 drzwi są zamknięte, a trzeci tworzy ślepy zaułek. Po prostu rób to losowo, aż wszystkie potencjalne drzwi będą zamknięte lub otwarte według reguły.

Dublowanie było trochę więcej pracy, ale zacząłem od podstaw i po prostu zbudowałem reguły, aby umożliwić tworzenie kopii lustrzanych, lokalizację duchów, minimalną długość ściany (bez pojedynczych rond ściennych) i maksymalną długość ściany itp.