theofrag / game_of_life Goto Github PK

https://k08.chatzi.org/2020/projects/project1/

make run 

Στον φάκελο programs/gif_example.

Παράμετροι γραμμής εντολών απο τα αριστερά προς τα δεξιά:

./myex '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, τα οποία θα είναι όλα μαύρα αν το κελί είναι ζωντανό, αλλιώς άσπρα.

speed (int >= 1): κάθε frame του gif (μετά το πρώτο) απεικονίζει την κατάσταση που προκύπτει μετά από speed εξελίξεις από το προηγούμενο frame. Αν δηλαδή speed = 2 τότε κάθε 2 εξελίξεις παράγεται ένα frame.

delay (int): ο χρόνος που διαρκεί κάθε frame (msecs).

gif (string): το αρχείο προς δημιουργία.

Ο βασικός κορμός του game of life είναι 2 maps. Το map1 κρατάει τις συντεταγμένες του "cell.x" ενώ το map2 του "cell.y". Θα μπορούσε να παρομοιαστεί με έναν 2d πίνακα απο στο map1 αποθηκευεται ο αριθμός της γραμμής,ενώ στο map2 της στήλης Το key του map1 αποθηκεύει την γραμμή την οποία βρισκόμαστε,ενώ το value του είναι δείκτης σε μια δομή map2 To key του map2 αποθηκεύει την στήλη την οποία βρισκόμαστε, ενώ το value του χαρακτηρίζει το cell με 1 αν είναι ζωντανο. Ουσιαστικά στο map θα μπαίνουν μόνο τα cells τα οποία είναι ζωντανά,όλα τα υπόλοια θα θεωρούνται νεκρά

Η συνάρτηση:

LifeState life_create();

Απλά δημιουργέι μια κατάσταση οπού ολα τα cells είναι νεκρά. Δεσμεύει χώρο για μια δομή τύπου lifestate και δημιουργέι το map1,δήλαδη το map που θα κρατάει την γραμμή στην οποία βρίσκονται τα cells. Δεν χρειάζεται να δημιουργήθει απο τώρα το map2,δηλαδή το map που κρατάει την στήλη που βρίσκονται τα cells καθώς έχει γίνει η σύμβαση ότι στο map αποθηκεύονται μόνο τα ζωντανά cells.

Η συνάρτηση:

LifeState life_create_from_rle(char* file);

Δημιουργεί μια κατάσταση του παιχνιδιού με βάση τα δεδομένα του αρχείο file (RLE format). Αν βρεί "o" στο file δημιουργέι τον χώρο που θα αποθηκευτεί αυτο το cell στην κατάλληλη γραμμή και στήλη. Αν βρεί "b" απλά το αγνοεί και δεν δημιουργέι χώρο για να το αποθηκεύσει,καθώς αποθηκεύονται μόνο τα ζωντανά,αυξάνει όμως τον αριθμό της στήλης κατα ένα,ώστε το επόμενο cell άν είναι ζωντανό να αποθηκευτεί στην επόμενη στήλη,και να διατηρηθέι παράλληλα η πληροφορία οτι στην στήλη που δεν αποθηκεύσαμε είναι νεκρό cell. Αν βρεθέι "$" σημαίνει οτι αλλάζουμε γραμμή.Συνεπώς πηγαίνουμε στην επόμενη γραμμή και ξεκινά πάλι η αρίθμηση των στήλων, της συγκεκριμένης γραμμής απο το 0.

Η συνάρτηση:

bool life_get_cell(LifeState state, LifeCell cell);

Επιστρέφει την τιμή του κελιού cell στην κατάσταση state (true: ζωντανό, false: νεκρό). Αρχικά ψάχνει να βρέι αν υπάρχει key στο map1 με τιμή cell.x. Αν δεν υπάρχει απλά επιστρέφει false, γιατι το αντιστοιχό cell δεν έχει αποθηκευτέι στην δομή καθως είναι νεκρό.Αν βρεί ότι υπάρχει cell.x στην δόμη,ψάχνει αν υπάρχει cell με τις αντίστοιχες συντεταγμένες. Αν δηλαδή δεν υπάρχει επιστρέφει false γιατί αυτο το cell είναι νεκρό,αλλίως true.

Η συνάρτηση:

void life_set_cell(LifeState state, LifeCell cell, bool value);

Αλλάζει την τιμή του κελιού cell στην κατάσταση state. Aν ζητηθεί να αλλάξει η τιμή ενός ζωντανού cell σε νεκρό,τότε αφαιρείται απο την δομή το συγκεκριμένο cell και ελευθερώνεται η μνήμη του. Αντίθετα αν ζητηθεί να αλλάξει η τιμή ενός νεκρού cell τότε δεσμεύεται η αντίστοιχη και δεσμεύεται χώρος για να εισαχθεί στην δομή,καθώς πλέον θεωρείται ζωντανό cell.

Η συνάρτηση:

LifeState life_evolve(LifeState state);

Παράγει και επιστρέφει μια νέα κατάσταση που προκύπτει από την εξέλιξη της κατάστασης state. Για κάθε ζώντανο cell που υπάρχει στο map, ελέγχόνται τα γειτόνικα του και το ίδιο για την κατάσταση στην οποία πρέπει να μεταβούν. Συνέπως ελέγχονται μόνο τα ζωντανά cells,αλλα και τα 8 γειτονικά τους.Τα υπόλοιπα δεν χρειάζεται να ελεγχθούν. Για να επιτευχθεί ο έλεγχος καλείται η συνάρτηση "life_count" που μέτραει τον αριθμό των ζωντανών γειτονικών κελιών σε κάθε cell που της δίνεται. Σε κάθε cell που ελέγχεται η κάτάσταση που θα μεταβέι δημιουργείται ένα καινούριο state και αποθηκεύεται εκέι,ώστε να μην χαθεί η παλιά κατάσταση αλλά και να μην επηρεαστούν τα υπόλοιπα cells απο την αλλαγή του εκάστοτε cell.

Η συνάρτηση:

void life_destroy(LifeState state);

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

Η συνάρτηση:

Vector rle_format(LifeState state)

Είναι μια συνάρτηση που δεν χρειάζεται να είναι ορατή στον χρήστη. Η λειτουργία της είναι να παίρνει μια κατάσταση και να δημιουργεί ενα vector απο το format της. Στο vector αυτό,το format που αποθηκεύεται απεικονίζει μονο το σχήμα της κατάστασης και οχι την θέση της στον χώρο.

Η συνάρτηση:

void life_save_to_rle(LifeState state, char* file)

Αποθηκεύει την κατάσταση state στο αρχείο file (RLE format). Αρχικά καλέι την συνάρτηση Vector rle_format(LifeState state) φτίαχνει ένα vector με το format της κατάστασης και στην συνέχεια αντιγράφει τα στοιχεία του στο file.

Η συνάρτηση:

int compare_s(Pointer a,Pointer b;

Είναι μια συνάρτηση που ελέγχει πότε δυο states με ιδιο format είναι ίδια. Η λειτουργία της βασίζεται στο γεγονός πως δύο states με ίδιο format είναι ίδια αν και μονο ξεκινάνε απο το ίδιο σημείο. Αυτό διότι δυό states με ίδιο format ή είναι ίδια ή το ένα σε σχέση με το άλλο έχουν διαφορετική μετατόπιση στον χώρο.Επομένως αν σε δύο states με ίδιο format βρεθεί ενα cell που έχει τις ίδιες συντεταγμένες και για τα δύο σημαίνει οτι είναι ίδιο και το state.

Η συνάρτηση:

List life_evolve_many(LifeState state, int steps, ListNode* loop);

Παίρνει μια κατάσταση state και επιστρέφει μια λίστα απο το πολύ step εξελίξεις. Αν βρεθέι επανάληψη, στο loop αποθηκεύεται ο κόμβος στον οποίο συνεχίζει η εξέλιξη μετά τον τελευταίο κόμβο της λίστας, διαφορετικά NULL. Αρχικά δημιουργώ μια λίστα που παίρνει σαν όρισμα για destroy_funtion, την "life_destroy" κάθως αυτά που αποθηκεύει είναι states. Στην συνέχεια χρειάζεται ένα map που θα είναι σε θέση να συγκρίνει πότε δυο states είναι ίδια. Βάζω την αρχική μου κατάσταση στην λίστα και ταυτόχρονα στο map. Σαν 'key' στο map μπαίνει το RLE format και σαν 'value' το state. Σε κάθε καινούριο state που προετοιμάζεται να εισαχθεί στην λίστα, ψάχνω αν υπάρχει παρόμοιο format στον map. Αν υπάρχει μπορεί το format αυτό να συμπίπτει με το state,μπορεί όμως όχι. Σε περίπτωση που το format και το state συμπίπτουν σημαίνει ότι φτάσαμε στην ίδια κατάσταση. Σε περίπτωση όμως που το format και το state δεν είναι ιδια σημαίνει απλά πως φτάσαμε στο ίδιο σχήμα,απλά μετατοπισμένο,όχι ομως στο ίδιο state. Για παράδειγμα το format bo$2bo$3o! επαναλαμβάνεται πολλές φορές κατα την διαδικασία παραγωγής states, η κατάσταση όμως δεν είναι ίδια,καθώς το σχήμα, αν και ιδιο, είναι μετατοπισμένο στον χώρο. Αν λοιπόν βρέθηκε στο map ίδιο format πρέπει να κληθεί η compare_s που συγκρίνει δυο states. Αν το state που πρόκειται να εισαχθεί είναι το ίδιο με αυτο που υπάρχει στο map,έχουμε πέσει σε βρόγχο,αλλίως όχι. Εφόσον έγινε ο έλεγχος και διαπιστώθηκε οτι δυο καταστάσεις, αν και ίδιο format,είχαν διαφορετίκο state,το μόνο που μπορεί να σημαίνει είναι οτι το σχήμα μετατοπίστηκε στον χώρο. Συνεπώς δεν προκειται να ξαναβρεθεί στην ίδια παλιά κατάσταση. Ταυτόχρονα όμως κάτι τέτοιο αποκλειει παράλληλα την εμφάνιση loop. Αυτό διότι εφόσον απο μια κατάσταση,βρέθηκα σε μια ίδια κατάσταση αλλά μετατοπισμένη,αυτο θα γίνει και στα μελλοντικά evolve.Εφοσον δεν υπήρχε loop μεχρι τώρα δεν θα υπάρχει ούτε μετά.Οπότε πλέον δεν χρειάζεται να ελέγχω αν πέφτω σε loop.

Όσον άφορα το myex.c είναι το αρχείο για την δημιουργία του gif και την απεικονιση του. Αν δεν δωθεί καμία παράμετρος,θα κάνει τα προεπιλεγμένα.

top,left,bottom,right: Θα πρέπει να δωθούν σαν συντεταγμένες.Δηλαδη το top ειναι για τον θετικο άξονα των y,το bottom για τον αρνητικό άξονα των y,αρα θα πρέπει να δωθεί με '-'.Ομοίως το left και right είναι ο αρνητικος και θετικος άξονας των x. Μέσα στο .c αρχειο το top μετατρέπεται σε αρνητικό και το bot σε θετικό.Αυτο διότι στο gif οι άξονες μετράνε απο την πάνω αριστερή μεριά της οθόνης και το y αυξάνεται προς τα κάτω.Στην δομή όμως ο y άξονας αυξανεται προς τα πάνω.

Διευκρίνηση: Τα pixels ορίζονται έτσι ώστε το gif να εμφανίζεται στο κέντρο της εικόνας.Για αυτο και στις συναρτησεις για την εμφάνιση pixels προστίθεται ο παράγοντας width/2 και height/2 αντίστοιχα.

zoom: υπάρχει η επιλογή για zoom>=1.Αν zoom<1 το αποτέλεσμα είναι μη ορισμένο.

speed:Όταν το speed !=1 κάθε frame του gif (μετά το πρώτο) απεικονίζει την κατάσταση που προκύπτει μετά από speed εξελίξεις από το προηγούμενο frame. Επομένως θα πρέπει να διαπερνάμε τόσους κομβούς όσους υπαγορεύει το speed, της λίστας που επιστρέφει η evolve_many. Εάν σε αυτή την διαδικασία πέσουμε σε list_eof σημαίνει πως η λίστα είναι μικρότερη απο τον αριθμό των frames γιατι υπάρχει επανάληψη. Άρα ξανα ξεκινάμε απο τον κόμβο που δείχνει το loop

Σημειωσή: Οι δομές των ADTMap, ADTlist, ADTVector δεν βρίσκονται στο παρών repository