Ten dział ma na celu przybliżyć Wam sposoby wykorzystania algorytmów w praktyce. Tytuł chyba najpowszechniej stosowanego podręcznika do algorytmiki autorstwa N.Wirtha brzmi: "Algorytmy + Struktury Danych = Programy". Zajmiemy się więc pisaniem programu, w którym wykorzystamy kilka algorytmów oraz struktur danych opisanych na tej stronie. Sporo czasu zajęło mi dobranie odpowiedniego programu przykładowego. Musi on być ciekawy i niezbyt skomplikowany. Zdecydowałem się na prostą grę. Sławny Bill Gates (ten od Microsoft) chwali się, że jednym z jego pierwszych programów była gra w kółko i krzyżyk. My pójdziemy trochę dalej i napiszemy tetris.
Oto założenia gry:

• W grze chodzi o ułożenie jak największej liczby klocków składających się z 4 kwadratów
• Linie całkowicie wypełnione klockami są usuwane
• Punktacja jest uzależniona od ilości jednocześnie usuniętych linii (od 1 do 4)
• 10 najlepszych wyników jest zapisana w pliku
• Jak każdy przykładowy program na tej stronie, gra jest napisana w Delphi 5

Możecie pobrać gotowy kod do gry, jednak zachęcam Was do samodzielnego napisania Tetrisu. Postępując zgodnie z moimi wskazówkami nie będziecie mieli problemów, choć zajmie Wam to zapewne 1 lub 2 wieczory. Po napisaniu jej jednak i skompilowaniu będziecie z siebie bardzo zadowoleni i będziecie mogli podpisać program swoim imieniem i nazwiskiem. A więc zaczynamy!
Podstawowe struktury danych
Zacznijmy od klocków i sposobu ich kodowania w pamięci. Oto 7 podstawowych klocków, każdy dodatkowo można obracać:

Musimy więc teraz dobrać odpowiednie struktury danych, których użyjemy do zapisu klocków w maszynie cyfrowej. Podobnie, jak było w przypadku grafów, graficzne przedstawienie klocków w pamięci komputera jest niemożliwe. Dobrym sposobem na zapisanie tych klocków jest dwuwymiarowa tablica logiczna. Ponieważ największy klocek (pierwszy na rysunku) ma wysokość równą 4 kwadraty a po obróceniu długość równą 4, więc tablica ta musi mieć rozmiary 4x4. Przy pomocy takiej tablicy możemy zapisać każdy z powyższych klocków, np. ostatni z naszego rysunki będzie zakodowany w następujący sposób:

F	T	T	F
T	T	F	F
F	F	F	F
F	F	F	F

W miejscu, w którym występuje kwadracik wpisujemy True a w pozostałych False. W tym przypadku wykorzystujemy tylko dwa pierwsze rzędy tablicy, ponieważ klocek ma wysokość 2 kwadraty.
Pierwszym krokiem będzie więc utworzenie siatek odpowiadającym wszystkim klockom (tak jak zrobiliśmy to przed chwilą dla ostatniego). Liczba tych siatek nie będzie jednak równa 7 (tyle, ile klocków) ponieważ każdy klocek można obarcać w dowolne strony (oprócz kwadratowego, który po obróceniu nadal jest kwadratem). Podliczmy więc ile musimy utworzyć siatek:

• Klocek #1: jeden + po obróceniu 1 = 2
• Klocek #2: jeden + po obróceniu 3 = 4
• Klocek #3: jeden + po obróceniu 3 = 4
• Klocek #4: obracanie nie ma sensu = 1
• Klocek #5: jeden + po obróceniu 3 = 4
• Klocek #6: jeden + po obróceniu 1 = 2
• Klocek #7: jeden + po obróceniu 1 = 2

Łącznie musimy więc przygotować 19 siatek. Zajmie to trochę czasu, lecz taki zapis będzie później bardzo przydatny, np. gdy gracz zechce obrócić klocek, wystarczy tylko zastąpić aktualną siatkę inną.
Przystąpmy teraz do sposoby zapisania planszy. Również ją można traktować jako tablicę logiczną. Rozmiary musicie dobrać sami (u mnie ma ona 17x25 pól) pamiętajcie jednak, by nie była ona zbyt duża (gracz będzie miał zbyt dużo czasu do namysłu i w rezultacie gra będzie zbyt łatwa) ani zbyt mała. Ta tablica mogłaby być również logiczna (True oznaczałoby, że jakiś klocek został w danym polu osadzony a False, że nie) jeśli chcemy jednak, aby gra wyglądała lepiej możemy zastosować tablicę liczb całkowitych (tak jak ja to zrobiłem). Zwiększa to trochę złożoność pamięciową, ale czyni grę wizualnie lepszą, a dlaczego? Liczba 0 będzie oznaczała to samo co False a liczby od 1 do 7 to samo, co True. Przy wyświetlaniu obrazu jednak będziemy sprawdzać wartość liczb różnych od zera. Jeśli będzie to 1 to wyświetlimy np. kwadracik kolory czerwonego, jeśli 2 to kwadracik będzie niebieski itd. aż do 7. Liczby te przyporządkujemy naszym klockom. W rezultacie wszystkie klocki w czasie lotu z góry na dół (gdy gracz może nimi operować) będą tego samego koloru a po osadzeniu klocek przyjmie odpowiedni kolor, np. jedne klocki będą czerwone inne niebieskie itd... Jeśli nie rozumiesz co mam na myśli zagraj w moją wersję Tetris (jeśli jeszcze tego nie robiłeś), to zrozumiesz
Jeśli zdecydowaliście już, jaki rozmiar ma mieć Wasza tablica dodajcie do liczby jej kolumn 2 a do liczby wierszy 1. Dlaczego? Ponieważ pierwszą i ostatnią kolumnę tablicy wypełnimy liczbami -1 (będzie to symbolizować ściany planszy, której gracz nie może przekroczyć przesuwając klocek). To samo zrobimy z ostatnim wierszem tablicy, też wpiszemy w nim -1 (symbolizuje to "podłogę", na której będą się zatrzymywać pierwsze klocki). Dlaczego wpisujemy -1? dlatego, ze 1 jest już zajęte, ale możemy zamiast tego wpisać dowolną liczbę większą od 7 (np. jeżeli Wasza tablica jest wypełniana liczbami naturalnymi).
Algorytm poruszania klockami
Przejdźmy teraz do algorytmu poruszania klockami. Jest on niezmiernie prosty. Moduł generujący wyznacza jeden z 7 klocków. Następnie przechodzimy do opuszczania klocka w dół. Specjalna funkcja (w mojej implementacji jest to funkcja check) sprawdza, czy nasz klocek może zostać opuszczony o jeden kwadarcik w dół. W jaki sposób? Korzystamy z naszych struktur danych, których opracowanie zajęło nam tyle czasu. Sprawdzamy każdy kwadracik naszej siatki klocka i jeśli jego wartość jest ustawiona True sprawdzamy, czy klocek niżej w tablicy planszy jest równy 0. Jeżeli chociaż jeden klocek ma wartość różną od 0 to funkcja zwraca wartość False. Uwaga: wartość liczby w tablicy planszy sprawdzamy tylko dla tych kwadracików, które mają wartość True! Jeśli nasza funkcja zwróci wartość True to możemy opuścić klocek o jeden kwadracik w dół a następnie znów wywołujemy funkcję sprawdzającą. Postępujemy tak aż funkcja zwróci wartość False. Oznacza to, że pod klockiem znajduje się "podłoga" lub inny klocek i nie można już go opuszczać. W takim wypadku należy zapisać w odpowiednich komórkach naszej planszy liczbę większą od zera (najlepiej numer klocka). Odpowiednie komórki to komórki na których znajdują się kwadraciki naszego klocka, czyli pokrywające się z komórkami siatki o wartości True. Następnie możemy (ewentualnie) zmienić kolor osadzonego klocka i znów wywołać procedurę generującą numer klocka do opuszczenia i zacząć wszystko od nowa. Przedtem sprawdzamy jednak, czy pierwszy rząd naszej tablicy planszy ma jakieś pole o wartości różnej od 0. Jeśli tak to oznacza to, że cała plansza została pokryta klockami i następuje koniec gry!
Zastanówmy się teraz nad algorytmem sterowania klockami przez gracza. Jest on bardzo podobny do algorytmu opuszczania z tą różnicą, że funkcja sprawdza nie pole pod klockiem, lecz na prawo (jeśli została wciśnięta strzałka w prawo) lub na lewo (jeśli wciśnięto strzałkę w lewo). Jeśli pole np. na lewo jest wolne, to znaczy równe 0 to przesuwamy klocek. Jeśli natrafiliśmy na liczbę większą od 0 to po lewej stronie znajduje się inny klocek i nie można przesunąć naszego. Jeśli natrafiliśmy na liczbę -1 to znaczy, że dotarliśmy do ściany.
Usuwanie zapełnionych linii
Teraz przejdźmy do usuwania linii zapełnionych klockami. Przed każdym wywołaniem procedury generującej numer klocka do opuszczenia należy sprawdzić (od góry), czy istnieje jakiś wiersz tablicy planszy cały wypełniony liczbami różnymi od 0. jeśli tak to ustawiamy wartość komórek tego wiersza na 0 a następnie opuszczamy o jedno pole wszystkie wiersze nad tym wierszem. A zatem jeśli np. 7 wiersz jest wypełniony to zerujemy go i opuszczamy o jeden wiersz 6, 5, 4, 3, 2, 1. Gdy to zrobimy przechodzimy do kolejnego wiersza i znów sprawdzamy, czy jest cały wypełniony liczbami różnymi od 0. Robimy to ze wszystkimi wierszami od pierwszego do ostatniego. Aby zmniejszyć złożoność obliczeniową tego procesu można go przerwać gdy jednocześnie zostaną usunięte 4 wiersze (ponieważ wyższy klocek ma wysokość 4 kwadraty). Należy jednocześnie liczyć ile wierszy zostało jednocześnie usuniętych, będzie to przydatne w punktacji, ponieważ im więcej wierszy zostało jednocześnie usuniętych, tym więcej punktów przyznaje się graczowi. W mojej implementacji jest to: 5 pkt. za 1 wiersz, 15 pkt. za 2 wiersze, 40 za 3 i 75 za 4.
Liczbę punktów również należy kontrolować, po przekroczeniu pewnego progu należy zwiększyć prędkość opadania klocka i tym samym zwiększyć poziom gry o 1.
Zapisywanie wyników
Teraz zajmiemy się przetwarzaniem wyników graczy. 10 najlepszych powinno znaleźć się w rankingu. Zapisujemy je w pliku. Z pliku wczytujemy je do tablicy rekordów(w moim przypadku rekord składał się z następujących pól: Imię gracza, liczba zdobytych punktów, poziom i czas gry). Tablica ma rozmiar 11. Po co 11 indeksów, jeśli pamiętamy tylko 10 wyników? Już wyjaśniam. Po zakończeniu gry wpisujemy wynik gracza do pierwszego wolnego indeksu tablicy. Index 11 wykorzystujemy w przypadku, gdy w naszym pliku mamy już 10 wyników. Następnie sortujemy tablicę (np. QuickSortem) wg. liczby punktów i zapisujemy w tym samym pliku ale znów tylko 10 wyników (eliminując 11, który jest najgorszy).
Podsumowanie

I to już wszystko. Macie już wszystko, co potrzeba do napisania gry Tetris. Powinniście otrzymać coś w stylu gry przedstawionej na poniższym obrazku:

Nie powinniście mieć większych problemów z implementacją, ale udostępniam Wam mój kod źródłowy. Jego analiza na pewno ułatwi Wam pracę. Poniżej podaję opis wszystkich ważniejszych funkcji procedur mojej implementacji.

• funkcja check sprawdza, czy pole pod klockiem, na lewo od niego, bądź na prawo (w zależności od parametru) jest wolne
• procedura dell_from_desk usuwa klocek z planszy
• procedura dock_block dokuje klocek na planszy: ustawia jego kolor oraz zapisuje w tablicy planszy jego identyfikator, by inne klocki nie mogły wejść na jego miejsce
• procedura end_of_game czyści planszę i podlicza punkty
• funkcja line sprawdza, czy na planszy znajduje się jakiś wiersz cały wypełniony klockami
• procedura erase wywołana przez funkcję line usuwa dany wiersz planszy i opuszcza wszystkie wiersze nad nim o jedno pole w dół
• procedure new_block generuje numer klocka do opuszczenia
• procedura print_on_desk rysuje klocek na planszy wg jego siatki
• procedura quicksortR_middle rekurencyjne sortowanie metodą szybką ze środkowym elementem wyboru
• procedura reset czyści tablicę planszy i klocka
• procedura refresh_desk rysuje kwadraciki w kolorze zależnym od wartości liczby w tablicy planszy
• procedura results wpisuje wynik do tablicy rekordów, wywołuje procedurę sortującą a następnie przepisuje dane do pliku