Εργασία 1

Last updated on Apr 14, 2025

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

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

Γενικά

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

Για την υλοποίηση του γραφικού 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,
// των οποίων η θέση position βρίσκεται εντός του παραλληλογράμμου με πάνω αριστερή
// γωνία top_left και κάτω δεξιά bottom_right.
List state_objects(State state, Vector2 top_left, Vector2 bottom_right);

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

Άσκηση 2 (20%)

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

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

Η βασική λειτουργία που έχετε να υλοποιήσετε είναι η κίνηση του φιδιού, το σώμα του οποίου αποτελείται από δύο ή περισσότερα τμήματα που αποθηκεύονται στη λίστα snake. Κάθε στοιχείο της λίστας είναι ένα διάνυσμα (τύπος Vector2) που περιέχει τη θέση του τμήματος:

  • η ουρά του φιδιού βρίσκεται στην αρχή της λίστας,
  • το κεφάλι βρίσκεται στο τέλος της.

Η κίνηση γίνεται με τον εξής τρόπο: κάθε τμήμα του φιδιού μετατοπίζεται στη θέση που βρίσκεται το επόμενό του, ενώ το κεφάλι μετατοπίζεται κατά SNAKE_SIZE στην κατεύθυνση της κίνησης του φιδιού. Για παράδειγμα, αν το φίδι έχει 10 τμήματα, τότε το 1o στη λίστα (η ουρά) μετατοπίζεται στη θέση του 2ου, το 2ο στη θέση του 3ου, κλπ, ενώ το 10ο (κεφάλι) μετατοπίζεται κατά SNAKE_SIZE pixels (στο αξόνα x αν η κίνηση είναι προς τα δεξιά).

Προσοχή: λόγω της ιδιαίτερης κίνησης του φιδιού, η μεταβολή της κίνησης του πρέπει να γίνεται κάθε UPDATE_STATE_FRAMES (όχι σε κάθε frame). Για να γίνει αυτό πρέπει να χρησιμοποιήσετε τη μεταβλητή frame_counter του state.

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

  • Κίνηση φιδιού:

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

  • Παύση και διακοπή:

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

Είστε ελεύθεροι να προσαρμόσετε τους κανόνες αυτούς, σε λογικά πλαίσια, ανάλογα με το interface που θα υλοποιήσετε αργότερα.

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

Άσκηση 3 (15%)

Στην άσκηση αυτή καλείστε να ολοκληρώσετε τη συνάρτηση state_update που υλοποιήσατε στην προηγούμενη άσκηση, προσθέτωντας τις παρακάτω λειτουργίες:

  • Δημιουργία μήλων και αετών: σε κάθε update πρέπει να υπάρχουν MIN_APPLES_NUM μήλα και MIN_EAGLES_NUM αετοί κοντά στο φίδι, όπου “κοντά” θεωρείται απόσταση έως MAX_DIST από το κεφάλι του φιδιού. Αν δεν υπάρχουν τότε δημιουργούνται όσα λείπουν, καλώντας τη συνάρτηση add_random_objects.

  • Κίνηση αετών:

    • Κάθε αετός μετατοπίζεται κατά EAGLE_SPEED στην κατεύθυνση της κίνησής του.
    • Σε κάθε update κάθε αετός μπορεί να αλλάξει κατεύθυνση τυχαία, με πιθανότητα EAGLE_TURN_PROB. Όταν γίνεται αλλαγή κατεύθυνσης η νέα κατεύθυνση επιλέγεται στην τύχη με ομοιόμορφη κατανομή.
    • Τα updates γίνονται κάθε UPDATE_STATE_FRAMES (όπως και για το φίδι).

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

    • Στις παρακάτων περιπτώσεις το παιχνίδι τελειώνει (game over):
      • Αν οποιοδήποτε τμήμα του φιδιού συγκρουστεί με αετό.
      • Αν το κεφάλι του φιδιού συγκρουστεί με οποιοδήποτε τμήμα του φιδιού.
    • Αν το κεφάλι του φιδιού συγκρουστεί με μήλο τότε το σώμα του φιδιού μεγαλώνει ως εξής: όλα τα τμήματα του φιδιού παραμένουν στη θέση τους (αντί να μετακινηθούν ως συνήθως) και προστίθεται ένα νέο κεφάλι μετατοπισμένο κατά SNAKE_SIZE σε σχέση με το παλιό (στην κατεύθυνση της κίνησης του φιδιού).

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

  • Σκορ: Για κάθε φαγωμένο μήλο το σκορ αυξάνεται κατά 1.

Τέλος, επεκτείνετε το tests/test_state.c ώστε να ελέγχει τις παραπάνω λειτουργίες. Όπως πάντα, δε χρειάζονται εξαντλητικά tests, αρκεί να ελέγχονται σύντομα οι συγκρούσεις και η κίνηση.

Άσκηση 4 (15%)

Ο αλγόριθμος κίνησης του φιδιού που περιγράφηκε στην Άσκηση 2 απαιτεί χρόνο $O(n)$, όπου $n$ το μήκος του φιδιού, αφού κάθε τμήμα πρέπει να μετακινηθεί. Τροποποιήστε την υλοποίησή σας ώστε η μετακίνηση του φιδιού να γίνεται σε χρόνο $O(1)$. Για να γίνει αυτό εκμεταλλευόμαστε το γεγονός ότι σχεδόν όλα τα τμήματα του φιδιού μετακινούνται σε σημείο όπου προηγουμένως βρισκόταν κάποιο άλλο τμήμα.

Η υλοποίησή σας θα πρέπει να περνάει τα tests που ήδη έχετε φτιάξει για την κίνηση του φιδιού.

Άσκηση 5 (20%)

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

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

  • Η state_update πρέπει να ενημερώνει μόνο τα αντικείμενα που βρίσκονται σε απόσταση το πολύ 2 οθόνων από το φίδι (τα υπόλοιπα μπορούν να παραμένουν ακίνητα). Η εύρεση των αντικειμένων δεν πρέπει να εξετάζει όλα τα αντικείμενα της πίστας.

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

Για την υλοποίησή σας μπορείτε να τροποποιήσετε το 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.

Φυσικά εσείς θα χρειαστείτε ελάχιστες από αυτές, δείτε κυρίως τις DrawLine, DrawText, DrawCircleLines, 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, και δοκιμάστε να προσθέσετε έναν μεγάλο αριθμό τυχαίων αντικειμένων μέχρι το FPS να πέσει κάτω από 60.

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

Design competition

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

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

Το design competition (όχι όλη η εργασία) είναι αυστηρά ομαδικό (για να μάθετε να συνεργάζεστε), σε ομάδες των τουλάχιστον τριών ατόμων (χωρίς άνω όριο). Δεν είναι απαραίτητο όλα τα μέλη της ομάδας να γράψουν κώδικα, μπορεί κάποιοι να ασχοληθούν με τα γραφικά, τη μουσική, το gameplay, κλπ (αλλά όλοι πρέπει να συμμετέχουν ενεργά). Μπορούν επίσης να συμμετέχουν άτομα εκτός μαθήματος (από άλλα έτη, τμήματα, σχολές, κλπ).

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

ΠΡΟΣΟΧΗ: η συνεργασία για το design competition πρέπει να ξεκινήσει μετά το τέλος της κανονικής εργασίας. Ομοιότητες στον κώδικα θα θεωρηθούν αντιγραφή, το design competition δεν θα αποτελέσει σε καμία περίπτωση δικαιολογία αντιγραφής

Χρήση σε Windows/WSL2

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

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

Credits

Ο σχεδιασμός και η υλοποίηση του παιχνιδιού έγινε από τους: