Mam siatkę płytek o znanym skończonym rozmiarze, która tworzy mapę. Niektóre kafelki na mapie są umieszczane w zestawie zwanym terytorium. Terytorium to jest połączone, ale nic nie wiadomo o jego kształcie. Przez większość czasu byłby to dość regularny kropelka, ale może być bardzo wydłużony w jednym kierunku i potencjalnie może mieć nawet dziury. Jestem zainteresowany znalezieniem (zewnętrznej) granicy terytorium.
To znaczy, chcę listę wszystkich kafelków, które dotykają jednego z kafelków na terytorium, nie będąc na tym terytorium. Jaki jest skuteczny sposób na znalezienie tego?
Dla dodatkowej trudności zdarza się, że moje kafelki są heksami, ale podejrzewam, że to nie robi zbyt wielkiej różnicy, każda płytka jest nadal oznaczona liczbą całkowitą współrzędną xiy, a biorąc pod uwagę płytkę, mogę łatwo znaleźć sąsiadów. Poniżej kilka przykładów: czerń to terytorium, a niebieska granica, którą chcę znaleźć.
To samo w sobie nie jest trudnym problemem. Jednym z prostych algorytmów tego, w pseudo-python, jest:
def find_border_of_territory(territory):
border = []
for tile in territory:
for neighbor in tile.neighbors():
if neighbor not in territory and neighbor not in border:
border.add(neighbor)Jest to jednak powolne i chciałbym coś lepszego. Mam pętlę O (n) nad terytorium, kolejną pętlę (krótką, ale nadal) nad wszystkimi sąsiadami, a następnie muszę sprawdzić członkostwo na dwóch listach, z których jedna ma rozmiar n. To daje okropne skalowanie O (n ^ 2). Mogę zredukować to do O (n), używając zestawów zamiast list dla granicy i terytorium, dzięki czemu członkostwo można szybko sprawdzić, ale nadal nie jest świetne. Oczekuję, że będzie wiele przypadków, w których terytorium jest duże, ale granica jest mała ze względu na proste skalowanie obszaru względem linii. Na przykład, jeśli terytorium ma heks o promieniu 5, ma rozmiar 91, ale granica ma tylko rozmiar 36.
Czy ktoś może zaproponować coś lepszego?
Edytować:
Aby odpowiedzieć na niektóre z poniższych pytań. Terytorium może mieć wielkość od około 20 do około 100. Zestaw kafelków tworzących terytorium jest atrybutem obiektu i to ten obiekt potrzebuje zestawu wszystkich kafelków granicy.
Początkowo terytorium jest tworzone jako blok, a następnie najczęściej zdobywa kafelki jeden po drugim. W tym przypadku prawdą jest, że najszybszym sposobem jest po prostu utrzymanie zestawu granicy i aktualizowanie go tylko na zdobytym kafelku. Czasami może się zdarzyć duża zmiana na terytorium - dlatego trzeba będzie go w pełni ponownie obliczyć.
Jestem teraz zdania, że wykonanie prostego algorytmu znajdowania granic jest najlepszym rozwiązaniem. Jedyna dodatkowa złożoność, którą to powoduje, polega na ponownym obliczeniu granicy za każdym razem, gdy zajdzie taka potrzeba, ale nie więcej. Jestem przekonany, że można to zrobić niezawodnie w moich obecnych ramach.
Jeśli chodzi o czas, w moim obecnym kodzie mam pewne procedury, które muszą sprawdzać każdy kafelek terytorium. Nie na każdym kroku, ale na stworzeniu, a czasem potem. Zajmuje to ponad 50% czasu działania mojego zestawu kodu testowego, mimo że jest to bardzo niewielka część całego programu. Dlatego chciałem zminimalizować wszelkie powtórzenia. JEDNAK kod testowy wymaga znacznie więcej tworzenia obiektów niż normalne uruchomienie programu (oczywiście), więc zdaję sobie sprawę, że może to nie być bardzo istotne.
źródło
Odpowiedzi:
Znalezienie algorytmu zwykle najlepiej jest przeprowadzić za pomocą struktury danych, która ułatwia algorytm.
W takim przypadku twoje terytorium.
Terytorium powinno być nieuporządkowanym (skrótem O (1)) zbiorem granic i elementów.
Ilekroć dodajesz element do terytorium, iterujesz po sąsiednich kafelkach i sprawdzasz, czy powinny to być kafelki granicy; w tym przypadku są kafelkami obramowania, jeśli nie są kafelkami elementów.
Za każdym razem, gdy odejmujesz element od terytorium, upewniasz się, że sąsiadujące z nim płytki nadal znajdują się na terytorium i widzisz, czy sam powinieneś zostać kafelkiem granicy. Jeśli potrzebujesz, aby było to szybkie, kafelki graniczne powinny śledzić ich „liczbę sąsiadów”.
Wymaga to pracy O (1) za każdym razem, gdy dodajesz lub usuwasz płytkę na terytorium lub z terytorium. Zwiedzanie granicy zajmuje O (długość granicy). Tak długo, jak chcesz wiedzieć „czym jest granica” znacznie częściej niż dodajesz / usuwasz elementy z terytorium, powinno to wygrać.
źródło
Jeśli potrzebujesz również znaleźć krawędzie dziur w środku swojego terytorium, to twoja liniowość w obszarze granicy terytorium jest najlepszym, co możemy zrobić. Każda płytka we wnętrzu może potencjalnie być dziurą, którą musimy policzyć, więc musimy przynajmniej raz spojrzeć na każdą płytkę w obszarze ograniczonym konturem terytorium, aby upewnić się, że znaleźliśmy wszystkie dziury.
Ale jeśli zależy ci tylko na znalezieniu zewnętrznej granicy (a nie wewnętrznych otworów), możemy to zrobić nieco bardziej wydajnie:
Znajdź jedną krawędź oddzielającą twoje terytorium. Możesz to zrobić przez ...
(jeśli znasz przynajmniej jeden kafelek terytorium i wiesz, że masz dokładnie jedną kroplę połączonego terytorium na mapie)
... zaczynając od dowolnego kafelka na twoim terytorium i zbliżając się do najbliższej krawędzi twojej mapy. Robiąc to, pamiętaj ostatnią krawędź, w której przeszedłeś z kafelka terytorium na kafelek nie będący terytorium. Po dotarciu do krawędzi mapy ta zapamiętana krawędź jest początkową krawędzią.
Ten skan ma liniową średnicę mapy.
lub (jeśli nie wiesz, gdzie znajduje się którykolwiek z kafelków twojego terytorium, lub twoja mapa może zawierać kilka rozłączonych terytoriów)
... zaczynając od krawędzi mapy, skanuj wzdłuż każdego rzędu, aż trafisz na kafelek terenu. Ostatnią krawędzią, którą przekroczyłeś z terenu bez terenu, jest Twoja krawędź początkowa.
Ten skan może być w najgorszym przypadku liniowy w obszarze mapy (kwadratowa w swojej średnicy), ale jeśli masz jakieś granice ograniczające twoje wyszukiwanie (powiedzmy, że wiesz, że terytorium prawie zawsze przecina środkowe rzędy), możesz poprawić to najgorsze- zachowanie przypadku.
Zaczynając od początkowej krawędzi znajdującej się w kroku 1, podążaj nią wzdłuż obwodu swojego terenu, dodając każdą płytkę niepozbawioną terenu na zewnątrz do kolekcji granic, aż wrócisz do początkowej krawędzi.
Ten krok wzdłuż krawędzi jest liniowy na obwodzie obrysu terenu, a nie na jego obszarze. Minusem jest to, że kod jest bardziej skomplikowany, ponieważ musisz wziąć pod uwagę każdy rodzaj obrotu, jaki może podjąć krawędź, i unikać podwójnego liczenia płytek granicznych na wlotach.
Jeśli twoje przykłady są reprezentatywne dla twojego rzeczywistego rozmiaru danych z dokładnością do kilku rzędów wielkości, to ja wybrałbym naiwne wyszukiwanie obszaru - nadal będzie niesamowicie szybko na tak małej liczbie kafelków i jest znacznie prostszy do napisania , zrozum i utrzymuj (zwykle prowadzi to do mniej błędów!)
źródło
Uwaga : To, czy kafelek znajduje się na granicy, zależy tylko od niego i jego sąsiadów.
Z tego powodu:
Łatwo jest uruchomić to zapytanie leniwie. Na przykład: Nie musisz szukać granicy na całej mapie, tylko na tym, co jest widoczne.
To zapytanie jest łatwe do uruchomienia równolegle. W rzeczywistości mogę wyobrazić sobie kod, który to robi. A jeśli potrzebujesz tego do innej wizualizacji, możesz wyrenderować teksturę i użyć tego.
Jeśli kafelek się zmienia, granica zmienia się tylko lokalnie, co oznacza, że nie trzeba ponownie obliczać całej rzeczy.
Możesz także wstępnie obliczyć granicę. Oznacza to, że jeśli zapełnisz heks, możesz zdecydować, czy kafelek jest w tym momencie granicą. Oznacza to, że:
Nie używaj listy dla granicy. Użyj zestawu, jeśli naprawdę musisz ( nie wiem, po co chcesz granicę ). Jeśli jednak utworzysz dowolną granicę kafelka lub nie jest to atrybut kafelka, nie musisz przechodzić do innej struktury danych w celu sprawdzenia.
źródło
Przesuń obszar w górę o jeden kafelek, następnie w górę w prawo, następnie w dół w prawo itp. Następnie usuń oryginalny obszar.
Scalanie wszystkich sześciu zestawów powinno być O (n), sortowanie O (n.log (n)), ustawianie różnicy O (n). Jeśli oryginalne kafelki są przechowywane w jakimś posortowanym formacie, scalony zestaw można również posortować w O (n).
Nie sądzę, aby istniał algorytm o wartości mniejszej niż O (n), ponieważ musisz uzyskać dostęp do każdej płytki przynajmniej raz.
źródło
Właśnie napisałem post na blogu o tym, jak to zrobić. Wykorzystuje pierwszą metodę, o której wspominał @DMGregory, rozpoczynając od komórki brzegowej i maszerując wokół obwodu. Jest w C # zamiast Python, ale powinien być dość łatwy do dostosowania.
https://dillonshook.com/hex-city-borders/
źródło
ORYGINALNY POCZTA:
Nie mogę komentować tej witryny, więc spróbuję odpowiedzieć za pomocą algorytmu pseudokodu.
Wiesz, że każde terytorium ma co najwyżej sześciu sąsiadów, którzy są częścią granicy. Dla każdego kafelka na terytorium dodaj sześć sąsiadujących kafelków do potencjalnej listy granic. Następnie odejmij każdą płytkę na terytorium od granicy, a pozostaną tylko płytki graniczne. Będzie działać najlepiej, jeśli użyjesz nieuporządkowanego zestawu do przechowywania każdej listy. Mam nadzieję, że byłam pomocna.
EDYCJA Istnieje wiele bardziej skutecznych sposobów niż prosta iteracja. Jak próbowałem powiedzieć w mojej (teraz usuniętej) odpowiedzi poniżej, możesz osiągnąć O (1) w najlepszych przypadkach i O (n) w najgorszym przypadku.
Dodawanie kafelka do terytorium O (1) - O (N):
W przypadku braku sąsiadów po prostu tworzysz nowe terytorium.
W przypadku jednego sąsiada dodajesz nowy kafelek do istniejącego terytorium.
W przypadku 5 lub 6 sąsiadów wiesz, że wszystko jest połączone, więc dodajesz nowy kafelek do istniejącego terytorium. Są to wszystkie operacje O (1), a aktualizacja nowych terytoriów granicznych również jest O (1), ponieważ jest to proste połączenie jednego zestawu z drugim.
W przypadku 2, 3 lub 4 sąsiednich terytoriów może być konieczne połączenie maksymalnie 3 unikalnych terytoriów. Jest to O (N) dla połączonego rozmiaru terytorium.
Usuwanie kafelka z terytorium O (1) - O (N):
Z zerowymi sąsiadami wymazuje terytorium. O (1)
Z jednym sąsiadem usuń płytkę z terytorium. O (1)
Z dwoma lub więcej sąsiadami można utworzyć do 3 nowych terytoriów. To jest O (N).
Wolny czas spędziłem przez ostatnie kilka tygodni, opracowując program demonstracyjny, który jest prostą grą opartą na heksach. Spróbuj zwiększyć swoje dochody, umieszczając terytoria obok siebie. 3 graczy, czerwony, zielony i niebieski, rywalizują ze sobą, aby uzyskać największe przychody poprzez strategiczne umieszczanie płytek na ograniczonym polu gry.
Możesz pobrać grę tutaj (w formacie .7z) hex.7z
Proste sterowanie myszą LMB umieszcza kafelek (można go umieścić tylko tam, gdzie jest podświetlony po najechaniu myszą). Wynik na górze, dochód na dole. Sprawdź, czy możesz wymyślić skuteczną strategię.
Kod można znaleźć tutaj:
Eagle / EagleTest
Do budowania z kodu źródłowego potrzebujesz Eagle i Allegro 5. Oba budują z cmake. Gra Hex jest obecnie budowana z projektem CB.
Odwróć te głosy do góry nogami. :)
źródło