podział na regiony

Podczas tworzenia Gizarmy musiałem wymyślić metodę na znalezienie podziału mapy na regiony. Nie mogła to być regularna siatka, więc zadanie nie było trywialne. Udało mi się wymyślić algorytm który taki podział wyznacza i chciałem go tutaj opisać

Założenia:

  • Regiony powinny mieć nieregularny kształt.
  • Regiony powinny być podobnej wielkości
  • Rozkład regionów powinien uwzględniać lądy i morza, to znaczy nie może istnieć region wodno-lądowy.
  • Regiony nie mogą znajdować się poza dopuszczonym obszarem

Poniżej mapa określająca warunki dla regionów oraz efekt działania algorytmu

Moja metoda jest inspirowana bakteriami (jakimiś amebami). Ameby żyją na planszy i żywią się cukrem. Cukier ma pewien losowy rozkład na całej planszy. Ameby mogą zajmować nowe terytoria (rozrastać się) i zżerać się nawzajem.

Plansza symbolizuje ląd który dzielimy na obszary, a kiedy ameby zajmą cały obszar planszy, kształt ich ciał utożsamiamy z obszarami których szukamy.

Koniec bajeczki, algorytm:

Na początku zdefiniuje funkcje oceny opłacalności rozrostu ameby N na jakiś punkt k. Punkt k nie należy do N, ale sąsiaduje z N

ocena =
wsp1*[liczba punktów zajmowanych przez amebę N w okolicy punktu k] +
wsp2*[liczba punktów zajmowanych przez inne ameby w okolicy punktu k] +
wsp3*[odległość k od punktu początkowego ameby N] +
wsp4*[natężenie cukru w punkcie k] +

(jeżeli punk k jest pusty + BONUS_PUSTOSCI)

 

  1. Rozrzucam punkty początkowe ameb na całej planszy w sposób losowy, ale tak aby odległość dwóch dowolnych punktów <Rmin
  2. Wstawiam ameby które początkowo mają kształt okręgów o r<Rmin
  3. Znajduje i zapamiętuje wszystkie punkty sąsiadujące z amebą

while (true) {
    Dla wszystkich ameb {

  1. Spośród wszystkich punktów brzegowych ameby N znajduje ten o najwyższej ocenie (nazywam go k)
  2. Jeżeli k jest pusty zajmij, continue
  3. Jeżeli k zajęty przez amebe N\’ oblicz ocena(N\’,k)
  4. Jeżeli ocena(N\’,k)<ocena(N,k) * wsp_drapieżności odgryź amebie N\’ punkt k

}

co n kroków sprawdź czy ameby mają spójny kształt, jeżeli jakaś nie ma usuń części nie mające połączenia ze swoimi punktami początkowymi

}

W mojej symulacji do osiągnięcia zadowalającego efektu wystarczało 5000 – 10000 iteracji tego algorytmu.