General
Cursuri
Laboratoare
Teme
General
Cursuri
Laboratoare
Teme
Jocul Metro este un board game de 1 sau mai mulți jucători, în care fiecare jucător dorește să câștige un număr cât mai mare de puncte. O implementare a jocului (în Java) se poate observa la acest link.
Jocul se desfășoară pe o tablă pătrată (harta) în care se pot plasa cărți (tiles) pătrate, conform cu un caroiaj de dimensiune d x d
. Harta reprezintă un spațiu unde se vor forma trasee de metrou. Fiecare carte (tile) conține 4 conexiuni între puncte de pe marginile cărții, conexiuni care formează, împreună cu celelalte cărți, traseele de metrou de pe hartă. Notăm spațiile de pe hartă cu perechi (X, Y)
, cu X ∈ [1, d] și Y ∈ [1, d], unde X este coordonata de pe orizontală, cu 1 fiind coloana cea mai din stânga, iar Y este coordonata de pe verticală, cu 1 fiind linia cea mai de sus.
Descrierea hărții este dată în fișierul T3base.pl
prin predicatele width/1
, height/1
, și limits/4
.
Pe fiecare latură a hărții se află d
puncte de intrare în hartă și d
puncte de ieșire din hartă, numite în joc trenuri, respectiv gări. Obiectivul unui jucător este de a conecta, folosind conexiunile de pe cărțile plasate în joc, trenuri cu gări, obținând trasee în așa fel încât traseele obținute să fie cât mai lungi. Un traseu primește un număr de puncte egale cu numărul de cărți prin care trece (poate trece prin unele cărți de mai multe ori).
În centrul hărții se află 4 spații care nu sunt disponibile pentru a pune cărți, care conțin gări (nu și trenuri). Un traseu care ajunge în una dintre cele 8 gări din centrul hărții primește un număr de puncte dublu față de lungimea sa în număr de cărți parcurse.
Spațiile din centrul hărții sunt descrise în fișierul T3base.pl
prin predicatul center_space/2
.
Descrierea punctelor de intrare și ieșire este dată în fișierul T3base.pl
prin predicatele entry_point/3
și exit_point/3
.
Mai jos se găsește o tablă de joc de dimensiune 8×8:
Există în joc 10 cărți diferite. Vom nota aceste cărți #1
… #10
– aceștia vor fi identificatorii cărților. Fiecare care conține 4 puncte de intrare și 4 puncte de ieșire, câte unul pe fiecare latură. Fiecare carte conține 4 conexiuni între câte un punct de intrare și un punct de ieșire. Vom reprezenta fiecare carte ca fiind o listă de 4 numere din mulțimea +0
, +1
, +2
, +3
, fiecare număr reprezentând pe a câta latură ajunge conexiunea față de latura de unde a pornit, în sens trigonometric, latura de unde a pornit fiind latura 0. Conexiunile sunt date în sensul trigonometric al laturilor din care pornesc.
Avem următoarele cărți (în aceste imagini conexiunile încep cu conexiunea care pornește de pe latura din stânga):
Cartea #1 : +0, +0, +0, +0 | Cartea #2 : +0, +0, +1, +3 | Cartea #3 : +0, +1, +1, +2 |
Cartea #4 : +0, +2, +0, +2 | Cartea #5 : +0, +2, +3, +3 | Cartea #6 : +1, +1, +1, +1 |
Cartea #7 : +1, +2, +2, +3 | Cartea #8 : +1, +3, +1, +3 | Cartea #9 : +2, +2, +2, +2 |
Cartea #10 : +3, +3, +3, +3 |
Toate cele 10 cărți sunt descrise în fișierul T3base.pl
prin predicatul tile/5
.
Când sunt plasate în spațiul de joc, cărțile pot fi rotite așa cum dorește jucătorul. Există 4 rotații:
R0
– cartea este în poziția originală, așa cum apare în tabelul de mai sus;R1
– cartea este rotită 90° în sens trigonometric față de poziția originală;R2
– cartea este rotită 180°;R3
– cartea este rotită 270° în sens trigonometric față de poziția originală.
Rotațiile sunt descrise în fișierul T3base.pl
prin predicatul rotation/2
.
Cărțile #1
, #6
, #9
și #10
nu are sens să fie rotite (au doar rotația R0
); cărțile #4
și #8
au două rotații diferite (R0
și R1
); iar celelalte cărți au 4 rotații posibile diferite: R0
, R1
, R2
și R3
. O rotație a unei cărți se reflectă într-o deplasare circulară a listei de conexiuni care o reprezintă. De exemplu, cartea #3
, reprezentată de lista +0, +1, +1, +2
, rotită o dată în sens trigonometric (deci cu rotația R1
) va fi reprezentată prin lista +2, +0, +1, +1
.
Vom numi R0
..R3
identificatorii pentru rotația unei cărți. Vom numi perechea dintre identificatorul unei cărți și identificatorul rotației sale carte rotită.
Mai jos aveți un exemplu de stare de joc. În aceasta, avem două trasee complete (sau închise), marcate cu verde și cu albastru. Avem de asemenea un traseu care pornește de la un tren (un punct de intrare), dar nu ajunge la o gară, și este deci un traseu deschis (traseul marcat cu roșu).
Cele două trasee închise din exemplu aduc jucătorului punte după cum urmează: 5 puncte pentru traseul albastru, care trece de două ori printr-o carte; și 5 puncte pentru traseul verde. În total, 10 puncte.
În acest exemplu, avem 6 cărți plasate pe hartă, având în spațiile (2, 1)
, (3, 1)
, (2, 2)
, (3, 2)
, (1, 3)
și (2, 3)
cărțile rotite (#5, R0)
, (#6, R0)
, (#7, R2)
, (#2, R1)
, (#9, R0)
și respectiv (#3, R2)
.
Un traseu va fi reprezentat prin punctul său de intrare și o listă de cărți rotite care compun calea. Punctul de intrare este coordonata spațiului din afara hărții de unde vine trenul, înainte să intre în hartă. Similar cu punctul de intrare putem defini punctul de ieșire al traseului.
Astfel, în exemplul de mai sus traseul albastru are punctul de intrare (2, 0)
și lista de cărți rotite (#5, R0)
, (#6, R0)
, (#2, R1)
, (#7, R2)
, (#5, R0)
. Punctul de ieșire al traseului este tot (2, 0)
.
Similar, traseul verde are punctul de intrare (3, 0)
și lista de cărți rotite (#6, R0)
, (#5, R0)
, (#7, R2)
, (#3, R2)
, (#9, R0)
. Punctul său de ieșire este (0, 3)
.
Jocul de 1 jucător se desfășoară astfel: Jucătorul va lua din teancul de cărți câte o carte (deci cărțile vin aleator) și o plasează (rotită așa cum dorește) într-un spațiu liber de pe hartă. Condițiile pentru plasarea unei cărți sunt următoarele:
#1
nu poate fi plasată niciodată lângă margine.Jocul se termină atunci când jucătorul nu poate plasa în spațiul de joc cartea care este la rând, fie pentru că nu mai sunt spații libere pe hartă, fie pentru că plasarea cărții ar crea trasee de lungime 1.
Pentru rezolvarea completă a temei este necesară implementarea tuturor predicatelor din fișierul T3.pl
din arhiva de pornire. Toate predicatele sunt documentate în detaliu în codul sursă oferit.
Sunt date de asemenea câteva predicate utile în fișierul sursă T3base.pl
.
Creați o reprezentare a unei stări a jocului Metro. Starea jocului poate conține orice informații doriți, dar este necesar să conțină cel puțin informații despre cărțile puse în joc. Este de asemenea necesar să se poată obține informații despre traseele existente în starea curentă, fie că ele sunt extrase la momentul interogării sau că sunt reținute în reprezentarea stării.
initial_game_state
.get_game_tiles
– obține o listă cu câte un triplet pentru fiecare carte plasată în joc, tripletul conținând coordonatele spațiului (ca pereche (X, Y)
), identificatorul cărții și identificatorul rotației cu care a fost plasată cartea în spațiul respectiv. Atenție! Rotațiile trebuie să fie doar din cele disponibile, e.g. cartea #1
are doar rotația R0
.get_open_paths
– obține lista traseelor deschise din starea curentă – trasee care încep de la un punct de intrare dar nu ajung la un punct de ieșire.get_closed_paths
– obține lista traseelor închise din starea curentă – trasee care încep de la un punct de intrare și ajung la un punct de ieșire.Reprezentarea traseelor este la alegerea voastră, dar pentru un traseu trebuie să fie disponibile următoarele predicate:
get_path_entry
– obține perechea (X, Y)
de coordonate ale punctului de intrare în traseu. Aceste coordonate sunt în mod necesar în afara hărții. Vedeți și predicatul entry_point
din T3base
.get_path_tiles
– obține lista de cărți prin care trece traseul, fiecare carte fiind reprezentată de o pereche între identificatorul cărții și identificatorul rotației.O mutare înseamnă plasarea unei cărți, cu o anumită rotație, într-un anumit spațiu de pe hartă. Reprezentarea unei mutări este la alegerea voastră. Pentru accesul la informațiile despre o mutare, dar și pentru construcția mutărilor, se vor implementa următoarele predicate:
get_move_space
, pentru relația dintre mutare și spațiul de pe hartă în care s-a realizat mutarea (descris ca o pereche (X, Y)
).get_move_tile_id
, pentru relația dintre mutare și identificatorul cărții care a fost plasată prin mutare.get_move_rotation_id
, pentru relația dintre mutare și identificatorul rotației cu care a fost plasată cartea.
Atenție! Cele 3 predicate de mai sus trebuie să funcționeze astfel încât, dacă variabilele Space
, TID
și RotID
sunt legate la valori corecte, și variabila M
este neinstanțiată, satisfacerea conjuncției
get_move_space(M, Space), get_move_tile_id(M, TID), get_move_rotation_id(M, RotID)
să lege variabila M
la o reprezentare corectă a mutării descrise.
Predicatul available_move
va fi folosit atât pentru a verifica dacă o mutare dată este disponibilă în starea curentă a jocului, cât și pentru a obține toate mutările valide posibile în starea dată a jocului.
Atenție! Dacă available_move
este apelat cu al doilea argument neinstanțiat, acesta trebuie să ofere pentru al doilea parametru, ca soluții succesive, câte o legare pentru fiecare mutare disponibilă, fără duplicate.
Predicatul apply_move
va fi folosit pentru a obține starea jocului în care se ajunge după aplicarea unei mutări într-o stare dată a jocului. Se va presupune că mutarea dată a fost deja obținută sau verificată folosind available_move
.
Pentru a putea desfășura un joc integral de un singur jucător, se vor implementa următoarele 2 predicate:
pick_move
– va alege o mutare dintre mutările disponibile care implică o carte dată. Pentru bonus predicatul va alege mutarea conform cu o euristică, în ideea obținerii unui scor cât mai mare (trasee cât mai lungi).play_game
– desfășoară un joc complet, pornind de la starea inițială a jocului. Pentru a obține o carte care să fie plasată, se va folosi obligatoriu predicatul next_tile(+Time, -TID)
, în apelul căruia primul argument va fi legat la numărul de mutări realizate până la momentul curent (pentru obținerea primei cărți va fi 0, pentru obținerea celei de-a doua va fi 1, etc).next_tile
poate fi apelat doar pentru momentul de timp la care s-a ajuns; de exemplu, inițial se va putea apela next_tile(0, T0)
, apoi pentru următoarea carte din teancul de cărți se va apela next_tile(1, T1)
, etc;tt_reset_stack/0
pentru a reseta teancul de cărți și tt_set_tile_range/1
pentru a da lista de identificatori de cărți din care next_tile
va întoarce cărți;play_game
trebuie să reușească întotdeauna; dacă nu se mai poate realiza nicio mișcare, play_game
se va întoarce, obținând starea jocului la care s-a ajuns.tt
between
, nth0
sau nth1
, findall.T3.pl