Bantumi

Bantumi

3x2CB

Introducere

Bantumi (Kalah) derivat dintr-un joc numit "Mancala" avand originea in Africa, sute de ani inainte. Exista multe varinate ale jocului, de la numarul de pietre in fiecare casuta la inceputul jocului pana la cum este castigata fiecare piatra in parte. Obiectivul jocului este de a muta pietrele dintr-o celula din josul ferestrei in casuta de scor din dreapta ecranului.

Acest joc a fost implementat in ideea de a folosi un algoritm de Analiza Algoritmilor. Dupa cu se va putea vedea daca veti juca acest joc, implementat si pe telefoanele produse de firma Nokia, acesta are 5 nivele de dificultate in functie de care calculatorul va analiza ce mutare sa faca. In continuare vom explica regulile jocului, cum a fost implementat si explicarea algoritmului folosit pentru mutarea calculatorului.

Pentru a reaminti despre ce joc este vorba am introdus o imagine a jocului care este pe telefoanele Nokia:

Sus

Regulile jocului (cum se joaca)

Pentru a intelege ce trebuie sa faci ca sa poti juca Bantumi trebuie mai intai sa stii cum arata si ce reprezinta fiecare componenta in parte:

Pentru inceput vom zice ca in fiecare celula se afla un numar de pietre. Jocul merge intotdeauna in sensul opus acelor de ceasornic. Se porneste alegand o celula cu pietre din randul de jos, care este zona ta. Dupa ce ai facut selectia, fiecare celula incrementeaza numarul de pietre in sensul acelor de ceasornic pana cand toate pietrele ridicate au fost epuizate. Nu poti lasa nici o piatra in casuta de scor al oponentului. Daca piatra ta ajunge in casuta ta cu scor acesta se va incrementa avand dreptul la inca o mutare. Daca ultima piatra aterizeaza in jumatatea ta sau al calculatorului intr-o casuta goala, este adaugata la scor si toate pietrele oponentului din casuta opusa de asemenea. Daca unul din jucatori nu mai are nici o piatra in jumatatea sa atunci jocul s-a terminat. Pietrele ramase in jumatatea celuilalt sunt adaugate automat la scorul acestuia. Castigatorul este cel care are cele mai multe pietre in casuta de scor.

Sus

Implementarea

Implementarea jocului este facuta in limbajul C si anume in C++ Builder. Am ales acest mediu de programare pentru usurinta de a creea si executa programe destinate mediului Windows in care detaliile conteaza si usurarea muncii utilizatorului este pe primul loc.

Dupa cum se va vedea daca jucati acest joc, acesta are cinci nivele de dificultate de la foarte usor, care este setat implicit la rularea programului, pana la foarte greu. Aceasta dificultate se poate alege din meniul cu acelasi nume, Dificultate, sau alegand una din tastele de "shortcut", de la F5 care reprezinta foarte usor pana la F9 pentru foarte greu. Nivelul de dificultate se va vedea pe bara de status. La schimbarea nivelului utilizatorul este avertizat ca va incepe un joc nou.

Daca se doreste un joc nou se va alege din meniu optiunea Nou din meniul Joc sau apasand tasta F2.

Jocul debuteaza cu care 4 pietre, cum le-am numit la prezentarea jocului, in fiecare casuta si cu 0 pietre in fiecare casuta de scor a fiecariu jucator. Se poate schimba numarul de pietre cu care se incepe din meniul Numar Boabe cu 3, 4 sau 5 boabe in fiecare casuta.

Primul incepe utilizatorul. El trebuie sa aleaga una din casutele de jos, reprezentate prin 6 elemente Label de culoare rosie. Nu se poate alege o casuta care nu are nici o piatra. Dupa ce a ales casuta dorita, pietrele continute in ea sunt distribuite in fiecare casuta de dupa ea, in fiecare care una singura. Dupa regurile explicate mai devreme se va vedea ca daca ultima piatra se opreste in casuta de scor al jucatorului, acesta are dreptul la inca o alegere. Daca ultima piatra ajunge intr-o casuta unde nu e nici o piatra atunci toate pietrele continute in casuta vecinului sunt adaugate la scorul jucatorului.

Dupa mutarea jucatorului urmeaza mutarea calculatorului. In functie de nivelul de dificultate dorit acesta "alege" casuta de unde sa distribuie pietrele, regulile urmate fiind aceleasi pe care le urmeaza si jucatorul.

Toate aceste mutari si alegeri sunt executate dintr-o singura functie: lbl_Click(int Index), unde variabila Index reprezinta numarul casutei in care a apasat utilizatorul. Alte functii care trebuie amintite sunt:

int getC(int x) care intoarce numarul de pietre dintr-o casuta;

void setC(int x, int val) care seteaza valoarea intr-o casuta;

int Alege_Casuta (void) returneaza casuta din care va muta colculatorul;

bool Is_Sfarsit (void) verifica daca s-a terminat jocul;

void Sfarsit_Joc (void) afiseaza rezultatul jocului.

. Pentru detalii despre celelalte functii declarate si folosite in cadrul programului va rugam sa cititi comentariile din fisierul sursa.

Sus

Algoritm

In continuare voi prezenta pentru fiecare nivel in parte cum se alege casuta din care calculatorul distribuie pietrele. Aceasta alegere se face in cadrul functiei Alege_Casuta. In cele ce urmeaza variabila Y reprezinta casuta care e aleasa. Casutele sunt numerotate de la 0 la 13, 0 fiind casuta din dreapta sus. Deci calculatorul va avea casutele 0 - 6, iar jucatorul casutele 7-13.

Nivelul ales:

Foarte usor: complexitate = 1

Y = rand()%6;
if (getC(Y) == 0) repeta=true;

Pentru acest nivel casuta se va alege la intamplare (aleator) din cele ramase cu pietre in ele. Daca s-a ales o casuta goala atunci se va alege din nou pana nimereste una cu pietre in ea.

Usor: complexitate = n

for (Y = 0; Y <= 5; Y++) {
if (getC(Y) != 0 && getC(Y) + Y == 6) return Y;
}
Y = rand() % 6;
if (getC(Y) == 0) repeta=true;

Pentru acest nivel se cauta acea casuta, plecand de la cea mai din dreapta casuta pana la cea mai din stanga, care daca s-ar lua pietrele din ea atunci ultima piatra s-ar opri exact in casuta de scor a calculatorului astfel incat el sa mai poata alege o data. Daca nu exista o astfel de casuta atunci va lua aleator o casuta ca nu este goala.

Mediu: complexitate = n

for (Y = 5; Y>= 0; Y--) {
if (getC(Y) != 0 && getC(Y) + Y == 6) return Y;
}
Y = rand() % 6;
if (getC(Y) == 0) repeta=true;

Codul pentru acest nivel este asemanator cu codul pentru nivelul usor doar ca aici cautarea se face de la stanga la dreapta.

Greu: complexitate = n

for (Y = 5; Y>=0; Y--) {
       if ((Y + getC(Y)) % 13 == 6) return Y;
       }
if (getC(5) != 0) {
       Y = 5;
       }
else {
       Y = rand() % 6;
       if (getC(Y) == 0) repeta=true;
       }

Pornind de la stanga la dreapta se cauta acea casuta a carei ultima piatra ar ajunge in casuta de scor a calculatorului sub orice conditie, chiar care face ocolul tablei o data. Daca nu exista nici o casuta cu conditia aceasta se va alege ultima casuta, binenteles daca aceasta are pietre in ea. Daca nu are se va lua iar o casuta aleatoare.

Foarte greu: complexitate = n

for (Y = 5; Y >= 0; Y--) {
       if (getC(Y) != 0) {
             if ((Y + getC(Y)) % 13 == 6) return Y;
             if (getC(Y + getC(Y)) % 13 == 0) return Y;
             }
       }
if (getC(5) != 0) {
       Y = 5;
       }
else {
       Y = rand() % 6;
       if (getC(Y) == 0) repeta=true;
       }

Pornind de la stanga la dreapta se cauta acea casuta a carei ultima piatra ar ajunge in casuta de scor a calculatorului sub orice conditie, chiar care face ocolul tablei o data, sau ajunge intr-o casuta a jucatorului care nu are nici o piatra in ea, caz in care pietrele din casuta vecina vor intra in casuta de scor al acestuia. Daca nu exista nici o casuta cu conditia aceasta se va alege ultima casuta, binenteles daca aceasta are pietre in ea. Daca nu are se va lua iar o casuta aleatoare.

Sus

Download

Deoarece acest program a fost implementat in C++ Builder pentru al putea rula veti avea nevoie de cateva librarii din acest mediu de programare. De aceea am creat un kit de instalare cu ajutorul programului Install Shield pentru C++ Builder cu care veti putea instala jocul si care cuprinde si librariile folosite de acesta. Daca doriti sa downloadati kitul de instalare apasati aici.

Pentru a downloada sursele apasati aici.

Sus

Program implementat de Ana Marin (333CB) si Dragos Dobre (332CB)