Losowe pole złożone z sześciokątów (Hex)

Witam.

Piszę małą gierkę i muszę wygenerować planszę do rozgrywki.

Plansza ma się składać z (również losowo wygenerowanych), sąsiadujących ze sobą (stykających się brzegami przynajmniej w 1 punkcie) pól, o różnym kształcie i różnej wielkości. Podstawowym budulcem każdego takiego pola, ma być "cegiełka" w postaci sześciokąta (hexa). Przykład graficzny:

Problem mam taki, że nie bardzo mam pomysł na jakiś sensowny algorytm generujący takie pola. Na obecną chwilę robię coś takiego:

1. Tworzę sobie tablicę dwuwymiarową, w której przechowuję siatkę hexów (tablica zawiera współrzędne wszystkich 6 wierzchołków każdego sześciokąta).

2. Wybieram sobie dany hex w tej siatce - np. [X = 5, Y = 5] i sprawdzam z jakimi sześciokątami sąsiaduje
3. Sprawdzam które z sąsiadujących hexów są dla mnie atrakcyjne, czyli nie zostały już przyporządkowane do innego pola. Jeżeli zostały, wyrzucam je z puli.
4. Po dokonaniu powyższej selekcji, losuję z puli sąsiadów któryś z pozostałych sześciokątów.
5. Przeskakuję na hexa którego właśnie wylosowałem, włączam go do pola i rozpoczynam algorytm od nowa (rozpoczynając od tego właśnie hexa).
6. Powyższe czynności powtarzam określoną ilość razy (np. 20, gdy chcę aby pole składało się z 20 hexów).

Niestety przy tak skonstruowanym algorytmie często dochodziło do sytuacji, gdy swoisty "wężyk" zaganiał się w kozi róg, dochodząc do sześciokąta, który nie miał już wolnych, nadających się do "wchłonięcia" sąsiadów, na których można by przeskoczyć (wywalało błąd).

Dodałem więc modyfikację:

Gdy algorytm dojdzie do sytuacji, w której brak jest wolnych sąsiadów (a nadal musi powtórzyć operację jeszcze określoną ilość razy), cofa się o 1 sześciokąt i próbuje ponownie. W razie porażki (nadal nie ma wolnych sąsiadów) znowu cofa się o 1 hexa, próbuje i tak aż do skutku.

Problem teoretycznie został rozwiązany, choć oczywiście jest to rozwiązanie bardzo "chałupnicze" i mało wydajne.

Pozostaje też drugi problem - koncentracja hexów. Zdając się na zupełną losowość, zbyt często dochodzi do sytuacji gdy sklecone z sześciokątów pole ma strasznie nieregularny kształt (jest zbyt szerokie, wąskie, za bardzo rozciągnięte, wężykowate, ma w środku dziury itd).

Dodałem więc coś na kształt priorytetów. Działa to tak, że algorytm losując np. ruch w prawo (przeskakując na sąsiada po prawej), automatycznie obniża priorytet dla ruchu wprawo i podnosi priorytet dla ruchu w lewo, dół i górę. Dzięki temu po np. 4 następujących po sobie ruchach w prawo, szansa na wykonanie piątego ruchu w prawo wynosi już tylko 0.6, natomiast dla pozostałych kierunków jest to 1.4 (modyfikator 0.1).

Trochę to pomogło ale nadal efekt nie jest zbyt dobry (nadal powstają dziwne potworki).

Doszedłem też do wniosku, że generując pola w ten sposób, będę miał zbyt duży problem w ich regularnym sąsiedztwie. To znaczy pola nie będą się ładnie i równo stykać krawędziami i będą miały jedynie (w najlepszym razie) kilka sąsiadujących ze sobą sześciokątów.

Szczerze mówiąc nie mam już pomysłu na modyfikację mojego pierwotnego pomysłu, dlatego zwracam się z prośbą o podsunięcie jakiejś koncepcji. Nie pytam o gotowy kod tylko o pomoc w skleceniu bardziej wydajnego algorytmu. Mile widziana byłaby możliwość kontroli wielkości pola (minimalna i maksymalna szerokość oraz wysokość).

Preferowany język programowania : Delphi

Rozważałeś użycie automatów komórkowych? Na pewno czytałem gdzieś w internecie o zastosowaniu ich w generowaniu map w postaci jaskiń (problem jaki rozwiązywały to takie wygenerowanie mapy, żeby z każdego punktu jaskini można było dotrzeć do każdego innego; brak oddzielnych, zamkniętych, odosobnionych obszarów).
To na pewno nie jest gotowe rozwiązanie, chociażby z tego powodu, że klasyczne automaty działają na siatce o polach w kształcie kwadratów. Poza tym Ty chcesz wydzielić n ciągłych obszarów i to jeszcze najlepiej o zadanym polu powierzchni... Ale może to krok w dobrym kierunku?

Wprowadziłem inne rozwiązanie. Nadal wymaga modyfikacji, ale czuję, że idę w dobrą stronę ;).

Otóż zrobiłem coś takiego:

1. Wyznaczam sobie hexy centralne każdego regionu (losuję im X,Y na siatce).
2. Sprawdzam jakich sąsiadów mają te hexy (może ich być od 0 do 6).
3. Znalezionych w punkcie 2 sąsiadów włączam do regionu.
4. Powtarzam cały proces z punktów 2 i 3, ale już nie dla hexów centralnych regionów, tylko dla wszystkich pól jakie włączyłem do regionu (przypomina to więc rozlewanie się cieczy, taki rozszerzający się okrąg z przyrostem 1 "obręczy" przy każdym powtórzeniu).
5. Oczywistym jest, że wcześniej czy później rozszerzające się okręgi wejdą w kolizję. W takim wypadku hexa "zagarnia" ten region, który jest bliżej tego "pożeranego" sześciokąta. Jeżeli oba regiony chcą zając hexa jednocześnie (mają tak samo blisko), rozstrzyga losowanie.

Wygląda to już całkiem nieźle.

Zalety:

1. Cała plansza jest zajęta.
2. Regiony ładnie i "czysto" ze sobą sąsiadują, nie ma czegoś takiego jak odcięte od reszty wysepki, ich linie graniczne ścierają się idealnie i na pełnej długości.
3. Mogę bez problemu wygenerować jednocześnie dowolną liczbę regionów.
4. Mogę łatwo sterować wielkością regionów, wyznaczając (zamiast hexów centralnych) całe "rdzenie" o określonej wielkości (np. 7 sześciokątów), do których algorytm łatwo dobuduje sobie resztę.

Wady:

1. Z uwagi na to, że hexy (lub rdzenie) centralne są losowo lokowane, algorytm generuje mi czasem straszne potworki. Np. 1 region jest ogromny (bo z nikim nie konkurował), a obok niego 5 malutkich poletek o powierzchni kilku sześciokątów (nie dały rady się rozrosnąć bo wzajemnie się zwalczały). Musiałbym wprowadzić jakieś ograniczenia, które sprawiłby, że regiony nie mogą "osiedlać się" zbyt blisko siebie. Nadal jednak musiałoby to być losowe, żeby każda plansza była inna i niepowtarzalna. Nie mam w tej materii żadnych sensownych pomysłów (zakładając, że rdzenie nie są identyczne).
2. Plansza generowana w ten sposób jest trochę "zbyt idealna". Brakuje jakiś postrzępień, luk, wyrw, nieregularnych krawędzi, dziur czy po prostu brakujących regionów. Niby mogę coś próbować losowo wycinać i wyrzucać, ale obawiam się, że efekty mogą być zbyt nieprzewidywalne (np. stworzę odcięte od reszty mapy wysepki albo brak oczywistego sąsiedztwa z powodu 1 brakującego hexa). Musiałbym wprowadzić jakieś obwarowania, żeby losowość nigdy nie była w stanie stworzyć takich efektów. Niestety nie mam jeszcze pomysłu jak.