Autor Wątek: Wykrywanie zamkniętych powierzchni  (Przeczytany 606 razy)

Offline t4fun

  • Użytkownik

# Kwiecień 23, 2010, 15:12:33
Witam,
z 10 lat mnie nie było na tym forum, dużo się pozmieniało, miło was znowu czytać.

Problem:
Upraszczając i dostosowując do tematyki forum to powiedzmy że robię edytor map levelu, załóżmy piętro budynku. Osoba edytująca może myszką rysować ściany (prostokąty), teraz ja chce z tych ścian wyznaczyć te które wyznaczają zamkniętą przestrzenie - pomieszczenia (pomijamy drzwi i okna). Ściany mogą na siebie nachodzić i się stykać (w sumie bez tego nie było by zamkniętych obszarów)

Pierwszy pomysł jaki mi przyszedł do głowy to wyznaczenie zakresów mix/max i stworzenie odpowiedniej wielkości bitmapy. Wypełnienie na jeden kolor, wyrysowanie w niej wszystkich ścian innym kolorem i jakimś rastrowym algorytmem wypełnianie do jeszcze innego koloru (każdy nowy kolor wyznaczył by nowe pomieszczenie). Ale przy bardzo skomplikowanych mapach będzie to wymagało bardzo dużo RAMu a także może okazać się dosyć wolne (chociaż to jest wykonywane w edytorze a nie w realtime, więc prędkość nie ma tak dużego znaczenia), po za tym dalej nie mam informacji które ściany tworzą pomieszczenie.

Wydaje mi się że muszę jakoś skorzystać z grafów. Nie mam z tym dużego doświadczenia więc proszę was o pomoc w wyborze jakiegoś algorytmu. Najpierw muszę ściany zamienić na graf. Mam 2 możliwości: każda ściana to 4 rogi i 4 krawędzie, jednak wydaję mi się, że z tego powstanie zbyt duży,niepotrzebny graf, zwłaszcza że przecięcia/połączenia ścian wygenerują dodatkowe  wierzchołki do grafu.
Druga możliwość: ściany zazwyczaj są w jakimś kierunku dłuższe niż szersze (pomijamy kolumny) więc myślę, żeby przyjąć 2 końce ściany jako wierzchołki grafu i a ich połączenie jako krawędź grafu. Do tego skrzyżowanie z inną ścianą doda kolejne wierzchołki.
Teraz gdy mamy graf muszę wyszukać cykle w nim. I tu główne pytanie jakich algorytmów użyć, z tego co dziś szukałem to głównie napotykałem na cykle komiwojażera, a mnie o to nie chodzi.

Pozdrawiam

Offline Mr. Spam

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

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Kwiecień 23, 2010, 15:41:39
A w jakim celu chcesz takie zamknięte przestrzenie wykrywać?

Offline t4fun

  • Użytkownik

# Kwiecień 23, 2010, 16:08:56
Muszę wykonać obliczenia na pomieszczeniach.
Jak mi się nie uda samemu je wyznaczać, to zmuszę użytkownika do zaznaczania ścian i grupowania je w pomieszczenia, ale chciałbym tego uniknąć. Im mniej użytkownik musi klikać tym lepiej. W sumie w grze "The Sims" jest coś podobnego. Użytkownik może sobie budować ścianki i jak zamknie powierzchnie, to jest to wykrywane i jest tam obliczana ilość światła wpadająca przez okna, można tapetować wszystkie ściany pomieszczenia itp.

Offline Liosan

  • Redaktor

# Kwiecień 23, 2010, 17:08:28
Co do drugiego pomysłu - dlaczego po prostu nie zrobisz jedna ściana = jeden węzeł grafu? Rozdziel problemy "wykrywanie, które ściany tworzą pomieszczenie" od "określanie, jaki kształt ma pomieszczenie". Jeśli ściany się przecinają, to jest krawędź między odpowiadającymi im wierzchołkami. Problem z takim podejściem jest taki, że powstanie Ci dużo więcej cykli niż pomieszczeń... ale tak samo miałbyś w Twoim oryginalnym pomyśle - 4 stykające się ze sobą pomieszczenia (na planie kwadratu) to jakieś kilkadziesiąt różnych cykli. Skąd wiesz, które to pomieszczenie?

Wydaje mi się, że słowo kluczowe tutaj to zamiatanie - przebiegasz płaszczyznę (mówimy o 2D, tak? ) od lewej do prawej za pomocą pionowej prostej. Oczywiście skaczesz tylko po interesujących punktach - czyli tam, gdzie jest jakiś wierzchołek ściany. Nie jestem pewien dokładnego algorytmu, ale mógłbyś to robić w jakiś taki sposób, że trzymasz listę wielokątów, które wedle Twojej aktualnej wiedzy są rozłączne (tzn rozdzielone ścianami). Jeśli widzisz, że dwa wielokąty się stykają, to je łączysz. Żeby było zabawniej, jeśli widzisz, że ten sam wielokąt się ze sobą styka, to go ze sobą scalasz... bo to wcale nie są wielokąty, tylko "wielokąty z dziurami". Na tym też się da pracować, ale generalnie cały algorytm się robi cholernie skomplikowany :) Z drugiej strony, raczej powinien działać i być wydajny...

Liosan