Algorytm wypełniania obszaru, przez zalewanie (ang. flood fill) w różnych odmianach, jest stosowany do kolorowania obrazów rastrowych. W tym artykule przedstawiono algorytm zalewania, który został wykorzystany, do rozwiązywania labiryntów z zawodów robotów micromouse. Wykonywanie dużych labiryntów i testowanie robota dla różnych konfiguracji labiryntów oraz algorytmów mapowania i znajdowania najkrótszej drogi do celu jest bardzo czasochłonne. W wielu przypadkach przed przystąpieniem do testów na rzeczywistym sprzęcie wygodniej i szybciej jest przetestować dany algorytm w symulatorze dla typowych konfiguracji labiryntu.

Do tworzenia takich symulatorów bardzo dobrze nadaje się Java, która dzięki bogatym IDE tj.: Eclipse, Netbeans pozwala na szybkie napisanie interaktywnego apletu. Taki aplet możemy następnie umieścić na stronie i każdy użytkownik, który ma zainstalowaną Wirtualną Maszynę Javy (JVM) może w pełni korzystać z naszego symulatora bez potrzeby jego instalacji czy ściągania dodatkowych plików.

Micromouse podstawy

Zawody micromouse polegają na skonstruowaniu robota, który w jak najkrótszym czasie dotrze z pozycji startowej do pozycji docelowej (środka labiryntu). Na wykonanie tego zadania robot ma zazwyczaj 2 przejazdy, z których pierwszy przejazd jest przejazdem wykorzystywanym na mapowanie struktury labiryntu a drugi polega na jak najszybszym dotarciu do środka labiryntu na podstawie danych zgromadzonych z 1 przejazdu (mapowania). Na ostateczny wynik czasu rozwiązania labiryntu składa się czas 2 przejazdu oraz 1/30 pierwszego (pomijam tu kary). Przy takim sposobie obliczania wyniku końcowego prędkości robotów przy 1 przejeździe są znacznie niższe niż przy 2, tak, aby dokładnie zmapować komórki labiryntu. Najpopularniejszą kategorią na zawodach micromouse jest tzw. kategoria „Classic Micromouse”.

W tej kategorii labirynt składa się z 256 kwadratowych komórek (16×16). Punkt startowy znajduje się w jednym z rogów kwadratowego labiryntu a punkt docelowy (meta) dokładnie w jego środku. Obszar docelowy jest łatwo wykrywalny przez robota gdyż jest pustym kwadratem składającym się z 4 komórek.

Algorytmy mapowania z poszukiwaniem celu

Mapowanie labiryntu polega na zapamiętywaniu położenia istniejących ścian dla każdej odwiedzonej komórki. W celu skrócenia czasu symulacji przyjęto, że robot dąży do celu jednocześnie mapując labirynt. Oznacza to, że w pierwszym przejeździe robot mapuje labirynt do momentu odnalezienia celu (środka labiryntu). W drugim przejeździe wybiera najkrótszą drogę z pośród zmapowanych wcześniej komórek (z 1 przejazdu).

Poszukiwanie celu może być wykonywane w oparciu o algorytmy naiwne wykorzystujące regułę prawej lub lewej ręki, co przedstawia rysunek 1. Nie pozwalają one jednak rozwiązać labiryntów, których środkowy kwadrat (cel) nie jest połączony za pomocą ścian z brzegiem labiryntu. Z pośród dostępnych w symulatorze labiryntów jedynie labirynt z 2008 roku można rozwiązać stosując obie te metody. W Algorytmie losowym (random) kolejny ruch robota jest losowany z puli ruchów możliwych do wykonania. Algorytm ten pozwala rozwiązać dowolny labirynt jednak czas mapowania nie jest powtarzalny.

Algorytm wykorzystujący regułę prawej ręki

Flood Fill - Algorytm Prawej Ręki Flood Fill - Labirynt rozwiązany algorytmem wykorzystującym regułę prawej ręki

Rysunek 1: Labirynt rozwiązany algorytmem wykorzystującym regułę prawej ręki

Algorytm zalewania

Zakładamy, że mamy jakieś źródło wody (lub innego ulubionego napoju). Zalewanie zaczynamy od punktu docelowego (do którego chcemy dotrzeć), czyli w naszym przypadku od środka labiryntu. Na samym początku nie mamy żadnej wiedzy o strukturze labiryntu stąd pierwsze zalewanie przeprowadzamy tak jakby labirynt był pustym kwadratem. Wiemy, że woda (napój) rozlewana z naszego źródła w środku labiryntu będzie się rozchodzić we wszystkich kierunkach równomiernie gdyż nie napotka na opór w postaci ścian wewnętrznych jak założyliśmy wcześniej. Rysunek 2 przedstawia drugi krok (poziom) zalewania a rysunek 3 krok, w którym cały labirynt został zalany.

Flood Fill - Początek zalewania labiryntu (2 poziom)
 

Rysunek 2: Początek zalewania labiryntu (2 poziom)
Jak wspomniano wcześniej cel składa się z czterech sąsiednich komórek (bloków) niepołączonych wewnątrz ścianami, dlatego zalewanie rozpoczyna się jednocześnie na tych 4 blokach. W pierwszym kroku zalewane są bloki sąsiadujące z 4 blokami celu w kierunkach poziomym i pionowym (zakładamy, że robot nie porusza się po skosie). Bloki zalane w kroku 1 mają wartość 1 i są pierwszym poziomem zalewania zgodnie z rysunkiem 2.

W dalszej kolejności zalewane są bloki sąsiadujące z blokami o wartości 1 i przypisana zostaje im wartość 2. Innymi słowy w bieżącym kroku zalewania zalewane są bloki sąsiadujące z blokami z poprzedniego kroku. Proces iteracyjnego zwiększania wartości bloków zalewanych w kolejnych krokach trwa do momentu zalania całego labiryntu. Schemat blokowy algorytmu zalewania całego labiryntu pokazano na rysunku 4. Dla pojedynczego bloku z danego poziomu zalewania (bieżącego kroku) zalewanie sprowadza się do sprawdzenia czy można zalać 4 sąsiadujące w pionie i poziomie bloki.

Przyjmując indeksowanie bloków labiryntu od 0 do 255 jak na rysunku 5 łatwo można znaleźć 4 sąsiadujące z nim bloki w granicach siatki labiryntu. Oznaczając indeks danego bloku, jako „I” wiemy, że jego prawy sąsiad będzie miał indeks „I+1”, lewy „I-1”, górny „I+16” a dolny „I-16” co można sprawdzić biorąc sobie blok o dowolnym indeksie z siatki labiryntu z rysunku 5. Zalewamy tylko te bloki, które jeszcze nie zostały zalane (o wartościach 0) oraz nieposiadające ściany od strony bloku, z którego następuje zalewanie zgodnie ze schematem blokowym z rysunku 6. Jeśli sąsiedni blok spełnia te wymagania to zostaje on zalany (otrzymuje wartość o 1 większą od wartości bloku, z którego zalewamy) a jego indeks zostaje zapamiętany w tablicy i sprawdzany w kolejnym kroku (poziomie) zalewania.

Flood Fill - Wartości komórek (bloków) labiryntu po całkowitym zalaniu (przed mapowaniem)

Rysunek 3: Wartości komórek (bloków) labiryntu po całkowitym zalaniu (przed mapowaniem)
Wykorzystanie algorytmu zalewania podczas mapowania i poszukiwania celu powoduje, że robot szybko dąży do środka labiryntu. W symulatorze ograniczono czas mapowania labiryntu do momentu osiągnięcia przez robota celu zgodnie ze schematem blokowym z rysunku 7. Ten schemat pokazuje, że robot wykrywa ściany komórki, w której aktualnie się znajduję a następnie sprawdza czy istnieje sąsiedni blok o mniejszej (lub równej) wartości, do którego może się przemieścić. Zalewanie labiryntu następuję dopiero wtedy, gdy wszystkie dostępne sąsiednie bloki mają większe wartości od wartości bloku, w którym aktualnie znajduje się robot. Ta operacja powoduje zmianę dotychczasowych wartości bloków labiryntu i wyznaczenie nowej trasy prowadzącej do celu (w kierunku malejących wartości). Po osiągnięciu celu następuję ostatnie zalewanie i wyznaczana jest najkrótsza droga łącząca punkt startowy z celem spośród zmapowanej części labiryntu, co pokazuje rysunek 8 (2 przejazd).

Podstawowe cechy symulatora:

  • wybór 1 z 4 metod rozwiązywania labiryntu
  • wybór labiryntu z zawodów All Japan Micromouse Competition z lat 2008-2011
  • regulacja prędkości robota (symulacji)
  • możliwość pracy krokowej (start, pauza, stop)
  • wyświetlanie liczby przejechanych bloków podczas mapowania (1 przejazd) i wyścigu do celu (2 przejazd)

Oprogramowanie Open Source użyte w projekcie:

  • kod symulatora – Eclipse
  • schematy blokowe – JavaBlock

Opisane w artykule przykłady zostały wygenerowane z symulatora napisanego przez autora w Javie. Symulator jest dostępny w postaci apletu na stronie mobilerobots.pl.

Flood Fill - Schemat blokowy algorytm zalewania całego labiryntu

Rysunek 4: Schemat blokowy algorytm zalewania całego labiryntu
Flood Fill - Przyjęte indeksowanie bloków labiryntu

Rysunek 5: Przyjęte indeksowanie bloków labiryntu
Flood Fill - Funkcja zalewania sąsiednich bloków

Rysunek 6: Funkcja zalewania sąsiednich bloków
Flood Fill - Mapowanie labiryntu z poszukiwaniem celu (algorytm flood-fill)

Rysunek 7: Mapowanie labiryntu z poszukiwaniem celu (algorytm flood-fill)
Flood Fill - Wynik działania algorytmu flood-fill - znalezienie najkrótszej drogi do celu spośród zmapowanej części labiryntu

Rysunek 8: Wynik działania algorytmu flood-fill – znalezienie najkrótszej drogi do celu spośród zmapowanej części labiryntu
Artykuł zwyciężył w konkursie, w którym do wygrania był WikiReader

  • Admn

    Bardzo ciekawy artykuł. Opisany prostym językiem i zainspirował mnie do rozwiązywania problemów algorytmicznych. Będzie więcej tego typu wpisów?