Autor Wątek: Gra w kropki - algorytm i struktury danych - otaczanie kropek  (Przeczytany 2579 razy)

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Listopad 10, 2015, 19:52:32
Witam. Niektórzy być może znają grę w kropki, w której gracze (tu 2 graczy) naprzemiennie stawiają kropki i ten który otoczy swoimi kropkami zbiór kropek innego gracza zakreśla "terytorium" będące wielokątem wypełnionym jego kolorem i zdobywa tyle punktów ile kropek mieści się w tym terytorium.

Obrazuje to poniższy skrin:



1 - gracz czerwony postawił swoje kropki
2 - gracz niebieski otoczył jego kropki i tym samym zdobył pole i 4 punkty

Potrzebuję znaleźć jak najlepszy sposób na wykrywanie zakreśleń / wielokątów otaczających. Regułą jest że pola muszą być domknięte. A za domknięte uważa się pole, którego kropki brzegowe są oddalone o jedną odległość (w metryce manhatan - chyba tak to mogę nazwać), czyli albo o 1 w bok, albo o 1 w przekątnej.

W częściowo napisanym programiku mam tablicę M x N typu enum. Enum to:
* Puste
* Niebieska kropka
* Czerwona kropka

Wielokąty trzymam jako serię punktów posortowanych, tak żeby interfejs graficzny mógł narysować prawidłowy wielokąt (nie poskręcany).

Czyli na wejściu mamy wyżej omówioną tablicę, a na wyjściu mam dostać listę wielokątów (listę posortowanych tablic punktów) dla czerwonego gracza i drugą listę wielokątów dla niebieskiego gracza, jak również aktualny stan punktowy dla danej tablicy wejściowej.

Jak to najlepiej zrobić (czyli w prosty i wydajny sposób)?

Z góry dziękuję za pomoc.

Offline Mr. Spam

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

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 10, 2015, 20:45:36
Cytuj
(w metryce manhatan - chyba tak to mogę nazwać)
Nie możesz. :) W metryce Manhattan odległość po skosie wyniesie 2.

Cytuj
Czyli na wejściu mamy wyżej omówioną tablicę, a na wyjściu mam dostać listę wielokątów (listę posortowanych tablic punktów) dla czerwonego gracza i drugą listę wielokątów dla niebieskiego gracza, jak również aktualny stan punktowy dla danej tablicy wejściowej.
Myślę że powinieneś pójść w kierunku algorytmu on-line (analiza w momencie postawienia kropki), bo kolejność stawiania kropek jest ważna (kropki odcięte nie mogą zamykać innych). Przykładowo algorytm mógłby dostać na wejściu szachownicę z kropek i nie znając kolejności nie dało by się nic o takim układzie powiedzieć.

Cytuj
Jak to najlepiej zrobić (czyli w prosty i wydajny sposób)?
Prosty i wydajny - flood fill. W momencie stawiania kropki próbujesz wystartować flood fill'a z każdego sąsiadującego pola na którym nie mamy własnej kropki (czyli puste i przeciwnicy). Flood fill wypełnia i jest ograniczony tylko kropkami tego gracza i brzegiem planszy. Flood przechodzi tylko w podstawowych 4 kierunkach (żeby dało się ograniczyć pole "na skos"). Jeśli flood nie dotknął brzegu planszy, to znaczy że mamy zamknięte pole - wszystkie pola wewnątrz flood'a można zaznaczyć jako zajęte, a kropki przeciwnika policzyć jako punkty i zaznaczyć jako nieaktywne.

Co do wielokąta: po udanym flood fillu można zacząć od pola z którego wystartował i przejść całe pole trzymając się lewej ściany (własnych punktów) aż wrócimy do początku. I mamy posortowaną listę wierzchołków wielokąta. Potem oczywiście trzeba to ztriangulować (np. metodą ear clipping), bo wielokąt nie musi być przecież wypukły.

Offline lethern

  • Użytkownik

  • +1
# Listopad 10, 2015, 20:52:54
Może to nie jest oczywiste, ale to jest prymitywna wersja gry https://en.wikipedia.org/wiki/Go_(game), do której stworzenie bota jest chyba następnym kamieniem milowym po szachach
« Ostatnia zmiana: Listopad 10, 2015, 21:35:39 wysłana przez lethern »

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Listopad 10, 2015, 23:15:41
Nie możesz. :) W metryce Manhattan odległość po skosie wyniesie 2.

No racja ;)

Zaimplementowałem floodfill - co do niego nie mam wątpliwości - dobry tip, dzięki :) (działa fajnie wykrywa kropki i poprawnie liczy punkty).

Natomiast za chwilę umieszczę filmik jak to działa i wykrywanie metodą w lewo nie działa (przynajmniej u mnie) - bo np. przypadek jest taki że zapętla na kropkach sąsiadująch (np. tworzących prostokąt 3x4).

UPDATE: Filmik: https://www.youtube.com/watch?v=KnvlVwJmr5M

Proponuje włączyć napisy :)
« Ostatnia zmiana: Listopad 10, 2015, 23:21:53 wysłana przez komorra »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 10, 2015, 23:20:59
Cytuj
Natomiast za chwilę umieszczę filmik jak to działa i wykrywanie metodą w lewo nie działa (przynajmniej u mnie) - bo np. przypadek jest taki że zapętla na kropkach sąsiadująch (np. tworzących prostokąt 3x4).
Znaczy źle zaimplementowałeś, albo źle wystartowałeś. Musisz wystartować "podróżnika" tak, by jego lewą ścianą była kropka dopiero co postawiona.

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Listopad 11, 2015, 00:07:24
Ok wszystko już działa, dziękuję za pomoc :)

Offline Xion

  • Redaktor
    • xion.log

# Listopad 11, 2015, 04:55:06
Na pierwszy rzut oka wygląda mi na to podobny problem do obliczania otoczki wypukłej:

https://en.wikipedia.org/wiki/Convex_hull_algorithms#Algorithms

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 11, 2015, 13:33:53
Na pierwszy rzut oka wygląda mi na to podobny problem do obliczania otoczki wypukłej
Proponuję wykonać drugi rzut. Tutaj chodzi o zupełnie coś innego.

Offline Xion

  • Redaktor
    • xion.log

# Listopad 11, 2015, 18:34:21
Eh? W obu przypadkach chodzi o znalezienie zbioru punktów na brzegu figury. Problem OP zdecydowanie dałoby się rozwiązać przy pomocy CH:

1. Bierzemy tylko punkty jednego koloru.
2. Znajdujemy dla nich CH.
3. Lecimy po wszystkich punktach przeciwnego koloru wewnątrz nich (np. iterując minX -> maxX & minY -> maxY) i zmieniamy ich kolor na kolor pierwszego gracza.

Oczywiście flood fill będzie prostszy i szybszy, ale jak widać przy pomocy CH też się da ;)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 11, 2015, 23:29:32
Cytuj
Problem OP zdecydowanie dałoby się rozwiązać przy pomocy CH
Tylko dla najprostszych przypadków, takich jak przykład w pierwszym poście, gdzie otoczka jest wypukła. W ogólności nie ma na to żadnej gwarancji i obszary zamknięte kropkami mogę mieć dowolny kształt, niekoniecznie wypukły. Wtedy siłą rzeczy algorytm znajdowania wypukłej otoczki w niczym nie pomoże.