Clasa a VI-a lecția 36 - 4 iun 2015

From Algopedia
Jump to: navigation, search

Lecție

Programarea jocurilor interactive

Structura unui joc

Componente

Pe cazul general un joc interactiv are următoarele componente:

  • O scenă a jocului. Ea poate fi un ecran in mod text, sau un labirint pe mai multe ecrane, sau o lume 3D foarte mare, precum in World of Warcraft.
  • Personaj (sau personaje) uman, numit și avatar, controlat de jucător.
  • Personaje calculator, elemente ce se pot deplasa în scenă, controlate de calculator.

Personajul uman este mișcat de către om prin intermediul tastaturii și mouse-ului. Uneori există și periferice specifice jocului, precum ați văzut în Guitar Hero. Prin contrast, personajele calculator sînt mișcate de către program, conform unor reguli de mișcare. Aceste reguli formează Inteligența Artificială, sau AI. AI este componenta de program din joc care ia decizii în numele calculatorului. Acest AI este opusul inteligenței umane, care comandă personajul propriu. De exemplu, în fazele avansate ale jocului Traversare, monștrii se vor deplasa o parte din timp aleator și altă parte către jucător. Secțiunea de cod care implementează această logică a mișcării se numește AI.

În multe jocuri secțiunea de AI ocupă o parte semnificativă a programului.

Diferența față de alte programe

Ceea ce face un joc interactiv diferit de un program obișnuit este faptul că majoritatea programelor tradiționale răspund la intrările utilizatorului și nu fac nimic cîtă vreme el nu a introdus ceva. De exemplu, un procesor de texte, gen LibreOffice Writer, adaugă sau formatează text pe măsură ce utilizatorul tastează sau dă comenzi. Unele comenzi s-ar putea să ia mai mult timp (salvarea, sau căutarea unui cuvînt în text), dar toate sînt inițiate de utilizator.

Într-un joc interactiv AI-ul este cel care declanșează acțiuni și în absența intrărilor dinspre utilizator.

Bucla de joc

Pentru a face posibil acest lucru majoritatea jocurilor folosesc o buclă a jocului. O buclă simplificată a jocului ar putea să arate astfel, în pseudocod:

while ( <condiție de terminare neîndeplinită> ) {
  verifică intrările de la user (tastatură, mouse, etc)
  execută acțiunile user, bazate pe intrările anterioare
  execută AI
  rezolvă coliziuni, condiții speciale (întîlnirea cu un monstru)
  trasează grafica
  emite sunete
}

Bucla de joc poate fi rafinată și modificată, dar majoritatea jocurilor se bazează pe această idee.

Nu toate acțiunile trebuie executate la fiecare iterație. Bucla trebuie executată des, la cîteva zeci de milisecunde, pentru ca jocul să răspundă rapid la comenzile jucătorului. Frecvența cu care se execută bucla se numește tactul jocului Dar ce facem dacă unii monștri se mișcă mai rar, iar alții mai des? Atunci nu vom mișca monștrii lenți la fiecare iterație. Să nu uităm, logica de mișcare este conținută în AI. Un mod de a mișca monștrii mai rar este să avem un contor care să contorizeze k perioade (tacți) pînă ce monștrii trebuie deplasați. De exemplu:

#define FACTOR_MONSTRI 5
contor_monstri = 0;
...
while ( <condiție de terminare neîndeplinită> ) {
  ... acțiuni de la user ...
  contor_monstri++;
  if (contor_monstri == FACTOR_MONSTRI) {
    contor_monstri = 0;
    ... mișcă monștrii ...
  }
  Sleep(50);
}

O altă metodă ar fi să menținem pentru fiecare monstru un număr de tacți și un astfel de contor pe care să îl incrementăm separat. Astfel, nu toți monștri trebuie să se miște în același timp, dacă pornesc cu altă valoare inițială a contorului:

#define FACTOR_MONSTRI 5
int factor[MAX_MONSTRI] = { 5, 5, 5, 1, 1, 1, 2, 2, 2 };
int contor[MAX_MONSTRI] = { 0, 1, 2, 0, 0, 0, 0, 1, 0 };
...
while ( <condiție de terminare neîndeplinită> ) {
  ... acțiuni de la user ...
  for ( i = 0; i < n; i++ ) { // pentru fiecare monstru
    contor[i]++;
    if ( contor[i] == factor[i]) {
      contor[i] = 0;
      ... mișcă monstrul i ...
    }
  }
  Sleep(50);
}

De remarcat că această buclă consideră că jocul se joacă pe un singur calculator. Pentru jocurile de rețea lucrurile se complică, fiind nevoie de un modul de menținere a stării jocului peste multiple calculatoare, cum se întîmplă, de exemplu, în Starcraft.

Citire asincronă

Sincron versus asincron

Să detaliem puțin prima acțiune din bucla de joc: citirea acțiunilor jucătorului. O primă observație este că nu putem folosi funcții clasice, gen scanf() sau getc() deoarece programul se va opri pînă ce jucătorul va introduce ceva. Aceasta înseamnă că acțiunile care trebuie să se întîmple independent de jucător, gen AI și deplasarea personajelor calculator, nu se vor mai întîmpla. Jocul se va opri. Ce facem, atunci?

Avem nevoie de alte funcții de citire, și anume funcții care să întrebe "Este tasta K apăsată în acest moment, sau nu? Și te rog nu te opri, mergi imediat mai departe!". Acest lucru este realizat în Windows de funcția GetAsyncKeyState(), iar în biblioteca textutil.h de funcția getKey().

Funcțiile scanf() și getc() se numesc funcții de citire sincronă, deoarece programul și tastatura se sincronizează pentru această citire. Cu alte cuvinte, programul nu merge mai departe pînă ce tastatura nu îi oferă ceva. Ele se "mișcă" în același timp, adică sincron.

Pe de altă parte funcția GetAsyncKeyState(), pe care se bazează funcția getKey() din textutil.h este o funcție asincronă, deoarece programul întreabă dacă există o intrare, dar nu așteaptă după ea. Dacă tastatura nu are ceva de oferit la acel moment, ci cîndva mai tîrziu, acea intrare este pierdută. Spunem că programul și tastatura nu se sincronizează pentru citire.

Probleme în citirea asincronă

Care este problema cu acest mod de abordare? Este posibil ca jucătorul să apese o tastă în timp ce se execută o altă parte a buclei de joc, de exemplu mutarea monștrilor pe ecran. Dacă jucătorul eliberează tasta rapid, înainte ca bucla să ajungă să o citească, jocul nostru va "pierde" apăsări de taste. Rețineți, acest mod de citire verifică dacă o tastă este apăsată la momentul execuției funcției de citire! Cum rezolvăm această problemă? Din fericire, de cele mai multe ori aceasta nu constituie o problemă. Calculatoarele de azi sînt rapide, ceea ce ne permite să citim de multe ori pe secundă tastatura sau mouse-ul. De exemplu, dacă bucla se execută în 50ms, aceasta înseamnă că pentru a pierde intrări ar trebui ca utilizatorul să apese o tastă și să o și elibereze în mai puțin de 50ms, adică de 20 de ori pe secundă!

Cu toate acestea, pe calculatoare mai vechi și cînd jucătorul este foarte rapid pot apărea probleme. Există și soluții mai bune, bazate pe coadă de evenimente, pe care nu le vom discuta aici.

Ceea ce trebuie, însă, să avem grijă, este ca bucla noastră de joc să se execute rapid. Aceasta înseamnă că nu avem voie să lăsăm AI-ul să se lanseze în niște calcule monstruoase (chiar dacă el mută monștri :-)

Tehnici de bună practică

Vom discuta în continuare reguli de bună practică în programarea jocurilor. Unele din aceste reguli se aplică în programarea aplicațiilor în general.

Procesor liber (sleep)

Am putea fi tentați să scriem o buclă de joc astfel:

quit = 0;
while ( quit == 0 ) {
  // asteapta pina ce jucatorul apasa ESC
  if ( getKey( VK_ESCAPE )
    quit = 1;
}

Deși la prima vedere programul arată în regulă, în realitate se întîmplă un lucru neașteptat: deoarece getKey() nu așteaptă introducerea unei taste, ci trece mai departe, calculatorul va executa în buclă continuă corpul buclei, de milioane de ori pe secundă. Acest lucru este rău din mai multe motive:

  • Procesorul va fi ocupat 100%, fără să facă ceva util, gen calcule, constituind o risipă.
  • Dacă avem și alte programe care se execută în același timp, ele nu vor putea folosi procesorul, deoarece el este ocupat cu lucruri inutile.
  • Un calculator care are procesorul ocupat 100% se simte lent și pare a nu răspunde la comenzi.
  • Consumul de curent este simțitor mai mare, ventilatoarele pornesc, zgomotul crește.
  • Un program care ocupă procesorul 100% inutil nu este un bun cetățean al ecosistemului de programe care se execută pe un calculator.

Cum scriem corect o astfel de buclă? Modificînd-o astfel încît să-i spunem procesorului că dacă nu avem tasta ESC apăsată, poate să se elibereze pentru o vreme. Acest lucru se face cu funcția Sleep(), (adormi, în engleză), care primește ca parametru un număr de milisecunde. După apelul acestei funcții execuția programului se oprește vreme de n milisecunde, unde n este parametrul funcției. Atenție: adormirea nu se referă la procesor, ci la program! În timpul cît programul "doarme", procesorul este liber să execute alte programe.

În general funcția Sleep() este apelată cu parametri de ordinul zecilor de milisecunde. Valori prea mari devin sesizabile, fiind percepute ca o întîrziere în răspuns a jocului. Gîndiți-vă că 50ms reprezintă o veșnicie pentru un procesor modern, care poate efectua 2 miliarde de operații pe secundă. În 50ms el va executa 100 milioane operații!

Forma corectă a buclei de mai sus este:

quit = 0;
while ( quit == 0 ) {
  // asteapta pina ce jucatorul apasa ESC
  Sleep( 50 );
  if ( getKey( VK_ESCAPE )
    quit = 1;
}

Buclă de joc rapidă

Să nu uităm că acțiunile jucătorului sînt citite doar o dată la execuția fiecărei iterații a buclei de joc. Aceasta înseamnă că ea trebuie să se execute foarte rapid, pentru a nu da senzația de întîrziere jucătorului. Nu este bine să chemăm acțiuni care ar putea să dureze mult, cum ar fi sortări de un milion de numere.

Constante, constante, constante

Un joc este prin definiție unul din cele mai dinamice programe, care evoluează mult pe parcursul dezvoltării programului. De aceea este bine ca orice număr care apare în program să nu fie scris ca atare în cod, ci să-l definiți ca constantă, cu #define. În acest fel, dacă veți constata la jumatea jocului că aveți nevoie să măriți paleta de tenis cu o pătrățică, nu va trebui sa căutați prin sute de linii de cod unde folosiți lungimea paletei. Veți înlocui doar valoarea constantei. Este indicat să dați nume clare constantelor, deoarece vor fi foarte multe. Se obișnuiește ca în C constantele să fie denumite cu litere mari, iar cuvintele să fie despărțite cu liniuță jos, ca în exemplu:

#define RACKET_LEN 4

Astfel, constantele sînt ușor de diferențiat de variabile, în codul jocului.

Funcții mici și clare

Deoarece codul unui joc poate fi lung, este bine să-l descompunem în bucăți cît mai mici, folosind funcții. Funcțiile în jocuri (și în aplicații în general) nu se introduc doar atunci cînd același cod apare în mai multe locuri în program. Folosim funcții și pentru claritatea codului, pentru a înțelege mai bine etapele unui program. Acest lucru este cu atît mai valabil la jocuri.

Eficiență și rapiditate

Orice program trebuie făcut cît mai eficient. Pentru aceasta este bine să creăm algoritmi cît mai eficienți, de complexitate cît mai mică. Apoi, odată creat algoritmul, implementarea trebuie să fie la rîndul ei cît mai eficientă, dar optimizarea codului este pe locul doi.

Aceste reguli devin foarte importante atunci cînd scriem un joc, deoarece acțiunile lente sînt foarte vizibile într-un joc. Toate calculele în joc trebuie să se petreacă în timp real. Nu putem aștepta două secunde pentru ca AI-ul să calculeze următoarea poziție a unui monstru, deoarece acel monstru trebuie să facă multe deplasări pe secundă pentru ca mișcarea să fie continuă.

Ca optimizări de cod trebuie să avem grijă să redesenăm strict ceea ce se schimbă din scena de joc. De exemplu, la jocul Traversare am putea să redesenăm tot ecranul la fiecare cadru, dar aceasta ar implica trasarea a circa 20 * 80 de caractere. De aceea este mai eficient să deplasăm doar obiectele care se mișcă, avînd grijă să le ștergem de la pozițiile vechi, prin scrierea unui caracter spațiu la acele coordonate.

În eventualitatea cînd avem nevoie să facem calcule care depășesc cele cîteva zeci de milisecunde disponibile pe buclă trebuie să împărțim acele calcule pe mai multe perioade. Lucru care nu este tocmai ușor. Gîndiți-vă cum ați face o sortare prin selecție "pe bucăți". Ar trebui ca la fiecare apel al funcției de sortare să mutăm un singur element la coadă și să revenim din funcție. Între apeluri ar trebui să păstrăm starea actuală, unde am ajuns în sortare.

Jocuri propuse

Pentru a pune în practică cele învăţate vom scrie un joc pe care îl veţi începe în clasă şi vă rămîne ca temă. Vă propun mai jos nişte jocuri, dar sînteţi liberi să veniţi cu alte idei, dacă nu vă surîde nimic din listă. Pentru jocurile care necesită "grafică" în mod text iată două fișiere utile, pe care le puteți include in proiectul CodeBlocks: http://algopedia.ro/wiki/images/2/2c/Textutil.zip. Nu uitați să includeți fișierul .h în programul vostru, astfel:

#include "textutil.h"

Lista jocurilor propuse este:

  • Ghicitul numerelor de la 1 la 1000 din zece întrebări. Omul își alege un număr între 1 și 1000. Calculatorul pune întrebări de forma "numărul este mai mare ca x?" După zece întrebări calculatorul va afișa numărul. Scrieți algoritmul de ghicire al calculatorului (calculatorul este cel care trebuie să ghicească numărul pe care şi-l alege jucătorul uman).
  • Traversare. Folosind funcţiile din textutil, postate mai sus, si aruncînd un ochi pe jocul de tenis făcut data trecută, folosind şi textutil, scrieți un joc în care jucătorul trebuie să miște un caracter astfel încît să traverseze ecranul. Jocul va fi implementat în etape:
    • Traversare ecran
    • Traversare ecran ocolind monştri care "omoară" la atingere
    • Monştrii se vor mișca aleator
    • Monştrii se vor mișca o parte din timp aleator, altă parte se vor mișca către personajul jucătorului.
    • Implementare niveluri de joc: cu cît nivelul este mai mare cu atît timpul în care obstacolele se mișcă către jucător este mai mare.
    • Orice altă modificare interesantă vă vine în minte (o elevă din anii precedenţi a creat un labirint cu monștri care se mișcă pe traiectorii fixe, labirint din care există o singură ieşire pe margine)
  • Centrate și necentrate. Este un joc de doi jucători care se joacă astfel. Unul din jucători își alege un număr de patru cifre distincte, care nu conține cifra zero. Celălalt jucător încearcă să ghicească numărul. El propune un număr, iar primul jucător îi răspunde cu două numere, cîte cifre sînt centrate și cîte sînt necentrate. Cifrele centrate sînt cele corecte și la locul lor. Cifrele necentrate sînt cele corecte, dar care nu sînt pe poziția corectă. De exemplu, dacă numărul original este 1493 și încercarea este 4398 atunci avem o cifră centrată, 9 și două cifre necentrate, 3 și 4. Al doilea jucător continuă să propună numere pînă ghicește numărul ales de primul jucător. Apoi rolurile se inversează. În final cîștigă jucătorul care a pus mai puține întrebări. Scrieți un program care să ghicească numărul. Puteți juca jocul aici. Aveți nevoie de un browser cu Java activat pentru a-l juca.
  • Minesweeper. Celebrul joc în care trebuie să găsiți mine într-o grilă de celule pătrate avînd ca informație numărul de vecini bombă. Aveți o variantă funcțională pe web aici: minesweeper.
  • Bază de date despre animale (detaliat la cerc).

Temă

  • Terminați jocul pe care l-ați început. Puteți scrie și jocuri din afara listei, la care v-ați gîndit voi.
  • Continuați programarea la jocul de concurs, Pah-tum. Nu uitați:
    • Folosiți pagina de testare pentru a vă depana programul.
    • Dacă știți că veți concura trimiteți-mi un email cît mai repede. Am nevoie să știu cîți concurenți voi avea, pentru a stabili structura concursului. Pot, de exemplu, sa vă dau mai mult timp pe multare.
    • Vă rog să introduceți antetul cerut în program, cel în care menționați numele programului, numele vostru și emailul.