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
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.

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.
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.




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