Qix – jak to działa? Algorytm wypełniania właściwej części ekranu.

Qix w oryginale na automatach

Qix – gra, w której zamalowuje się ekran i w zasadzie nic więcej. Pisałem już o niej kiedyś. Dziś chcę zajrzeć bardziej w głąb i zapytać czy zastanawialiście się kiedyś jak to działa? Tym razem artykuł bardziej dla programistów i ciekawskich niż dla zwykłych graczy, ale liczę na to, że zainteresuję i zainspiruję wiele osób.

Qix

Na wstępie, w telegraficznym skrócie, przypomnienie. Na początku gry jest tylko ramka wokół ekranu, a w środku pusto. Lata tam Qix, czyli taki mały stworek, którego nie wolno dotykać. Gracz porusza się małą kropką w 4 kierunkach. Może to robić bezkarnie po krawędziach ekranu, ale jak wejdzie do środka, to zaczyna rysować za sobą linię. Qix nie może dotknąć linii, bo zabija gracza. Linię trzeba rysować docierając do dowolnej krawędzi. Rysując można dowolnie zakręcać, ale nie można przecinać rysowanej linii. Po dotarciu do krawędzi tworzy się zamknięty obszar. Ten obszar wypełniany jest kolorem i gracz może rysować dalej. Zmniejsza to puste wnętrze ekranu, dając Qixowi coraz mniej przestrzeni. Gracz wygrywa, gdy zamaluje odpowiednio dużą część powierzchni całego ekranu. Ot, cała filozofia.
Nadmienię jeszcze, że gier takich, jak Qix, było więcej; np. Volfied, czy Xonix.

Pierwsza porażka

Qix na PC – całkiem niezła konwersja z automatów

Pamiętam, że długie lata temu (będzie ze 20) myślałem nad algorytmem odpowiedniego zamalowania obszaru, gdy próbowałem zrobić swoją grę opartą na pomyśle Qixa. Jednak wtedy na tym poległem. Choć temat pozornie jest prosty, to sporym problemem okazuje się określenie, po której stronie linii zamalować ekran.

Odłożyłem ten temat na półkę, na długi czas. Nie chciałem jednak być pokonany. To nie może być tak trudne, jeśli mógł to zrobić komputer 8-bitowy! Niedawno pomyślałem, że spróbuję ponownie i wpadłem na pomysł… Czyli to jednak jest proste!

Jeśli ktoś z Was chce sam spróbować wymyślić, jak to działa, to w tym miejscu powinien przestać czytać. Zamierzam dość jasno przedstawić algorytm wypełniania właściwej części ekranu. Reszta gry jest tak prosta, że raczej nie wymaga wytłumaczenia.

Wstęp do algorytmu wypełnienia

W gruncie rzeczy to bardzo prosty algorytm, który można zrobić co najmniej na dwa sposoby – prostszy i bardziej złożony. W Qix funkcjonuje raczej ten prosty, ale złożony nie wymagał dużych zmian i też go zrobiłem. Różnica jest taka, że prosty algorytm zakłada, że ekran zostanie podzielony zawsze tylko i wyłącznie na dwie części, z czego w jednej jest tytułowy Qix, a w drugiej nie. To wystarcza do tej gry. Zauważcie, że w Qix może być tylko opisana wyżej sytuacja. Wyjątkiem są etapy, gdzie są dwa Qixy na ekranie, ale ich rozdzielenie powoduje natychmiastowe skończenie gry, bez zamalowywania! Czyli na jedno wychodzi.

Xonix na PC: Błąd w algorytmie wypełniania – zostały dziury.

Algorytm złożony pozwolił mi na zamalowanie jednocześnie wielu pół na ekranie i nie ma znaczenia ile jest Qixów. Podstawowa zasada jest taka, że wypełnia się tylko obszar, w którym nie ma Qixa. Każdy pusty i zamknięty obszar musi zostać zamalowany.  Podobny algorytm mógłby być w grze Xonix, w której jest więcej przeszkód jednocześnie na ekranie. Jednak gdy przyjrzałem się działaniu tej gry, to zauważyłem, że algorytm na pewno jest inny, pewnie ze względu na szybkość. Jednak jest niedoskonały. Dość często zdarza się, że nie cała powierzchnia zostanie poprawnie wypełniona i zostają „dziury”. Mój algorytm złożony nie posiada tej wady.

Kluczem do rozwiązania zagadki jest stworzenie odpowiedniego algorytmu Flood Fill, który w najprostszy możliwy sposób rekurencyjnie zamalowuje obszar na dwuwymiarowej bitmapie. Znacie to choćby z Painta w Windows.

Flood Fill

Flood Fill jest osobnym algorytmem, ale skrótowo go omówię, bo jest prosty jak konstrukcja cepa. Na dwuwymiarowej bitmapie rozpoczyna się w dowolnym punkcie zamalowanie. Funkcja rekurencyjna zamalowuje podany piksel i sprawdza wszystkie 4 strony wokół tego piksela na bitmapie. Jeśli znajdzie się tam piksel, który jest w tym samym kolorze, co kolor początkowy, to rekurencyjnie wywoływana jest ta sama funkcja dla każdej z 4 stron wokół środka.
Tym sposobem zostaje zamalowana cała połączona przestrzeń w jednym kolorze, niezależnie od jej rozmiaru i kształtu.
Ograniczeniem może być wyłącznie pamięć, ponieważ wywołania rekurencyjne odkładają się na stosie i im większa bitmapa, tym więcej pamięci zostanie zajęte w momencie krytycznym, co może spowodować brak miejsca na stosie i przerwanie algorytmu. Pomińmy jednak ten problem, gdyż dziś ma małe znaczenie, choć z pewnością na 8-bitowcach było to bardzo ważne!

Algorytm prostszy

Wracając do Qix, omówię najpierw algorytm prostszy, czyli ten, który prawdopodobnie jest w grze Qix. Mówię „prawdopodobnie”, ponieważ nigdy nie widziałem kodu tej gry, a algorytm wymyśliłem i sprawdziłem samodzielnie. Jeśli jest inny, to trudno – może znalazłem alternatywę :).

Na początku ważne założenia:

a) proces wypełniania rozpoczyna się natychmiast po zakończeniu rysowania linii, która musi zostać doprowadzona do dowolnej krawędzi
b) linia nie może się z niczym stykać ani przecinać (także siebie)
c) poprowadzona linia zawsze podzieli powierzchnię ekranu na dwie części w dowolnych kształtach

Proces

Trudność polegająca na decyzji, którą część zamalować, najłatwiej rozwiązać zamalowując… cokolwiek! Tak. Wystarczy znaleźć pierwszy z brzegu punkt niezamalowany i rozpocząć wypełnianie. Dla porządku zapiszę kroki w punktach:

1. Najpierw trzeba znaleźć pierwszy piksel na mapie, który nie jest jeszcze wypełniony. Na początku będzie to piksel w samym rogu mapy, a później trzeba go już odszukać. Najłatwiej przeglądać po kolei wszystkie piksele aż do momentu znalezienia wolnego.
2. Aby nie malować od razu po mapie widocznej na ekranie (nazwijmy ją A), trzeba ją skopiować do osobnej bitmapy. Nazwijmy ją B.
3. Rozpoczyna się Flood Fill na bitmapie B w  znalezionym miejscu (pkt 1).
4. Podczas wypełniania algorytmem Flood Fill należy sprawdzać jednocześnie w każdym zamalowywanym pikselu, czy stoi na nim Qix. Jeśli stoi, to należy ten fakt zapamiętać (nic to nie zmienia w wypełnianiu).
5. Po skończeniu wypełniania powierzchni mamy pewność, że:
a) zamalowana została jedna z dwóch części mapy
b) jeśli podczas wypełniania nie trafiono na miejsce, gdzie stoi Qix, to jest już pewne, że zamalowana została poprawna część ekranu
c) w przeciwnym wypadku, jeśli podczas wypełniania trafiono na miejsce, gdzie stoi Qix, to wiadomo, że powinna być wypełniona pozostała część ekranu (odwrócenie zamalowanego obszaru)
6. Teraz należy skopiować z mapy B do mapy A zamalowany obszar zgodnie z zasadami:
a) należy kopiować tylko piksel, który na mapie A nie był wcześniej zamalowany
b) jeśli podczas wypełniania nie trafiono na pozycję Qixa, to trzeba skopiować cały obszar wypełniony na mapie B
c) w przeciwnym wypadku, jeśli podczas wypełniania trafiono na pozycję Qixa, to trzeba na mapie A zamalować piksel, który na mapie B nie był zamalowany (odwrócenie)

To wystarczy. Niezależnie od miejsca Qixa i kształtu linii, zamalowany zawsze będzie właściwy obszar. Algorytm wymaga jednego przebiegu Flood Fill oraz dwóch kopiowań całej bitmapy. Nie jest to tak dużo. Zwróćcie uwagę ile czasu zajmuje w oryginalnej grze zamalowanie każdego obszaru! Wcale nie tak szybko.

Algorytm złożony

Jest to już moje usprawnienie algorytmu prostszego. Powyższy algorytm nie wystarczy, jeśli zechcemy mieć na ekranie więcej niż 1 Qixa i pozwolić na dowolne zamalowywanie obszarów. W przypadku dwóch Qixów może dojść do błędnej sytuacji po rozdzieleniu Qixów na oddzielnych obszarach. Po narysowaniu kolejnego obszaru zostaną utworzone 3 osobne, niezamalowane obszary, z czego w dwóch są Qixy. Wówczas wypełniony zostanie jeden z obszarów z Qixem w środku.
Drugi problem to dopuszczenie do sytuacji, kiedy chcemy w jednym przebiegu zamalować kilka pustych obszarów naraz, niezależnie od tego ile jest Qixów na ekranie. Jeśli zamalowywany będzie obszar bez Qixa, to wszystkie pozostałe obszary zostaną uznane za „odwrotność” i tylko ten jeden będzie zamalowany, a reszta zostanie pusta. Czyli nie zamaluje się wszystko naraz.

Przykładowa aplikacja obrazująca opisany algorytm (źródła poniżej)

Modyfikacja algorytmu polega na wprowadzeniu pętli. Cały algorytm powtarzany jest w tej pętli wielokrotnie. Dodamy zostaje prosty licznik przebiegów (identyfikator, nazwijmy go ID).
1. Początek pętli, zwiększenie ID o 1
2. Trzeba wyszukać pierwszy niezamalowany piksel na mapie B.
3. Jeśli nie znaleziono pustego piksela, to algorytm zostaje zakończony.
4. Jeśli znaleziono, to wykonuje się wypełnianie zgodnie z algorytmem prostym. Drobna modyfikacja podczas wypełniania polega na tym, by każdemu zamalowanemu pikselowi zapisać dodatkowo bieżącą wartość ID (czyli piksel powinien się składać z dwóch wartości: czy jest zamalowany i jaki ma ID)
5. Następuje kopiowanie z mapy B do A. Tu kolejna modyfikacja: jeśli podczas wypełniania trafiono na pozycję z Qix, to kopiowanie zostaje pominięte. Jeśli nie, to kopiowane zostają tylko piksele, które mają wartość ID taką, jaka jest bieżąca wartość ID.
6. Powrót do początku pętli (pkt 1).

Po co wprowadzony jest ID? Podczas Flood Fill nigdy nie wiadomo czy zostanie znaleziony Qix czy nie. Dlatego każde wypełnianie ma swój osobny identyfikator. Kopiowany jest więc tylko ostatnio wypełniony obszar, pod warunkiem nie natknięcia się na Qix. W całym przebiegu algorytmu zamalowywana jest zawsze cała mapa B, aby mieć pewność, że żaden obszar nie został pominięty. Stąd potrzeba odróżnienia tych obszarów. Na koniec pętli w mapie A zostają zamalowane tylko zamknięte obszary, w których nie ma Qix i obojętne jest ile Qixów na mapie się znajduje i ile obszarów jest pustych.

Zakończenie

Skomplikowane? Nie! To naprawdę proste. Program robiący to, co opisałem, też jest bardzo krótki! Chcecie zobaczyć? Pewnie, że chcecie. Poniżej link do pobrania źródeł programu. Możecie sobie przejrzeć, modyfikować, pobawić się i napisać na bazie tego dowolną grę w tylu Qix! Jeśli komuś pomogłem, to największą radością będzie dla mnie, gdy wyśle do mnie wiadomość (może być w komentarzach poniżej) i opowie co zrobił, a nawet się tym pochwali. Cały program jest mojego autorstwa, więc będzie mi miło, jeśli zostanie użyty, a gdzieś małym druczkiem pojawi się informacja o tym skąd zaczerpnięte są źródła. Nic więcej nie potrzebuję w zamian!

Jakies komentarze? Uwagi? Może inne podejście do problemu? Piszcie w komentarzach, chętnie porozmawiam.

Tym razem było mniej niż zwykle o starych grach, a jednak to też temat starych gier.

Do pobrania:

  • Qix Algorithm – przykładowy projekt w C# (.NET 4.5, WPF)
  • Qix Algorithm – przykładowy projekt w Delphi XE 10.2 (może być w wersji Community)

O GadZombiE

Zajrzyj na stronę "O mnie i o stronie".
Tagi , , , , , , , , , , , .Dodaj do zakładek Link.

Dodaj komentarz

Twój adres email nie zostanie opublikowany.