Im just not sure how to get his going
Πανεπιστήμιο Κρήτης Τμήμα Επιστήμης Υπολογιστών, 19 Οκτωβρίου 2020 ΗΥ240: Δομές Δεδομένων Χειμερινό Εξάμηνο - Ακαδημαϊκό Έτος 2020-2021 Διδάσκουσα: Παναγιώτα Φατούρου Προγραμματιστική Εργασία - 1ο Μέρος Ημερομηνία Παράδοσης: Δευτέρα, 16 Νοεμβρίου 2020, ώρα 09:59 πμ Τρόπος παράδοσης: Χρησιμοποιώντας το πρόγραμμα turnin. Πληροφορίες για το πώς λειτουργεί το πρόγραμμα turnin παρέχονται στην ιστοσελίδα του μαθήματος. Φωτογραφία: https://upload.wikimedia.org/wikipedia/en/7/72/AmongUs_CoverArt.jpg Γενική Περιγραφή Εργασίας Στην εργασία αυτή καλείστε να υλοποιήσετε μία προσομοίωση, μίας παρτίδας του παιχνιδιού Among Us. «Among Us is an online multiplayer social deduction game, developed and published by American game studio InnerSloth and released on June 15, 2018. The game takes place in a space-themed setting where players each take on one of two roles, most being Crewmates, and a predetermined number being Impostors. The goal for the Crewmates is to identify the Impostors, remove them from the game, and complete tasks around the map; the Impostors' goal is to covertly sabotage the Crewmates and remove them from the game before they complete all their tasks. Through a plurality vote, players believed to be Impostors may be removed from the game. If all Impostors are removed from the game or all tasks are completed, the Crewmates win; if there are an equal number of Impostors and Crewmates, or if a critical sabotage goes unresolved, the Impostors win.» (Wikipedia) Αξίζει να σημειωθεί, ότι για τους εκπαιδευτικούς σκοπούς του μαθήματος ορισμένα σημεία της εργασίας ενδέχεται να αποκλίνουν από το πραγματικό παιχνίδι. Αναλυτική Περιγραφή Ζητούμενης Υλοποίησης Κάθε παίκτης (player), εξωγήινος (impostor) ή άνθρωπος (crewmate), περιγράφεται από ένα μοναδικό αναγνωριστικό. Πληροφορίες για τους παίκτες αποθηκεύονται σε μία διπλά συνδεδεμένη κυκλική λίστα με κόμβο φρουρό (Σχήμα 1), που λέγεται λίστα παικτών. Κάθε στοιχείο της λίστας είναι ένα Πανεπιστήμιο Κρήτης Τμήμα Επιστήμης Υπολογιστών, 19 Οκτωβρίου 2020 struct τύπου Player και αντιστοιχεί σε έναν παίκτη. Για κάθε παίκτη, υπάρχει μία μεταβλητή τύπου int (που λέγεται is_alien), η οποία υποδηλώνει αν ο παίκτης είναι εξωγήινος ή άνθρωπος και μία μεταβλητή τύπου int (που λέγεται evidence), η οποία δείχνει κατά πόσο ο παίκτης θα θεωρηθεί ύποπτος σε επόμενες ψηφοφορίες. Σημειώνεται ότι, παρότι γίνεται καταγραφή του τύπου του κάθε παίκτη στη λίστα, θεωρούμε ότι οι άλλοι παίκτες δεν έχουν πρόσβαση στο πεδίο is_alien κάθε παίκτη και άρα δεν μπορούν να ανακαλύψουν από εκεί, αν ο παίκτης είναι εξωγήινος ή άνθρωπος. Πιο συγκεκριμένα, μια εγγραφή τύπου struct Player έχει τα ακόλουθα πεδία: ● pid: Αναγνωριστικό (τύπου int) που χαρακτηρίζει μοναδικά τον παίκτη. ● is_alien: Flag (τύπου int) που χαρακτηρίζει εάν ο παίκτης είναι εξωγήινος (impostor) ή άνθρωπος (crewmate). ● evidence: Ακέραιος που περιγράφει το βαθμό κατά τον οποίο ένας παίκτης θεωρείται ύποπτος (τύπου int). ● prev: Δείκτης (τύπου struct Player) που δείχνει στον προηγούμενο κόμβο της λίστας παικτών. ● next: Δείκτης (τύπου struct Player) που δείχνει στον επόμενο κόμβο της λίστας παικτών. ● tasks_head: Δείκτης (τύπου struct Task) που δείχνει στο πρώτο στοιχείο μιας λίστας με κόμβο φρουρό (που ονομάζεται λίστα εργασιών του παίκτη και περιγράφεται στη συνέχεια), η οποία περιέχει πληροφορίες για τις εργασίες (tasks) που θα ανατεθούν στον παίκτη. ● tasks_sentinel: Δείκτης (τύπου struct Task) που δείχνει στον κόμβο φρουρό της λίστας εργασιών του παίκτη. Σχήμα 1. Η λίστα παικτών που είναι διπλά συνδεδεμένη, κυκλική, με κόμβο φρουρό και μη ταξινομημένη. Το δεύτερο πεδίο δείχνει αν ένας παίκτης είναι εξωγήινος ή όχι και το τρίτο πεδίο φανερώνει κατά πόσο ύποπτος είναι ένας παίκτης. Για λόγους απλοποίησης του σχήματος, θεωρούμε ότι το πεδίο tasks έχει την τιμή NULL σε όλα τα Πανεπιστήμιο Κρήτης Τμήμα Επιστήμης Υπολογιστών, 19 Οκτωβρίου 2020 στοιχεία της παραπάνω λίστας. Ο κάθε παίκτης έχει διάφορες εργασίες (tasks) να ολοκληρώσει. Έτσι, για κάθε παίκτη υπάρχει μια απλά συνδεδεμένη ταξινομημένη λίστα με κόμβο φρουρό, που λέγεται λίστα εργασιών του παίκτη. Για κάθε εργασία του παίκτη υπάρχει ένα μοναδικό αναγνωριστικό (tid) και ένας βαθμός δυσκολίας (difficulty). Η λίστα εργασιών κάθε παίκτη είναι ταξινομημένη ως προς το βαθμό δυσκολίας της κάθε εργασίας που περιέχει. Όλες οι εργασίες που πρέπει να πραγματοποιηθούν για να νικήσουν οι άνθρωποι, εισάγονται αρχικά σε μία απλά συνδεδεμένη λίστα , η οποία είναι επίσης ταξινομημένη βάσει του βαθμού δυσκολίας. Η λίστα αυτή ονομάζεται γενική λίστα εργασιών (Σχήμα 2). Αφού όλες οι εργασίες εισαχθούν στη γενική λίστα εργασιών, θα μοιραστούν τελικά στις λίστες εργασιών των παικτών (Σχήμα 3). Κάθε κόμβος της γενικής λίστας εργασιών αλλά και της λίστας εργασιών ενός συγκεκριμένου παίκτη, αποτελεί μία εγγραφή τύπου struct Task με τα ακόλουθα στοιχεία: ● tid: Αναγνωριστικό (τύπου int) που χαρακτηρίζει μοναδικά την κάθε εργασία. ● difficulty: Ο βαθμός δυσκολίας (τύπου int) της κάθε εργασίας. Υπάρχουν 3 βαθμοί δυσκολίας (που σηματοδοτούνται από τους αριθμούς 1, 2 και 3). ● next: Δείκτης (τύπου struct Task) που δείχνει στον επόμενο κόμβο. Υπάρχει ένα struct, τύπου General_List που περιέχει τα εξής πεδία: GL: Δείκτης σε struct τύπου Τask που δείχνει στο πρώτο στοιχείο της γενικής λίστας εργασιών. tasks_count[3]: Πίνακας τριών ακεραίων. Το count[i] μετράει πόσες εργασίες βαθμού (i+1) υπάρχουν στη γενική λίστα εργασιών. Υπάρχει και μια καθολική μεταβλητή Total_Tasks που αποθηκεύει το συνολικό πλήθος των εργασιών που αποθηκεύονται στη λίστα εργασιών. Σχήμα 2. Η γενική λίστα εργασιών. Πρόκειται για μια απλά συνδεδεμένη λίστα που είναι ταξινομημένη ως προς τη δυσκολία της κάθε εργασίας. Πανεπιστήμιο Κρήτης Τμήμα Επιστήμης Υπολογιστών, 19 Οκτωβρίου 2020 Σχήμα 3. Η διπλά συνδεδεμένη κυκλική λίστα με κόμβο φρουρό παικτών, η οποία είναι μη-ταξινομημένη, μετά την ανάθεση εργασιών στους παίκτες. Παρατηρήστε ότι η λίστα των εργασιών κάθε παίκτη είναι ταξινομημένη όπως και η γενική λίστα εργασιών με βάση τη δυσκολία της κάθε δουλειάς. Αφότου έχουν καταχωρηθεί οι δουλειές στους ανθρώπους (μέλη του πληρώματος – creawmates), τότε εκείνοι αρχίζουν να τις υλοποιούν έτσι ώστε να καταφέρουν να νικήσουν την παρτίδα. Κάθε φορά που κάποιος άνθρωπος ολοκληρώσει μία εργασία τότε αυτή αφαιρείται από τη λίστα των εργασιών του και εισάγεται σε μία στοίβα ολοκλήρωσης εργασιών (Σχήμα 4). Κάθε κόμβος της στοίβας αποτελεί μία Πανεπιστήμιο Κρήτης Τμήμα Επιστήμης Υπολογιστών, 19 Οκτωβρίου 2020 εγγραφή τύπου struct Task (δηλαδή έχει ίδιου τύπου στοιχεία με τη γενική λίστα εργασιών και τις λίστες εργασιών των παικτών). Υπάρχει ένα struct, τύπου Head_Completed_Task_Stack που περιέχει τα εξής πεδία: Head: Δείκτης σε struct τύπου Τask που δείχνει στο κορυφαίο στοιχείο της στοίβας. count: Ακέραιος που αποθηκεύει το πλήθος των στοιχείων της στοίβας. Σχήμα 4. Η στοίβα με τις ολοκληρωμένες εργασίες. Αν γεμίσει τότε οι άνθρωποι νίκησαν την παρτίδα. Τρόπος Λειτουργίας Προγράμματος Το πρόγραμμα που θα δημιουργηθεί θα πρέπει να εκτελείται καλώντας την ακόλουθη εντολή:
όπου είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)executable> είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out) και είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)input-fle> είναι το όνομα ενός αρχείου εισόδου (π.χ. testile) το οποίο περιέχει γεγονότα των ακόλουθων μορφών: P Γεγονός τύπου insert Player που υποδηλώνει την εισαγωγή ενός παίκτη με αναγνωριστικό είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)pid> στο παιχνίδι. Κατά το γεγονός αυτό ένα στοιχείο (που θα αντιστοιχεί στο νέο παίκτη) θα εισάγεται στη λίστα παικτών. Τα πεδία evidence και is_alien του στοιχείου αυτού πρέπει να αρχικοποιούνται με τις τιμές 0 και είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)is_allien>, αντίστοιχα (αν η είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)is_allien> είναι 1 τότε ο παίκτης είναι εξωγήινος, διαφορετικά είναι άνθρωπος, μέλος του πληρώματος). Η λίστα εργασιών του παίκτη αρχικοποιείται να περιέχει μόνο τον Πανεπιστήμιο Κρήτης Τμήμα Επιστήμης Υπολογιστών, 19 Οκτωβρίου 2020 κόμβο φρουρό της. Θεωρήστε ότι το είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)pid> είναι μοναδικό (δηλαδή όλα τα είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)pid> που σχετίζονται με γεγονότα τύπου P στο test_file είναι διαφορετικά). Υλοποιήστε την εισαγωγή με τον πιο αποτελεσματικό τρόπο. Μετά το πέρας της εκτέλεσης ενός τέτοιου γεγονότος, το πρόγραμμα θα πρέπει να τυπώνει την ακόλουθη πληροφορία: P Players = … DONE όπου n είναι ο αριθμός των κόμβων στη λίστα παικτών και για κάθε i {1,...,n}, είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος (π.χ. a.out)pid∊{1,...,n}, είναι το αναγνωριστικό του παίκτη που αντιστοιχεί στον i-οστό κόμβο της λίστας αυτής. T Γεγονός τύπου Insert Task που υποδηλώνει τη δημιουργία μίας εργασίας με αναγνωριστικό είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος