>
> To nadal wersja beta. Gra jest deterministyczna. Mam z nią mały problem - niekiedy
generuje labirynty, których nie da się przejść. Problem jest w klasie maze_generator.
>

Wrzuciłem wersję 0.0.8, algorytm generowania labiryntu jest poprawiony, są też różne
poziomy trudności.

Idea labiryntu jest taka:
Labirynt dzieli się na n komnat (w programie nazywanych "chambers"), wszędzie tam
gdzie to możliwe powstają drzwi łączące komnaty, maksymalnie jest ich n*(n-1)/2, ale
może być mniej, zależnie od topologii. Tworzona jest macierz zero-jedynkowa
zawierająca przejścia między komnatami. Jest ona kwadratowa i symetryczna. W
programie nazywa się "matrix_of_transition_chambers". Ilość jedynek w tej macierzy to
dwa razy ilość drzwi w labiryncie.

Następnie generowane są wszystkie symetryczne macierze, które w miejscu jedynek
macierzy przejścia mają zera lub jedynki, czyli wybieramy kombinacje. Ich ilość
wynika z ilości wszystkich kluczy i symbolu Bernoulliego. Bierzemy tylko te z
macierzy, które zawierają dwa lub mniej kluczy. Mówiąc po prostu generujemy
kombinacje wszystkich par i jedynek kluczy (macierz zerowa też jest odrzucona). To
arbitralna decyzja, chciałem żeby gracz miał w każdej chwili maksymalnie dwa klucze,
ale nigdy zero. Wszystkie te macierze będę dalej nazywał macierzami kluczy.

Następnie generowane są pary (komnata, macierz kluczy). Właściwy labirynt to tak
naprawdę graf nieskierowany, w którym węzłami są te właśnie pary. Krawędzie grafu
odpowiadają albo przejściu do innej komnaty z TYMI SAMYMI kluczami, albo wymianie
kluczy w TEJ SAMEJ komnacie.

Nawet na najniższym poziomie trudności, dla trzech komnat, ilość tych par może być
np. 15. Dla siedmiu komnat wyszło mi 144 (to oczywiście wartość losowa). Przejście do
innej komnaty jest możliwe zawsze, gdy mamy odpowiedni klucz. Natomiast wymiana
kluczy w tej samej komnacie nie zawsze jest możliwa.

W każdej komnacie, w której można wymienić klucze chodzi sobie ork, któremu odpowiada
pewna relacja równoważności na zbiorze macierzy kluczy. Relacja ta dzieli ów zbiór na
klasy równoważności. Wymienić się można tylko na macierze-reprezentantów klasy,
której reprezentanta już mamy. Czyli ork pozwala nam odwrócić każdą transakcję, ale
nie na każdą transakcję się zgodzi. Mimo to labirynt jest tak skonstruowany, że
istnieje rozwiązanie, tj. istnieje ścieżka w grafie z każdej pary (komnata, macierz
kluczy) do każdej innej pary.

Przepraszam, jeśli trochę przynudzam. Tego typu labirynty wydają mi się ciekawe.
Myślałem o grze, w której oprócz kluczy mamy jeszcze inne przedmioty, które
zwiększają ilość węzłów w grafie. Wówczas orki mogłyby oferować różne transakcje,
zależnie od tego czy mamy np. Święty Gral, czy nie.

Pozdrawiam,
Paweł Biernacki