jak tam sylwek?

[Moho]

@up

 

Nie pijam kawy.

[Jakim]

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:

 

 

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.

[Wojo]

ta grafika wygląda mega stylowo (serio)

 

[Jakim]

Nic dziwnego, pochodzi z oryginału :).

 

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

 

 

Zredukujmy ją do grafu:

 

 

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

 

 

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)*:

 

 

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

 

 

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

 

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.

[Wojzax]

Ty niee no to ######sty sylwek xD

 

A gdyby połączyć Sokobana z Super Bombermanem

grałbym

[Wojo]

w sumie fajnie jakby połączyć gothica z gta że możesz ukraść np ścierwojadowi lowridera i się spokojnie wozić po jednym z wybranych obozów

[exp]

ale mocno przyciskasz ten długopis

[Sutikku]

jak już sylwek to bawimy się po całości w końcu

[ANtY]

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

 

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

[Wojo]

W sumie zastanawia mnie dlaczego część z was spędzała akurat sylwestra przed kompem.

[ANtY]

a gdzie indziej? czemu cie to zastanawia? XD

[Wojo]

no bo to troche smutne nie spędzać tego dnia razem z koleżkami bądź koleżankami jak większość

[ANtY]

wybieraj: komputer albo koleżanki B)

[Wojo]

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

[Jakim]

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

 

 

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.

[Wojo]

Ale ty masz łeb xD

Swoją drogą macie teraz jakieś kłopoty z powodu sylwestra ? Bo ja nie

 

[Sutikku]

miałem dużo badań krwi, ale pod kątem antyTPO, więc nie xd