Conway's Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input.
make
Test life.c module:
cd tests
cd life_test
./life_test
Make a life gif:
cd programs
cd askisi6
./life_gif <rle file> <top coordinates> <left coordinates> <bottom coordinates> <right coordinates> <frames>=1> <zoom>0> <speed>=1> <delay> <gif name>
For example:
./life_gif file 0 0 20 20 100 1 1 1 life_gif
while file.rle contains: bo$2bo$3o!
Το “Παιχνίδι της Ζωής” (“Game of Life”) είναι ένα “κυτταρικό αυτόματο” το οποίο κατασκευάστηκε από τον μαθηματικό John Horton Conway το 1970. Κάθε κατάσταση του παιχνιδιού αυτού περιλαμβάνει έναν δισδιάστατο πίνακα απείρου μεγέθους, στον οποίο κάθε κελί έχει ακέραιες συντεταγμένες x,y. Ως συνήθως ο άξονας x είναι ο οριζόντιος, στον οποίο οι συντεταγμένες αυξάνονται προς τα δεξία, ενώ y είναι ο κατακόρυφος, στον οποίο βολεύει περισσότερο οι συντεταγμένες να αυξάνονται προς τα κάτω (αν προτιμάτε ο y να αυξάνεται προς τα πάνω κανένα πρόβλημα). Κάθε κελί μπορεί να είναι είτε “ζωντανό” είτε “νεκρό”. Το παιχνίδι ξεκινάει από κάποια δοσμένη αρχική κατάσταση, και σε κάθε χρονική στιγμή εξελίσσεται ακολουθώντας τους παρακάτω πολύ απλούς κανόνες:
Κάθε ζωντανό κελί με λιγότερους από 2 ή περισσότερους από 3 ζωντανούς γείτονες πεθαίνει (λόγω υπο- και υπερ-πληθυσμού αντίστοιχα). Κάθε νεκρό κελί με ακριβώς 3 ζωντανούς γείτονες ζωντανεύει (λόγω αναπαραγωγής). Ολα τα υπόλοιπα κελιά (ζωντανά ή νεκρά) παραμένουν ως έχουν. Παρά τους πολύ απλούς κανόνες, στο Game of Life παρατηρούνται εξαιρετικά πολύπλοκα και ενδιαφέροντα patterns. Σκοπός της εργασίας είναι η προσωμοίωση του παιχνιδιού.
Αρχικά δημιουργήστε ένα module life το οποίο θα παρέχει τις παρακάτω λειτουργίες.
// Δημιουργεί μια κατάσταση του παιχνιδιού όπου όλα τα κελιά είναι νεκρά.
LifeState life_create();
// Δημιουργεί μία κατάσταση του παιχνιδιού με βάση τα δεδομένα του αρχείο file (RLE format)
LifeState life_create_from_rle(char* file);
// Αποθηκεύει την κατάσταση state στο αρχείο file (RLE format)
void life_save_to_rle(LifeState state, char* file);
// Επιστρέφει την τιμή του κελιού cell στην κατάσταση state (true: ζωντανό, false: νεκρό)
bool life_get_cell(LifeState state, LifeCell cell);
// Αλλάζει την τιμή του κελιού cell στην κατάσταση state
void life_set_cell(LifeState state, LifeCell cell, bool value);
// Παράγει και επιστρέφει μια νέα κατάσταση που προκύπτει από την εξέλιξη της κατάστασης state.
// Η ίδια η state δε μεταβάλλεται (ούτε καταστρέφεται).
LifeState life_evolve(LifeState state);
// Καταστρέφει την κατάσταση ελευθερώντας οποιαδήποτε μνήμη έχει δεσμευτεί
void life_destroy(LifeState state);
Ο τύπος LifeCell ορίζεται ως εξής:
typedef struct {
int x, y;
} LifeCell;
Λόγω απλότητας, ο τύπος αυτός μπορεί να είναι ορατός στο χρήστη, χωρίς τη χρήση handle (μια μεταβλητή τύπου LifeCell περιέχει το ίδιο το struct).
Ο τύπος LifeState θα πρέπει να είναι κατάλληλα ορισμένος ώστε να αποθηκεύει με αποδοτικό τρόπο οποιαδήποτε πληροφορία χρειάζεστε για την υλοποίηση των μεθόδων αυτών, χρησιμοποιώντας οποιονδήποτε από τους ΑΤΔ που είδαμε στο μάθημα θεωρείτε σκόπιμο. Ας σημειωθεί ότι παρόλο που ο χώρος του παιχνιδιού είναι άπειρος, σε κάθε χρονική στιγμή μπορεί να υπάρχει μόνο ένας πεπερασμένος αριθμός από ζωντανά κελιά (άρα αποθηκεύοντας μόνο τα ζωντανά κελιά μπορείτε να αναπαραστήσετε πλήρως μια κατάσταση). Όμως οποιοδήποτε κελί με συντεταγμένες που περιέχονται σε μια μεταβλητή τύπου LifeCell μπορεί να είναι ζωντανό. Συνιστάται η υλοποίηση του τύπου LifeState να γίνει μέσω handle, ώστε να μην είναι ορατή στο χρήστη του module (information hiding).
Το “RLE” είναι ένα πολύ απλό text-only format για την περιγραφή ενός LifeState: με b σημειώνουμε ένα νεκρό κελί, με o ένα ζωντανό, με $ την αλλαγή γραμμής, ενώ ένας αριθμός πριν από κάποιο χαρακτήρα απλά επαναλαμβάνει τόσες φορές τη σημασία του χαρακτήρα. Ένα ! δηλώνει το τέλος του αρχείου. Πχ ένα glider αποθηκεύεται ως bo$2bo$3o!. Το pattern ξεκινάει από τις συντεταγμένες x= 0, y = 0. Αναλυτική περιγραφή του format υπάρχει εδώ, δείτε και τα παραδείγματα στο τέλος και θα κατανοήσετε τη λογική. Τις γραμμές που αρχίζουν από # καθώς και τη γραμμή x = m, y = n μπορείτε να τις αγνοήσετε.
Δημιουργήστε απλά unit tests για όλες τις λειτουργίες (δε χρειάζεται εκτελέσιμο πρόγραμμα), στα οποία θα δοκιμάζετε τις λειτουργίες πάνω σε δεδομένα για τα οποία γνωρίζετε το αναμενόμενο αποτέλεσμα.
Βασιζόμενοι στην υλοποίηση της προηγούμενης άσκησης, προσθέστε τις παρακάτω λειτουργίες.
Αρχικά, μια συνάρτηση η οποία πραγματοποιεί διαδοχικές εξελίξεις του παιχνιδιού και τις επιστρέφει σε μία λίστα. Η συνάρτηση αυτή θα πρέπει να ελέγχει και αν κατά τις εξελίξεις αυτές το παιχνίδι πέφτει σε ατέρμονη επανάληψη, το οποίο συμβαίνει αν παράγουμε κάποια κατάσταση που έχουμε ήδη παράξει στο παρελθόν.
// Επιστρέφει μία λίστα από το πολύ steps εξελίξεις, ξεκινώνας από την κατάσταση
// state. Αν βρεθεί επανάληψη τότε στο *loop αποθηκεύεται ο κόμβος της λίστας στον
// οποίο συνεχίζεται η εξέλιξη μετά τον τελευταίο κόμβο, διαφορετικά NULL.
List life_evolve_many(LifeState state, int steps, ListNode* loop);
Με άλλα λόγια, σε κάθε εξέλιξη ελέγχουμε αν το νέο state έχει ξαναεμφανιστεί. Αν ναι, δεν προστίθεται στη λίστα, αποθηκεύουμε στο *loop τον κόμβο στον οποίο έχει εμφανιστεί το state, και διακόπτουμε τις εξελίξεις (δεν υπάρχει λόγους να συνεχίσουμε, περαιτέρω εξελίξεις θα παράγουν ήδη γνωστά states). Αν μετά από steps εξελίξεις δεν έχει βρεθεί επανάληψη σταματάμε θέτωντας *loop = NULL (και η λίστα θα περιέχει steps+1 states). Πχ:
Έστω ότι ξεκινώντας από state = Α, η πλήρης ακουθία εξελίξεων είναι A,B,C,B,C,B,.... Η κλήση life_evolve_many(state, 2, loop) επιστρέφει A,B,C και θέτει *loop = NULL. Η κλήση life_evolve_many(state, 3, loop) επιστρέφει επίσης A,B,C αλλά θέτει *loop = Β. Ο έλεγχος ατέρμονης επανάληψης μπορεί να γίνει αποδοτικά με τρόπο παρόμοιο με την Άσκηση 2, αρκεί να ορίσετε μια κατάλληλη διάταξη (συνάρτηση compare) του τύπου LifeState (αλλά και μη αποδοτικές υλοποιήσεις θα γίνουν δεκτές).
Στη συνέχεια, υλοποιήστε ένα πρόγραμα life_gif το οποίο να δημιουργεί ένα GIF animation του οποίου κάθε εικόνα (frame) απεικονίζει τμήμα μιας κατάστασης του παιχνιδιού, δείχνοντας την εξέλιξή του από μια αρχική κατάσταση. Το πρόγραμμα θα καλείται ως εξής:
life_gif <state> <top> <left> <bottom> <right> <frames> <zoom> <speed> <delay> <gif>
Οι παράμετροι περιγράφονται παρακάτω:
state (string): η αρχική κατάσταση (αρχείο RLE).
top, left, bottom, right (int): το gif θα περιλαμβάνει μόνο τα κελιά που ανήκουν στο παραλληλόγραμμο που ορίζεται από τις συντεταγμένες αυτές. Δηλαδή ένα κελί x,y εμφανίζεται στο gif αν left <= x <= right και top <= y <= bottom (υπεθύμιση: οι y συντεταγμένες αυξάνονται προς τα κάτω).
frames (int >= 1): ο αριθμός των εικόνων του gif animation.
zoom (float > 0): πόσα pixels του GIF αντιστοιχούν σε ένα cell
αν zoom >= 1 τότε για κάθε cell (μέσα στα όρια που δίνονται) θα παράγονται round(zoom) x round(zoom) pixels στο GIF, τα οποία θα είναι όλα μαύρα αν το κελί είναι ζωντανό, αλλιώς άσπρα. αν zoom < 1 τότε για κάθε round(1/zoom) x round(1/zoom) κελιά (μέσα στα όρια που δίνονται) θα παράγεται ένα pixel στο GIF, το οποίο θα είναι μαύρο αν η πλειοψηφία των αντίστοιχων κελιών είναι ζωντανά, αλλιώς άσπρο. Σημείωση: το zoom δεν επηρρεάζει ποια κελιά εμφανίζονται στο gif, αλλά το μέγεθός τους.
speed (int >= 1): κάθε frame του gif (μετά το πρώτο) απεικονίζει την κατάσταση που προκύπτει μετά από speed εξελίξεις από το προηγούμενο frame. Αν δηλαδή speed = 2 τότε κάθε 2 εξελίξεις παράγεται ένα frame.
delay (int): ο χρόνος που διαρκεί κάθε frame (msecs).
gif (string): το αρχείο προς δημιουργία.
Αν η υλοποίηση κάποιας συγκεκριμένης παραμέτρου, πχ του zoom, σας δυσκολεύει ιδιαίτερα, απλά αγνοήστε την.
Στο παρακάτω site θα βρείτε έναν τεράστιο αριθμό από ενδιαφέροντα patterns για να δοκιμάσετε. Μπορείτε να χρησιμοποιήσετε και το πρόγραμμα Golly για να δοκιμάσετε τα patterns.
Για τη δημιουργία GIFs μπορείτε να χρησιμοποιήσετε τη βιβλιοθήκη bitmap, η οποία περιέχεται στο git repository της εργασίας, μαζί με ένα παράδειγμα της χρήσης της (gif_example). Documentation θα βρείτε στα αντίστοιχα modules (bmp.h, gif.h).