Autor Wątek: usuwanie cykli w prostokątnym labiryncie  (Przeczytany 4769 razy)

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Marzec 27, 2008, 14:17:03
Cześć.
Nie ma działu "algorytmy", więc piszę tu, choć z inteligencją to ten wątek nie będzie silnie związany.
Piszę sobie (długo już) grę, w której główną atrakcją są dynamicznie generowane labirynty.
Przy okazji tworzę biblioteczkę GUI do SDLa. Nie wliczając wielu nieznaczących opcji, można generować już
labirynty czterema różnymi (jeśli chodzi o widoczny efekt) algorytmami. Można też wybrać pomiędzy dwoma rodzajami labiryntu: "grubym", gdzie ściana zajmuje całe pole oraz "cienkim", gdzie jest cienką kreską pomiędzy polami. Widać tę różnicę w załącznikach. Ostatnio zauważyłem, że moja "gra" jest jedynie łamigłówką, bo nie ma żadnego konfliktu, więc wymyśliłem sobie, że będzie przeciwnik i dla niego wymyśliłem algorytmy, które nim sterują. I tu pojawił się problem, bo te algorytmy zakładają, że labirynt jest drzewem (nie ma w nim pętli). Jak na razie są generowane labirynty, gdzie nie ma odizolowanych obszarów i jest zawsze rozwiązanie, ale labirynty te mają cykle.
Trzeba więc usunąć te cykle. Dla labiryntu "cienkiego" mam następujący algorytm:
- zalej powodzią cały labirynt i dla każdego pola:
    - sprawdź, czy któreś z sąsiednich pól, pomijając to, z którego weszliśmy, jest już zalane;
        - jeśli jest, to mamy cykl, więc wstawiamy ścianę przed tym polem
        - jeśli nie, to zalewamy pole i przekazujemy mu pozycję bieżącą, czyli tę, z której go zalewamy
Problem w tym, że to nie zadziała dla "grubego" labiryntu, bo jak wstawimy tam ścianę zajmującą całe pole, to możemy zastawić sobie jakiś korytarz. Nie wiem, czy rozwiązanie w ogóle jest, więc na razie spróbuję zrobić gameplay w cienkim, a gruby sobie zostanie jako ciekawostka i do grania np. na przechodzenie na czas, ale bez przeciwnika.
Będę wdzięczny za wszelkie sugestie, jak to zrobić w "grubym".

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Marzec 27, 2008, 14:20:04
Cytuj
Trzeba więc usunąć te cykle.
Albo zmienić algorytm przeciwnika. Osobiście fajniej by mi się ganiało po labiryntach, które te cykle jednak mają. :)

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Marzec 27, 2008, 14:46:01
Akurat nie chodzi o ganianie się :) Gdyby tak było, to te "algorytmy przeciwnika" byłyby kilkoma instrukcjami warunkowymi, może jeszcze z   A* do znajdowania najkrótszej drogi (ten zresztą już mam). Swoją drogą ganianie się też można zrobić, dzięki wielkie za sugestię. Chodzi o to, że w labiryncie byłyby rozrzucone skarby różnej wielkości i zadaniem graczy byłoby zebrać jak najwięcej z nich zanim zderzą się z innymi graczami. W przypadku zderzenia gracz, który ma więcej wygrywa. Te algorytmy muszą więc obliczyć, gdzie najbardziej opłaca się iść, a tu cykle są trochę niepożądane.

Offline mwojt

  • Użytkownik

# Marzec 27, 2008, 14:58:08
to chyba trzeba rozwiązać problem komiwojażera, mając algorytm najkrótszej drogi możesz przy wypełnianiu tablicy od skarbu x mieć od razu wszystkie odległości do innych skarbów (sprawdzając wartość w tablicy ze skarbem y).

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Marzec 27, 2008, 15:31:09
Cytuj
Te algorytmy muszą więc obliczyć, gdzie najbardziej opłaca się iść, a tu cykle są trochę niepożądane.
W takim razie wystarczy że w dowolny sposób wyznaczysz podgraf grafu labiryntu, który jest drzewem, a na to to już jest cała masa sposobów, w zależności od tego, co chcesz uzyskać (np. algorytmy Kruskala i Prima do wyznaczania minimalnych drzew spinających). :)

Cytuj
to chyba trzeba rozwiązać problem komiwojażera
Jeżeli tutaj labirynt ma być drzewem, to problem komiwojażera nie będzie już wcale problemem - wystarczy zwykłe przejście DFS i mamy optymalne rozwiązanie (przez każdą krawędź przechodzimy dwukrotnie). :)

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Marzec 27, 2008, 15:47:43
Cytuj
to chyba trzeba rozwiązać problem komiwojażera, mając algorytm najkrótszej drogi możesz przy wypełnianiu tablicy od skarbu x mieć od razu wszystkie odległości do innych skarbów (sprawdzając wartość w tablicy ze skarbem y).

Przepraszam, może jestem trochę mało domyślny, ale o jaką tablicę chodzi? Tablicę wszystkich skarbów, przez które mamy po kolei przejść? Jeśli tak, to rzeczywiście można zrobić taką tablicę i przechodzić sobie potem od jednego do drugiego i jak coś się zmieni, np. gracz ludzki weźmie skarb, to zaktualizować ją. Tylko jak proponujesz rozwiązać ten problem komiwojażera? :)

Ja chcę raczej trzymać się niskich złożoności, więc wymyśliłem, że
jeśli potraktować labirynt jako graf, gdzie wierzchołkami będą skarby i skrzyżowania, a krawędzie będą miały wagę równą liczbie pól pomiędzy wierzchołkami, to:
- można podzielić labirynt na sektory, będące ścieżkami (kombinacjami wierzchołek-krawędź-wierzchołek-krawędź... bez rozwidleń i cykli), a każdy sektor będzie też miał zapisaną sumę wszystkich skarbów i długość (sumę wag krawędzi);
- będzie drzewo takich sektorów, tworzone na początku od startu;
- każdy sektor w tym drzewie będzie przechowywał listę obiektów, a w każdym będzie:
    - wskaźnik na inny, bezpośrednio połączony sektor
    - suma skarbów i koszt przemierzenia w tym sektorze i wszystkich połączonych z nim sektorów
Zatem jeśli mamy gracza, to jest on zawsze w jakimś sektorze. Jeśli wiemy w którym, to możemy sprawdzić, w którym podsektorze stosunek liczby skarbów do kosztu przemierzenia jest największy i tam iść. Gdy tam dojdziemy to znowu wybieramy najlepszy podsektor i tak dalej. Oczywiście przy wybieraniu najlepszego podsektora musimy też uwzględnić to, jak długo będziemy do niego iść w bieżącym sektorze i ile skarbów po drodze weźmiemy.
To wszystko jest fajne, bo jak jesteśmy w danym sektorze, to tylko wybieramy jedno z kilku miejsc, gdzie można iść, mając wskazane,  co się za tym miejscem kryje. Gdyby to nie było drzewo, to wygenerowanie i aktualizowanie tego grafu miałoby cholernie dużą złożoność.
Muszę doczytać o tym Kruskalu i Primie.

Aha, jeszcze jedna uwaga: układ skarbów będzie się zmieniał dynamicznie, więc zależy mi raczej na szybkim wyborze kolejnego skarbu/skrzyżowania, do którego trzeba pójść, a nie na znalezieniu i zapisaniu najlepszej ścieżki przez cały labirynt. Bo nie chodzi o to, aby znaleźć najkrótszą ścieżkę przez wszystkie skarby, ale taką, gdzie jak największą sumę skarbów zbierze się jak najszybciej :) Przecież na planszy jest drugi gracz, który tylko czeka, żeby mieć chwilowo więcej skarbów i zderzyć się z naszym biednym botem.
« Ostatnia zmiana: Marzec 27, 2008, 15:54:35 wysłana przez klosio.neostrada.pl »

Offline mwojt

  • Użytkownik

# Marzec 27, 2008, 16:21:00
nie wiem z jakiego algorytmu szukania drogi korzystasz ale w tym dość popularnym wypełnia się tablicę od punktu celu np. 0 wszystkie przylegające punkty do 0 oznacza się 1 wszystkie przylegające do jedynek 2 itd. później aby znaleść drogę do celu wystarczy przejść od numeru leżącego na współrzędnych x,y np. 10 później przechodzimy po kolei na 9, 8, 7... i tak dochodzimy do celu. Chodziło mi o to, że mając wypełnioną tablicę od współrzędnych ludzika wiemy na jakim numerze leży skarb i jest to jednocześnie odległość do niego, właściwie mamy odległości do wszystkich obiektów.

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Marzec 27, 2008, 17:51:43
@medivo
Cytuj
nie wiem z jakiego algorytmu szukania drogi korzystasz ale w tym dość popularnym wypełnia się tablicę od punktu celu np. 0 wszystkie przylegające punkty do 0 oznacza się 1 wszystkie przylegające do jedynek 2 itd. później aby znaleść drogę do celu wystarczy przejść od numeru leżącego na współrzędnych x,y np. 10 później przechodzimy po kolei na 9, 8, 7... i tak dochodzimy do celu. Chodziło mi o to, że mając wypełnioną tablicę od współrzędnych ludzika wiemy na jakim numerze leży skarb i jest to jednocześnie odległość do niego, właściwie mamy odległości do wszystkich obiektów.
Rozumiem, ale tak możemy znaleźć pojedynczy skarb, do którego najbardziej opłaca się iść. Mnie potrzeba skarbu, do którego się najbardziej opłaca, ale z uwzględnieniem reszty :) Można sobie wyobrazić gracza komputerowego, który jest obok człowieka i z jednej strony ma krótki korytarz z bardzo wartościowym skarbem, a po drugiej długi z kilkoma skarbami, których suma przekracza wartość tego w krótkim korytarzu. Komputer pójdzie do krótkiego korytarza i przegra, bo człowiek będzie pierwszy w długim.

Offline mwojt

  • Użytkownik

# Marzec 27, 2008, 17:57:45
to trzeba jeszcze dodać do tego kto jest bliżej skarbu i np. jeżeli człowiek jest bliżej dużego skarbu to komputer może sobie odpuścić podążanie w jego kierunku lub zaczekać chwilkę czy człowiek nie zacznie przypadkiem iść w innym kierunku. Widzę, że gra nie jest taka prosta bo jak komputer ma szansę zdobyć skarb to może zginąć od człowieka jak tamten będzie silniejszy...

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Marzec 27, 2008, 18:01:18
No wlasnie. I z tego dokladnie powodu twoja metoda sie nie nadaje :)

Offline mwojt

  • Użytkownik

# Marzec 27, 2008, 18:28:07
no nie wiem to tylko taka metoda szukania drogi i wyliczania odległości w labiryncie. Oczywiście, że może się przydać ale to tylko część problemu. Przykład: mam początek rozgrywki dwóch zawodników i 30 skarbów dla każdego obiektu tworzę tablicę i wypełniam od współrzędnych danego obiektu dla skarbów wystarczy jedno wypełnienie i można korzystać z tablicy w całej rozgrywce a dla ludzików tablica się zmienia przy każdym ruchu. Jak mam odległości między wszystkimi obiektami to potrzebne mi są tylko wyliczenia opłacalności do którego obiektu mam iść. Chcę np. sprawdzić odległość do skarbu x to pobieram bajt z tablicy tego skarbu na współrzędnych mojego ludzika. Problemem może być duża plansza np. 100x100 przy 30 obiektach to by było 30*10000 już 300kb na tablice.
« Ostatnia zmiana: Marzec 27, 2008, 18:33:59 wysłana przez medivo »

Offline ŁukaszB

  • Użytkownik

# Marzec 28, 2008, 15:21:43
BFS? A*?
to chyba takie najsłynniejsze:)