Skocz do zawartości

jak tam sylwek?


Chell

Rekomendowane odpowiedzi

Napisałem Sokobana i algorytm sprawdzający podstawowe (oczywiście, nie wszystkie) warunki, czy dana plansza jest solvable*. W głowie mam obraz kodu wykrywcza deadlocków, tj. sytuacji oraz segmentów, które gwarantują nierozwiązywalność planszy, np. cztery zbite obok siebie skrzynki:

 

xMM4wUc.png

 

Niestety chęci i sił mi nie starczyło, by rzetelnie dokończyć ten problem (innymi metodami niż brute force czy naiwną heurystyką) więc rzuciłem zagadnienie; natomiast zająłem się samym poruszaniem gracza po klocowatej planszy i zredukowałem planszę do multigrafu, a w zasadzie klasy abstrakcji multigrafów, w której każde dwa grafy o wszystkich jednakowych tunelach (tj. ścieżce z punktu A do B, dla której istnieje tylko jedna trasa łącząca te punkty, niezależnie jak ułożona i jakiej długości) są sobie równoważne. Gdyby tylko istniał dobry soft, który ogarnia struktury grafów, napisałbym algorytm redukujący graf do grafu minimalnego. Dodatkowo sformułowałem twierdzenie, które orzeka o tym, czy dla danego grafu istnieje plansza, której odpowiadający graf jest równoważny z danym (np. żaden graf o węzłach stopnia większych niż 4 nie ma swojej reprezentacji na dwuwymiarowej planszy, skoro kierunki ograniczone są przez górę, dół, lewo oraz prawo).

 

No i przy okazji nabiłem parę leveli w klasycznym Sokobanie, a dzień później padła mi płyta główna w komputerze. Dlatego bez rysunku dot. powyższego :(.

 

Na temat Sokobana napisano parę prac naukowych oraz artykułów:

http://www.whatisthought.com/schaulthesis.pdf

http://liacs.leidenuniv.nl/~takesfw/pdf/sokoban.pdf

http://weetu.net/Timo-Virkkala-Solving-Sok...ters-Thesis.pdf

 

Zapaleni mogą nawet napisać pracę magisterską/doktorską z informatyki w ramach tego tematu, problem nie jest trywialny, a rozwiązanie planszy w tej grze jest problemem PSPACE-complete-trudnym.

 

* - wlicza się w to sprawdzenie, czy:

  • ? plansza jest zamknięta,

? wszystkie segmenty plansze są osiągalne,

? liczba skrzynek i miejsc "parkowania" się zgadza,

? każdą skrzynkę z osobna daje się prawidłowo umieścić,

? nie istnieje skrzynka, której nie można ruszyć z miejsca niezależnie od posunięć gracza.

Odnośnik do komentarza
Udostępnij na innych stronach

Nic dziwnego, pochodzi z oryginału :).

 

A oto przykład redukcji planszy do grafu minimalnego. Niech to będzie nasza przykładowa plansza:

 

UAENwSN.png

 

Zredukujmy ją do grafu:

 

m6PVV8G.png

 

Możemy usunąć oczywiste węzły z tuneli z grafu:

 

ud63RNT.png

 

Pozostaje wyeliminować wszystkie węzły o stopniu 2, które nie są sprzężone same ze sobą (na nasze szczęście nie ma tu takich)*:

 

oYa83VB.png

 

Voila! Ostatecznie możemy sobie narysować graf (pisane ręcznie numerki oznaczają stopnie węzłów):

 

9dJNNyD.jpg

 

i zapisać w postaci listy

 

[[1,2],[2,3],[2,4],[3,4],[3,5],[5,6;2]]

 

Oczywiście ciekawszy jest problem odwrotny, tj, jak z grafu "odzyskać" planszę 2D, o ile istnieje**.

 

Wynik można uogólnić na plansze 3D i wyższego wymiaru (wówczas limit stopnia węzła wynosi oczywiście 2n).

 

No, a wy jak bawiliście się w Sylwka? Bo ja fajnie, nie to co Nikas, który musiał pić alkohol, żeby się dobrze bawić.

 

* - węzeł może być "bezkarnie" usunięty wtedy i tylko wtedy, jeżeli jest stopnia drugiego oraz nie jest połączony sam ze sobą.

** - jakąkolwiek, wiadomo, że plansze są równoważne, jeżeli odpowiadające im grafy są równoważne; możemy szukać minimalnej planszy, ale na pierwszy raz nie ma co się ograniczać takimi warunkami.

 

PS Warto zwrócić uwagę, że gdyby można było poruszać się na ukos, pętla po prawej nie byłaby równoważna dużej pętli ze środka.

Odnośnik do komentarza
Udostępnij na innych stronach

  • Filar Społeczności

a jakby tak połączyć gwint butelki wódki z ustami?

 

nieee, co ja gadam, jakieś pojebane, na pewno by się nie udało

Odnośnik do komentarza
Udostępnij na innych stronach

W sumie z logicznego punktu widzenia wybór jest trudny ale jednego dnia można zrobić wyjątek i spędzić jednak ten dzień z ludźmi żywymi (no chyba, że ktoś spędza sylwestra w kostnicy albo przy kompie).

Odnośnik do komentarza
Udostępnij na innych stronach

  • 5 tygodni później...

Tak gdyby kogoś interesowało*, wykończyłem algorytm, który sprawdza, czy plansze są topologicznie równoważne, tj. w pewnym sensie niewiele się od siebie różnią, jeżeli chodzi o układ pomieszczeń. Dla wygody kod napisałem w Mathematice (by móc łatwo operować adekwatnymi strukturami: grafami).

 

bSevS6C.png

 

Plansze w binarnej bitmapie, poniżej graf naturalny planszy, a na samym spodzie graf minimalny planszy.

 

A tu kod:

 

http://pastebin.com/J08PiLy1

 

* - nope, nikogo.

Odnośnik do komentarza
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się
  • Ostatnio przeglądający   0 użytkowników

    • Brak zarejestrowanych użytkowników przeglądających tę stronę.
×
×
  • Dodaj nową pozycję...