Σχεδιασμός και υλοποίηση σοβαρού παιγνίου για τον υπολογισμό κύκλων και μονοπατιών Euler
Loading...
Date
2025-09-19
Authors
Πολυδωρόπουλος, Στέφανος-Ιωάννης
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Από την αρχαιότητα, η κατανόηση και η επίλυση προβλημάτων αποτέλεσαν θεμέλια της εξέλιξης του ανθρώπινου πολιτισμού, επηρεάζοντας κάθε πτυχή της ανθρώπινης δραστηριότητας. Ο άνθρωπος παρατήρησε ότι μπορούσε να μοντελοποιήσει τις σχέσεις και τις αλληλεπιδράσεις μεταξύ τόπων, προσώπων ή εννοιών, χρησιμοποιώντας δομές, που ονομάζονται γραφήματα. Όταν ένα γράφημα αναπαριστά κάποιο δίκτυο, τότε οι κορυφές του λέγονται κόμβοι και οι ακμές του σύνδεσμοι. Έτσι, η δομή πολύπλοκων συστημάτων και δικτύων έγινε πιο σαφής και κατανοητή, οδηγώντας σταδιακά στην ανάπτυξη της θεωρίας γραφημάτων.
Το πρώτο καταγεγραμμένο πρόβλημα της θεωρίας γραφημάτων αποδίδεται στο γνωστό πρόβλημα των επτά γεφυρών του Königsberg, το οποίο μελετήθηκε και λύθηκε από τον Ελβετό μαθηματικό Leonhard Euler το 1736. Το πρόβλημα απασχολούσε τους κατοίκους της πόλης και αφορούσε το κατά πόσο είναι δυνατόν να ξεκινήσει κανείς από ένα σημείο, να διασχίσει όλες τις γέφυρες που ένωναν τις τέσσερις περιοχές της πόλης ακριβώς μία φορά, και να επιστρέψει στο αρχικό σημείο. Η αρνητική απάντηση του Euler και η μεθοδολογία του θεμελίωσαν την έναρξη της μελέτης διαδρομών σε γραφήματα, εισάγοντας τους όρους μονοπάτι Euler και κύκλος Euler, δηλαδή ακολουθίες κορυφών και ακμών που διασχίζουν κάθε ακμή του γραφήματος ακριβώς μία φορά. Οι ακολουθίες αυτές παραμένουν μέχρι σήμερα αντικείμενο μελέτης αλλά και εφαρμογής σε πολλούς επιστημονικούς τομείς.
Στη σύγχρονη εποχή, προβλήματα όπως η εύρεση διαδρομής που διασχίζει κάθε δρόμο σε ένα αστικό δίκτυο ή η ανακατασκευή αλληλουχιών DNA στη βιοπληροφορική, μπορούν να διατυπωθούν ως προβλήματα εύρεσης μονοπατιών ή κύκλων Euler. Η κατανόηση του προβλήματος, είναι επομένως χρήσιμη όχι μόνο σε θεωρητικό επίπεδο, αλλά και για την επίλυση πραγματικών προβλημάτων. Ένας αποτελεσματικός τρόπος, ώστε όσοι ενδιαφέρονται, να κατανοήσουν το μονοπάτι και τον κύκλο Euler, καθώς και να εξοικειωθούν με τη διαχείριση πρακτικών στιγμιότυπων του προβλήματος, είναι μέσω παιχνιδιών που προσφέρουν διαδραστική και βιωματική μάθηση.
Τα σοβαρά παίγνια (serious games) αποτελούν ψηφιακές εφαρμογές, οι οποίες, αξιοποιώντας αρχές και μηχανισμούς παιχνιδιών, έχουν σαν κύριο στόχο την εκπαίδευση και την μάθηση του παίκτη και όχι μόνον την ψυχαγωγία του. Μέσω της αλληλεπίδρασης, της διαδραστικότητας και της αίσθησης επιτεύγματος που προσφέρουν, τα σοβαρά παίγνια λειτουργούν σήμερα ως αποτελεσματικά εργαλεία διδασκαλίας και κατανόησης σύνθετων εννοιών.
Στο πλαίσιο της παρούσας διπλωματικής εργασίας παρουσιάζεται το σοβαρό παίγνιο «Τα νησιά του Επίλεκτου» («Islands of the Chosen One») που αποσκοπεί να βοηθήσει φοιτητές ή όσα άτομα ενδιαφέρονται να κατανοήσουν τα προβλήματα εύρεσης μονοπατιών και κύκλων Euler και να πειραματιστούν με σχετικές αλγοριθμικές λύσεις από την βιβλιογραφία. Σύμφωνα με την πλοκή του παιχνιδιού, οι παίκτες είναι εξερευνητές που καλούνται να κατασκευάσουν – εφόσον υπάρχουν – μονοπάτια και κύκλους Euler μέσα από συμπλέγματα νησιών, συνδεδεμένα μεταξύ τους. Οι παίκτες μπορούν να επιλέξουν να παίξουν είτε σε έναν μοναδικό γύρο, είτε σε επίπεδα. Στον μοναδικό γύρο, οι παίκτες καθορίζουν το επιθυμητό επίπεδο δυσκολίας τους, παρέχοντας τις απαραίτητες παραμέτρους για την δημιουργία τυχαίων γραφημάτων, που αντιστοιχούν στα συμπλέγματα νησιών και τις συνδέσεις μεταξύ τους. Τα επίπεδα περιλαμβάνουν τρεις επιλογές διαβαθμισμένης δυσκολίας «Αρχάριος», «Κανονικός», «Προχωρημένος», όπου τα γραφήματα, δηλαδή τα συμπλέγματα των νησιών, δημιουργούνται αυτόματα από το ίδιο το παιχνίδι. Και στην περίπτωση του μοναδικού γύρου και στην περίπτωση των επιπέδων, πριν τους ζητηθεί να σχεδιάσουν έναν κύκλο ή ένα μονοπάτι Euler, οι παίκτες καλούνται πρώτα να προσδιορίσουν αν υπάρχουν τέτοιοι κύκλοι ή μονοπάτια. Η σωστή απάντηση προϋποθέτει κατάλληλο θεωρητικό υπόβαθρο στην θεωρία γραφημάτων, ενώ ο σχεδιασμός κύκλων ή μονοπατιών Euler απαιτεί γνώση των αλγοριθμικών λύσεων που προτείνονται από την βιβλιογραφία. Το σοβαρό παίγνιο που υλοποιήσαμε επιτρέπει στους παίκτες να δοκιμάσουν και να ενισχύσουν τις θεωρητικές τους γνώσεις, εφαρμόζοντάς τις σε πρακτικό επίπεδο.
Το παιχνίδι μας είναι προς το παρόν διαθέσιμο στα αγγλικά και στα ελληνικά και είναι ελεύθερα προσβάσιμο μέσω οποιουδήποτε προγράμματος περιήγησης ιστού. Έχει δημιουργηθεί χρησιμοποιώντας την Godot, μια πλατφόρμα για ανάπτυξη παιχνιδιών ανοιχτού κώδικα, που είναι διαδεδομένη λόγω των ενσωματωμένων εργαλείων της, που διευκολύνουν τη δημιουργία σύνθετων διεπαφών χρήστη.
Description
Keywords
Σοβαρά παιχνίδια, Συμπλέγματα νησιών, Εξερεύνηση, Κύκλοι και μονοπάτια Euler, Αλγόριθμος του Fleury, Μηχανή παιχνιδιών Godot