Εργασία 1

  • Ανακοινώθηκε: 15/3/2021
  • Προθεσμία παράδοσης: 11/4/2021 18/4/2021 23:59
  • 16% του συνολικού βαθμού στο μάθημα
  • Link εγγραφής: https://classroom.github.com/a/7OM6pi33
  • Repository: https://github.com/chatziko-k08/2021-project-1-<username>

Σημαντικό: διαβάστε τις οδηγίες (κοινές για όλες τις εργασίες). Περιέχουν μεταξύ άλλων και πληροφορίες για τη χρήση του git, η οποία είναι ολόιδια με τα εργαστήρια.

Στην εργασία αυτή θα χρησιμοποιήσετε έτοιμη υλοποίηση για τους περισσότερους ΑΤΔ που είδαμε στο μάθημα, η οποία παρέχεται από τη βιβλιοθήκη k08.a στο git repository της εργασίας. Τον κώδικα τον κάνουμε compile όπως έχουμε δει στο μάθημα. Στα Windows χρειάζεστε επιπλέον το εργαλείο VcXsrv, δείτε τις οδηγίες για WSL.

Γενικά

Στην εργασία αυτή καλείστε να υλοποιήσετε ένα video game, με γραφικό interface και interactive gameplay. Στο παιχνίδι αυτό ένας χαρακτήρας κινείται σε μια δισδιάστατη πίστα με τριών ειδών αντικείμενα:

  • Εμπόδια, τα οποία είναι ακίνητα και ο χαρακτήρας πρέπει να αποφύγει τρέχοντας ή πηδώντας.
  • Εχθρούς, που κινούνται και επίσης ο χαρακτήρας πρέπει να αποφύγει.
  • Πύλες, στις οποίες τόσο ο παίκτης όσο και οι εχθροί μπορούν να εισέλθουν, και να μεταφερθούν σε μια άλλη πύλη σε ένα οποιοδήποτε σημείο της πίστας (αλλά και να γυρίσουν πίσω, αν εισέλθουν στην πύλη προς την αντίθετη κατεύθυνση).

Σκοπός του παιχνιδιού είναι ο χαρακτήρας να φτάσει και να εισέλθει στην τελευταία πύλη της πίστας. Στην περίπτωση αυτή πετυχαίνει μία νίκη και το παιχνίδι ξεκινάει από την αρχή.

Για την υλοποίηση του γραφικού interface του παιχνιδιού θα χρησιμοποιήσετε τη βιβλιοθήκη raylib η οποία περιέχεται στο repository της εργασίας. Η βιβλιοθήκη υποστηρίζει όλα τα βασικά λειτουργικά συστήματα, αλλά και δίνει τη δυνατότητα να κάνουμε compile το παιχνίδι σε μορφή που μπορεί να ενσωματωθεί σε μια web σελίδα.

Είναι παράδειγμα υλοποίησης του παιχνιδιού υπάρχει εδώ.

Modules και information hiding. Η διαχείριση της κατάστασης του παιχνιδιού γίνεται από το module state.h, που θα βρείτε στο repository της εργασίας:

  • include/state.h : το interface
  • modules/state.c : η υλοποίηση που θα φτιάξετε

Σε ένα τέτοιο project οφείλουμε να διαχωρίσουμε τον κώδικα που διαχειρίζεται την κατάσταση του παιχνιδιού (module state.h), από τον κώδικα που διαχειρίζεται το interface (module interface.h, θα το φτιάξουμε αργότερα). Για το λόγο αυτό, κάθε module θα πρέπει να εμφανίζει στο χρήστη μόνο τις πληροφορίες που είναι απαραίτητες, και όχι πληροφορίες που αφορούν την εσωτερική λειτουργία του. Οι “δημόσιες” αυτές πληροφορίες βρίσκονται στο state.h, ενώ πληροφορίες που αφορούν την υλοποίηση βρίσκονται μέσα στο state.c.

Game example. Ένα πολύ απλό παράδειγμα παιχνιδιού υπάρχει στο directory programs/game_example στο repository της εργασίας. Συστήνεται ισχυρά να μελετήσετε τη δομή και τον κώδικα του παραδείγματος πριν ξεκινήσετε την εργασία.

Άσκηση 1 (15%)

Στο αρχείο modules/state.c είναι ήδη υλοποιημένο το μεγαλύτερο μέρος της συνάρτησης state_create η οποία δημιουργεί την αρχική κατάσταση state του παιχνιδιού. Η κατάσταση state περιλαμβάνει τις θέσεις όλων των αντικειμένων και άλλες πληροφορίες για το παιχνίδι.

Αρχικά μελετήστε τον κώδικα της state_create και κατανοήστε τους τύπους που χρησιμοποιούνται (State, Object, StateInfo) και τα περιεχόμενα της κατάστασης του παιχνιδιού.

Στη συνέχεια υλοποιήστε τις ακόλουθες συναρτήσεις του module state.h :

// Επιστρέφει τις βασικές πληροφορίες του παιχνιδιού στην κατάσταση state
StateInfo state_info(State state);

// Επιστρέφει μια λίστα με όλα τα αντικείμενα του παιχνιδιού στην κατάσταση state,
// των οποίων η συντεταγμένη x είναι ανάμεσα στο x_from και x_to.
List state_objects(State state, float x_from, float x_to);

Τέλος, χρησιμοποιώντας τις συναρτήσεις αυτές, δημιουργήστε ένα unit test που να ελέγχει την ορθότητα της state_create. Στο αρχείο tests/state_test.c υπάρχει η βασική δομή του test, το οποίο πρέπει να επεκτείνετε (δε χρειάζεται πρόγραμμα που να παίρνει είσοδο από το χρήστη, μόνο το unit test). Το test δεν χρειάζεται να είναι εξαντλητικό, αλλά να ελέγχει τα βασικά χαρακτηριστικά της κατάστασης που δημιουργεί η state_create, πχ τον αριθμό, τις συντεταγμένες, κλπ, των αντικειμένων. Επίσης το test θα πρέπει να δοκιμάζει κλήσεις της state_objects για 2-3 διαφορετικές τιμές των x_from,x_to.

Άσκηση 2 (15%)

Επεκτείνετε τη συνάρτηση state_create, ώστε να αρχικοποιεί τη λίστα state->portal_pairs (τη μοναδική πληροφορία του state που δεν αρχικοποιείται από την υπάρχουσα υλοποίηση).

Η λίστα portal_pairs περιέχει ζευγάρια εισόδου/εξόδου πυλών (στοιχεία τύπου PortalPair). Ένα ζευγάρι (entrance=A,exit=B) σημαίνει η πύλη A οδηγεί στην B (μπαίνοντας από την A βγαίνουμε από την B). Αυτό δε σημαίνει ότι αναγκαστικά η B οδηγεί στην A. Κάθε πύλη οδηγεί σε ακριβώς μια άλλη, και επίσης είναι έξοδος για ακριβώς μία άλλη, οπότε δεν μπορεί να υπάρχουν δύο ζευγάρια στη λίστα με το ίδιο entrance ή το ίδιο exit.

Η έξοδος κάθε πύλης επιλέγεται τυχαία, οπότε μπορείτε να δημιουργήσετε τη λίστα ως εξής:

  • Για κάθε πύλη entrance, επιλέγετε τυχαία μια exit από όλες τις πύλες τις πίστας.
  • Αν αυτή που επιλέξατε υπάρχει ήδη στη λίστα, επιλέγετε την επόμενη σειριακά, μέχρι να βρείτε μια διαθέσιμη, οπότε και προσθέτετε το ζευγάρι στη λίστα.

Τέλος, υλοποιήστε και την ακόλουθη συνάρτηση του state.h :

// Καταστρέφει την κατάσταση state ελευθερώνοντας τη δεσμευμένη μνήμη.
void state_destroy(State state);

Άσκηση 3 (20%)

Συνεχίζοντας την υλοποίηση του παιχνιδιού, καλείστε να ολοκληρώσετε το stats.h υλοποιώντας την τελευταία συνάρτηση:

// Ενημερώνει την κατάσταση state του παιχνιδιού μετά την πάροδο 1 frame.
// Το keys περιέχει τα πλήκτρα τα οποία ήταν πατημένα κατά το frame αυτό.
void state_update(State state, KeyState keys);

Η κατάσταση του παιχνιδιού ενημερώνεται ανάλογα με τα πλήκτρα που είναι πατημένα στο συγκεκριμένο frame (παράμετρος keys) με βάση τους ακόλουθους κανόνες:

  • Κίνηση Χαρακτήρα:

    • μετακινείται 7 pixels σε κάθε frame στην κατεύθυνση της κίνησής του. Αν είναι πατημένο το βέλος στην ίδια φορά με την κίνησή του τότε μετακινείται 12 pixels.

    • Αν είναι πατημένο το βέλος αντίθετα στη φορά της κίνησής του, αλλάζει κατεύθυνση.

    • Αν είναι στο έδαφος και είναι πατημένο το πάνω βέλος, μπαίνει σε κατάσταση άλματος.

    • Στην κατάσταση άλματος μετακινείται 15 pixels προς τα πάνω σε κάθε frame, μέχρι να φτάσει 220 pixels από το έδαφος. Τότε αρχίζει πτώση, πάλι 15 pixels ανά frame, μέχρι να φτάσει στο έδαφος.

  • Κίνηση Εχθρών : 5 pixels ανά frame στην κατεύθυνση της κίνησής τους.

  • Συγκρούσεις:

    • Αν ο Χαρακτήρας συγκρουστεί με Εχθρό ή Εμπόδιο τερματίζει το παιχνίδι.
    • Αν ένας εχθρός συγκρουστεί με Εμπόδιο, αλλάζει κατεύθυνση.
    • Αν ο Χαρακτήρας ή ένας Εχθρός συγκρουστεί με μια Πύλη A ενώ κινείται στην κανονική κατεύθυνση (προς τα δεξιά), τότε μετακινείται στην αντίστοιχη πύλη B στην οποία οδηγεί η Α. Αν κινείται ανάποδα, τότε η μετακίνηση είναι αντίστροφη, δηλαδή μετακινείται στην πύλη B η οποία οδηγεί στην A.
    • Αν ο χαρακτήρας συγκρουστεί με την τελευταία πύλη, τότε προστίθεται μία νίκη και μετακινείται στην αρχή της πίστας (χωρίς να αλλάξει κάτι άλλο).

    Για τις συγκρούσεις μπορείτε να χρησιμοποιήσετε (χωρίς να είναι απαραίτητο) τις συναρτήσεις CheckCollisionRecs, CheckCollisionPointRec, ... από το libraylib.h.

  • Εκκίνηση και διακοπή:

    • Αν το παιχνίδι έχει τελειώσει και πατηθεί enter, τότε ξαναρχίζει από την αρχή.
    • Αν πατηθεί P το παιχνίδι μπαίνει σε pause και δεν ενημερώνεται πλέον.
    • Αν το παιχνίδι είναι σε pause και πατηθεί N τότε ενημερώνεται για μόνο 1 frame (χρήσιμο για debugging).

Είστε ελεύθεροι να προσαρμόσετε τους κανόνες αυτούς, σε λογικά πλαίσια, ανάλογα με το interface που θα υλοποιήσετε αργότερα. Πχ μπορείτε να προσαρμόσετε την ταχύτητα των αντικειμένων, μπορεί η έξοδος από μια πύλη να γίνεται στη μέση ή στο τέλος της πύλης, μπορεί ο χαρακτήρας κατά την έξοδο να είναι σε κατάσταση άλματος, κλπ.

Τέλος, επεκτείνετε το tests/test_state.c ώστε να ελέγχει τη λειτουργία της state_update. Δεν χρειάζεται στο test να ελέγξετε όλο το functionality της state_update, αρκεί μόνο ο έλεγχος ότι η θέση του χαρακτήρα ενημερώνεται σωστά ανάλογα με τα πλήκτρα που είναι πατημένα. Δεν απαιτούνται έλεγχοι για τις συγκρούσεις ή για τα αντικείμενα της πίστας (αλλά φυσικά μπορείτε να προσθέσετε επιπλέον ελέγχους αν το επιθυμείτε).

Άσκηση 4 (15%)

Υλοποιήστε ένα module set_utils.h με τις παρακάτω λειτουργίες:

// Επιστρέφει την μοναδική τιμή του set που είναι ισοδύναμη με value,
// ή αν δεν υπάρχει, την μικρότερη τιμή του set που είναι μεγαλύτερη
// από value. Αν δεν υπάρχει καμία τότε επιστρέφει NULL.

Pointer set_find_eq_or_greater(Set set, Pointer value);

// Επιστρέφει την μοναδική τιμή του set που είναι ισοδύναμη με value,
// ή αν δεν υπάρχει, την μεγαλύτερη τιμή του set που είναι μικρότερη
// από value. Αν δεν υπάρχει καμία τότε επιστρέφει NULL.

Pointer set_find_eq_or_smaller(Set set, Pointer value);

Η υλοποίηση πρέπει να είναι αποδοτική, χωρίς να διατρέχει ολόκληρο το set. Ένας γενικός τρόπος (που δεν απαιτεί γνώση της υλοποίησης του ADTSet) είναι ο εξής: πρώτα ελέγχετε αν το value υπάρχει ήδη. Αν όχι, τότε το εισάγετε, χρησιμοποιείτε το νέο στοιχείο για να βρείτε το αμέσως επόμενο/προηγούμενο, και τέλος το αφαιρείτε.

Επίσης υλοποιήστε ένα test που να ελέγχει (εν συντομία) την υλοποίηση του module.

Άσκηση 5 (20%)

Η υλοποίηση modules/state.c του module state.h που φτιάξατε στις προηγούμενες εργασίες είναι πολύ καλή για να δημιουργήσουμε ένα γρήγορο prototype του παιχνιδιού, αλλά η αποθήκευση δεδομένων στα Vector objects και List portal_pairs δημιουργεί σημαντική καθυστέρηση στους αλγορίθμους.

Στην άσκηση αυτή καλείστε να φτιάξετε μια τροποποιημένη υλοποίηση modules/state_alt.c του ίδιου module, χρησιμοποιώντας οποιονδήποτε ADT είδαμε στο μάθημα, με τους παρακάτω στόχους:

  • Η συνάρτηση state_objects πρέπει γρήγορα να επιστρέφει τα αντικείμενα που βρίσκονται ανάμεσα στα x_from και x_to, χωρίς να εξετάζει όλα τα αντικείμενα της πίστας.

  • Στην state_update, ο έλεγχος αν ένα συγκεκριμένο αντικείμενο βρίσκεται σε σύγκρουση με κάποιο άλλο πρέπει να γίνεται γρήγορα, χωρίς να εξετάζονται όλα τα αντικείμενα της πίστας.

  • Η εύρεση της πύλης Β στην οποία οδηγεί η πύλη A (ή αντίστοιχα η πύλη A η οποία οδηγεί στη B) πρέπει να γίνεται γρήγορα, χωρίς να εξετάζονται όλες τα ζευγάρια πυλών.

Για την υλοποίησή σας μπορείτε να τροποποιήσετε το state_alt.c όπως νομίζετε, αλλά καμία αλλαγή δεν επιτρέπεται στο state.h (ώστε οι χρήστες του module να συνεχίζουν να δουλεύουν χωρίς τροποποιήσεις). Η υλοποίησή σας θα πρέπει επίσης να περνάει το tests/state_test.c που έχετε φτιάξει στις προηγούμενες ασκήσεις, χωρίς καμία τροποποίηση.

Άσκηση 6 (15%)

Στο τελικό στάδιο είμαστε πλέον έτοιμοι να υλοποιήσουμε το πλήρες παιχνίδι. Για το σκοπό αυτό καλείστε να υλοποιήσετε ένα module interface.h με τις ακόλουθες συναρτήσεις.

// Αρχικοποιεί το interface του παιχνιδιού
void interface_init();

// Κλείνει το interface του παιχνιδιού
void interface_close();

// Σχεδιάζει ένα frame με την τωρινή κατάσταση του παιχνδιού
void interface_draw_frame(State state);

Η βασική συνάρτηση είναι η interface_draw_frame στην οποία πρέπει αρχικά να συλλέξετε πληροφορίες για την κατάσταση του παιχνιδιού, χρησιμοποιώντας το state.h module, και στη συνέχεια να σχεδιάσετε τα αντικείμενα τα οποία είναι ορατά στο συγκεκριμένο frame.

Για το σχεδιασμό μπορείτε να χρησιμοποιείτε όλες τις συναρτήσεις του raylib.h, δείτε το παράδειγμα του programs/game_example για να ξεκινήσετε. Πλήρης λίστα με τις συναρτήσεις υπάρχει στο raylib.h, αλλά και στο παρακάτω reference. Φυσικά εσείς θα χρειαστείτε ελάχιστες από αυτές, δείτε κυρίως τις DrawLine, DrawText, DrawRectangleRec, DrawTexture, .... Τα γραφικά δεν χρειάζεται προφανώς να είναι σύνθετα, μπορεί το κάθε αντικείμενο να είναι απλά ένα χρωματιστό παραλληλόγραμμο, αρκεί το τελικό αποτέλεσμα να είναι playable.

Προσοχή: στην οθόνη θέλετε να σχεδιάσετε μόνο το ορατό μέρος της συνολικής πίστας. Οπότε πρέπει να βρείτε τα αντικείμενα που είναι ορατά (μέσω της state_objects) αλλά και να μετατρέψετε τις συντεταγμένες του state σε συντεταγμένες της οθόνης.

Για να ολοκληρωθεί το παιχνίδι χρειάζεται τέλος και μία συνάρτηση main η οποία θα ξεκινάει το “main loop” του παιχνιδιού, καλώντας διαδοχικά τις state_update και interface_draw_frame. Και πάλι, δείτε το παράδειγμα του programs/game_example. Η συνάρτηση main πρέπει να βρίσκεται στο αρχείο programs/game/game.c.

Παρατηρήσεις: Το παιχνίδι θα πρέπει να δουλεύει και με τις δύο υλοποιήσεις του state.h module που υλοποιήσατε. Για να δείτε τη διαφορά στην απόδοση, προσθέστε ένα framerate (FPS) counter, και αυξήστε τη σταθερά PORTAL_NUM μέχρι το FPS να πέσει κάτω από 60. Αναφέρετε στο README.md μια τάξη μεγέθους για τον αριθμό που άντεξε κάθε υλοποίηση.

Επίσης, όπως αναφέρθηκε και στην Άσκηση 3, είστε ελεύθεροι να τροποποιήσετε την υλοποίηση του state.h module για να προσαρμόσετε το παιχνίδι στο interface που δημιουργήσατε. Στο interface του module από την άλλη δεν επιτρέπονται αλλαγές (αλλά έχετε πλήρη ελευθερία για αλλαγές στο παρακάτω design competition).

Design competition

Αφήστε τη δημιουργικότητά σας να δουλέψει και εξελίξτε το παιχνίδι με οποιοδήποτε τρόπο θέλετε! Βάλτε νέους χαρακτήρες, εξελίξτε το gameplay, φτιάξτε καλύτερα physics, βελτιώστε τα γραφικά, προσθέστε storyline, σχεδιάστε πίστες, animations, ή οτιδήποτε άλλο θέλετε.

Νικητής του διαγωνισμού θα είναι απλά το πιο ευχάριστο παιχνίδι. Αυτό δε σημαίνει το πιο σύνθετο τεχνικά, συχνά τα απλά παιχνίδια είναι και τα πιο εθιστικά. Η επιλογή θα γίνει με ψηφοφορία (ίσως μετά από προεπιλογή, αν οι συμμετοχές είναι πάρα πολλές). Όλοι οι συμμετέχοντες μπορούν να κερδίσουν bonus έως 25% στο βαθμό της εργασίας (ανάλογα με τις βελτιώσεις που έχουν υλοποιήσει), ενώ οι 2 πρώτοι κερδίζουν bonus 50% και 100% αντίστοιχα.

Για να συμμετέχετε στο διαγωνισμό, φτιάξτε το παιχνίδι σας στο directory programs/competition, και βεβαιωθείτε ότι τρέχοντας make game στο directory αυτό παράγεται το εκτελέσιμο game του παιχνιδιού. Τα περιεχόμενα του directory δε θα ληφθούν υπόψη στη βαθμολόγηση παρά μόνο στο διαγωνισμό. Για τις βελιτώσεις του παιχνιδιού έχετε μία επιπλέον εβδομάδα από την προθεσμία της εργασίας. Αλλαγές στo repository που θα γίνουν μετά την προθεσμία, και πριν το τέλος της επιπλέον εβδομάδας, θα ληφθούν υπόψη για τον διαγωνισμό αλλά όχι για τη βαθμολόγηση της εργασίας. Επίσης περιγράψτε τις βελτιώσεις που υλοποιήσατε στο README.md.

Game Competition

Τέλος, στο παιχνίδι που θα κερδίσει τον παραπάνω διαγωνισμό, θα ακολουθήσει game competition για να αποδείξετε ότι είστε ο καλύτερος gamer του DI! Ο διαγωνισμός θα έχει χαρακτήρα esport, θα μεταδοθεί live και θα μπορεί να συμμετέχει οποιοσδήποτε φοιτητής του τμήματος. Περισσότερες λεπτομέρειες θα ανακοινωθούν μετά την παράδοση της εργασίας.

Χρήση σε Windows/WSL

Για να κάνετε compile το game_example σε WSL:

  • Αρχικά ακολουθήστε τις οδηγίες εγκατάστασης και εκτελέστε το

    curl https://k08.chatzi.org/vscode/config.sh | bash
    

    (ίσως χρειαστεί να το ξανατρέξετε, αν δεν το έχετε κάνει πρόσφατα).

  • Στη συνέχεια εγκαταστήστε το VcXsrv το οποίο επιτρέπει να τρέχουμε Linux προγράμματα με γραφικό interface στο WSL.

  • Αφού το εγκαταστήσετε, εκτελέστε το VcXsrv, επιλέξτε τις default ρυθμίσεις, και κρατήστε το ανοικτό όσο δουλεύετε.

  • Τέλος κάνουμε compile/debug από το VS Code ως συνήθως (Ctrl-Shift-B, F5, κλπ).

Αν θέλουμε να τρέξουμε το παιχνίδι manually από την κονσόλα, εκτελούμε πιο πριν export DISPLAY=:0 (το Makefile το κάνει αυτό αυτόματα).

Τρέχοντας το παιχνίδι μέσα από WSL δεν θα έχει ήχο, αλλά δεν είναι απαραίτητος ο ήχος για την εργασία. Οι πιο τολμηροί μπορούν να δοκιμάσουν τις παρακάτω οδηγίες για ήχο σε WSL (αλλά ίσως είναι απλούστερο απλά να χρησιμοποιήσετε Linux).

Τέλος το Makefile που σας δίνεται επιτρέπει να παράγετε και native executables (.exe) μέσα από το WSL, τα οποία υποστηρίζουν και ήχο:

sudo apt install gcc-mingw-w64-x86-64
make OS=Windows_NT