Dokumentacja programu semestralnego "Szewc" autor: Karol Bienkowski, I Inf, 1998/99, gr. JJ Patrz tez plik: pomoc.txt 1. Podstawowe informacje o programie 1.1. Program bedzie umozliwiac rozegranie partii Szewca na planszy toroidalnej o rozmiarach MxN, gdzie 1<=M,N<=10) 1.2. Program pracowac bedzie w trybie graficznym, przy czym obsluga grafiki zostanie opracowane przy wykorzystaniu standardu BGI. Komunikacja z uzytkownikiem odbywac sie bedzie przy pomocy myszki oraz klawiatury 1.3. Mozliwosci programu: - rozgrywanie gry miedzy czlowiekiem i komputerem, dwiema osobami oraz przez komputer z samym soba, zliczanie wygranych gier - wyswietlanie na ekranie informacji o aktualnym stanie gry, dzwiekowe powiadamianie o niektorych zdarzeniach - cofanie sekwencji ruchow (uzytkownik moze cofnac ruchy tak by ostatnim cofnietym ruchem byl jego wlasny) - automatyczne generowanie planszy wg kryteriow ustalonych przez uzytkownika (wymiary i procent zajetych bokow) - wczytanie i zapisanie planszy do pliku - ustawienia (i zapisanie) opcji programu: dzwiek, parametry generowanej planszy, imiona graczy, czas do namyslu - ustawienie ograniczenia czasu przeznaczonego na gre dla komputera 1.4. Wymagania programu - system DOS lub Windows - komputer z karta graficzna pracujaca w standardzie VGA - wskazany (ale niekoniecznie) kolorowy monitor i mysz 1.5. Ponizszy schemat ilustruje wyglad ekranu: /-------------------------------------------\ | +------------------+ +---------------+ | | | | |Gracze i punkty| | | | PLANSZA | +---------------+ | | | | | | | | Przyciski | | | | funkcyjne, | | +------------------+ Ustawienia | | Miejsce na komunikacje | \-------------------------------------------/ Miejsce na komunikacje - w tej czesci ekranu pojawiac sie beda zapytania skierowane do uzytkownika, np. "podaj nazwe pliku:","czy na pewno chcesz zakonczyc gre?". 1.6. Algorytm szukania optymalnej strategii: Za sukanie ruchow komputera jest odpowiedzialny modul Grajacy. Ma on struktury danych, ktore zawieraja ruchy uznane przeze mnie za najlepsz. Procedura rekurencyjna wynajduje kolejne najlepsze ruchy i wywoluje sie rekurencyjnie, i na tej podstawie ocenia wartosc ruchu, by wybrac najlepszy (kryterium 'najlepszosci' to maksymalna ilosc zdobytych punktow). 2. Planowany podzial na moduly: 1. Program - glowna petla, wykonywanie na zmiane ruchow 2. Deklarac - deklaracje typow uzyawnych w wiekszosci modulow 3. Plansza - obsluga planszy 4. PlanElem - wyswietlanie elementow planszy gry 5. Napisy - wyswietlanie pozostalych elementow graficznych, glownie napisow 6. Opcje - modyfikacja ustawien programu 7. Pliki - obsluga plikow - z plansza, konfiguracja, scizka do BGI 8. StosCofn - obsluga stosu cofania 9. Mysz - obsluga myszki 10. Grajacy - strategia komputera Ponizej przedstawione sa najwazniejsze cechy modulow, ich powiazania, glowne zmienne i procedury. Oprocz opisanych wiekszosc modulow wukorzystuje takze moduly Crt, Graph, Deklarac. Na poczatku opisu modulu jest czesc interface modulu. 2.1. Program glowny uses Plansza, Grajacy, Napisy, Pliki, StosCofn, Mysz; Zawiera petle odpowiedzialna za przebieg gry, tzn. wykonywania na zmiane ruchow przez graczy. Ruchy komputera wczytuje z modulu Grajacy, a gracza modulu Plansza. Inicjuje i konczy grafike. Do tego ma wlasne procedury. 2.2 unit Deklarac interface Function Lanc (i : integer) : string; Procedure Dzwiek (typ : Tdzwiek); type TGracz = record rodzaj : Trodzaj; nazwa : string[20]; punkty : integer; partie : integer; mozeCof : boolean; {czy juz wykonal ruch (wtedy moze cofac)} end; TGracze = array[1..2] of Tgracz; {informacje o graczach} Tboki = array[orPion..orPoz,1..maxM,1..maxN] of TstanBoku; Tpola = array[1..maxM,1..maxN] of record typ : TtypPola; czyje : byte; {kto zajal pole - numer gracza} ile : byte; end; var ustawienia : Tustawienia; {konfiguowalne ustawienia programu} gracze : Tgracze; {dane o graczach} boki : Tboki; {Przechowuje informacje o bokach na planszy} pola : Tpola; {Przechowuje inforamcje o polach (kwadratach) na planszy} To tylko najwazniejsze zmienne zadeklarowane w tym module. boki i pola przechowuja informacje o sytuacji na planszy (o wyswietlonych bokach i polach), gracze - dane o graczach, ustawienia - wszystkie konfigurowalne ustawienia programu. Ze zmiennych tego modulu korzystaja praktycznie wszystkie inne (glownie Plansza i Pliki). Modul zawiera deklaracje wszystkich stalych, m.in. sciezek dostepu do plikow i stalych graficznych: wielkosci,polozenia i kolorow obiektow na ekranie. Zawiera jedna funkcje pomocnicza: Lanc - tworzy lancuch z liczby i jedna funkcje: Dzwiek - wydaje przy pomocy glosniczka PC dzwieki wg typu. 2.3. unit Plansza interface uses Napisy, Pliki, StosCofn, Mysz, Grajacy, {grajacego uzywa do cofaniaruchow} PlanElem, Opcje; Procedure WczytajRuch (var x,y : integer; var zdobyl : boolean); Procedure WyswietlRuch (x,y : integer; rodzaj : typRuchu; nrGracza : byte; var zdobyl : boolean); Procedure WyswietlEkranGry; Glowny modul. Uzywany tylka przez program glowny, sam uzywa wszystkich. Jest odpowiedzialny za wczytanie ruchu od gracza (w trybie graficznym oczywiscie) - procedura WczytajRuch i wyswietlenie ruchu komputera (WyswietlRuch). Te procedury odpowiednio modyfikuja wszystkie zmienne odpowiedzialne za stan gry (planszy), ktore sa zadeklarowane w module Deklarac. WyswietlEkranGry - wyswietla caly ekran na poczatku gry. 2.4. unit PlanElem interface uses Mysz; Procedure WyswietlBok (x,y : byte; orient : Torientacja; typBoku : TtypBoku); Procedure WyswietlPole (x,y : byte); Procedure WyswietlRog (x,y : byte); Modul uzywany tylko przez modul Plansza. Wyswietla na ekranie graficzne elementy planszy do gry, tzn. boki, pola i rogi (skrzyzowania bokow). Procedura WyswietlBok wyswietla takze kursor (jezeli typBoku=bokKurs). Modul Mysz jest uzywanty do ukrywania wskaznika myszy na czas wyswietlania elementu. 2.5. unit Napisy interface uses Mysz; Procedure Komunikat (tekst : string; typ : typKomunikatu); Function PytanieTN (tekst : string) : boolean; Function WczytajLanc (tekst : string) : string; Procedure WyswietlGraczy; Procedure WyswietlRamke; Procedure WyswietlInfo; Procedure WyswietlPomoc; Procedure WyswietlUstawienia; Zawiera procedury wyswietlajace na ekranie elementy nie tworzace bezposrednio planszy gry, tzn. glownie napisy. Uzywany przez wiele modulow (Program, Plansza, Pliki, Opcje). Trzy pierwsze procedury wyswietlaja cos na dole ekranu: Komunikat - wyswietla napis na dole ekranu, PytanieTN - wyswietla na dole ekranu pytanie z dwoma mozliwymi odpowiedziami i czeka na reakcje uzytkownika WczytajLanc - czyta lancuch z klawiatury, WyswietlInfo i WyswietlUstawienia wyswietlaja wymiennie dostepne klawisze z prawej strony ekranu, u dolu. WyswietlPomoc - uzywa calego ekranu do wyswietlenia 30 wierszy plik txt, WyswietlRamke - ramka dookola calego ekranu z tytulem programu. 2.6. Opcje interface uses Napisy, Pliki, Mysz; {***Wywolywane podczas normalnej gry***} Procedure ZmienNazwe (ktory : byte); - zmienia nazwe gracza Procedure PrzelaczDzwiek; Procedure CzyWyjsc; Function Nowa_Gra : boolean; Procedure NowaPlansza (nazwa : string); Procedure ZmienUstawienia; {***Wywolywane w trybie 'Ustawienia'***} Procedure ZmienKtoZKim; Procedure WczytajDwieLiczby (tekst : string; separator : char; var i1,i2 : integer; var sukces : boolean); Procedure ZmienWymiarMin; Procedure ZmienWymiarMax; Procedure ZmienProcZaj; Procedure ZmienCzasNamyslu; Uzywany tylko przez modul Plansza. Zawiera procedury przuporzadkowane klawiszom wyswietlanym w prawej dolnej czesci ekranu. Procedury te w interakcji z uzytkownikiem nadaja nowe wartosci zmiennym, dlownie z rekordu ustawienia, zadeklarowanego w module Deklarac. 2.7. unit Pliki interface uses Napisy; Procedure WczytajPlansze; Procedure ZapiszPlansze (nazwa : string); Procedure TworzPlansze; Procedure WczytajUstawienia; Procedure ZapiszUstawienia; Function WczytajSciezkeBGI : string; Procedure ZapiszSciezkeBGI (sciezka : string); Zawiera trzy grupy procedur obslugujacych trzy rozne pliki. Pierwsza WczytajPlansze,ZapiszPlansze,TworzPlansze odnosi sie do pliku w ktorym zapisane sa wymiary planszy i zajete boki (tak jak w konkursie). Procedury te korzystaja ze zmiennych boki i pola (oraz innych), odpowiednio je modyfikujac (WczytajPlansze). TworzPlansze generuje plik z plansza wg ustawien uzytkownika (record ustawienia). Druga grupa (WczytajUstawienia,ZapiszUstawienia) obsluguja plik konfiguracja programu (file of Tustawienia), a ostatnia plik tekstowy w ktorym jest zapisana sciezka do biblioteki BGI. 2.8. unit StosCofn interface {*** Standardowe funkcje obslugi stosu ***} Procedure DodajS (x,y : integer); Procedure ZdejmijS (var x,y : integer; var czyj : byte); Procedure UsunS; {*** Dodatkowe funkcje (przegladanie (od dolu)} Procedure PierwszyOdDolu (var x,y : integer); Procedure NastepnyOdDolu (var x,y : integer); Modul korzysta z jednego stosu, zadeklarowanego wewnetrznie (w czesci implentation). Jest wykorzystywany przez moduly: Program (kladzie na stos) Plansza (zdejmuje podczas cofania rucho) i Grajacy (tez cofanie). Oprocz standardowych funkcji obslugi stosu (DodajS,ZdejmijS,UsusS) w module sa takze funkcje dostepu do stosu 'od dolu' (typ stos ma dodatkowe pole link : stos). Po wywolaniu procedury PierwszyOdDolu, ktora zwraca wartosc (bez zdejmowania) najglebszego elementu na stosie mozna pobierac kolejne wartosci od dolu (NastepnyOdDolu). Wykorzystywane jest to przy cofaniu ruchu w module grajacym. 2.9. unit Mysz interface uses Dos; Procedure PokazMysz; Procedure UkryjMysz; Procedure BadajMysz (var zmianaPol : boolean; var kursX,kursY : byte; var kursOr : Torientacja; var klawiszNac : boolean; var klawisz : char); Procedure BadajMyszUst (var klawiszNac : boolean; var klawisz : char); Procedure Klik; Function MyszTN : char; Zawiera podstawowe funkcje obslugi myszy (PokazMysz,UkryjMysz) wykorzystywane przez wiekszosc modulow oraz procedury specyficzne dla tego programu. BadajMysz i BadajMyszUst na podstawie polozenia myszy i nacisnietych przyciskow przekazuja procedurze, ktora je wywolala klawisz ktorego nacisnicie jest rownowazne kliknieciu mysza. Sa wywolywane w petli, kiedy komputer czeka na reakcje uzytkownika. Procedura Klik czeka na przycisniecie dowolnego klawisza, a MyszTN sprawdza czy nacisnieto jeden z przyciskow ,. 2.10. unit Grajacy interface uses Deklarac, StosCofn; Procedure InitGame(var f : TFileOfPairs; sec : integer); Procedure Turn(var x,y : integer); Procedure ZwolnijPamGraj; Procedure CofnijGraj; Zdecydowanie najdluzszy modul. Odpowiada za strategie gry komputera. W czesci interface zawiera dwie standardowe procedury (wymagane przez konkurs): Turn - dostaje ruch przeciwnika i wykonuje komputera oraz InitGame - przygotowuje modul do gry oraz procedury dodatkowe wykorzystywane przez program Szewc. Procedura ZwolnijPamGraj usuwa z pamieci zmienne dynamiczne modulu, a procedura CofnijGraj cofa ruch, tzn. najpierw resetuje zmienne komputera a potem pobiera od dolu ze stosu kolejne ruchy i stopniowo modyfikuje zmienne tak jak w czasie zwyklej gry. Modul korzysta z modulu Deklarac, zeby miec deklaracje typu TfileOfPairs, a z modulu StosCofn do pobierania kolejnych ruchow przy cofaniu. Pozostale zmienne modul ma niezalezne. Informacje o poczatkowym ustawieniu kresek na planszy sa mu przekazywane przez plik na dysku. Modul w trakcie gry gromadzi w licznych zmiennych informacje o ruchach dostepnych na planszy, a dokladniej o multiruchach. ___Multiruch___ to ciag ruchow gracza rozdzielonych pasowaniem przeciwnika. Multiruchem jest zajecie korytarza, a ___korytarz___ to ciag sasiednich pol, z ktorych kazde ma dokladnie dwie (lub trzy - na koncu) kreski i ktore stykaja sie nie zajetymi bokami. Jezeli na koncu korytarza jest pole z jednym zajetym bokiem to ten koniec nazywam zamknietym. Jezeli korytarz ma chociaz jeden koniec zajety to mozna wykonac multiruch polegajacy na zamknieciu calego takiego korytarza, choc czasami sie oplaca nie zajac calego ('wystawic' przeciwnikowi), zeby zyskac w nastepnym ruchu. Jezel korytarz jest obustronnie otwarty to postawienie w nim kreski umozliwia przeciwnikowi zajecie go. ___Neutralnym___ nazywam taki ruch, ze po jego wykonaniu na planszy nie pojawi sie pole o trzech lub czterech kreskach. Zmienne opisujace stan gry modulu sa poloczone w rekord Tsgry. Najwazniejsza zmienna opisujacych stan gry jest tablica ipola - array[,] of record nast,poprz,info,koryt : byte end. Zawiera informacje o ulozeniu korytarzy na planszy. Wszystkie pola jednego korytarza maja ustawiona ta sama wartosc pola koryt, a pola nast i poprz wskazuja sasidnie pola w korytarzu. W zmiennej info sa zakodowane nst. wartosci: ktore boki sa zajete, czy korytarz tworzy cykl, czy ma zamkniete konce. Kazdy korytarz ma inny numer, ktory jest indeksem w tablicy koryt, ktora trzyma dane o korytarzach: ich dlugosc, wspolrzedne konca i poczatki, informacje o zamknieciu koncow. Ostatnia duza struktura jest tablica dwuwymiarowa wboki, ktorej pola (po jednym dla kazdego boku) mowia czy ruch wykonany przez podswietlenie danego ruchu jest neutralny. Zmienna sgry : Tsgry jest oddzielna dla kazdego poziomu wywolan rekurencyjnych. Podczas kolejnych wywolywan sa tworzone w pamieci kolejne kopie tej zmiennej i dany poziom rekurencyjny modyfikuje tylko 'swoja' zmienna. Za modyfikowanie zmiennej sgry jest odpowiedzialna procedura ModyfikujZm, (najdluzsza w module), ktora dostaje wspolrzedne (x,y) ruchu i odpowiednio zmienia uklad korytarzy, dane o nich i o wolnych bokach. Ze zmiennych koryt i wboki korzysta procedura ZnajdzRuch, ktora wyszukuje najlepszy ruch z mozliwych. Mozliwe ruchy to takie, ktore mozna postawic na planszy oraz nie zostaly juz zbadane wczesniej (wtedy sa zaznaczone w specjalnej zmiennej juzZajete : TjuzZajete). Najlepszego ruchu szuka sprawdzajac kolejno czy pozostaly nastepujace rodzaje ruchow: a) jak najdluzszy korytarz do zajecia b) neutralne pole c) jak najkrotszy korytarz do wystawienia. Pocedura ZnajdzRuch wyszukuje multiruchow. Np. gdy mamy dlugi korytarz (np. dlugosci 10), obustronnie zajety to znalezionym multiruchem jest zajecie korytarza bez czterech ostatnich pol.O tym, czy je potem zajac, czy postawic kreske w srodku tych czterech pol tak by je wystawic przeciwnikowi rozstrzyga dopiero rekurencja. Za rekurencje bezposrednio jest odpowiedzialna procedura RuchRek. Otrzymuje ona wykonany na nizszym poziomie rekurencyjnym multiruch i modyfikuje swoja zmienna sgry (i ma w niej obraz planszy po ciagu rozpatrywanych multiruchow). Nastepnie wywoluje z gory okreslona liczbe rrazy (zalezna od poziomu rekurencyjnego -im wyzszy tym mniej ruchow jest rozwazanych oraz od czasu na gre - zawarte jest to w tablicy ileR : TileRuch) procedure ZnajdzRuch i nastepnie siebie rekurencyjnie. Okresla wage multiruchu jako sume zdobytych punktow (lub ujemna sume - jezeli RuchRek rozpatruje ruch przeciwnika) i maksymalna (lub minimalna - jezeli rozwaza przeciwnika) wage podruchow. Procedura Turn takze wywoluje RuchRek i wykonuje ruch o najwiekszej wadze.