Tworzenie pomieszczeń z muru

[peterz_pl]

Witajcie moi drodzy,

 

Dziś zwracam się do was z prośbą o wsparcie w poniższym dylemacie.

W mojej grze za pomocą myszki można stawiać obiekty 32x32 na siatce (murek).

 

I tu moje pytanie. Jak sprawić, aby GM sprawdzał czy mur tworzy zamkniętą przestrzeń? Jeżeli jakiś obiekt "jest w pomieszczeniu" to zmień zmienną z 0 na 1.

 

Z góry dziękuję za pomoc.

 

 

[Sutikku]

Jeśli bloczki są wyrównywane do siatki, to może kombinować coś w rodzaju automatu komórkowego. Jak coś wymyślę konkretnego, to napiszę.

[Chell]

sprawdzaj w każdym obiekcie czy na polach dookoła niego są równo 2 obiekty po czym przełącz jakiegoś globala na 1, najprościej

 

edit: a, wróć, może raczej jak są to nic nie rób a jak jest 0 albo 1 bloczek w okolicy to zmieniaj na 1

[Amaterasu]

Czy te pomieszczenia mają być prostokątne, czy dowolnego rozmiaru?

[peterz_pl]

Pomieszczenia dowolnego rozmiaru i ksztaltu.

 

@chell, myslalem juz o tym, czyli mial sprawdzac czy jest obiekt muru x + 32 etc. Ale nie dzialalo jak obiekt byl oddalony od muru na np 200pix.

[Chell]

hm? w sensie każdy murek nie jest osobną instancją, tylko masz narożniki między którymi rysujesz?

 

jeśli każdy murek jest osobną instancją nie ma najmniejszej potrzeby sprawdzania tego co jest 200 px dalej, bo jeśli nie są bezpośrednimi sąsiadami to będzie przerwa, pokój nie będzie zamknięty i lipa

 

jeśli murek jest rysowany na podstawie obiektów w narożnikach użyj collision_line(x,y,x2,y2,osciana,0,1) zamiast place_meeting i będzie ok

 

generalnie nie wiem ani czy dokładnie zrozumiałem Twój problem, ani czy nie wyskoczy zaraz ktoś mądrzejszy z dużo wydajniejszym rozwiązaniem

[Amaterasu]

Dowolny kształt bardzo utrudnia sprawę.

 

Są metody do rozwiązywania takich spraw:

1. Metoda "zamalowywania", działająca jak narzędzie wypełniania w Paincie - rekurencyjnie sprawdzaj kolejne obszary wokół komórki, czy są puste czy zajęte. Sprawdzanie zakończy się, jeżeli sprawdzana komórka wyjdzie poza zakres mapy. Ta metoda żre dużo procesora, ale działa niezawodnie, i o ile mapa nie jest duża, to można ją stosować, jeśli sprawdzanie odbywa się tylko przy stawianiu obiektu (tzn. obiekt się nie rusza).

 

2. Metoda topologiczna - przy postawieniu każdego murku dokonuj triangulacji całego zespołu murków połączonych z tym świeżo postawionym, a następnie wylicz dla tej triangulacji liczbę Eulera - liczba utworzonych pomieszczeń jest równa (1-liczbaEulera). Problem polega na tym, jak znaleźć taką triangulację (sam dokładnie nie wiem, ale to nie jest trywialna sprawa). Nie jestem w stanie nic powiedzieć nt. wydajności, ale sposób niżej jest chyba możliwszy do zrealizowania.

 

3. Automat komórkowy - każdy murek ma trzy stany 0, 1 lub 2. Przy każdym postawieniu murku X, stwórz listę L zawierającą wszystkie murki połączone z X (niekoniecznie sąsiedzi). Zresetuj wszystkim murkom z L stan na 0. Następnie, począwszy od X, zmieniaj stan na 1, i zmieniaj stan na 1 sąsiadom, o ile ci nie mają stanu 1 lub 2. Jeżeli jednak mają, to ustaw im, i wszystkim murkom z nimi połączonymi i mającymi stan 1, stan 2. Po zakończeniu działania automatu, wszystkie murki ze stanem 2 tworzą zamkniętą przestrzeń. To tylko jeśli chodzi o sprawdzanie, czy mur jest zamknięty - sprawdzanie, czy obiekt jest wewnątrz muru, jest zagadnieniem rozwiązywalnym przy pomocy struktur danych (głównie ds_grid). Zaletą jest to, że sprawdzanie, czy obiekt jest wewnątrz, jest bardzo szybkie.

 

Jak widać, problem jest niefajny, ale rozwiązywalny.

 

EDIT: odnośnie metody 2, to triangulacja powinna wyglądać następująco:

V - ilość wierzchołków

E - ilość krawędzi

F - ilość ścian

liczbaEulera=V-E+F

dla figury złożonej ze wszystkich ścian mających połączenie ze świeżo położonym murkiem:

V=2+2N

E=5N_0+4N_1+3N_2+2N_3+N_4

F=2N

gdzie

N - liczba wszystkich murków branych pod uwagę

N_X - liczba murków mających X sąsiadów

liczbaEulera<1 => mur zamknięty

 

chyba metoda 2 wychodzi nieco prościej (co do sprawdzania zamkniętości muru)

[Jakim]

Metodę poniższą wykorzystałem do sprawdzania, czy plansza Sokobana jest poprawna.

 

1. Znajdujemy obiekt wewnątrz pola, które chcemy badać.

2. Wstawiamy w jego miejsce detektor (nie powinien być to obiekt, a jakaś struktura danych*) oraz ustawiamy licznik na 1.

3. W każdym kroku każdy z generatorów tworzy kolejne detektory wokół siebie (pamiętaj, by nie tworzyć duplikatów - wtedy liczba detektorów rośnie wykładniczo! W tym miejscu jest pole do optymalizacji kodu), a licznik dodajemy o wartość utworzonych detektorów w turze.

3. W kroku, w którym nie pojawił się już żaden detektor lub któryś z detektorów "wypadł" poza planszę, zatrzymaj algorytm. W przypadku pierwszej z możliwości obszar pokryty detektorami stanowi szukany zamknięty obszar.

 

Algorytm działa jak wypełnianie powierzchni w Paincie. W porównaniu do metody porównywania murków tutaj dostajemy również współrzędne pól, które należą do obszaru.

 

* - ew. element tablicy dwuwymiarowej [i, j], gdzie (i, j) to współrzędne w siatce, a wartość 0/1 (nie ma detektora/jest detektor).

 

Dla całkiem regularnego kształtu sposób ten wymaga podzielenia obszaru (w przypadku mapy złożonej z bloczków sprawa jest dużo prostsza) na siatkę na tyle małą, żeby uwzględnić wszystkie nieregularności oraz, z drugiej strony, na tyle dużą, by minimalizować liczbę operacji, można się nastawiać na prosty algorytm rzędu O(n?), gdzie n jest średnicą obiektu liczoną w polach siatki.

 

Rozszerzając ten algorytm, możemy przekonać się również, czy plansza jest spójna, a - jeżeli nie - na jakie składowe spójności się rozbija, tzn. które z pomieszczeń są odgrodzone od reszty i niedostępne.

[Threef]

Ja jeszcze dodam że ten algorytm nazywa się "Flood fill" jakby ktoś chciał szukać na ten temat więcej informacji.

[peterz_pl]

Ok, a przykładowo. Stworzyliśmy już cały mur, następnie stawiam w środku pokoju obiekt pomocniczy (ręcznie).

Wtedy ten obiekt pomocniczy sprawdza, czy może znaleźć ścieżkę do punktu na mapie x=0; y=0;. Jeżeli PRAWDA= obiekt otwarty, jeżeli FAŁSZ= obiekt zamknięty. Oczywiście w każdym przypadku nie idź po ścieżce, tylko zwróć massage i usuń obiekt pomocniczy. Próbowałem skorzystać z przykładu "Znajdowanie_Drogi", ale nie do końca mam pomysł jak go zmienić.

[Threef]

W sumie jeżeli potrzeba tylko sprawdzić czy pomieszczenie jest zamknięte i nie ma wyjścia to można to zrobić przy pomocy A* (mp_grid)

 

GML

grid = mp_grid_create(0, 0, room_width / 32, room_height /32, 32, 32)

mp_grid_add_instances(grid, obj_Wall, 1);

if(mp_grid_path(id, path, xstart, ystart, xgoal, ygoal, allowdiag)) {

// jest przejście

} else {

// Nie ma przejścia

}

mp_grid_destroy(grid);

[Amaterasu]

Problem może powstać, gdy komórka 0,0 jest otoczona przez kilka zamkniętych pomieszczeń, wtedy może się zdarzyć, że obiekt jest na zewnątrz, ale wg algorytmu nie istnieje ścieżka prowadząca do komórki 0,0.

Poza tym jednak, ta metoda jest bardzo dobra (mp_grid_* korzystają z wewnętrznych metod, które są szybsze od tych pisanych przez użytkownika).

Tylko że tworzenie siatki i niszczenie jej przy każdym sprawdzaniu, czy obiekt jest w pomieszczeniu, jest bez sensu. Lepiej zamiast tego na początku gry stworzyć jedną siatkę, a potem w trakcie gry dodawać/usuwać przeszkody.

[peterz_pl]

@Amaterasu: Siatka nie będzie na całej planszy (w odległości 64 kratki od boków mapy nie można tworzyć żadnych obiektów). Tak czy inaczej z tym jakoś sobie poradzę,

 

@Threef: Chyba czegoś nie zmieniłem (ściana nazywa się obj_Wall, kod umieszczony w Create).

 

 

################################################################################
############
FATAL ERROR in
action number 1
of Create Event
for object obj_pomoc:

Variable obj_pomoc.allowdiag(100008, -2147483648) not set before reading it.
at gml_Object_obj_pomoc_CreateEvent_1 (line 3) - if(mp_grid_path(id, path, xstart, ystart, xgoal, ygoal, allowdiag)) {
################################################################################
############

[Threef]

Ja podałem tylko pseudokod wzięty na szybko. W tej funkcji musisz uzupełnić wszystkie argumenty. Wszystko znajdziesz w dokumentacji.

[peterz_pl]

Zrobione, ale caly czas nie znajduje drogi. Coś zaraz wymyślę.

 

EDIT: ok, już działa. Dziękuję wszystkim za pomoc.